Алгоритмы обработки запросов к дедуктивным базам данных и реализация алгоритма
УДК 004.047
Алгоритмы обработки запросов к дедуктивным базам
данных и реализация алгоритма QSQ
© А.И. Выборнов, А.В. Дубанов
МГТУ им. <...> Н.Э. Баумана, Москва, 105005, Россия
Рассмотрены существующие алгоритмы обработки запросов к дедуктивным базам данных, основанных на языке Datalog. <...> Наиболее эффективный из них — рекурсивный алгоритм «запрос-подзапрос» (QSQR) — реализован в составе прототипа
интерфейса программирования приложений. <...> Необходимой частью любой системы управления
базами данных (СУБД) является язык запросов к базе данных (БД). <...> В настоящее время наибольшее распространение получил «язык
структурированных запросов» (Structured Query Language — SQL),
который ориентирован на реляционную модель данных. <...> Применение дедуктивных языков определяется следующим обстоятельством: с помощью реляционных языков
очень сложно выразить любой рекурсивный запрос [2], такой как
транзитивное замыкание бинарного отношения. <...> Под транзитивным замыканием бинарного отношения R понимают наименьшее транзитивное отношение, включающее R [3]. <...> А.И. Выборнов, А.В. Дубанов
Здесь и далее: p — предикат, задающий отношение; X , Y и Z —
переменные. <...> Транзитивное замыкание бинарного отношения в запросах может
возникать при решении задач широкого круга предметных областей. <...> Существует ряд реализаций СУБД с дедуктивным языком запросов. <...> Большая их часть реализована в виде интерфейса программирования приложений (Application Programming Interface — API) для различных функциональных языков программирования общего назначения <...> Для языков, поддерживающих парадигму объектно-ориентированного программирования (Java, C++) и широко применяемых для
промышленной разработки приложений, существует небольшое число реализаций [5, 6]. <...> Таким образом, сохраняется актуальность СУБД с дедуктивным языком запросов, способных работать с большими объемами
данных с API на наиболее широко применяемых языках программирования <...>