4 Cvi., например, A. V. Alio and J. D. Ullnisn, Foimdalions of Cmnparer Science, Computer Science Press, New York, 1992.

Многократно применяя логические операторы AND, OR или NOT, можно получать еще более сложные условия отбора. Однако широко известен метод приведения любого Логического выражения в конъюнктивную нормальную форму , состоящую из конъюнктов связанных между собой OR. Конъюнкты - это литералы, а литерал-это условие или отрицательное сравнение.

Любой литерал можно представить с помощью подцели, которой иногда предшествует NOT. В арифметической подцели NOT можно ввести в оператор сравнения. Например, NOT х>100 можно записать как х< 100. Тогда любой конъюнкт представим единственным правилом Datalog, содержащим по одной подпели для каждого сравнения, И наконец, каждое выражение в конъюнктивной нормальной форме можно записать с помощью множества правил, содержащего по одному правилу лля каждого конъюнкта. Эти правила выражают объединение результатов, полученных из каждого конъюнкта.

Пример 4.26. Простой образец такого алгоритма приведен в примере 4.25. Более сложный пример можно построить, отрицая условие этого примера. В результате получается выражение

not ilensllil 100 or даЛоЛогар-Ток) (Movie) ,

означающее, что нужно найти фильмы, которые ие являются длинными и не принадлежат студии Fox.

Здесь NOT применяется к выражению, не являющемуся простым сравнением. Значит, следует переместить отрицание вовнутрь по закону Де Моргана, согласно когоролу отрицание выражения с OR эквивалентно соединению AND отрицаний его частей. Таким образом, выбор можно записать как

<(ЫСТ (torjAi 00)) AND (NOT fшйоЛапи- 1чя)) (MoVJe)

Теперь можно ввести отрицание в сравнения и получить

ktigh < 100 AND яш/Шане - Тм (MOVJe)

Это выражение конвертируется в следующее правило Datalog:

S(f,yl,c.s.p,)-<-KflovIe(f,yl,c,s.p) AND К 100 AND s *Fox □

Пример 4.27. Рассмотрим похожий пример, в котором есть отрицание условий, связанных посредством AND. Теперь мы используем вторую форму закона Де Моргана, согласно которой отрицание AND эквивалентно отрицаниям, связанным посредством OR, Начнем с алгебраического выражения

NOJUengfhum AND шйо№тр = Tort (Movie)

т.е. иайде.м фильмы не длинные и не принадлежащие студии Fox. По закону Дс Моргана проносим NOT внутрь AND и получаеАТ

(мог (totstfi к 100)1 or ttJOr (мийюлтир = ток!) (MoVJe)

Затем вносим отрицание в компоненты, чтобы получить

< 100 or ч, Г: Иа г то< (MovIe)

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

1. S(t,y.l,c,s,p) <-Movie(t.yl,CS,p) AND <100

2. S(t,y,l,c,s,p) <- Movle(t,y l,c,s,p} AND s ф Fox □

4.3.6 Произведение

Произведение двух отношений i можно представить единственным правилом Datalog, HMCiOHuiM две подцели, по одной для R и S. Калсдая из них содержит различные переменные, по одной для каждого атрнбута из Л или S. Арг)менты предиката iDB в голове это переменные, входящие п каждую из подцелей, и переменные, входящие в подиель R, предшествующие переменным, входящим в подцель S.

Пример 4.28. Рассмотрим четырехатрнбугивные отношения Л и .У из примера 4.20. Правило

Р(а,Ь c,d,w,x,y,z) R{a,b,c,d) AND S(w,x,y,2)

определяет P как Д x 5. Для аргументов R произвольно использовались переменные из начала латинского алфавита, а для .S- из конца. Все они входят в голову правила. □

4.3.7 Соединения

Натуральное соединение двух отношений можно провести по правилу Datalog, очень похожему на правило произведения. Отличие состоит в том, что при получе-Н1Ш Ri>4S н)жно следить за зем, чтобы одна и та же переменная применялась для азрибутов Rk Sc одним и тем же именем шн же указывать для них разные переменные. Например, в качестве переменных можно применять имена самих атрибутов. Голова правила - предикат IDB, в который каждая переменная входит только один раз.

Пример 4.29. Рассмотрим отношения со схемами R(A, В) и S{B, С, D). Их на-typwibiioe соединение можно определить с помошью правила

J{a,b.c.d) R(a,b) AND S(b.c,d)

Переменные, используемые в подце.аях, очевидным образом соответствуют атрибутам отношений R и S. □

Тета-сосдинения также конвертируются в Datalog довольно простым способом. В разделе 4.1.9 было показано, как выразить тета-соединенис в виде произведения с последующим отбором. Если условие отбора конъюнктивно, т.е. представляет собой сравнения, связанные с помошью AND, можно просто начать с правила Datalog для произведения, а затем добавить арифметические подцели, по одной для каясдого сравнения.

Пример 4.30. Рассмотрим отношения U{A, В, Q и У{В, С, D) из примера 4.9, где применялось тета соединение:

A<DIKt i (/. . у.в

Эту же операцию можно выполнить с помошью правила

J{a, ub, ос, vb, vc, d) ч- U(a, ub, uc) AND V(vb, vc, d) AND a < d AND ub vb

Мы указываем ub как переменную, соответствующую атрибуту В из i/ (аналогично используются vb, ис и vc), хотя было бы лучше применить шесть любых переменных для шести атрибутов обоих отношений. Первые две подцели вводят два отношения, а две последние определяют два сравнения, появляющихся в условии тета-соединения. □

Если условие тета-соединения не является конъюнкцией, оно переводится в конъюнктивную нормальную форму, как показано в разделе 4.3 5, а затем строится отдельное правило для каждого конъюнк-та. Головные части всех правил идентичны, и для каждого атрибута участвующих в тета-сосдинении отношений имеется один аргумент.

Пример 4.31. Изменим алгебраическое выражение из примера 4.30, заменив AND на OR. В выражении нет отрицаний, поэтому оно уже находится в конъюнктивной нормальной форме. В нем два конъюнкта, каждый из которых имеет единственный литерал:

JA<l>OR V.B, KB

Применив такую же схему именования переменных, как и в примере 4.30, получаем два правила:

1. J(a, ub, ис, vb, vc, d) <- U(a, ub. uc) AND V(vb. vc, d) AND a < d

2. J{a, ub, uc. vb, VC, d) - U{a, ub, uc) AND V(vb. vc, d) AND ub st vb

Каждое из них имеет подцели для двух отношений и одно из двух условий: A<D

или и.в* КВ. а

4.3-8 Моделирование сложных операций в Datalog

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

Пример 4.32. Рассмотрим алгебраическое выражение

гй/ллмг (о*,айг100 (Movie) г, a jMcm,VBx- (Movie))

из примера 4.10, представленное в виде дерева на рис. 4.7 и воспроизведенное здесь на рис. 4.14.

year

Glength> 100 G StudioName-Fo

Movie

Рис 4.14. Дерево вырожений

Movie