Викиконспекты - Вклад участника [ru]

Исчисление доменов и его реляционная полнота

2021-12-26T19:55:56Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
{{Утверждение
|statement=Исчисление доменов реляционно полно
|proof=
Выразим базис реляционной алгебры в терминах исчисления доменов:

'''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, для которых в исходном отношении есть кортеж, в котором атрибуты $A_1$...$A_n$ принимают значения $A_1$...$A_n$.
$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Фильтр $σ_θ(R)$'''
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

'''Переименовывание $ε_{A=expr}(R_1)$'''
Просто используем специальный синтаксис
..., $expr$ as $A$, ... where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Объединение $R_1 ∪ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

'''Разность $R_1 ∖ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

'''Декартово произведение $R_1 × R_2$'''
Выбираем наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что ($A_1$...$A_n$) есть в $R_1$, а ($B_1$...$B_n$) есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

'''Естественное соединение $R_1 ⋈ R_2$'''
Выбираем такие наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$, что $B_1$, ..., $B_m$ что ($A_1$, ..., $A_n$, $B_1$, ..., $B_m$) входит в $R_1$, а ($B_1$, ..., $B_m$, $C_1$, ..., $C_l$) в $R_2$. Автоматически получаем соединение по $B_1$, ..., $B_m$. Это можно было бы записать иначе - явной проверкой равенства этих атрибутов (тогда придётся использовать ещё m переменных), но проще сделать так.
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

<div></div>
}}

Исчисление доменов и его реляционная полнота

2021-12-26T19:55:29Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
{{Утверждение
|statement=Исчисление доменов реляционно полно
|proof=
Выразим базис реляционной алгебры в терминах исчисления доменов:

'''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, для которых в исходном отношении есть кортеж, в котором атрибуты $A_1$...$A_n$ принимают значения $A_1$...$A_n$.
$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Фильтр $σ_θ(R)$'''
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

'''Переименовывание $ε_{A=expr}(R_1)$'''
Просто используем специальный синтаксис
..., $expr$ as $A$, ... where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Объединение $R_1 ∪ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

'''Разность $R_1 ∖ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

'''Декартово произведение $R_1 × R_2$'''
Выбираем наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

'''Естественное соединение $R_1 ⋈ R_2$'''
Выбираем такие наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$, что $B_1$, ..., $B_m$ что ($A_1$, ..., $A_n$, $B_1$, ..., $B_m$) входит в $R_1$, а ($B_1$, ..., $B_m$, $C_1$, ..., $C_l$) в $R_2$. Автоматически получаем соединение по $B_1$, ..., $B_m$. Это можно было бы записать иначе - явной проверкой равенства этих атрибутов (тогда придётся использовать ещё m переменных), но проще сделать так.
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

<div></div>
}}

Datalog и рекурсия

2021-12-26T19:51:04Z

5.18.184.8: /* Реляционная полнота */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.

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

==Примеры запросов==
===Идентификаторы и фамилии всех Иванов===
Рассмотрим такой запрос на языке исчисления доменов
Id, LastName where Students{Id = Id, FirstName = 'Иван', LastName = LastName}

Его можно переписать на Datalog так:
Ivans(Id, LastName) :-
Students(Id, 'Иван', 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 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, _).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-26T19:42:50Z

5.18.184.8: /* Реляционная полнота */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.

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

==Примеры запросов==
===Идентификаторы и фамилии всех Иванов===
Рассмотрим такой запрос на языке исчисления доменов
Id, LastName where Students{Id = Id, FirstName = 'Иван', LastName = LastName}

Его можно переписать на Datalog так:
Ivans(Id, LastName) :-
Students(Id, 'Иван', 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 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, _).

Здесь есть проблема - во-первых, мы даже не знаем тип <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).

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

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

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

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

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

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

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

Исчисление доменов и его реляционная полнота

