Datalog и рекурсия

Язык Datalog

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

Синтаксис

Отношение

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

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

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

Цель

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

Атом

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

Реляционный

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

• Кортеж принадлежит отношению R(x1, x2, ..., xn)
• Кортеж не принадлежит отношению ¬R(x1, x2, ..., xn)

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

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

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

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

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

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

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

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

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

Или ещё проще:

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(N, FN) :- Person(_, N, FId, _),
    Person(FId, FN, _, _).
Parents(N, MN) :- Person(_, N, _, MId),
    Person(MId, MN, _, _).

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

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

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

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

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

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

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

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

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

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

[math]\triangleright[/math]

Выразим базис реляционной алгебры на языке Datalog: Проекция $\pi_{A_1, ..., A_n}(R)$ 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$ Q(A1, ..., An) :- R1(A1, ..., An), ¬R2(A1, ..., An). Декартово произведение $R_1 × R_2$ Q(A1, ..., An, B1, ..., Bm) :- R1(A1, ..., An), R2(B1, ..., Bm). Естественное соединение $R_1 ⋈ R_2$ Q(A1, ..., An, B1, ..., Bm, C1, ..., Cl) :- R1(A1, ..., An, B1, ..., Bm), R2(B1, ..., Bm, C1, ..., Cl).

[math]\triangleleft[/math]

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

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

Смысл

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

Parent(Id, ParentId)

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

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

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

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

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

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

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

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

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