Datalog и рекурсия

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Язык Datalog

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

Синтаксис

Отношение

Программа на Datalog - набор отношений. Отношение на языке Datalog определяется так:

Отношение(x1,x2...xn) :- Цель.

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

Цель

Цель в свою очередь - это набор атомов, перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.

Атом

Атомы бывают двух типов: реляционные и арифметические

Реляционный

Аналог конструкции условия принадлежности из исчисления доменов. Есть два вида:

• Кортеж удовлетворяет атому R(x1, x2, ..., xn) тогда и только тогда, когда принадлежит отношению R.
• Кортеж удовлетворяет атому ¬R(x1, x2, ..., xn) тогда и только тогда, когда такого кортежа нет в отношении R.

Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.

Арифметический

Сюда входят сравнения арифмитических выражений на равенство и неравенство.

Примеры запросов

Идентификаторы и фамилии всех Иванов

Рассмотрим такой запрос на языке исчисления доменов

Id, LastName where Students{Id = Id, FirstName = 'Иван', LastName = LastName}

Его можно переписать на Datalog так:

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(Name, FatherName) :- Person(_, Name, FatherId, _),
    Person(FatherId, FatherName, _, _).
Parents(Name, MotherName) :- Person(_, Name, _, MotherId),
    Person(MotherId, MotherName, _, _).

Идентификаторы студентов не сдавших курс с CId=10

На языке исчисления доменов этот запрос можно записать так:

SId where ¬∃Points (Points ≥ 60 ∧ Points{SId = SId, Points = Points, CId = 10})

Перепишем его на язык Datalog. Так как в Datalog нет явных кванторов, то мы вынуждены пользоваться неявным квантором существования, который в Datalog связывает все свободные переменные цели. Над ним невозможно поставить отрицание, поэтому запишем вспомогательное отношение, в котором есть те и только те студенты, которые сдали курс, затем построим отрицание.

Graded(SId) :- Points(SId, Points, 10), Points >= 60.
Failed(SId) :- Points(SId, _, _), ¬Graded(SId).

Ограничение отношений

Как и на любую другую программу, на синтаксически корректную программу на языке Datalog нужно наложить дополнительные ограничения, чтобы она имела смысл.

Рассмотрим отношения

Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

Здесь есть проблема - во-первых, мы даже не знаем тип x, y, Id и Name, это значит, что мы не знаем области их значения. Во-вторых, даже если бы мы знали их тип, пусть это будут, например, целые числа, то получили бы бесконечное отношение, с такими мы работать не умеем.

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

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

Реляционная полнота

Утверждение:

Язык Datalog реляционно полон

[math]\triangleright[/math]

Выразим базис реляционной алгебры на языке Datalog: Проекция $\pi_{A_1, ..., A_n}(R)$ Цели удовлетворяют те и только те кортежи, для которых в исходном отношении есть кортеж, совпадающий с ними по первым n атрибутам 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$ Цели удовлетворяют только такие кортежи, которые есть в $R_1$, но не в $R_2$. Q(A1, ..., An) :- R1(A1, ..., An), ¬R2(A1, ..., An). Декартово произведение $R_1 × R_2$ Цели удовлетворяют такие кортежи, что первые $n$ значений атрибутов взяты из первого отношения, а следующие $m$ - из второго Q(A1, ..., An, B1, ..., Bm) :- R1(A1, ..., An), R2(B1, ..., Bm). Естественное соединение $R_1 ⋈ R_2$ Почти как декартово произведение, но теперь переменные $B_1 \ldots B_m$ - атрибуты, по которым идёт соединение - используются сразу в двух атомах. Q(A1, ..., An, B1, ..., Bm, C1, ..., Cl) :- R1(A1, ..., An, B1, ..., Bm), R2(B1, ..., Bm, C1, ..., Cl). Переименовывание Заметим что в Datalog нет имён атрибутов, роль имён здесь играют позиции. Поэтому переименовывание не нужно, вместо этого можно сделать перестановку атрибутов.

[math]\triangleleft[/math]

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

Синтаксис Datalog позволяет написать рекурсивный запрос, но может быть не очевидно, какой смысл придавать такой конструкции. Далее будет рассмотрен пример и приведены некоторые рассуждения о семантике рекурсивных запросов.

Смысл

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

Parent(Id, ParentId)

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

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

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

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

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

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

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

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

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