В качестве первого шага предполагаем, что FollowOn пусто. Тогда объединение SequelOf и FollowOn в уравнении с фиксированной точкой тоже пусто и кортежи берутся только из первого терма объединения, т.е. из SequelOf. Поэтому значение FollowOn совпадает со значением SequelOf, т.е. получается отношение, показанное на рис. 4 16.

Рис. 4.16, Отношение FollowOn после первого шого вычислений

переименованная так, чтобы ее атрибуты соответствовали атрибутам отношения FollowOn. Второй терм -это тета-соединение SequelOf ixi p, FollowOn всех пар (й, Ь) из SequelOf с парами {Ь, с) из FollowOn, в результате которого получаются кортежи (а, Ь, Ь, с), атрибутами которых являются movie, sequel, х и у соответственно. Этот терм проецируется на первый и четверты! компоненты, movie и у, после чего производится переименование атрибутов х и у.

Итак, в уравнении с фиксированной точкой FollowOn приравнивается к объединению отношения SequelOf с результатом второго терма, который вычисляет следующие продолжения. Таким образом, FollowOn состоит из всех таких пар (л-, у), что (х, у) входит в SequelOf или у следует за продолжением х Другими словами, у - это продолжение продолжения продолжения ... продолжения д-для некоторого числа применений термина продолжение . □

4.4.2 Вычисление наименьшей фиксированной точки

Из уравнения, приведенного в примере 4.34, не совсем ясно, почему наименьший результат для FollowOn является множеством следующих одна за другой пар фильмов. Чтобы понять смысл оператора фиксированной точки, нужно усвоить, как вычисляется наименьшая фиксированная точка. В разделе 4.4.4 будет рассмоч-рена проблема, возникающая при наличии в уравнении оператора разности, а для уравнения без этого оператора действует следующий метод.

1. Принимается допущение о том, что отношение R в левой части уравнения пусто.

2. Заново вычисляется значение отношения Л путем вычисления правой части с помощью старого значения R.

3. Действия прекращаются, если после одного повторения старое и новое значения оказываются одинаковыми.

Пример 4.35. Проведем вычисление отношения FollowOn для случая, в котором SequelOf состоит из следующих трех кортежей:

Далее с noMouibio этого отношения вычисляем правую часть уравнения с фиксированной точкой, Из первого тер.ш объсдинення, SequelOf, получаются три уже имеющихся кортежа. Для второго терма нужно получить соединение отношения SequelOf. содержащего три кортежа, показанных на рис. 4.16, с текущим отношением FollowOn, причем эти отношения совпадают. Для этого мы ищем такие пары кортежей, чтобы второй компонент кортежа из SequelOf совпадал с первым компонентом кортежа нз FollowOn.

Итак, можно взять кортеж (Rocky, Rocky II) из SequelOf и соедингггь его с кортежем (Rocky II. Rocky II) из FollowOn, чтобы получить новый кортеж (Rocky, Rocky III) для отношения FollowOn. .Аналогично, мо.жно взять кортеж

(Rocky II Rocky III)

из отношения SequelOf, чтобы получить новый кортеж (Rocky III, Rocky IV) для отношения FollowOn. Никакие другие пары кортежей, один из которых взят из SequelOf, а другой из FollowOn со старым значением, ие объединяются. Значит, после второго шага отношение FollowOn содержит пять кортежей, изображенных на рнс. 4.17. Отношение, изображенное на рнс. 4.16, содержало только последователей одного продолжения, а отношение, представленное на рис. 4.17, включает в себя одно или два продолжения.

Рие, 4.17. Отношение РоИоуЮп после второго шого вычисления

И наконец, используется отношение FollowOn, изображенное на рис. 4.17, и заново вычисляется правая часть уравнения с фиксированной точкой. В результате получаются уже имевшиеся кортежи и один новый. Объединяя кортеж (Rocky, Rocky II) из SequelOf с кортежем (Rocky II, Rocky IV) из текущего значения отношения FollowOn, получаем новый кортеж (Rocky, Rocky IV). После этого шага отношение становится таким, как оно изображено на рис. 4.18.

Рис. 4.18. Отношение FollowOn после третьего tuora аьчиа<ения

Делая сле.аующин шаг. мы не получаем новых кортежей, поэтому процедура вычисления заканчивается. Hctvihho€ отношение FollowOn, определяемое таким пыне\ущнрощцноГ1 точки, показано на рис. 4.18. □

Другие формы рекурсии

в примерах 4.34 и 4.36 реализована правосторонняя рекурсия. При этом рекурсивное отношение FollowOn применяется после EDB-отиошения SequelOf. Можно записать и аналогичные правила левосторонней рекурсии, в которых первым стоит рекурсивное отношение:

1. FollowOn(x, у) - SequelOf(x. у)

2. FollowOn(x, у) <- FollowOn(x, z) AND SequelOf(z, у)

Неформально: у- последователь х, если у - продолжение х или продолжение последователя х.

Можно даже использовать рекурсивное отношение дважды, как это делается при нелинейной рекурсии:

1. FollowOn(x, у) - SequelOf{x, у)

2. FollowOn(x, у) <- FolIowOnjx, z) AND FollowOn(z, у)

Неформально: у - последователь х, если у - продолжение х или последователь последователя х. Все три формы рекурсии дают одно и то же значение отношения FollowOn - мтюжсство таких пар (х, у), что у - продолжение прололже ния продолжения ... х.

Пример 4.36. lDB-отношение FollowOn можно определить с помощью следующих правил Datalog:

1. FollowOn(x, у) -с- SequelOf(x, у)

2. FollowOn(x, у) SequelOf(x, z) AND FollowOn(z, у)

Первое из них формирует базис и означает, что всякое продолжение является последопатслсм. Оио соответствует первому терму объединения в уравнении из примера 4.,34.

Второе правило означает, что каждый последователь продолжения фильма л является последователем к. Более точно: если г - продолжение .v, в. у - последователь г, то >>- последователь х. О

4.4.3 Уравнения с фиксированной точкой в Datalog

Для построения достаточно сложных выражений реляционной алгебры необходимы уравнения с фиксированной точкой. Часто их можно выразить с помощью множества правил Datalog. Именно такой способ будет применяться в данном разделе. В разделе 5.10 будет показано, что при реализации такого подхода в SQL3 применяется нотация, имеющая скорее алгебраический, нежели логический характер, так как она больше соответствует стилю SQL

Общая идея, лежащая в основе логических уравнений с фиксированной точкой, заключается в том, чтобы начинать вычисления с отношений EDB. Другие отношения, определяемые путем их введения в головы правил, являются отношениями IDB. Тела этих правил могут содержать подцели, предикатами которых являются отношения EDB или IDB, а также арифметические атомы. Если одно отношение 1DB (или более) определяется по правилам, имеющим одни и те же отношения в своих телах, такие правила эффективно определяют данные стношения 1DB с помощью уравнений с фиксированной точкой, как это делают в уравнении реляционной алгебры из примера 4.34.