ПБД (9) - Лекция №9 - Datalog

Datalog

Язык логических запросов Database Logic. Основан на использовании предикатов.

Предикат - функция, принимающая аргументы, возвращает true или false. Аргументы могут быть константы или переменные.

Атом - предикат, с подставленными в него аргументами. Атомы бывают:

• реляционные - на основе отношений БД, совпадают с названиями таблиц;
• арифметические - операция сравнения двух арифметических выражений.

Количество и последовательность аргументом должны совпадать абсолютно.

// реляционный предикат
Actor("123", "Иванов", "высшее") // если есть такой актёр, то вернёт true, иначе false

Для создания запроса используются правила "если ... то":

// в общем виде
заголовок <-- набор >= подцель AND подцель AND ...
 
// конкретно
ЧёрноБелыеФильмы(н,г,ст) <-- Фильм (н, г, д, т, ст) AND т = "ч/б"

Есть анонимные переменные - не используются для выполнения сравнения и получения результата. Ставятся на место обычных переменных, заменяя их знаком подчёркивания: "_".

Правила

Вычисление правил:

1. определение кортежей из реляционный подцелей без отрицания;
2. получение согласованного набора кортежей;
3. для согласованного набора проверяются все подцели;
4. для истинных подцелей формируем результат.

Согласованный набор - это когда одним и тем же переменным соответствуют одни и те же значения (результат выполнения естественного соединения):

АВФ(фио,н) <-- Актёр(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, до)

Рекурсия выполняется, пока есть изменения.

Виды рекурсии:

• правая рекурсивная форма - если рекурсивная часть справа;
• левая рекурсивная форма - если рекурсивная часть слева;
• нелинейная рекурсия - если вычисляемый предикат применяется в правиле несколько раз.

Изолированность рекурсии - чтобы её определить, строится граф рекурсии.