Datalog и рекурсия

Содержание

1 Язык Datalog
2 Синтаксис
3 Примеры запросов
- 3.1 Идентификаторы и фамилии всех Иванов
- 3.2 Имена родителей
4 Ограничение отношений
5 Реляционная полнота
6 Рекурсивные запросы

Язык Datalog

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

Синтаксис

Отношение

Программа на Datalog - набор отношений. Отношение на языке Datalog определяется так:

Отношение(x1,x2...xn) :- Цель.

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

Цель

Цель в свою очередь - это набор атомов, перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.

Атом

Атомы бывают двух типов: реляционные и арифметические

Реляционный

Аналог конструкции условия принадлежности из исчисления доменов. Есть два вида:

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

Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.

Арифметический

Сюда входят сравнения арифмитических выражений на равенство и неравенство.

Примеры запросов

Идентификаторы и фамилии всех Иванов

Рассмотрим такой запрос на языке исчисления доменов

Id, LastName where Students{Id = Id, FirstName = 'Иван', LastName = LastName}

Его можно переписать на Datalog так:

Ivans(Id, LastName) :-
    Students(Id, 'Иван', LastName).

Имена родителей

Пусть есть таблица Person(Id, Name, MotherId, FatherId)

Получить имена обоих родителей каждого человека (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 where ¬∃Points (Points ≥ 60 ∧ Points{SId = SId, Points = Points, CId = 10})

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

Graded(SId) :- Points(SId, Points, 10), Points >= 60.
Failed(SId) :- Points(SId, _, _), ¬Graded(SId).

Ограничение отношений

Как и на любую другую программу, на синтаксически корректную программу на языке Datalog нужно наложить дополнительные ограничения, чтобы она имела смысл.

Рассмотрим отношения

Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

Здесь есть проблема - во-первых, мы даже не знаем тип x, y, Id и Name, это значит, что мы не знаем области их значения. Во-вторых, даже если бы мы знали их тип, пусть это будут, например, целые числа, то получили бы бесконечное отношение, с такими мы работать не умеем.

Поэтому, нужно запретить такую ситуацию, для этого добавим требование:

Каждая переменная должна входить в неотрицательный реляционный атом

Реляционная полнота

Утверждение:

Язык Datalog реляционно полон

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

Рекурсивные запросы

Синтаксис Datalog позволяет написать рекурсивный запрос, но может быть не очевидно, какой смысл придавать такой конструкции. Далее будет рассмотрен пример и приведены некоторые рассуждения о семантике рекурсивных запросов.

Смысл

Пусть есть некоторое отношение "потомок-родитель"

Parent(Id, ParentId)

Хотим найти его транзитивное замыкание, по определению:

Ancestor(Id, PId) :- Parent(Id, PId).
Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).

Пусть $P$ - множество всех людей, у которых есть хотя бы один родитель. Очевидно, что $P \times P$ есть неподвижная точка, то есть правая часть отношения совпадает с левой, но найденное отношение не является транзитивным замыканием исходного.

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

Алгоритм поиска минимальной неподвижной точки

Проинициализируем отношения из нерекурсивных определений
Пока не достигли неподвижной точки
  Пополняем отношения из рекурсивных определений

Циклы и отрицание

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

Поэтому, введём стратифицированное отрицание, то есть запрет на отрицание в циклах.