Datalog и рекурсия
Содержание
Datalog и рекурсия
Язык Datalog
Декларативный язык на осноке исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog
Программа на языке Datalog представляет из себя набор определений отношений, результат выполнения - тело одного из отношений.
Синтаксис
Структура программы
Программа на Datalog - набор отношений: Отношение(x1,x2...xn) :- Цель.
Цель
Цель - Набор атомов, перечисленных через запятую
Атом
Реляционный
Арифметический
реляционные Аналог конструкции условия принадлежности из исчисления доменов Есть два вида: - Кортеж принадлежит отношению R(x1, x2, ..., xn) - Кортеж не принадлежит отношению ¬R(x1, x2, ..., xn)
-- заметим, что в Datalog нет имён атрибутов, атрибуты вместо этого различаются по позиции
арифметические всевозможные сравнения на равенство/неравенство
Ограничение отношений
Рассмотрим отношения Less(x,y) :- x < y. NotStudent(Id, Name) :- not 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 подходит под записанные уравнения, но не является транзитивным замыканием.
Это не то, что мы хотим, поэтому будем искать минимальное по включению решение. Сначала наполним выполним нерекурсивные правила, затем будем выполнять рекурсивные до достижения неподвижной точки.
Запретим отрицание в циклах, чтобы избежать парадокса брадобрея. 'стратифицированное отрицание'
