ПБД (9) - Лекция №9 - Datalog
Datalog
Язык логических запросов Database Logic. Основан на использовании предикатов.
Предикат - функция, принимающая аргументы, возвращает true или false. Аргументы могут быть константы или переменные.
Атом - предикат, с подставленными в него аргументами. Атомы бывают:
- реляционные - на основе отношений БД, совпадают с названиями таблиц;
- арифметические - операция сравнения двух арифметических выражений.
Количество и последовательность аргументом должны совпадать абсолютно.
// реляционный предикат
Actor("123", "Иванов", "высшее") // если есть такой актёр, то вернёт true, иначе false
Для создания запроса используются правила "если ... то":
// в общем виде
заголовок <-- набор >= подцель AND подцель AND ...
// конкретно
ЧёрноБелыеФильмы(н,г,ст) <-- Фильм (н, г, д, т, ст) AND т = "ч/б"
Есть анонимные переменные - не используются для выполнения сравнения и получения результата. Ставятся на место обычных переменных, заменяя их знаком подчёркивания: "_".
Правила
Вычисление правил:
- определение кортежей из реляционный подцелей без отрицания;
- получение согласованного набора кортежей;
- для согласованного набора проверяются все подцели;
- для истинных подцелей формируем результат.
Согласованный набор - это когда одним и тем же переменным соответствуют одни и те же значения (результат выполнения естественного соединения):
АВФ(фио,н) <-- Актёр(i, фио, _) AND ФА(н, 1979, i) AND i > 1000
Правило безопасности - каждая переменная из правила должна быть и в реляционной подцели без отрицания.
Реляционные операции
Для результатов можно использовать операции реляционной алгебры:
- объединение;
- разность;
- проекция;
- селекция;
- декартово произведение;
- естественное соединение.
// декартово произведение
S(a,b,x,y) <-- X(a,b) AND Y(x,y)
// естественное соединение
S(a,z,x) <-- X(a,z) AND (z, x)
Примеры:
// фильмы, снятые на Мосфильме
ФильмМосфильм(н,г) <-- Фильм(н, г, _, _, ст) AND ст = "Мосфильм"
// актёры с МосФильма, работавщие в 1990
АктМосфильм(фио) <-- Актёр(i, фио, _) AND ФА(н, 1990, i) AND Фильм(н, 1990, _, _, "Мосфильм")
// актёры, никогда не работавшие на МосФильме
АктНикогдаМосфильм(фио) <-- Актёр(i, фио, _) AND NOT ФА(н, г, i) AND Фильм(н, г, _, _, "Мосфильм")
// студия, снявшая более одного фильма
СтБольшеОдногоФильма(ст) <-- Фильм(н, г, _, _, ст) AND Фильм(н2, г2, _, _, ст) AND (н2 != н)
ДНФ
Если в запросе сочетаются И / ИЛИ / вложенные подзапросы, то используется дизъюнктивно-нормальная форма. Конъюнкт - это литералы (атом или атом с отрицанием), соединённые через И. Конъюнкты объединяются в правила.
Рекурсия
Надо, например, построить маршрут по городам:
Road(от, до, ц, тип)
// база рекурсии
Path(от, до) <-- Road(от, до, _, _)
// индукция рекурсии
Path(от, до) <-- Road(от, до, _, _)
Path(от, до) <-- Road(от, до1, _, _) AND Path(до1, до)
Рекурсия выполняется, пока есть изменения.
Виды рекурсии:
- правая рекурсивная форма - если рекурсивная часть справа;
- левая рекурсивная форма - если рекурсивная часть слева;
- нелинейная рекурсия - если вычисляемый предикат применяется в правиле несколько раз.
Изолированность рекурсии - чтобы её определить, строится граф рекурсии.