Datalog и рекурсия
Содержание
Язык Datalog
Декларативный язык для запросов к базам данных на основе исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog. Широкого применения в реальных базах данных не получил, но повлиял на формирование более поздних языков для запросов, таких как SQL.
Синтаксис
Отношение
Программа на Datalog - набор отношений. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
Цель
Цель в свою очередь - это набор атомов, перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
Атом
Атомы бывают двух типов: реляционные и арифметические
Реляционный
Аналог конструкции условия принадлежности из исчисления доменов. Есть два вида:
- Кортеж принадлежит отношению
R(x1, x2, ..., xn) - Кортеж не принадлежит отношению
¬R(x1, x2, ..., xn)
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.
Арифметический
Сюда входят сравнения арифмитических выражений на равенство и неравенство.
Примеры запросов
Идентификаторы и фамилии всех Иванов
Рассмотрим такой запрос на языке исчисления доменов
Id, LastName where Students{Id = Id, FirstName = FirstName, LastName = LastName} $\wedge$ FirstName = 'Иван'
Его можно переписать на Datalog так:
Ivans(Id, LastName) :-
Students(Id, FirstName, LastName),
FirstName = 'Иван'.
Или ещё проще:
Ivans(Id, LastName) :-
Students(Id, 'Иван', LastName).
Имена родителей
Пусть есть таблица Person(Id, Name, MotherId, FatherId)
Получить имена обоих родителей каждого человека (Name, Father, Mother)
Запишем конъюнкцию атомов: "FatherId - отец Name", "MotherId - мать Name", "Имя FatherId - FatherName", "Имя MotherId - MotherName":
Parents(Name, FatherName, MotherName) :- Person(_, Name, FatherId, MotherId),
Person(FatherId, FatherName, _, _), Person(MotherId, MotherName, _, _).
Получить для каждого человека всех его родителей (Name, Parent)
Воспользуемся тем, что в Datalog при определении отношений дважды, они объёдиняются:
Parents(N, FN) :- Person(_, N, FId, _),
Person(FId, FN, _, _).
Parents(N, MN) :- Person(_, N, _, MId),
Person(MId, MN, _, _).
Ограничение отношений
Как и на любую другую программу, на синтаксически корректную программу на языке Datalog нужно наложить дополнительные ограничения, чтобы она имела смысл.
Рассмотрим отношения
Less(x,y) :- x < y. NotStudent(Id, Name) :- ¬Students(Id, Name, _).
Здесь есть проблема - во-первых, мы даже не знаем тип x, y, Id и Name, это значит, что мы не знаем области их значения.
Во-вторых, даже если бы мы знали их тип, пусть это будут, например, целые числа, то получили бы бесконечное отношение, с такими мы работать не умеем.
Поэтому, нужно запретить такую ситуацию, для этого добавим требование:
Каждая переменная должна входить в неотрицательный реляционный атом
Реляционная полнота
| Утверждение: |
Язык Datalog реляционно полон |
|
Выразим базис реляционной алгебры на языке Datalog: Проекция $\pi_{A_1, ..., A_n}(R)$ Q(A1, ..., An) :- R(A1, ..., An, _, ..., _). Фильтр $σ_θ(R)$ Q(A1, ..., An) :- R(A1, ..., An), θ. Объединение $R_1 ∪ R_2$ Q(A1, ..., An) :- R1(A1, ..., An). Q(A1, ..., An) :- R2(A1, ..., An). Разность $R_1 ∖ R_2$ Q(A1, ..., An) :- R1(A1, ..., An), ¬R2(A1, ..., An). Декартово произведение $R_1 × R_2$ Q(A1, ..., An, B1, ..., Bm) :-
R1(A1, ..., An), R2(B1, ..., Bm).
Естественное соединение $R_1 ⋈ R_2$ Q(A1, ..., An, B1, ..., Bm, C1, ..., Cl) :-
R1(A1, ..., An, B1, ..., Bm), R2(B1, ..., Bm, C1, ..., Cl).
|
Рекурсивные запросы
Синтаксис Datalog позволяет написать рекурсивный запрос, но может быть не очевидно, какой смысл придавать такой конструкции. Далее будет рассмотрен пример и приведены некоторые рассуждения о семантике рекурсивных запросов.
Смысл
Пусть есть некоторое отношение "потомок-родитель"
Parent(Id, ParentId)
Хотим найти его транзитивное замыкание, по определению:
Ancestor(Id, PId) :- Parent(Id, PId). Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).
Пусть $P$ - множество всех людей, у которых есть хотя бы один родитель. Очевидно, что $P \times P$ есть неподвижная точка, то есть правая часть отношения совпадает с левой, но найденное отношение не является транзитивным замыканием исходного.
Поэтому, следует уточнить, что мы ищем минимальную по включению неподвижную точку, начиная с пустого множества, тогда наш запрос отработает корректно.
Алгоритм поиска минимальной неподвижной точки
Проинициализируем отношения из нерекурсивных определений Пока не достигли неподвижной точки Пополняем отношения из рекурсивных определений
Циклы и отрицание
Представим ситуацию, когда принадлежность кортежа к отношению зависит от отрицания его принадлежности к отношению. Это в чистом виде парадокс брадобрея и мы знаем, что такая конструкция не имеет смысла.
Поэтому, введём стратифицированное отрицание, то есть запрет на отрицание в циклах.
