маем из входного потока. В результате получается поток, состоящий только из тех кадров, в которых связывание для ?x не удовлетворяет (должность ?x (компьютеры программист)). Например, при обработке запроса

(and (начальник ?x ?y)

(not (должность ?x (компьютеры программист))))

первый подзапрос породит кадры со связанными значениями ?x и ?y. Затем выражение not отфильтрует этот поток, удалив все кадры, в которых значение ?x удовлетворяет ограничению, что ?x является программистом.70

Особая форма lisp-value реализуется при помощи подобного же фильтра для потоков кадров. При помощи каждого кадра из потока мы конкретизируем все переменные образца, а затем применяем лисповский предикат. Все кадры, для которых предикат оказывается ложным, мы удаляем из входного потока.

Унификация

Чтобы обрабатывать правила языка запросов, нам нужно уметь находить правила, в которых заключения соответствуют данному входному образцу. Заключения правил подобны утверждениям, но только в них могут содержаться переменные, так что нам требуется обобщенный вариант сопоставления с образцом, - называемый унификация (unification), - в котором как «образец», так и «данные» могут содержать переменные.

Унификатор берет два образца, в каждом из которых могут быть константы и переменные, и определяет, возможно ли присвоить переменным значения, которые сделают два образца одинаковыми. Если да, то он возвращает кадр, содержащий эти значения. Например, при унификации (?x a ?y) и (?y ?z a) получится кадр, в котором все три переменные ?x, ?y и ?z связаны со значением a. С другой стороны, унификация (?x ?y a) и (?x b ?y) потерпит неудачу, поскольку не имеется такого значения для ?y, которое бы сделало два образца одинаковыми. (Чтобы вторые элементы образцов оказались равными, ?y должно равняться b; однако, чтобы совпали третьи элементы, ?y обязан быть a.) Подобно сопоставителю, унификатор, используемый в системе запросов, принимает на входе кадр и проводит унификации, не противоречащие содержимому этого кадра.

Алгоритм унификации - самая технически сложная часть запросной системы. При наличии сложных образцов может показаться, что для унификации требуются дедуктивные способности. Например, чтобы унифицировать (?x ?x) и ((a ?y c) (a b ?z)) , алгоритм обязан вычислить, что ?x должен быть равен (a b c), ?y должен быть ?b, а ?z должен быть равен c. Можно считать, что этот процесс решает систему уравнений, описывающую компоненты образцов. В общем случае это будут взаимозависимые уравнения, для решения которых требуются существенные преобразования.71 К примеру, унификацию (?x ?x) и ((a ?y c) (a b ?z)) можно рассматривать как систему уравнений

?x = (a ?y c) ?x = (a b ?z)

70Существует тонкое различие между реализацией not в виде фильтра и значением отрицания в математической логике. См. раздел 4.4.3.

71В одностороннем сопоставлении с образцом все уравнения, которые содержат переменные, заданы явно и уже решены относительно неизвестного (переменной образца).

Из этих уравнений следует, что

(a ?y c) = (a b ?z)

а отсюда, в свою очередь, что

a = a, ?y = b, c = ?z

и, следовательно,

?x = (a b c)

При успешном сопоставлении с образцом все переменные оказываются связанными, и значения, с которыми они связаны, содержат только константы. Это верно и для всех примеров унификации, которые мы до сих пор рассмотрели. Однако в общем случае успешная унификация может не полностью определить значения переменных; какие-то переменные могут остаться неопределенными, а значения других сами могут содержать переменные.

Рассмотрим унификацию (?x a) и ((b ?y) ?z) . Можно вычислить, что ?x = (b ?y), а a = ?z, но ничего больше нельзя сказать о значениях ?x и ?y. Унификация заканчивается успешно, поскольку, естественно, можно сделать образцы одинаковыми, присвоив значения ?x и ?y. Поскольку сопоставление никак не ограничивает значение, которое может принимать переменная ?y, никакого ее значения не оказывается в кадре-результате. Однако результат ограничивает значение ?x. Какое бы значение не имела переменная ?y, ?x должен равняться (b ?y). Таким образом, в кадр помещается связывание ?x со значением (b ?y). Если позже значение ?y оказывается определенным (путем сопоставления с образцом или унификации, которая должна соответствовать этому кадру) и добавляется в кадр, значение, связанное с ?x, будет ссылаться

