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

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

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