Изменения

Перейти к: навигация, поиск

Datalog и рекурсия

1273 байта добавлено, 22:42, 26 декабря 2021
Реляционная полнота
Выразим базис реляционной алгебры на языке 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).
Анонимный участник

Навигация