Изменения

Декларативный язык для запросов к базам данных на осноке основе исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog. Широкого применения в реальных базах данных не получил, но повлиял на формирование более поздних языков для запросов, таких как SQL.

==Синтаксис=====Отношение===Программа на языке Datalog представляет из себя - набор определений '''отношений'''. Отношение на языке Datalog определяется так: Отношение(x1, результат выполнения x2...xn) :- тело Цель.Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.===Цель==='''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.===Атом===Атомы бывают двух типов: реляционные и арифметические====Реляционный====Аналог конструкции условия принадлежности из отношенийисчисления доменов.Есть два вида:* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции. ====Арифметический====Сюда входят сравнения арифмитических выражений на равенство и неравенство. ==Примеры запросов=====Идентификаторы и фамилии всех Иванов===Рассмотрим такой запрос на языке исчисления доменов Id, LastName <font color=blue>where</font> Students<font color=red>{</font>Id = Id, FirstName = <font color=green>'Иван'</font>, LastName = LastName<font color=red>}</font>

Его можно переписать на Datalog так: Ivans(Id, LastName) :- Students(Id, <font color==Синтаксис==green>'Иван'</font>, LastName).

====Структура программы=Имена родителей===Программа на Datalog - набор '''отношений''': Пусть есть таблица <code>ОтношениеPerson(x1Id, Name, MotherId,x2...xnFatherId) :- Цель.</code>====ЦельПолучить имена обоих родителей каждого человека (Name, Father, Mother)===='''Цель''' Запишем конъюнкцию атомов: "FatherId - Набор '''атомов'''отец Name", "MotherId - мать Name", "Имя FatherId - FatherName", перечисленных через запятую"Имя MotherId - MotherName":====Атом==== Parents(Name, FatherName, MotherName) :- Person(_, Name, FatherId, MotherId),=====Реляционный==========Арифметический===== Person(FatherId, FatherName, _, _), Person(MotherId, MotherName, _, _).

реляционные====Получить для каждого человека всех его родителей (Name, Parent)====Аналог конструкции условия принадлежности из исчисления доменовВоспользуемся тем, что в Datalog при определении отношений дважды, они объёдиняются:Есть два вида Parents(Name, FatherName) :- Кортеж принадлежит отношениюPerson(_, Name, FatherId, _),R Person(x1FatherId, x2FatherName, _, _)... Parents(Name, xnMotherName):- Кортеж не принадлежит отношениюPerson(_, Name, _, MotherId),¬R Person(x1MotherId, x2MotherName, _, _)...====Идентификаторы студентов не сдавших курс с CId=10====На языке исчисления доменов этот запрос можно записать так: SId <font color=blue>where</font> ¬∃Points (Points ≥ 60 ∧ Points<font color=red>{</font>SId = SId, Points = Points, xnCId = 10<font color=red>}</font>)

Перепишем его на язык Datalog. Так как в Datalog нет явных кванторов, то мы вынуждены пользоваться неявным квантором существования, который в Datalog связывает все свободные переменные цели. Над ним невозможно поставить отрицание, поэтому запишем вспомогательное отношение, в котором есть те и только те студенты, которые '''сдали курс''', затем построим отрицание. Graded(SId) :-Points(SId, Points, 10), Points >= 60. Failed(SId) :- заметимPoints(SId, что в Datalog нет имён атрибутов_, _), атрибуты вместо этого различаются по позиции¬Graded(SId).

арифметические==Ограничение отношений==всевозможные сравнения Как и на равенство/неравенстволюбую другую программу, на синтаксически корректную программу на языке Datalog нужно наложить дополнительные ограничения, чтобы она имела смысл.

Less(x,y) :- x < y. NotStudent(Id, Name) :- not Students¬Students(Id, Name, _). Здесь есть проблема - во-первых, мы даже не знаем тип <code>x</code>, <code>y</code>, <code>Id</code> и <code>Name</code>, это значит, что мы не знаем области их значения.Во-вторых, даже если бы мы знали их тип, пусть это будут, например, целые числа, то получили бы бесконечное отношение, с такими мы работать не умеем. Поэтому, нужно запретить такую ситуацию, для этого добавим требование: '''Каждая переменная должна входить в неотрицательный реляционный атом''' ==Реляционная полнота=={{Утверждение|statement=Язык Datalog реляционно полон|proof=Выразим базис реляционной алгебры на языке Datalog: '''Проекция $\pi_{A_1, ..., A_n}(R)$''' Цели удовлетворяют те и только те кортежи, для которых в исходном отношении есть кортеж, совпадающий с ними по первым n атрибутам Q(A1, ..., An) :- R(A1, ..., An, _, ..., _).'''Фильтр $σ_θ(R)$''' Цели удовлетворяют те и только те кортежи, которые есть в исходном отношении и удовлетворяют условию θ Q(A1, ..., An) :- R(A1, ..., An), θ.'''Объединение $R_1 ∪ R_2$''' Отношение содержит кортежи, которые удовлетворяют хотя бы одной из целей, а значит принадлежит хотя бы одному из исходных отношений. Q(A1, ..., An) :- R1(A1, ..., An). Q(A1, ..., An) :- R2(A1, ..., An).'''Разность $R_1 ∖ R_2$''' Цели удовлетворяют только такие кортежи, которые есть в $R_1$, но не в $R_2$. Q(A1, ..., An) :- R1(A1, ..., An), ¬R2(A1, ..., An).'''Декартово произведение $R_1 × R_2$''' Цели удовлетворяют такие кортежи, что первые $n$ значений атрибутов взяты из первого отношения, а следующие $m$ - из второго Q(A1, ..., An, B1, ..., Bm) :- R1(A1, ..., An), R2(B1, ..., Bm). '''Естественное соединение $R_1 ⋈ R_2$''' Почти как декартово произведение, но теперь переменные $B_1 \ldots B_m$ - атрибуты, по которым идёт соединение - используются сразу в двух атомах. Q(A1, ..., An, B1, ..., Bm, C1, ..., Cl) :- R1(A1, ..., An, B1, ..., Bm), R2(B1, ..., Bm, C1, ..., Cl).'''Переименовывание''' Заметим что в Datalog нет имён атрибутов, роль имён здесь играют позиции. Поэтому переименовывание не нужно, вместо этого можно сделать перестановку атрибутов. <div></div>}} ==Рекурсивные запросы==Синтаксис Datalog позволяет написать рекурсивный запрос, но может быть не очевидно, какой смысл придавать такой конструкции.Далее будет рассмотрен пример и приведены некоторые рассуждения о семантике рекурсивных запросов.===Смысл===Пусть есть некоторое отношение "потомок-родитель" Parent(Id, ParentId) Хотим найти его транзитивное замыкание, по определению: Ancestor(Id, PId) :- Parent(Id, PId). Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId). Пусть $P$ - множество всех людей, у которых есть хотя бы один родитель.Очевидно, что $P \times P$ есть неподвижная точка, то есть правая часть отношения совпадает с левой, но найденное отношение не является транзитивным замыканием исходного.

Здесь есть проблема - мы даже не знаем тип xПоэтому,yследует уточнить,Idчто мы ищем '''минимальную по включению неподвижную точку''',Name, по сути там могут быть любые значения. Мы породили бесконечное отношение.Запретим так делатьначиная с пустого множества, а именно добавим ограничение:Каждая переменная должна входить в неотрицательный реляционный атомтогда наш запрос отработает корректно.

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

Запретим отрицание в циклахПоэтому, чтобы избежать парадокса брадобрея. введём '''стратифицированное отрицание''', то есть запрет на отрицание в циклах.