Алгоритмы обработки запросов к дедуктивным базам данных и реализация алгоритма
7
го предиката. Это определение применяется рекурсивно: подзапрос
для подзапроса тоже является подзапросом.
Алгоритм QSQ использует два множества:
P
— множество отве-
тов и
Q
— множество текущих подзапросов. Множество
P
содер-
жит ответы как на главный запрос, так и на промежуточные подза-
просы, а множество
Q
— все рассматриваемые или уже рассмотрен-
ные к данному моменту запросы и подзапросы. На каждом шаге
алгоритм QSQ хранит состояние, представленное парой множеств:
P
и
Q
. Алгоритм генерирует новые ответы и новые подзапросы, под-
лежащие ответу. Алгоритм QSQ может быть реализован в двух вари-
антах — итеративном и рекурсивном.
Рекурсивный QSQ (QSQR)
отдает предпочтение обработке подза-
просов. При обнаружении нового подзапроса алгоритм рекурсивно
запускает этот подзапрос, а процесс отыскания ответов откладывает-
ся до того момента, к которому данный подзапрос будет уже полно-
стью обработан.
Итеративный QSQ (QSQI)
отдает предпочтение продуцирова-
нию ответов. При обнаружении нового подзапроса его выполнение
откладывается до тех пор, пока не будут порождены все возможные
факты, которые могли бы быть получены к данному моменту.
Далее будет рассмотрен QSQR, у которого на прикладных зада-
чах результат лучше, чем у QSQI. Для каждого правила, голова кото-
рого соответствует начальной цели, процесс вычисления начинается
при пустом
P
и
Q
, содержащем только начальный запрос. На каждом
шаге рекурсии множества
P
и
Q
дополняются.
Процесс завершается, когда не порождаются новые подзапросы и
новые ответы. На момент окончания работы алгоритма множество
P
будет содержать минимально необходимые факты, требуемые для
получения ответа на запрос. В свою очередь ответ может быть полу-
чен путем фильтрации множества
P
по запросу. Более подробное
изложение данного алгоритма можно найти в [7].
Как было отмечено выше, QSQ требует доступ только к мини-
мально необходимому числу фактов из БД и порождает только те
факты, которые требуются для вывода ответа на запрос. Все это поз-
воляет успешно применять QSQ при вычислении программ на
Datalog, работающих с большими объемами данных.
Прототип дедуктивной СУБД.
Аппаратное и программное обес-
печение.
Разработка и тестирование прототипа СУБД были осуществ-
лены на персональном компьютере с процессором Intel Core i7-3770K
(3,5 ГГц) и 16 Gb RAM под управлением операционной системы
Windows 7. Кроме того, были использованы компилятор JavaSE-1.7 и
библиотека sqLite JDBC 3.7.2 (для применения вспомогательной БД).
