А.И. Выборнов, А.В. Дубанов
4
и фактов в БД. Результат не зависит от порядка правил в теле про-
граммы.
Отсюда Datalog, как язык запросов к БД, намного более удобен,
чем Prolog. Но из изложенного вытекает и относительный недостаток
языка Datalog: поиск всех фактов, удовлетворяющих запросу, требует
больших затрат времени. Таким образом, необходим эффективный
алгоритм вычисления программы на Datalog.
Методы вычисления программ на языке Datalog.
Теоретиче-
ские основы вычисления программ на Datalog разрабатывались с
1970-х годов. Они базируются на математической логике и логиче-
ском программировании. Возможны три основных метода вычисле-
ния программ на Datalog: метод резолюций (resolution), прямой вы-
вод (top-down evaluation) и обратный вывод (bottom-up evaluation).
Кратко рассмотрим принципы, достоинства и недостатки этих ме-
тодов.
Метод резолюций
получил наибольшее распространение в обла-
сти логического программирования. Данный метод позволяет дока-
зать, что некоторое утверждение ложно. Поясним метод резолюций
на примере. Пусть даны некоторая БД и запрос:
).
,( :?
Xap
−
Этому выражению соответствует дизъюнкт Хорна, записанный
вместе с квантором
∀
:
).
,(
XapX
¬∀
В методе резолюций предпринимается попытка опровержения это-
го утверждения путем генерации контрпримеров посредством поиска
таких
X
, для которых дизъюнкт Хорна
) ,(
Xap
¬
будет ложным. Так
будут получены все значения
X
, для которых дизъюнкт
) ,(
Xap
будет
истинным, эти же значения и станут ответом на запрос.
Метод резолюций используется в реализациях языка Prolog. Для
этого метода актуальна проблема останова, т. е. определения итера-
ции, после которой необходимо прекратить порождать контрприме-
ры. В Prolog-системах алгоритм резолюции может бесконечно по-
рождать контрпримеры. Задача своевременного останова при этом
возлагается на программиста. Предложен ряд решений данной зада-
чи. Наиболее полно и эффективно она решена в алгоритмах обратно-
го вывода [7].
Несмотря на то что метод резолюции предоставляет очень мощ-
ный способ вычисления логических программ, он не является прием-
лемым для языка Datalog, поскольку дает ответы на запросы по од-
ному, в то время как от него требуется получать все факты, удовле-
творяющие запросу.
