Datalog и рекурсия

Язык Datalog

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

Программа на языке 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$ есть неподвижная точка, но найденное отношение не является транзитивным замыканием.

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

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

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

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

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