А.И. Выборнов, А.В. Дубанов
6
Задача обратного вывода состоит в построении таких деревьев
для каждого факта, являющегося ответом на запрос. Данная схема
реализуется с помощью деревьев поиска, отличающихся от дерева
доказательства следующим:
• вместо фактов используются предикаты, включающие и кон-
станты и переменные;
• во всех предикатах дерева переменные с одинаковыми именами
имеют одно и то же значение.
При обратном выводе корнем дерева является предикат запроса.
Он образует дерево поиска нулевой глубины. Для всех правил про-
граммы, голова которых унифицируема с корнем, подбираются такие
предикаты, чтобы при подстановке их в правило с головой, заданной
корневым узлом, получалось верное утверждение. В результате по-
лучаем несколько деревьев первого уровня. Аналогично обрабатыва-
ем все листья деревьев первого уровня, затем второго и т. д. Ввиду
бесконечности этого процесса используются различные условия
останова (как правило, динамические).
После того как будут порождены все необходимые деревья поис-
ка, в каждом из них необходимо заменить переменные в листьях на
факты из БД, что выполняется обходом дерева снизу вверх. Таким
образом, получаем деревья доказательства, содержащие ответ на за-
прос. В общем случае одному дереву поиска может соответствовать
несколько деревьев доказательства.
При реализации большинства алгоритмов обратного вывода по-
строение деревьев поиска и доказательства используется не явно.
Данный подход достаточно ресурсоемок, однако дает возмож-
ность сократить количество обращений к БД, а значит, и время вы-
числения результатов запроса. Наиболее эффективной реализацией
обратного вывода является
алгоритм QSQ
(Query-SubQuery — «за-
прос-подзапрос») [3].
Алгоритм QSQ представляет собой дальнейшее развитие алго-
ритма обратного вывода. Главными достоинствами алгоритма QSQ
являются обеспечение доступа к минимальному числу фактов из БД,
необходимых для ответа на запрос, и, соответственно, минимальное
количество обращений к БД. Рассмотрим этот алгоритм более по-
дробно.
При получении ответа на искомый запрос, а именно при обработ-
ке правил программы, в ней могут встретиться предикаты, требую-
щие уточнения. Они могут не только содержаться в БД, но и быть
выведены из правил программы. Для объяснения способа вычисле-
ния таких предикатов введем понятие подзапроса.
Подзапрос — запрос для конкретизации требующего уточнения
предиката в теле правила, заключающийся в запуске QSQ для данно-
