Алгоритмы обработки запросов к дедуктивным базам данных и реализация алгоритма
3
Предикаты
1
p
и
2
p
унифицируемы, если существует такая под-
становка ,
θ
что
1
2
p p
⋅ θ = ⋅ θ
(здесь запись
1
p
⋅ θ
означает подстанов-
ку фактических аргументов
θ
вместо формальных аргументов пре-
диката
p
). Например, предикат
) , ,(
bbap
унифицируем с предиката-
ми:
) , ,(
XXap
, так как существует подстановка
{ / }
X b
θ =
(здесь и
далее символ «
/
» обозначает подстановку), и
) , , (
ZYXp
— подста-
новка
{
}
/ , / , / .
X a Y b Z b
θ =
В свою очередь, предикат
) , ,(
bbap
не
унифицируем с предикатом
) , ,(
XXbp
.
Множество фактов являются БД. Факт языка Datalog можно рас-
сматривать как строку таблицы реляционной БД. Таким образом,
набор фактов можно представить набором реляционных таблиц.
Отношения между фактами задаются с помощью правил. Под
правилом понимают строку вида
голова
−
:
тело
. В качестве тела вы-
ступает набор предикатов с доменом из констант и переменных, а в
качестве головы — единственный предикат также с доменом из кон-
стант и переменных. При этом все переменные, присутствующие в
голове, должны использоваться в теле правила. Правило является
импликацией вида
тело
⇒
голова
и читается следующим образом:
голова правила истинна для всех тех наборов переменных, для кото-
рых истинен каждый предикат из тела правила. Например, правило
( , ) :
( , ), ( , )
p X Y p X Z p Z Y
−
.
задает транзитивное замыкание бинарного предиката
p
. Если факты
) ,(
bap
и
),(
cbp
— истинны, то на основе этого правила может быть
установлена истинность факта
),(
cap
. Таким образом, правила в
языке Datalog эквивалентны дизъюнктам Хорна — дизъюнкции пре-
дикатов с не более чем одним положительным предикатом. При этом
отрицательные литералы задают тело, а положительный — голову.
Соответственно, факт представляет собой дизъюнкт Хорна с един-
ственным положительным дизъюнктом. Запрос представляет собой
дизъюнкт Хорна с единственным отрицательным предикатом и зада-
ется с помощью единственного предиката с доменом из переменных
и констант. Результатом вычисления запроса является множество
фактов, унифицируемых с запросом. Например, запрос:
).
,( :?
Xap
−
вернет все факты, которые хранятся в БД либо выводятся из фактов
БД по правилам и которые унифицируемы с предикатом
) ,(
Xap
.
Программа на языке Datalog представляет собой набор правил и
запросов. Вычисление программы на языке Datalog сводится к выво-
ду фактов, унифицируемых с запросом, на основе правил программы