2021-12-26T18:32:00Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
{{Утверждение
|statement=Исчисление доменов реляционно полно
|proof=
Выразим базис реляционной алгебры в терминах исчисления доменов:

'''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, для которых в исходном отношении есть кортеж, в котором атрибуты $A_1$...$A_n$ принимают значения $A_1$...$A_n$.
$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Фильтр $σ_θ(R)$'''
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

'''Переименовывание $ε_{A=expr}(R_1)$'''
Просто используем специальный синтаксис
..., $expr$ as $A$, ... where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Объединение $R_1 ∪ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

'''Разность $R_1 ∖ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

'''Декартово произведение $R_1 × R_2$'''
Выбираем наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

'''Естественное соединение $R_1 ⋈ R_2$'''
Выбираем такие наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$, что $B_1$, ..., $B_m$ совпадает с соответствующими атрибутами и $R_1$ и $R_2$. Это можно записать как с явной проверкой равенства этих атрибутов (тогда придётся использовать ещё m переменных), так и с неявной, как это сделано здесь.
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

<div></div>
}}

Datalog и рекурсия

2021-12-20T09:49:12Z

5.18.184.8: /* Примеры запросов */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.

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

==Примеры запросов==
===Идентификаторы и фамилии всех Иванов===
Рассмотрим такой запрос на языке исчисления доменов
Id, LastName where Students{Id = Id, FirstName = 'Иван', LastName = LastName}

Его можно переписать на Datalog так:
Ivans(Id, LastName) :-
Students(Id, 'Иван', 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 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, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-20T09:32:09Z

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

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
Заметим, что в Datalog нет имён атрибутов, атрибуты различаются только по своей позиции.

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

==Примеры запросов==
===Идентификаторы и фамилии всех Иванов===
Рассмотрим такой запрос на языке исчисления доменов
Id, LastName where Students{Id = Id, FirstName = 'Иван', LastName = LastName}

Его можно переписать на Datalog так:
Ivans(Id, LastName) :-
Students(Id, 'Иван', 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, _, _).

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-20T09:15:22Z

5.18.184.8: /* Реляционный */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж удовлетворяет атому <code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
Заметим, что в 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).
===Имена родителей===
Пусть есть таблица <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, _, _).

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-20T09:15:09Z

5.18.184.8: /* Реляционный */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж удовлетворяет атому <code>R(x1, x2, ..., xn)</code> тогда и только тогда, когда принадлежит отношению R.
* Кортеж удовлетворяет атому code>¬R(x1, x2, ..., xn)</code> тогда и только тогда, когда такого кортежа нет в отношении R.
Заметим, что в 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).
===Имена родителей===
Пусть есть таблица <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, _, _).

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-20T09:08:09Z

5.18.184.8: /* Получить для каждого человека всех его родителей (Name, Parent) */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>

Заметим, что в 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).
===Имена родителей===
Пусть есть таблица <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, _, _).

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-20T09:07:08Z

5.18.184.8: /* Получить имена обоих родителей каждого человека (Name, Father, Mother) */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>

Заметим, что в 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).
===Имена родителей===
Пусть есть таблица <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(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, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-19T22:23:24Z

5.18.184.8: /* Ограничение отношений */

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

==Синтаксис==
===Отношение===
Программа на Datalog - набор '''отношений'''. Отношение на языке Datalog определяется так:
Отношение(x1,x2...xn) :- Цель.
Определение одного и того же отношения может повторяться несколько раз, тогда в это отношение будут входить кортежи, которые удовлетворяют хотя бы одной цели.
===Цель===
'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую. Кортеж удовлетворяет цели, если он удовлетворяет всем атомам цели.
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>

Заметим, что в 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).
===Имена родителей===
Пусть есть таблица <code>Person(Id, Name, MotherId, FatherId)</code>
====Получить имена обоих родителей каждого человека (Name, Father, Mother)====
Атомы в Datalog находятся в неявной конъюнкции, поэтому чтобы записать утверждение "FId - отец N, а MId - мать N", запишем их через запятую:
Parents(N, FN, MN) :- Person(_, N, FId, MId),
Person(FId, _, FN, _), Person(MId, MN, _, _).
====Получить для каждого человека всех его родителей (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, _).

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

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

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

==Реляционная полнота==
{{Утверждение
|statement=Язык Datalog реляционно полон
|proof=
Выразим базис реляционной алгебры на языке 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).

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

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

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

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

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

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

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

Datalog и рекурсия

2021-12-19T21:54:18Z

5.18.184.8: /* Получить для каждого человека всех его родителей (Name, Parent) */

Datalog и рекурсия

2021-12-19T21:53:44Z

5.18.184.8: /* Примеры запросов */

Datalog и рекурсия

2021-12-19T21:43:28Z

5.18.184.8: /* Идентификаторы и фамилии всех Иванов. */

Datalog и рекурсия

2021-12-19T21:43:15Z

5.18.184.8:

Datalog и рекурсия

2021-12-19T21:25:24Z

5.18.184.8: /* Синтаксис */

Datalog и рекурсия

2021-12-19T21:17:23Z

5.18.184.8: /* Смысл */

Datalog и рекурсия

2021-12-19T21:01:05Z

5.18.184.8: /* Рекурсивные запросы */

Datalog и рекурсия

2021-12-19T20:42:56Z

5.18.184.8: /* Синтаксис */

Datalog и рекурсия

2021-12-19T20:35:45Z

5.18.184.8: /* Язык Datalog */

Datalog и рекурсия

2021-12-19T20:35:17Z

5.18.184.8: /* Язык Datalog */

Исчисление доменов и его реляционная полнота

2021-12-19T20:24:18Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
{{Утверждение
|statement=Исчисление доменов реляционно полно
|proof=
Выразим базис реляционной алгебры в терминах исчисления доменов:

'''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R. Это важно, тк если опустить <code>where</code>, то получим декартово произведение доменов
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Фильтр $σ_θ(R)$'''
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

'''Переименовывание $ε_{A=expr}(R_1)$'''
Просто используем специальный синтаксис
..., $expr$ as $A$, ... from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Объединение $R_1 ∪ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

'''Разность $R_1 ∖ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

'''Декартово произведение $R_1 × R_2$'''
Выбираем наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

'''Естественное соединение $R_1 ⋈ R_2$'''
Выбираем такие наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$, что $B_1$, ..., $B_m$ совпадает с соответствующими атрибутами и $R_1$ и $R_2$. Это можно записать как с явной проверкой равенства этих атрибутов (тогда придётся использовать ещё m переменных), так и с неявной, как это сделано здесь.
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

<div></div>
}}

