Datalog и рекурсия

Язык Datalog

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

Синтаксис

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

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

Атом

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

Реляционный

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

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

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

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

всевозможные сравнения на равенство/неравенство

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

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

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

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

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

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

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

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

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

Смысл

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

Parent(Id, ParentId)

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

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

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

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

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

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

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

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

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