Изменения

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

===Отношение===Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так: <code> Отношение(x1,x2...xn) :- Цель.</code>Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.===Цель==='''Цель''' в свою очередь - Набор это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.

* Кортеж принадлежит отношению удовлетворяет атому <code>R(x1, x2, ..., xn)</code>тогда и только тогда, когда принадлежит отношению R.* Кортеж не принадлежит отношению удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code>тогда и только тогда, когда такого кортежа нет в отношении R.

всевозможные Сюда входят сравнения арифмитических выражений на равенствои неравенство. ==Примеры запросов=====Идентификаторы и фамилии всех Иванов===Рассмотрим такой запрос на языке исчисления доменов 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). ===Имена родителей===Пусть есть таблица <code>Person(Id, Name, MotherId, FatherId)</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, _), Person(FatherId, FatherName, _, _). Parents(Name, MotherName) :- Person(_, Name, _, MotherId), Person(MotherId, MotherName, _, _).====Идентификаторы студентов не сдавших курс с CId=10====На языке исчисления доменов этот запрос можно записать так: SId <font color=blue>where</font> ¬∃Points (Points ≥ 60 ∧ Points<font color=red>{</font>SId = SId, Points = Points, CId = 10<font color=red>}</font>) Перепишем его на язык Datalog. Так как в Datalog нет явных кванторов, то мы вынуждены пользоваться неявным квантором существования, который в Datalog связывает все свободные переменные цели. Над ним невозможно поставить отрицание, поэтому запишем вспомогательное отношение, в котором есть те и только те студенты, которые '''сдали курс''', затем построим отрицание. Graded(SId) :- Points(SId, Points, 10), Points >= 60. Failed(SId) :- Points(SId, _, _), ¬Graded(SId).

Здесь есть проблема - во-первых, мы даже не знаем тип <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 нет имён атрибутов, роль имён здесь играют позиции. Поэтому переименовывание не нужно, вместо этого можно сделать перестановку атрибутов.

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

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