Сопоставитель, который используется в запросной системе, принимает на входе образец, структуру данных и кадр (frame), в котором указываются связывания для различных переменных образца. Он проверяет, соответствует ли структура данных образцу без противоречия со связываниями переменных, уже находящимися в кадре. Если да, то сопоставитель возвращает кадр, дополнив его связываниями, определенными во время сопоставления. Если нет, он указывает, что сопоставление неудачно.

Например, сопоставление образца (?x ?y ?x) со списком (aba) при пустом начальном кадре вернет кадр, в котором переменная ?x связана со значением a, а ?y со значением b. Попытка сопоставления того же списка с тем же образцом при начальном кадре, в котором указывается, что ?y связывается с a, окажется неудачной. Попытка сопоставления с теми же данными и образцом, при начальном кадре, в котором ?y связана со значением b, а ?x несвязана, вернет исходный кадр, дополненный связыванием a для ?x.

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

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

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

Потоки кадров

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

В нашей системе запрос принимает входной поток кадров и для каждого кадра применяет вышеописанную операцию сопоставления, как показано на рис. 4.4. А именно, для каждого кадра во входном потоке запрос генерирует новый поток, содержащий все расширения этого кадра, порожденные сопоставлением с утверждениями из базы. Затем все эти потоки собираются в один громадный поток, который содержит все возможные расширения всех кадров входного потока. Этот поток и есть результат запроса.

Чтобы ответить на простой запрос, мы применяем его к потоку, который состоит из одного пустого кадра. Поток на выходе содержит все расширения

67Поскольку сопоставление - в общем случае весьма дорогая операция, нам хотелось бы избежать применения полного сопоставителя к каждому элементу базы данных. Обычное решение этой проблемы - разбить процесс на грубое (быстрое) сопоставление и окончательное сопоставление. Грубое сопоставление отфильтровывает базу и находит кандидатуры на окончательное сопоставление. Если действовать аккуратно, можно построить базу данных таким образом, что часть работы грубого сопоставителя проделывается при построении базы, а не в момент отбора кандидатов. Это называется индексированием (indexing) базы данных. Существует множество приемов и схем индексирования баз данных. Наша реализация, которую мы описываем разделе 4.4.4, содержит простейший вариант такой оптимизации.

поток утверждений из базы данных

Рис. 4.4: Запрос обрабатывает поток кадров

входной поток кадров

выходной поток кадров

база данных

Рис. 4.5: Комбинация двух запросов через and осуществляется последовательной обработкой потока кадров.

пустого кадра (то есть, все ответы на наш запрос). Затем на основе этого потока кадров создается поток копий исходного образца запроса, в которых переменные конкретизированы значениями из всех кадров, и этот поток в конце концов печатается.

Составные запросы

Изящество реализации с потоками кадров по-настоящему проявляется при работе с составными запросами. При обработке составных запросов мы пользуемся тем, что наш сопоставитель умеет требовать, чтобы сопоставление не противоречило указанному кадру. Например, чтобы обработать and от двух запросов, скажем,

(and (может-замещать ?x (компьютеры программист стажер)) (должность ?person ?x))

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

(может-замещать ?x (компьютеры программист стажер))

Получается поток кадров, каждый из которых содержит связывание для ?x. Затем для всех кадров этого потока мы находим записи, соответствующие образцу

(должность ?person ?x)

входной

поток

кадров

выходной

поток

кадров

база данных

Рис. 4.6: Комбинация двух запросов через or осуществляется лельной обработки потока кадров и слияния результатов.

путем парал-

таким образом, чтобы не менять уже известное связывание переменной ?x. Каждое новое сопоставление породит кадр, в котором будут содержаться связывания для ?x и ?person. And от двух запросов можно рассматривать как последовательное применение двух составляющих запросов, как показано на рис. 4.5. Кадры, прошедшие через первый запрос, фильтруются и расширяются вторым запросом.

На рисунке 4.6 показан аналогичный метод для вычисления or от двух запросов через параллельное выполнение двух составляющих запросов. Каждый запрос отдельно расширяет входной поток кадров. Затем два получившихся потока сливаются и образуют окончательный поток-результат.

Даже из этого высокоуровневого описания ясно, что обработка составных запросов может занимать много времени. Например, поскольку запрос может породить более одного выходного кадра для каждого входного, а каждый подзапрос в and принимает входные кадры от предыдущего подзапроса, в наихудшем случае число сопоставлений, которые должен произвести запрос and, растет экспоненциально с числом подзапросов (см. упражнение 4.76).68 Несмотря на то, что системы для обработки простых запросов вполне могут быть практически полезны, обработка сложных запросов чрезвычайно трудоемка.69

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

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

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

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

69Имеется обширная литература по системам управления базами данных, в которой основной темой является эффективная обработка сложных запросов.