Алгоритмы обработки запросов к дедуктивным базам данных и реализация алгоритма
9
Пусть
list
— список подстановок, полученный при обработке по-
следнего предиката. Необходимо применить каждую подстановку из
list
к голове правила. Получим результат обработки правила, кото-
рый необходимо добавить к множеству
P
.
Во время обработки правила происходит вызов подзапросов.
В процессе формирования
i
ans
из
i
temp
возникает проблема в опре-
делении всех унифицируемых фактов для предикатов, требующих
уточнения. Именно для этих предикатов и запускается подзапрос.
В практической реализации алгоритма QSQ важным является по-
рядок обработки предикатов тела правила. Оптимальной считается
обработка предикатов тела правила в порядке убывания количества
констант [7], поэтому авторы выполняли сортировку предикатов тела
каждого правила перед вычислением.
Для того чтобы рассмотреть реализацию алгоритма QSQ в дета-
лях, введем некоторые дополнительные понятия.
Подстановку
1
θ
будем называть более общей по отношению к
2
θ
тогда и только тогда, когда существует подстановка ,
θ
такая что
1
2
.
θ ⋅ θ = θ
Наиболее общим унификатором двух предикатов будем
называть более общий по отношению ко всем остальным унифи-
катор.
В алгоритме QSQ выполняется проверка двух предикатов на
унифицируемость. Данную задачу мы решаем поиском наиболее об-
щего унификатора с помощью алгоритма
ifier
tGeneralUn
produceMos
[7], представленного ниже. В этом алгоритме функция
) (
p size
воз-
вращает количество аргументов в предикате
p
, функция
) (
p name
—
имя предиката
p
, a
i
p
обозначает
i
-й аргумент
p
. При успешном вы-
полнении возвращается наиболее общий унификатор, в противном
случае —
.
null
Данный алгоритм представлен на рис. 3.
В некоторых случаях в ходе выполнения этого алгоритма может
возникнуть ситуация, когда переменная в составе правила (например,
переменная
X
в правиле
) , ( :) , (
XYP YXp
−
) и переменная с тем же
именем в предикате (например, переменная
X
в факте
) ,(
Xap
)
имеют различное значение. Во избежание ошибок мы выполняем пе-
реименование всех переменных следующим образом: если перемен-
ная уже встречалась ранее в текущем предикате, правиле или запро-
се, ей назначается то же имя, что и при предыдущем появлении пе-
ременной с таким же именем. В противном случае для переменной
назначается имя, отличное от всех ранее употреблявшихся.
В алгоритме QSQ используются упомянутые выше множества
P
(множество ответов) и
Q
(множество текущих подзапросов), а также
функции, описанные ниже.
