Прави-по в целом гласит; UmgMovied, у) истинно, если в Movie найдется кортеж, содержащий

a) гнув качестве первых двух компонентов (для title и year):

b) третий компонент / (для length) со значением не менее 100;

c) любые значения компонентов от 4 до 6.

Это правило эквивале1Гтно следующему оператору оценки и реляционной алгебре:

LongMovie = л, (а, 4, ,оо (Movie)) ,

правая часть которого есть выражс1гие реляцион)1оП алгебры. □

Запрос в Datalog - это непустое множество правил. Если головой правил является одно и то же отношение, его значение считается ответом на запрос. Значит, в примере 4.16 LongMovie - это ответ на запрос. Если головой правил являются несколько отношений, одно из них считается ответом, а другие участвуют в определении ответа. Отношение, предназначенное для выражения ответа, нужно отметить, например, словом Ansvver.

4.2.4 Смысл правил Datalog

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

Пусть, например, шесть переменных из примера 4.16 пробегают по всем возможным значениям. Единственная комбинация значений, делающая все подцели истинными, это значения (/, у, I, с, j, р), стоящие в том порядке, в котором они расположены в кортеже из Movie. Более того, поскольку подцель /> 100 тоже должна быть истинной, этот кортеж должен быть таким кортежем, в котором /, т.е. значение компонента length, не менее 100. Определив такую комбинацию значений, берем кортеж (t,y) в качестве головы отношения LongMovie.

Следует учитывать следующие ограничения на применение переменных о правилах: результат правила есть конечное отношение, а правила с арифметическими подцелями или отрицательными подцелями (которым предшествует NOT) имеют содержательный смысл. Запомните условие безопасности:

Каждая включенная в правило переменная должна входить и в неотрицательную реляционную подцель этого правила.

В частности, переменная, включенная в голову правила, в отрицательную реляционную подцель или в любую арифметическую подцель, лолхсна входить и в неотрицательную реляционную подцель.

Пример 4.17. Рассмотрим правило

LongMovie(l. у) ♦ - Movie(J. у. I. . . ) AND I г 100

из примера 4.16. Первая подцель положительна и содержит все переменные, входящие в это правило. В частности, переменные i и у. включенные в голову, входят и в подцель тела. Переменная / вхоцит в арифметическую подцель и в первую подцель. □

Пример 4.18. В следующем правиле ттебование безопасности нарушено трижаы: Р(х. у) *- Q(x. z) AND NOT R(w, x. z) AND x < у

i: Переменная у входит в голову, но не входит ни в одну неотрицательную подцель. Заметим, что факт вхождения у D арифметическую подцель х<у не помогает ограничить возможные значения у до конечного множества. Когда мы находим для w, х и г соответственно значения а, b и с, удоялег-воряющие первым двум подцелям, в отношение Р головы правила привносится бесконечное число кортежей {а, J), где rf> о.

2. Перемещая w nxofiirr n отрнцателыгую, но не в неотрицательную реляционную подцель.

3. Переменная у входит в арифметическую поаиель, но не в неотрицательную реляционную подцель.

Значит, это правило не безопасно и не может применяться в Datalog. □

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

Для каждого непротиворечивого приписывания рассматриваются отрицательные реляционные и арифметические подцели. Это необходимо для того, чтобы убедиться, что приписывание сцел1и10 все эти подцели истинными. Напоминаем, что отрицательная подцель истинна, если ее атом ложен. Если все подцели истинны, видно, каким кортежем становится голова правила при данном приписывании значений переменным. Этот кортеж добавляется к отношению, предикат которого является головой.

Пример 4.19. Рассмотрим правило из Datalog:

Р(х, у) <- Q{x, Z) AND R(z у) AND NOT Q(x у)

Пусть отношение Q содержит два кортежа (1,2) и (I, 3), а отношение R кортежи (2.3) и (3. 1). Здесь две положительные подцели Q{x, z) и R{z,y), поэтому нужно рассмотреть все комбинации приписываний этим подцелям кортежей из отношений (? и Л соответственно. Эти комбинашт показаны в таблице на рис. 4..3.

Рис. 4.13. 6ce fiosjwDMHbie приписыеония ксртежей Q(x, z) и R(z, i)

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

Первый вариант, в котором подцели Q{x, z) приписан кортеж (1,2), а подцели Fiz,y) кортеж (2,3)-это непротиворечивое приписывание переменным .v, у и г значений 1, 3 и 2 соответственно. Значит, нужно проверить другие отрицательные реляционные подцели. Такая подцель здесь одна: NOT Q(x, у). При данном приписывании значений переменным она имеет вид NOT Q(1,3) и является ложной, так как (1,3) -это кортеж из Q. Поэтому при варианте приписывания кортежей (!) никакой головной кортеж не порождается.

Последнее приписывание (4) непротиворечиво; переменным х, у ц z приписываются значе1П1я I, I и 3 соответственно. Подцель NOT Q(x, у) принимает истинное значение NOT 0(1,1). Так как (1,1) не является кортежем из Q, эта подцель истинна. Таким образом, мы оцениваем голову Я{х,у) для этого приписывания значений переменным и определяем, что ее оценкой является P(\J) Значит, кортеж (1,1) В.ХОДИТ в отношение Р. Поскольку были исчерпаны все приписывания значений кортежам, этот кортеж является единственным кортежем отношения Р. □

4.2.5 Экстенсиональные и интенциональные предикаты

t. Следует различать:

Экстенсиональные предикаты, отношения которых хранятся в БД,

Интенциональные предикаты, отношения которых вычисляются по одному или нескольким правилам Datalog.

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

Говоря о правилах Datalog, Mbf будем называть отношение, соответствующее предикату, экстенсиональным или итенциональным , если предикат соответственно экстенсионален или интенционален. Ссылаясь на интенциональный предикат или соответствующее ему отношение, будем обозначать интеиииональную БД аббревиатурой /DB, а аббревиатурой EDB- экстенсиональную БД для экстенсиональных предикатов или соответствующих им отношений.

Значит, в примере 4.16 Movie -это отношение EDB, определяемое его объемом, а /rowV? - предикат EDB. От1юшение и предикат LongMovie интенииональны

Предикат EDB никогда не может входить в голову правила, хотя может входить в его тело. Предикаты IDB могут входить в любую часть правила или по все части сразу. Единственное отно 1ение обычно строится путем применения множества правил с одним предикатом в голове правила. Такой подход иллюстрируется в примере 4.21, касающемся объединения двух отношений

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