Алгоритмы обработки запросов к дедуктивным базам данных и реализация алгоритма
5
Прямой вывод
подразумевает последовательный вывод новых
фактов на основе правил, БД и ранее выведенных фактов. Данный
метод также называют методом вывода «снизу вверх» (восходящий
алгоритм).
Алгоритм прямого вывода достаточно прост и состоит в следую-
щем. Поместим все факты из БД в множество
F
, а все правила из
программы — в множество
R
. Пусть функция
) arg ,
(arg
2
1
getFacts
принимает два аргумента (
1
arg
— множество фактов,
2
arg
— прави-
ло) и возвращает множество фактов, которые можно получить из
2
arg
, используя факты из
1
arg
. Тогда с помощью псевдокода этот ал-
горитм можно записать так, как показано на рис. 1.
Рис. 1.
Псевдокод, поясняющий метод прямого вывода
Для получения необходимого ответа следует отфильтровать по-
лученное множество
F
по запросу.
Очевидно, что данный способ вычисления программы на Datalog
неэффективен, так как порождает множество фактов, которые не по-
требуются для ответа на запрос, и использует абсолютно все факты
из БД. Для повышения эффективности требуется сократить число
рассматриваемых фактов за счет тех, которые не нужны для вычис-
ления программы (нерелевантных фактов). Прямой вывод такого со-
кращения обеспечить не может.
Обратный вывод.
В отличие от прямого при обратном выводе
вычисление начинается с запроса. Метод состоит в построении дере-
ва доказательства для каждого ответа на запрос. В контексте обрат-
ного вывода под деревом доказательства понимают дерево, облада-
ющее следующими свойствами:
• узлы дерева представляют собой либо факт, либо правило, со-
держащееся в программе;
• если узел является правилом или фактом из БД, он не имеет ли-
стьев;
• если узел является не содержащимся в БД фактом, его листья
представляют собой такие правила и факты, что при условии истин-
ности фактов из правила будет следовать факт, записанный в этом
узле.