Исчисление доменов и его реляционная полнота

2021-12-19T20:04:20Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
{{Утверждение
|statement=Исчисление доменов реляционно полно
|proof=
Выразим базис реляционной алгебры в терминах исчисления доменов:

'''Проекция $\pi_{A_1, ..., A_n}(R)$'''
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Фильтр $σ_θ(R)$'''
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

'''Переименовывание $ε_{A=expr}(R_1)$'''
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

'''Объединение $R_1 ∪ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

'''Разность $R_1 ∖ R_2$'''
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

'''Декартово произведение $R_1 × R_2$'''
Выбираем наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

'''Естественное соединение $R_1 ⋈ R_2$'''
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

<div></div>
}}

Исчисление доменов и его реляционная полнота

2021-12-19T19:53:02Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
{{Утверждение
|statement=Исчисление доменов реляционно полно
|proof=
Выразим базис реляционной алгебры в терминах исчисления доменов:

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
Выбирает наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

}}

Исчисление доменов и его реляционная полнота

2021-12-19T19:47:22Z

5.18.184.8:

==Исчисление доменов==
{{Определение
|definition=
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
}}

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

Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.

===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
Выразим базис реляционной алгебры в исчислении доменов, тем самым докажем реляционную полноту исчисления доменов:

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
Выбирает наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Исчисление доменов и его реляционная полнота

2021-12-19T19:29:15Z

5.18.184.8: /* Реляционная полнота исчисления доменов */

==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==
Выразим базис реляционной алгебры в исчислении доменов, тем самым докажем реляционную полноту исчисления доменов:

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
Выбирает наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что $A_1$...$A_n$ есть в $R_1$, а $B_1$...$B_n$ есть в $R_2$
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Исчисление доменов и его реляционная полнота

2021-12-19T17:53:47Z

5.18.184.8: /* Примеры использования условия принадлежности */

==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Исчисление доменов и его реляционная полнота

2021-12-19T17:52:52Z

5.18.184.8: /* Исчисление доменов */

==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Исчисление доменов и его реляционная полнота

2021-12-19T17:51:16Z

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

==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
Также как и в исчислении кортежей, в исчислении доменов можно использовать кванторы. Студент не сдал курс, если у него нет положительных оценок за этот курс.

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

==Реляционная полнота исчисления доменов==

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Исчисление доменов и его реляционная полнота

2021-12-19T17:32:17Z

5.18.184.8: /* Идентификаторы всех студентов */

==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
Запишем запрос для получения идентификаторов всех студентов. Можно представлять это так: единственная свободная переменная SId пробегает все возможные значения из домена (все возможные идентификаторы студентов), а в результирующее отношение попадают только те её значения, для которых реально существовал такой студент.

SId where S{SId = SId}

=====Идентификаторы студентов, не сдавших курс с CId=10=====
SId where ¬∃Points (Points ≥ 60 ∧ Points{SId = SId, Points = Points, CId = 10})

==Реляционная полнота исчисления доменов==

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Исчисление доменов и его реляционная полнота

2021-12-19T17:18:58Z

5.18.184.8: /* Условие принадлежности */

==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

===Примеры использования условия принадлежности===
Предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

Имя атрибута может совпадать с именем переменной, это может поначалу немного запутывать. Слева от знака равенства стоит имя атрибута, справа - значение, с которым атрибут сравниваем

S{FirstName = FirstName, LastName = LastName}

===Примеры запросов===
=====Идентификаторы всех студентов=====
SId where S{SId = SId}
=====Идентификаторы студентов, не сдавших курс с CId=10=====
SId where ¬∃Points (Points ≥ 60 ∧ Points{SId = SId, Points = Points, CId = 10})

