4.2.6 Упражнения к разделу 4.2

Зпрожненис 4.2.1. Запишите каждый запрос из упражнения 4.!.1 на языке Datalog. При этом применяйте только безопасные правила: впрочем, можно использовать множество предикатов IDB, cooiвегствуюгшпс подвыражениям сложных выражений реляшюныой алгебры.

Ыпрожненис 4.2.2. Запишите каждый запрос из упражнения 4.1.3 на языке Datalog. ПрнмеияРгге только безопасные правила, но нри желании можно использовать множество предикатов ID В.

1! Ыпрожнсиие 4.2.3. Условия безопасности правил Datalog достаточны для гарантии того, ггобы головной предикат имел конечное отношение, если предикаты реляционных подцелей имеют конечные отношения. Но это слишком жесткое ограничение. Приведите гример правила Daialog, которое нарушает данное ограничение, но тем ие менее при приписывании конечных отношений реляционным предикатам головное отношение будет конечным.

4-3 Переход от реляционной алгебры к Datalog

Любой оператор реляционной алгебры можно изобразить с помошью одного иди нескольких правил Datalog. В этом разделе мы снова рассмотрим все эти операторы и покажем, как комбиЦ1ровать правила Datalog для имигации сложных алгебраических выракений.

4.3-1 Пересечение

Пересечение двух опюшений выражается правилом, имеющим подцели для обоих ланнььх отношений с теми же самыми переменными в соответствующих аргументах.

Пример 4.20, Рассмотрим отношения R и 5, изображенные на рнс. 4.1. Каждое из них имеет схему с атрибутами name, address, gender и birthdate. Результат вычисления пересечения этих отношений по правилам Datalog:

l{n.a,g,b) <- R (n,a,g.b) AND S(n.a,g.b)

Здесь /-предикат IDB, отношением которого при применении данного правила становится Rr\S . Таким образом, чтобы обе подцели были истинными для кортежа (п, в,я, Ь), он должен находшъся в обоих отношениях - R v S. О

4.3-2 Объединение

Объединение двух отношений строится с помощью двух правил. Kaжюe из них в качестве своей единственной подцели имеет атом, соответствующий одному из отношений, а головы обоих правил содержат один и тот же предикат. Ар1>менты го;ювы каждого правила в точности совпадают с аргументами его подцели.

Пример 4.21. Для получения объединения отношений Л и .S из примера 4.20 применяются два правила:

1. и (n.a,g,b)-(- R (n.a.g.b) 2 и (n,a,g.b) S (п,а.д,Ь)

Переменные локальны по отношению к правилам

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

U(w, X. у. z) S(w, X. у, Z)

оставив при этом первое правило без изменений. В результате два правила по-прежнему будут вычислять объединение Л и 5. Однако при замене в правиле переменной а на другую переменную Ь вместо какдого вхождения а в рассматриваемое правило необходимо подставлять Ь. Более того, при этой подстановке 6 должно быть переменной, которая не входит в данное правило.

4.3.3 Разность

Разность отношений Rvi S строится с помощью единственного правила с отрицательной подцелью. Это означает, что положительная подцель ттмеет предикат Л, а отрицательная - предикат S. В соответствующие друг другу аргументы головы и подцелей входят одни и те же переменные.

Пример 4.22. Если Rw S- отношения из примера 4.20, то правило

D(n,a.g.b) <- R (n.a.g.b) AND NOT S(n.a.g.b) определяет D как отношение R-S. □

4.3.4 Проекция

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

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

Правило (1) гласит, что каждый кортеж из Л является кортежем ЮВ-отношения U, а согласно правилу (2), каждый кортеж из S входит в U- Значит, из двух этих правил следует, что каждый кортеж из RS входит в U. Если не писать больше правил с (/ в головных элементах, никакие другие кортежи не смогт попасть в U, и тогда можно сделать вывод, что V совпадает с RuS? Поскольку отношения являкггся множествами, каждый кортеж входит в U только один раз, даже если он ачодит и в Д и в 5. □

Пример 4.23. Построим проекцию отношения

Wove(tille. year, length. inCotor, studraName, producerC#)

на его первые три этрибута, как в примере 4.2. Отношение Р, являющееся результатом такой проекции, определяется по правилу

P(t,y.l) Movie(t.y,l,c,s,p) О

43-5 Отбор

Выразить отбор в Datalog немного труднее. Простым является случай, в котором условием отбора яе)ляется AND или арифметические сравнения. При этом строится правило, содержащее:

1. Одну реляционную подцель для отношения, на котором проводится отбор. Этот атом содержит различные пере.мениые для каждого компонента, по одной для каждого атрибута отношения.

2. Ариф.метическую подцель для каждого сравнения в условии отбора, идентичную этому сравнению. Но так же, как при условии отбора используется имя атрибута, в арифметической подцели применяется соответствующая ему переменная в соответствии с установленной реляционной подцелью.

Пример 4.24. Отбор

</явЛ i -СО AND studhNawe - Tos (Movlo)

из примера 4.4 можно записать в виде следующего правила Datalog:

S(t,y,l.c,s.p.) Movie{t,y.l.c.s.p) AND 1>100 AND s = Fox

В результате получается отношение S. Заметим, что переменные f и .г соответствуют атрибутам length н studioName в стандартном порядке, примененном для атрибутов Movie. □

Теперь рассмотрим отбор, в котором условия соединены связкой OR. Его не всегда можно заменить единственным правилом Datalog. Однако отбор, содержащий два условия, соединенных OR, эквивалентен отбору по каждому из условий в отдельности с последующим объединением результатов. Значит, условий, соединенных связкой OR можно выразить с помощью п правил, каждое из которых определяет один и тот же головной предикат, /-е правило выполняет выбор для /-го условия из числа п

!1римср 4.25. Изменим выбор из примера 4.4, заменив AND на OR. и получим

ifi grh s WO OR iwmww = To.- (Movie)

To есть, цужчо найти все длинные фильмы или принадлежащие студии Fox. Можно написать два правила для этих условий:

1 S{t.y,l,cs,p) t-Movie(t,y l,cs,p) AND 1>100 2. S(t.y,l,c s.p) \- Movie(t,y l.c.s.p) AND s = Fox

Первое порож.аает ф1ьмы, длящиеся более 100 мин, а второе фильмы, принадлежащие стздни Fox. □