Datalog и рекурсия — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
==Язык Datalog==
 
==Язык Datalog==
Декларативный язык на осноке исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog
+
Декларативный язык для запросов к базам данных на основе исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog. Широкого применения в реальных базах данных не получил, но повлиял на формирование более поздних языков для запросов, таких как SQL.
 
 
Программа на языке Datalog представляет из себя набор определений отношений, результат выполнения - тело одного из отношений.
 
  
 
==Синтаксис==
 
==Синтаксис==
Программа на Datalog - набор '''отношений''': <code>Отношение(x1,x2...xn) :- Цель.</code>
+
===Отношение===
 
+
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:  
'''Цель''' - Набор '''атомов''', перечисленных через запятую
+
Отношение(x1,x2...xn) :- Цель.
 +
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
 +
===Цель===
 +
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
 
===Атом===
 
===Атом===
 +
Атомы бывают двух типов: реляционные и арифметические
 
====Реляционный====
 
====Реляционный====
 
Аналог конструкции условия принадлежности из исчисления доменов.
 
Аналог конструкции условия принадлежности из исчисления доменов.
 
Есть два вида:
 
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
+
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>
+
* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
 
 
 
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.
 
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.
  
 
====Арифметический====
 
====Арифметический====
всевозможные сравнения на равенство/неравенство
+
Сюда входят сравнения арифмитических выражений на равенство и неравенство.
 +
 
 +
==Примеры запросов==
 +
===Идентификаторы и фамилии всех Иванов===
 +
Рассмотрим такой запрос на языке исчисления доменов
 +
Id, LastName <font color=blue>where</font> Students<font color=red>{</font>Id = Id, FirstName = <font color=green>'Иван'</font>, LastName = LastName<font color=red>}</font>
 +
 
 +
Его можно переписать на Datalog так:
 +
Ivans(Id, LastName) :-
 +
    Students(Id, <font color=green>'Иван'</font>, LastName).
 +
 
 +
===Имена родителей===
 +
Пусть есть таблица <code>Person(Id, Name, MotherId, FatherId)</code>
 +
====Получить имена обоих родителей каждого человека (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 <font color=blue>where</font> ¬∃Points (Points ≥ 60 ∧ Points<font color=red>{</font>SId = SId, Points = Points, CId = 10<font color=red>}</font>)
 +
 
 +
Перепишем его на язык Datalog. Так как в Datalog нет явных кванторов, то мы вынуждены пользоваться неявным квантором существования, который в Datalog связывает все свободные переменные цели. Над ним невозможно поставить отрицание, поэтому запишем вспомогательное отношение, в котором есть те и только те студенты, которые '''сдали курс''', затем построим отрицание.
 +
Graded(SId) :- Points(SId, Points, 10), Points >= 60.
 +
Failed(SId) :- Points(SId, _, _), ¬Graded(SId).
  
 
==Ограничение отношений==
 
==Ограничение отношений==
Строка 27: Строка 58:
 
  NotStudent(Id, Name) :- ¬Students(Id, Name, _).
 
  NotStudent(Id, Name) :- ¬Students(Id, Name, _).
  
Здесь есть проблема - мы даже не знаем тип x, y, Id и Name, это значит, что мы не знаем области их значения.
+
Здесь есть проблема - во-первых, мы даже не знаем тип <code>x</code>, <code>y</code>, <code>Id</code> и <code>Name</code>, это значит, что мы не знаем области их значения.
 +
Во-вторых, даже если бы мы знали их тип, пусть это будут, например, целые числа, то получили бы бесконечное отношение, с такими мы работать не умеем.
 +
 
 +
Поэтому, нужно запретить такую ситуацию, для этого добавим требование:
 +
 
 +
'''Каждая переменная должна входить в неотрицательный реляционный атом'''
 +
 
 +
==Реляционная полнота==
 +
{{Утверждение
 +
|statement=Язык Datalog реляционно полон
 +
|proof=
 +
Выразим базис реляционной алгебры на языке 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 нет имён атрибутов, роль имён здесь играют позиции. Поэтому переименовывание не нужно, вместо этого можно сделать перестановку атрибутов.
  
Запретим так делать, а именно добавим ограничение: Каждая переменная должна входить в неотрицательный реляционный атом.
+
<div></div>
 +
}}
  
 
==Рекурсивные запросы==
 
==Рекурсивные запросы==
 +
Синтаксис Datalog позволяет написать рекурсивный запрос, но может быть не очевидно, какой смысл придавать такой конструкции.
 +
Далее будет рассмотрен пример и приведены некоторые рассуждения о семантике рекурсивных запросов.
 +
===Смысл===
 +
Пусть есть некоторое отношение "потомок-родитель"
 +
Parent(Id, ParentId)
 +
 +
Хотим найти его транзитивное замыкание, по определению:
 +
Ancestor(Id, PId) :- Parent(Id, PId).
 +
Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).
 +
 +
Пусть $P$ - множество всех людей, у которых есть хотя бы один родитель.
 +
Очевидно, что $P \times P$ есть неподвижная точка, то есть правая часть отношения совпадает с левой, но найденное отношение не является транзитивным замыканием исходного.
 +
 +
Поэтому, следует уточнить, что мы ищем '''минимальную по включению неподвижную точку''', начиная с пустого множества, тогда наш запрос отработает корректно.
  
Допустим, у нас есть отношение
+
===Алгоритм поиска минимальной неподвижной точки===
Parent(Id, ParentId)
 
  
Хотим найти транзитивное замыкание, запишем определение транзитивного замыкания:
+
Проинициализируем отношения из нерекурсивных определений
Ancestor(Id, PId) :- Parent(Id, PId).
+
Пока не достигли неподвижной точки
Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).
+
  Пополняем отношения из рекурсивных определений
  
Пусть P - множество всех людей, у которых есть хотя бы один родитель.
+
===Циклы и отрицание===
Очевидно, что PxP подходит под записанные уравнения, но не является транзитивным замыканием.
 
  
Это не то, что мы хотим, поэтому будем искать минимальное по включению решение.
+
Представим ситуацию, когда принадлежность кортежа к отношению зависит от отрицания его принадлежности к отношению. Это в чистом виде парадокс брадобрея и мы знаем, что такая конструкция не имеет смысла.
Сначала наполним выполним нерекурсивные правила, затем будем выполнять рекурсивные до достижения неподвижной точки.  
 
  
Запретим отрицание в циклах, чтобы избежать парадокса брадобрея. 'стратифицированное отрицание'
+
Поэтому, введём '''стратифицированное отрицание''', то есть запрет на отрицание в циклах.

Текущая версия на 19:22, 4 сентября 2022

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

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

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

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

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

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

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