А.И. Выборнов, А.В. Дубанов
2
Здесь и далее:
p
— предикат, задающий отношение;
X
,
Y
и
Z
—
переменные.
Транзитивное замыкание бинарного отношения в запросах может
возникать при решении задач широкого круга предметных областей.
Так, характерным примером является анализ молекулярных и реак-
ционных графов в био- и хемоинформатике.
Существует ряд реализаций СУБД с дедуктивным языком запро-
сов. Большая их часть реализована в виде интерфейса программиро-
вания приложений (Application Programming Interface — API) для раз-
личных функциональных языков программирования общего назначения
[4]. Для языков, поддерживающих парадигму объектно-ориентиро-
ванного программирования (Java, C++) и широко применяемых для
промышленной разработки приложений, существует небольшое чис-
ло реализаций [5, 6].
Таким образом, сохраняется актуальность СУБД с дедуктив-
ным языком запросов, способных работать с большими объемами
данных с API на наиболее широко применяемых языках програм-
мирования.
В данной работе авторами был реализован прототип СУБД с язы-
ком запросов Datalog и API на языке Java и выполнена оценка ее
применимости к большим объемам данных. Были рассмотрены суще-
ствующие алгоритмы вычисления программ на Datalog и выбран ал-
горитм, наиболее подходящий для реализации.
Язык Datalog.
Данный язык дедуктивных запросов является
подмножеством языка логического программирования Prolog. Одна-
ко программа на языке Datalog полностью декларативна, в то время
как программы на языке Prolog на практике имеют двойное значе-
ние — декларативное (логическое) и императивное (процедурное).
Программа на языке Prolog может определять порядок вычислений, в
то время как порядок вычислений в программе на языке Datalog
определяется реализацией последнего. Предикаты в Datalog могут
рассматриваться как чистые (значение предиката однозначно опреде-
ляется подстановкой переменных, вычисление значений не сопро-
вождается побочными эффектами). Поэтому в дальнейшем будем го-
ворить именно о
вычислении
программы, а не о ее
выполнении
. По-
скольку Datalog не получил широкого распространения в практике
программирования, рассмотрим его более подробно.
Факт в языке Datalog представляет собой предикат с множеством
аргументов (доменом), состоящим из констант. Факт, отображающий
отношение
p
от констант
a
и
b
, на языке Datalog записывается как
) ,(
bap
.
Факт является предикатом, значение которого всегда истинно.
