А.И. Выборнов, А.В. Дубанов
12
из
P
, унифицируемые с
) ,(
Yap
:
)} ,({
bap
, получаем подстановку
{ / }
Y b
′θ =
. Обработка предиката
) ,(
Yap
завершена,
}} / {{
bY
list
=
.
Рассматриваем предикат
) , (
ZYp
. Применяя к нему подстановку
из
,
list
получаем предикат
) ,(
Zbp
. Данный предикат требует уточ-
нения, поэтому для него вызывается алгоритм QSQ. После выполне-
ния алгоритма имеем:
)} ,( ),
,({
ZbpXap Q
=
,
)} ,( ), ,({
cbpbap P
=
.
Теперь, получив все факты из
P
, унифицируемые с
)} ,({:) ,(
cbp Zbp
,
получаем подстановку
{ / , / }
Y b Z c
′θ =
. Обработка предиката оконче-
на,
}} / , / {{
cZbY
list
=
.
Обработка всех предикатов завершена. Применив подстановку из
list
к голове правила, получаем множество
),(
cap
, являющееся от-
ветом на запрос.
Интерфейс программирования приложений.
Прототип СУБД с
языком запросов Datalog был реализован в виде библиотеки на языке
Java. Для работы с этой библиотекой предоставляется API, который
включает набор классов, реализующих базовые структуры языка
Datalog (аргумент предиката, предикат, факт, правило, запрос), набор
классов для работы с программой на языке Datalog (включая контей-
нер для трех множеств — запросов, множество правил и фактов) и
собственно интерпретатор языка Datalog, включающий реализацию
рекурсивного алгоритма QSQ.
Результаты тестов
.
Предварительные тесты показали, что полу-
ченная реализация дедуктивной СУБД обладает приемлемой произво-
дительностью только в случаях, не порождающих глубокую рекурсию.
Тест с глубокой рекурсией, заключающийся в построении транзитивно-
го замыкания множества вида:
) ,
( ,
),
, ( ),
, (
1
3 2
2 1
n
n
a ap
aap aap
−
K
при
n
порядка 1000, требует времени, которое в рамках прикладного при-
менения можно считать бесконечным. Но при более простых запро-
сах, не подразумевающих глубокую рекурсию, алгоритм показал
приемлемое время работы, не превышающее 1 c на БД, содержащей
порядка 100 000 фактов.
Исходя из этих результатов, мы считаем нецелесообразным ис-
пользование Datalog в качестве основного языка запросов для работы
с БД больших объемов. Но, на наш взгляд, применение Datalog удоб-
но и оправдано как для запросов, не использующих глубокую рекур-
сию, так и для более сложных запросов к выборкам, предварительно
сделанным из реляционных БД традиционным способом.
Заключение.
Было показано, что Datalog вряд ли может быть ре-
комендован в качестве основного языка для работы с БД. В то же
время его использование целесообразно для некоторых типов запро-
сов. Таким образом, развитие дедуктивных СУБД с языком запросов
