Алгоритмы обработки запросов к дедуктивным базам данных и реализация алгоритма
1
УДК 004.047
Алгоритмы обработки запросов к дедуктивным базам
данных и реализация алгоритма QSQ
© А.И. Выборнов, А.В. Дубанов
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Рассмотрены существующие алгоритмы обработки запросов к дедуктивным ба-
зам данных, основанных на языке Datalog. Наиболее эффективный из них — рекур-
сивный алгоритм «запрос-подзапрос» (QSQR) — реализован в составе прототипа
интерфейса программирования приложений.
Ключевые слова:
база данных, Datalog, алгоритм QSQ, дерево доказательства.
Введение.
Необходимой частью любой системы управления
базами данных (СУБД) является язык запросов к базе данных (БД).
В настоящее время наибольшее распространение получил «язык
структурированных запросов» (Structured Query Language — SQL),
который ориентирован на реляционную модель данных. Однако
существуют языки запросов к БД, работающие в терминах матема-
тической логики. Подобные языки часто называют дедуктивными.
Запрос к БД, сформулированный на таком языке, часто оказывает-
ся более кратким и понятным по сравнению с запросом на языке
SQL.
Наиболее распространенным дедуктивным языком запросов яв-
ляется Datalog. Язык удобен для описания отношений наследования,
семантических сетей и иных моделей из различных предметных об-
ластей, где наиболее выразительным способом представления дан-
ных является граф [1]. Применение дедуктивных языков определяет-
ся следующим обстоятельством: с помощью реляционных языков
очень сложно выразить любой рекурсивный запрос [2], такой как
транзитивное замыкание бинарного отношения.
Бинарное отношение — отношение двух переменных
( , )
R a b
.
Данное отношение называют транзитивным, если для любых трех
элементов
a
,
b
и
c
выполнение отношений
) ,(
baR
и
),(
cbR
влечет
выполнение отношения
),(
caR
. Под транзитивным замыканием би-
нарного отношения
R
понимают наименьшее транзитивное отноше-
ние, включающее
R
[3]. На языке Datalog такой запрос может быть
записан следующим образом:
). , ( ), , ( :) , (
YZpZXp YXp
−
