В этом дереве четыре внутренних ухча, поэтому нужно построить четыре предиката IDB, к каждому из которых относится единственное правило IDB. Все эта правила

перечислены на рис. 4.15.

1. W(t, у, 1. с, S, р) Movie{t у. 1, с, s. р) AND I > 100

2. X(t. у. 1. С, S, р) <- Movie(t. у, I, с, s. р) AND s = Fox

3. Y(t. у. I. с. s. p) - W(t. y, r. c. s, p) AND XCt. y. I, c, s. p)

4. 2(t, y) <- Y(t. y. I. c, s, p)

Рис. 4.15. Провило Dcitolog дпя выполнения множества С1лгеброичео операций

Два нижних внутренних узла дерева на рис. 4.14 выполняют две простые операции отбора на EDB-отношенин Movie, поэтому для их представления можно построить lDB-предикаты W и X. Эти операции описаны правилами I и 2 из рис. 4.15. Например, правило I определяет Икак кортежи отношения Movie, в которых атрибут length имеет значение не менее 100.

Правило 3 определяет предикат К как пересечение IV у\ X. причем применяется форма правила пересечения, описанная в разлеле 4.3.1. И наконец, правило 4 определяет Z как проекцию Y иа атрибуты title и year. Здесь применяется метод представления проекции, описанный в разделе 4.3.4. Z-это предикат отвега , т.е. независимо от значения отношения Movie отношение, определяемое Z, совпадает с результатом алгебраического выражения, с которого начинался данный пример.

В этом примере подцель Y из правила 4 можно заменить на тело из правила 3. Затем вместо подцелей Wh Xможно подставить тела из правил I и 2 соответственно. Поскольку подцель Movie входит в оба тела, одну ее копию можно удалить. В результате 2 определяется единственным правилом:

Z(t. у) <- Movie(l. у. 1, с, S. р) AND 12 100 AND s = Fox*

Однако это не значит, п-о сложное выражение реляционной алгебры всегда экви-впентио единственному правилу Datalog- □

4.3.9 Упражнения к разделу 4.3

Упражнение 4.3.1. Пусть Я{о, Ь, с), 5(о, Ь, с) и До, Ь, с) - три отношения. Напишите правила Datalog, определяющие результат каждого из перечисленных выражений реляционной алгебры:

&) RkjS

с) R - S

!е) (Л-5)г,(Л~Г) t)

Упражнение 4.3.2. Пусть R(x. у, z) - отношение. Напнш1гге npasiuia Datalog.

определяющие ст (Л), 1де С-одно из следующих условий:

а) х = у

V < у <

movie

sequel

Naked Gun Naked Gun 2% Naked Gun ih Naked Gun ЗЗз

с) д: < у. OR у< I й) NOT(.v<> OR .v> у) *! е) NOT {(x<yORx> у) AND y<z) ] Г) NOT i{x <y OKx<z) AND у < г)

Упрожнение 4.3.3. Пусть R(a, b, с), S{b, с, d) и T\d, e) - три отношения. Напишите единственное правило Datalog для каждого из следующих натуральных соединений:

a) RtxS

b) StxT

! с) (Л Cxi 5) Cxi Г [Примечание. Поскольку натуральное соединение ассоииативно и коммутативно, порядок соединения этих чзсх отношений не имеет значения.)

апрожнение 4.3.4. Пусть Я(х,у, г) и S{x,y, z) - отношения. Напишите правила Datalog, определяющие результат каждого тета-соединеиия йм-, где С-одно из условий из упражнения 4.3.2. Для каждого условия интерпретируйте любое арифметическое сравнение как сравнение, в левой части которого стоит атрибут из Л, а в правой - атрибут из .У. Например, х<у означает Л.х< S.y.

! апрожнение 4.3,5. Правила Datalog тоже можно конвертировать в эквивалентные им выражения реляционной алгебры. Хотя мы и не рассматривали общий метод такого перевода, можно привести множество простых примеров. Для каждого из перечисленных ниже правил Datalog запишите выражение реляционной алгебры, определяющее отношение, которое является головой этого правила.

*а) Р(х, у) Q{x. z) AND R{z, у)

b) P(x, у) *- Q(x, z) AND Q{z, y)

c) P(x, y) <- Q(x. z) AND R(z, y) AND x < у

