глава на правилото. Символът , който четем като “ако”. Тяло

Едно примерно правило е следното:

LongMovie (t, y)  Movie (t, y, l, c, s, p) AND l >= 100

То се отнася за базата от данни със схема

Movie (title, year, length, inColor, studioName, producerC#).

Семантиката на това правило е следната: LongMovie (t, y) е истина точно когато в релацията Movie има кортеж със следните свойства:

стойност t за title, стойност y за year, стойност по-голяма от 100 за length и произволни стойности за останалите атрибути.

Да отбележим, че в релационната алгебра това правило е еквивалентно на следното присвояване: LongMovie := _{title, year} (_length>=100 (Movie)).

LongMovie (t, y)  Movie (t, y, l, _, _, _) AND l >= 100.

Ако в главата на всички правила от заявката присъства една и съща релация, то тази релация се приема за отговор на заявката. Естествено,

предвид смисълът на релационните атоми, релацията резултат е обединение на всички релации, които се получават от правилата.

В горния пример отговорът на заявката е релацията LongMovie.

Ако в главите на правилата от заявката присъства повече от една релация, то точно една от тези релации е отговор на заявката, а останалите се разглеждат като обслужващи. Най-често за резултатната релация се използва име Answer.
Семантика на правилата в Datalog
Всяка променлива от едно правило има някаква област от стойности.

Тогава когато при конкретни стойности на променливите всички подцели се оценяват до истина, само тогава се добавя съответен кортеж към релацията в главата на правилото.

Върху начина по който се използват променливи в правилата трябва да се въведат ограничения за да е сигурно, че резултатната релация ще бъде крайна и че аритметичните и отречените подцели ще носят интуитивния си смисъл. Едно достатъчно условие за това е така нареченото условие за безопасност, според което всяка променлива, която се появява в правило трябва да присъства и в някоя неотречена релационна подцел на това правило. По-точно променливите, които се появяват в главата, в отречените подцели и в аритметичните подцели на едно правило трябва да се появяват и в неотречена релационна подцел на това правило.

Например, правилото LongMovie (t, y)  Movie (t, y, l, c, s, p) AND l >= 100 е безопасно, тъй като релационната подцел съдържа всички променливи, които участват в правилото.

В правилото P (x, y)  Q (x, z) AND NOT R (x, w, z) AND x < y има три нарушения на условието за безопасност:

1. 
   Променливата y присъства в главата, но не присъства в неотречена релационна подцел.
   
2. 
   Променливата w присъства в отречена подцел, но не присъства в неотречена релационна подцел.
   
3. 
   Променливата y присъства в аритметична подцел, но не присъства в неотречена релационна подцел.
   

Има и друг начин за дефиниране на семантиката на правилата. Вместо да разглеждаме всички възможни стойности на променливите, ограничаваме множеството от тези стойности до кортежите на неотречените релационни подцели. Когато някое присъединяване на кортежи е съгласувано, в смисъл че то присъединява една и съща стойност за всяка поява на една променлива в правилото, тогава разглеждаме резултатното присъединяване на стойности на всички променливи. Тъй като правилото е съгласувано, то всяка променлива ще е получила стойност. За всяко съгласувано присъединяване при което отречените релационни подцели и аритметичните подцели се оценяват с истина, добавяме кортеж към резултатната релация в главата на правилото.

P (x, y)  Q (x, z) AND R (z, y) AND NOT Q (x, y).

В правилото има две неотречени релационни подцели - Q (x, z) и R (z, y).

Нека релацията Q има два кортежа (1, 2), (1, 3) и релацията R има два кортежа (2, 3), (3, 1).

Всевъзможните присъединявания на тези кортежи са следните:

Q (x, z)	R (z, y)	съгласувано
(1, 2)	(2, 3)	да
(1, 2)	(3, 1)	не
(1, 3)	(2, 3)	не
(1, 3)	(3, 1)	да

1. 
   Екстенсионални предикати - те съответстват на релации, които се съхраняват в базата от данни.
   
2. 
   Интенсионални предикати - те съответстват на релации, които са резултат от изчисление на едно или повече правила.
   

В този смисъл в контекста на Datalog, една релация наричаме екстенсионална (EDB), ако тя съответства на екстенсионален предикат и интенсионална (IDB), ако тя съответства на интенсионален предикат.

В релационната алгебра екстенсионалните релации са операндите на изразите, а интенсионалните релации са междинните резултати и крайният резултат. В примера с филмите, релацията Movie е екстенсионална, а релацията LongMovie е интенсионална.
Една EDB не може да присъства в глава на правило, но може да присъства в тяло на правило. За IDB няма ограничения - може да присъства както в главата, така и в тялото на правило. Една IDB може да се дефинира с няколко правила, в които главата е един и същ интенсионален предикат. Използвайки IDB можем да дефинираме

по-сложни релации. Този процес е подобен на изграждането на израз в релационната алгебра.

Концептуално по-лесно е да се използва вторият подход - ако набор от кортежи за всяка релационна подцел, която не е отречена дава съгласувани стойности за всяка променлива в правилото и всички аритметични подцели се оценяват като истина, то добавяме съответен кортеж към релацията в главата. При това, тъй като в случая релациите са мултимножества, не премахваме дубликатите от резултата.

Също така, ако един кортеж присъства много пъти в релация, съответна на релационна подцел, то всяко срещане на кортежа се разглежда независимо когато оценяваме променливите в правилото.

Изрично отбелязваме, че в модела с мултимножества не може да се дефинира ясно смисълът на правила, в които участват отречени релационни подцели.

Ще разгледаме пример. Нека е дадено следното правило:

H (x, z)  R (x, y) AND S (y, z).

Нека релацията R има следните кортежи: (1, 2), (1, 2), а релацията S има следните кортежи: (2, 3), (4, 5), (4, 5). Всевъзможните присъединявания на тези кортежи са следните:

R (x, y)	S (y, z)	съгласувано
(1, 2)	(2, 3)	да
(1, 2)	(4, 5)	не
(1, 2)	(4, 5)	не
(1, 2)	(2, 3)	да
(1, 2)	(4, 5)	не
(1, 2)	(4, 5)	не

Ще разгледаме пример. Нека е дадена следната заявка:

H (x, y)  S (x, y) AND x > 1,

H (x, y)  S (x, y) AND y < 5.

Тук релацията S има три кортежа: (2, 3), (4, 5), (4, 5).

Тогава резултатната релация H ще има следните кортежи:

(2, 3), (2, 3), (4, 5), (4, 5).
Преобразуване на изразите от релационната алгебра в Datalog правила
Всяка една от операциите в релационната алгебра може да се моделира чрез правила. Първо ще покажем как се моделират основните операции, а след това ще видим как се моделират изрази от релационната алгебра с произволна сложност.
Сечение
Сечението на две релации се моделира с едно правило, което съдържа по една подцел за всяка от двете релации. При това в двете подцели се използват еднакви променливи в съответните аргументи.

Например, ако R и S са релации, които имат по два атрибута, то тяхното сечение се пресмята от следното Datalog правило:

Intersection (x, y)  R (x, y) AND S (x, y).
Обединение
Обединение на две релации се моделира с две правила. Те имат по една релационна подцел, отговаряща на всяка от релациите. Аргументите на главата на всяко от правилата съвпадат с аргументите на техните подцели. Например, ако R и S са релации, които имат по два атрибута, то тяхното обединение се пресмята от следната заявка:

Union (x, y)  R (x, y),

Union (x, y)  S (x, y).

Да отбележим, че за разлика от моделирането на сечението, което е правилно само ако релациите са множества, при обединението моделирането е коректно дори ако релациите са мултимножества.

По принцип в тези разглеждания предполагаме, че релациите се интерпретират като множества, освен ако изрично не е указано друго.

Също да отбележим, че няма връзка между променливите в различни правила. Причината е, че всяко правило се оценява независимо от другите правила. Например, по-горе можем да заменим второто правило със следното: Union (u, v)  S (u, v). Естествено, когато преименуваме една променлива, трябва да внимаваме да не променим смисъла на правилото - новата променлива не трябва да се среща в правилото и освен това трябва да се преименуват всички срещания на старата променлива.

Difference (x, y)  R (x, y) AND NOT S (x, y).

по-трудно в Datalog. Най-простият случай е когато условието е конюнкция на едно или повече аритметични сравнения.

В този случай образуваме едно правило, което има:

1. 
   Една релационна подцел за релацията, върху която се извършва селекция, при това в тази подцел се използват различни променливи, по една за всеки атрибут на релацията.
   
2. 
   По една аритметична подцел за всяко от аритметичните сравнения, съвпадаща с това сравнение. Естествено, аргументите на подцелите съответстват на аргументите, които се използват в релационната подцел.
   

Нека е дадена следната селекция: _{length>=100 AND studioName =’ Fox’} (Movie).

В Datalog тя се моделира по следния начин:

Selection (t, y, l, c, s, p)  Movie (t, y, l, c, s, p) AND l >= 100 AND s = “Fox”.

Например, нека е дадена следната селекция:

_{length>=100 OR studioName =’ Fox’} (Movie).

В Datalog тя се моделира със следната заявка:

Selection (t, y, l, c, s, p)  Movie (t, y, l, c, s, p) AND l >= 100,

Selection (t, y, l, c, s, p)  Movie (t, y, l, c, s, p) AND s = “Fox”.

NOT A = B е еквивалентно на A  B и т.н. Всяка конюнкция може да се представи чрез едно правило, както по-горе описахме и след това дизюнкцията представяме чрез няколко правила, по едно за всяка конюнкция.

Главата на правилото има за аргументи всички променливи и от двете подцели, при това променливите на релацията в лявата част на декартовото произведение предшестват променливите на релацията в дясната част. Например, ако R и S са релации с два атрибута декартовото произведение R x S се пресмята чрез следното правило:

Product (x, y, u, v)  R (x, y) AND S (u, v).
Съединения
Моделирането на естествено съединение в Datalog е подобно на моделирането на декартово произведение, но с тази разлика, че трябва да се използват еднакви променливи за общите атрибути на двете релации. Например, ако имаме две релации със следните схеми:

R (A, B), S (B, C, D), то тяхното естествено съединение се описва със следното правило: NaturalJoin (a, b, c, d)  R (a, b) AND S (b, c, d).

Ако условието е конюнкция на аритметични сравнения, то използваме едно правило, което описва декартово произведение на двете участващи релации, като добавяме по една аритметична подцел за всяко от аритметичните сравнения.

Като пример разглеждаме две релации със следните схеми:

U (A, B, C) и V (B, C, D). Нека имаме следното тита-съединение:

U ⋈_{A < D AND U.B  V.B} S. То се моделира със следното правило:

Thetajoin (a, ub, uc, vb, vc, d)  U (a, ub, uc) AND V (vb, vc, d) AND

a < d AND ub  vb.

Ако условието в тита-съединението е произволно, то го привеждаме в дизюнктивна нормална форма. За всяка конюнкция образуваме по едно правило по описания начин. Естествено, главите на правилата, съответни на конюнкциите трябва да са едни и същи.

Например, за горните релации U и V да разгледаме следното

тита-съединение: U ⋈_{A < D OR U.B  V.B} S. To се описва със следната заявка:

Thetajoin (a, ub, uc, vb, vc, d)  U (a, ub, uc) AND V (vb, vc, d) AND a < d,

Thetajoin (a, ub, uc, vb, vc, d)  U (a, ub, uc) AND V (vb, vc, d) AND ub  vb.

Например, нека имаме следният релационен израз:

_{title, year} (_length>=100 (Movie)  _{studioName=’Fox’} (Movie)).

Той се представя чрез следното дърво:

За да моделираме този израз в Datalog можем да

използваме следната заявка:

W (t, y, l, c, s, p)  Movie (t, y, l, c, s, p) AND l >= 100

X (t, y, l, c, s, p)  Movie (t, y, l, c, s, p) AND s = “Fox”

Y (t, y, l, c, s, p)  W (t, y, l, c, s, p) AND X (t, y, l, c, s, p)

Z (t, y)  Y (t, y, l, c, s, p)
Рекурсия в Datalog
Съществуват заявки, които не могат да се изразят с помощта на релационната алгебра. Пример за такива заявки са безкрайни, рекурсивни поредици от операции.
Ще разгледаме пример, в контекста на базата от данни за филмите.

Един филм може да има продължение, продължението от своя страна също може да има продължение и т.н. Да си мислим, че имаме релация със следната схема SequelOf (movie, sequel). Нейните кортежи съдържат двойки от филм и негово непосредствено продължение.

Примерен екземпляр на релацията е следния:

movie	sequel
Naked Gun	Naked Gun 2
Naked Gun 2	Naked Gun 3

Под продължение разбираме продължение от произволна дълбочина.

Не е ясно как да се опише подобна заявка в релационната алгебра.

Можем да опишем продължение на филм на две нива, т.е. непосредствено продължение на непосредствено продължение по следния начин: _{first, third} (_{R (first, second)} (SequelOf) ⋈ _{R (second, third)} (SequelOf)).

По аналогичен начин, чрез суперпозиция на естествени съединения можем да получим продължения на произволно фиксирано ниво i.

Това, което не можем в релационната алгебра е да образуваме безкрайно обединение на релациите за i = 1, 2, ….

Това става по следния начин:

FollowOn (x, y)  SequelOf (x, y)

FollowOn (x, y)  SequelOf (x, z) AND FollowOn (z, y).