72

на него.72

Применение правил

Главной операцией в компоненте запросной системы, который производит логический вывод на основе правил, является унификация. Чтобы увидеть, как этот компонент работает, рассмотрим обработку запроса, содержащего обращение к правилу, например:

(живет-около ?x (Хакер Лиза П))

Обрабатывая этот запрос, сначала мы при помощи описанной ранее обыкновенной процедуры сопоставления смотрим, имеются ли в базе данных утверждения, которые сопоставляются с данным образцом. (В данном случае таковых не окажется, поскольку в нашей базе данных нет никаких прямых утверждений о том, кто около кого живет.) На следующем шаге мы пытаемся унифицировать образец-запрос с заключением каждого правила. Мы обнаруживаем, что образец унифицируется с заключением правила

72Можно считать, что унификация находит наиболее общий образец, который является специализацией двух входных образцов. А именно, унификация (?x a) и ((b ?y) ?z) равна ((b ?y) a), а унификация (?x a ?y) и (?y ?z a), описанная выше, равна (a a a). Однако в нашей реализации удобнее считать, что результатом унификации является не образец, а кадр.

(rule (живет-около ?person-1 ?person-2)

(and (адрес ?person-1 (?town . ?rest-1)) (адрес ?person-2 (?town . ?rest-2)) (not (same ?person-1 ?person-2))))

и получается кадр, в котором переменная ?person-2 связана со значением (Хакер Лиза П), а переменная ?x связана с (должна иметь то же значение, что и) ?person-1. Теперь по отношению к этому кадру мы вычисляем составной запрос, содержащийся в теле правила. Успешные сопоставления расширят кадр, сообщив значение переменной ?person-1, а соответственно, и ?x, которую мы можем использовать при конкретизации исходного образца-запроса.

В общем случае обработчик запросов при применении правила, когда он пытается распознать образец-запрос в кадре, который содержит связывания для некоторых переменных образца, использует следующий метод:

•Унифицировать запрос с заключением правила и получить (если унификация успешна) расширение исходного кадра.

•По отношению к расширенному кадру вычислить запрос, который является телом правила.

Обратите внимание, насколько это похоже на метод применения процедуры в интерпретаторе eval/apply для Лиспа:

•Связать параметры процедуры с ее аргументами и получить кадр, расширяющий исходное окружение процедуры.

•По отношению к расширенному окружению вычислить выражение, которое является телом процедуры.

Подобие двух вычислителей неудивительно. Точно так же, как в Лиспе средством абстракции являются определения процедур, в языке запросов средством абстракции являются определения правил. В каждом случае мы развертываем абстракцию, создавая соответствующие связывания и вычисляя тело правила либо процедуры по отношению к расширенной среде.

Простые запросы

В этом разделе мы уже рассматривали, как вычислять простые запросы при отсутствии правил. Теперь, разобравшись, как применяются правила, мы можем описать, как простые запросы вычисляются с помощью как правил, так и утверждений.

Получая запрос-образец и поток кадров, мы порождаем для каждого входного кадра два новых потока:

•поток расширенных кадров, получаемых сопоставлением образца со всеми утверждениями базы данных (при помощи сопоставителя), а также

•поток расширенных кадров, полученных применением всех возможных правил (при помощи унификатора).73

73 Поскольку унификация является обобщением сопоставления, можно было бы упростить систему и порождать оба потока с помощью унификатора. Однако обработка простого случая с помощью обычного сопоставителя показывает, как сопоставление (а не полноразмерная унификация) может само по себе быть полезным.