4-4 Рекурсивное программирование в Datalog

Несмотря на то что средствами реляционной алгебры можно выразить многие полезные операции, есть вычисления, представить которые в виде выражений этой алгебры, нельзя. Распространенный вид операции на данных, которую нельзя вь[-разить в реляционной алгебре, включает в себя бесконечную посгшдовЕпгельность сходных, но при этом возрасгающих алгебраических выражений, которая называется рекурсией.

Пример 4.33. Пример рекурсивной операции, взятый из области киноиндустрии, касается продолжений фильма. Часто за удачным фильмом следует его продолжение, за ним другое и т.д. Итак, фильм может стать предшественником длинной последовательности фильмов. Рассмотрим отношение SeqLielOf{movie, sequel), содержащее пару, состоящую из фильма и его непосредственного продолжения. Примеры кортежей этого отношения:

Можно применить euie Более обшее понятие Следует за... к фильму, который является продолжением, продолжением продолжения и т.д. В приведенном выше отношении Naked Gun 5J/, следует за Naked Gun, но не является его продолжением в строгом смысле используемого здесь термина продолжение . Пространство памяти можно сэкономить, сохраняя в отношениях только непосредственные продолжения и создавая последующие только в случае необходимости. В данном примере фиксируется всего лишь одна наименьшая пара, ио для пяти фильмов с участием Рокки уже нужно запо.мннать шесть пар. а дпя фильмов Пятница, 13-е число минимальных пар возрастает до 136.

Совсем не очевидно, как построить отношение следования за... из отиошения SequelOf. Продолжение продолжений можно построить плтем однократного соединения SequelOf с самим собой. В результате получается выражение, в котором применяется переименование и соединение становится натуральным:

(Рл<л . с л (SequelOf) М pj, . ., (SequelOf))

В этом выраженш SequelOf встречается дважды. В первом случае его атрибуты называются first и second, а во втором second и third. Значит, натуральное соединение требует, чтобы в SequelOf были кортежи (т mi) и (mj, т), где = ту Затем вводится пара (т,. т). Заметим, что т - продолжение й,.

Аналогичным образом можно соединить три копни SequelOf и получить продолжения продолжений продолжений (например, Рокки и Рокки /И). Фактически, можно построить i-c продолжения для любого фиксированного значения /, соединяя SequelOf с самим собой /-1 раз. Тогда, обьединяя SequelOf с конечным множеством таких соединени!?, можно получить все продолжения вплоть до некоторого фиксированного предела.

В реляционной алгебре невозможно получтъ бесконечное объединение бесконечной последовательности выражений, порождающих /-е продолжения для каждого /. Объединение в реляционной алгебре - это объединение только двух, а не бесконечного числа отношений. Применяя в алгебраическом выражении оператор объединения конечное число раз, можно получить объединение любого конечного числа отношений, а объединение бесконечного числа отношений - нет. О

4-4.1 Оператор фиксированной точки

в реляционную алгебру не требуется вводить никакого искусственного соглашения, позволяюще1хз выразить бесконечные объединения одинаковых выражений. Есть общий способ выражения отношений типа FollowOn(x, у) (т.е. фильм у следует за фильмом х, как показано в примере 4.33), которые строятся в бесконечном, но все же рег>-лярном процессе из др>тих отношений типа SequelOf. Записывается уравнение, в которо.м FollowOn выражаетч:я в своих собственных терминах и в терминах SequelOf, а затем говорится, что значение FollowOn - это наименьшее отношение (наименьшая фиксированная точка), удовлетворяющее этому уравнению. Оператор наименьшей фиксированной точки, применяемый к уравнонш, мы будем обозначать символом ф.

Пример 4.34. Рассмотрим применение оператора наименьшей фиксированной точки к уравнению, выражающему отношение FollowOn(x. у):

ф (FollowOn = Pi , ,o .,., (SequelOf) с/Рл,. ,.,(п , ,. (SequelOf X , ., FollowOn)))

Это уравнение означает: Фильм следует за фильмом х, если у является продолжением X или следует за продолжением .\ .

Здесь 0Т1Юшенне FollowOn с атрибутами х у приравнивается к объединению двух термо!!. Первый терм pj qi j (SequelOf) - это копия отношения SequelOf,