ПБД (9) - Лекция №9 - Datalog: различия между версиями
ILobster (обсуждение | вклад) (Новая страница: «== Datalog == Язык логических запросов Database Logic. Основан на использовании предикатов. '''Преди...») |
ILobster (обсуждение | вклад) м (многие стрелки автозаменились на //, починил) |
||
Строка 20: | Строка 20: | ||
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
// в общем виде | // в общем виде | ||
заголовок < | заголовок <-- набор >= подцель AND подцель AND ... | ||
// конкретно | // конкретно | ||
ЧёрноБелыеФильмы(н,г,ст) | ЧёрноБелыеФильмы(н,г,ст) <-- Фильм (н, г, д, т, ст) AND т = "ч/б" | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Строка 38: | Строка 38: | ||
Согласованный набор - это когда одним и тем же переменным соответствуют одни и те же значения (результат выполнения естественного соединения): | Согласованный набор - это когда одним и тем же переменным соответствуют одни и те же значения (результат выполнения естественного соединения): | ||
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
АВФ(фио,н) < | АВФ(фио,н) <-- Актёр(i, фио, _) AND ФА(н, 1979, i) AND i > 1000 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Текущая версия от 16:56, 21 ноября 2012
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, до)
Рекурсия выполняется, пока есть изменения.
Виды рекурсии:
- правая рекурсивная форма - если рекурсивная часть справа;
- левая рекурсивная форма - если рекурсивная часть слева;
- нелинейная рекурсия - если вычисляемый предикат применяется в правиле несколько раз.
Изолированность рекурсии - чтобы её определить, строится граф рекурсии.