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

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

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

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

Смысл

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

Parent(Id, ParentId)

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

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

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

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

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

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

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

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

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