==Реляционная полнота исчисления доменов==

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}

Datalog и рекурсия

2021-12-19T13:38:40Z

5.18.184.8: /* Атом */

==Язык Datalog==
Декларативный язык на основе исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog

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

==Синтаксис==
Программа на Datalog - набор '''отношений''': Отношение на языке Datalog определяется так: <code>Отношение(x1,x2...xn) :- Цель.</code>

'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую
===Атом===
Атомы бывают двух типов: реляционные и арифметические
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>

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

====Арифметический====
всевозможные сравнения на равенство/неравенство

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Рекурсивные запросы==
===Смысл===
Пусть есть некоторое отношение "потомок-родитель"
Parent(Id, ParentId)

Хотим найти его транзитивное замыкание, по определению:
Ancestor(Id, PId) :- Parent(Id, PId).
Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).

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

Поэтому, следует уточнить, что мы ищем '''минимальную по включению неподвижную точку'''.

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

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

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

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

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

Datalog и рекурсия

2021-12-19T13:25:46Z

5.18.184.8: /* Синтаксис */

==Язык Datalog==
Декларативный язык на основе исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog

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

==Синтаксис==
Программа на Datalog - набор '''отношений''': Отношение на языке Datalog определяется так: <code>Отношение(x1,x2...xn) :- Цель.</code>

'''Цель''' в свою очередь - это набор '''атомов''', перечисленных через запятую
===Атом===
Атомы бывают двух типов
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>

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

====Арифметический====
всевозможные сравнения на равенство/неравенство

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Рекурсивные запросы==
===Смысл===
Пусть есть некоторое отношение "потомок-родитель"
Parent(Id, ParentId)

Хотим найти его транзитивное замыкание, по определению:
Ancestor(Id, PId) :- Parent(Id, PId).
Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).

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

Поэтому, следует уточнить, что мы ищем '''минимальную по включению неподвижную точку'''.

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

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

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

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

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

Datalog и рекурсия

2021-12-19T13:23:25Z

5.18.184.8: /* Язык Datalog */

==Язык Datalog==
Декларативный язык на основе исчисления доменов. Разработан в 1978 году, синтаксически - подмножество языка Prolog

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

==Синтаксис==
Программа на Datalog - набор '''отношений''': <code>Отношение(x1,x2...xn) :- Цель.</code>

'''Цель''' - Набор '''атомов''', перечисленных через запятую
===Атом===
====Реляционный====
Аналог конструкции условия принадлежности из исчисления доменов.
Есть два вида:
* Кортеж принадлежит отношению <code>R(x1, x2, ..., xn)</code>
* Кортеж не принадлежит отношению <code>¬R(x1, x2, ..., xn)</code>

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

====Арифметический====
всевозможные сравнения на равенство/неравенство

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

Рассмотрим отношения
Less(x,y) :- x < y.
NotStudent(Id, Name) :- ¬Students(Id, Name, _).

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

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

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

==Рекурсивные запросы==
===Смысл===
Пусть есть некоторое отношение "потомок-родитель"
Parent(Id, ParentId)

Хотим найти его транзитивное замыкание, по определению:
Ancestor(Id, PId) :- Parent(Id, PId).
Ancestor(Id, GId) :- Parent(Id, GId), Ancestor(PId, GId).

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

Поэтому, следует уточнить, что мы ищем '''минимальную по включению неподвижную точку'''.

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

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

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

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

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

Исчисление доменов и его реляционная полнота

2021-12-19T13:05:30Z

5.18.184.8: /* Исчисление доменов */

Исчисление доменов и его реляционная полнота

2021-12-19T12:47:12Z

5.18.184.8: /* Исчисление доменов */

==Исчисление доменов==
В отличие от исчисления кортежей, где областью знацения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
===Синтаксис===
Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

-- Условие принадлежности отношению
Отношение {
Атрибут1 = Значение1,
Атрибут2 = Значение2,
...
}

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

S{FirstName = 'Иван', LastName = 'Иванов'}

===Примеры запросов===
=====Идентификаторы всех студентов=====
SId where S{SId = SId}
=====Идентификаторы студентов, не сдавших курс с CId=10=====
SId where ¬∃Points (Points ≥ 60 ∧ Points{SId = SId, Points = Points, CId = 10})

==Реляционная полнота исчисления доменов==

====Проекция $\pi_{A_1, ..., A_n}(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Фильтр $σ_θ(R)$====
$A_1$, ..., $A_n$ from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

====Переименовывание $ε_{A=expr}(R_1)$====
expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

====Объединение $R_1 ∪ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

====Разность $R_1 ∖ R_2$====
$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

====Декартово произведение $R_1 × R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

====Естественное соединение $R_1 ⋈ R_2$====
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}