Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 96
Текст из файла (страница 96)
(В упражнении 4.69 можно найти правила, с помощьюкоторых выводятся более сложные родственные связи.)4.4.2. Как действует система обработки запросовВ разделе 4.4.4 мы представим реализацию интерпретатора запросов в виде наборапроцедур. В этом разделе дается обзор системы и объясняется ее общая структура,без низкоуровневых деталей реализации. После того, как мы опишем интерпретатор,нам легче будет понять его ограничения и некоторые тонкости, в которых логическиеоперации языка запросов отличаются от операций математической логики.Должно быть очевидно, что вычислителю запросов требуется какая-то разновидностьпоиска, чтобы сопоставлять запросы с фактами и правилами в базе данных.
Одним изспособов сделать это была бы реализация системы запросов в виде недетерминистскойпрограммы с использованием amb-интерпретатора из раздела 4.3 (см. упражнение 4.78).Другая возможность состоит в том, чтобы управлять поиском при помощи потоков. Нашареализация использует этот второй подход.Запросная система организована вокруг двух основных операций, которые называются сопоставление с образцом (pattern matching) и унификация (unification).
Сначаламы опишем сопоставление с образцом и объясним, как эта операция, вместе с организацией информации в виде потоков кадров, позволяет нам реализовывать как простые,так и составные запросы. Затем мы обсудим унификацию — обобщение сопоставленияс образцом, которое требуется для реализации правил. Наконец, мы покажем, как частиинтерпретатора связываются воедино процедурой, классифицирующей выражения, подобно тому, как eval разбирает выражения в интерпретаторе, описанном в разделе 4.1.Сопоставление с образцомСопоставитель (pattern matcher) — это программа, которая проверяет, соответствуетли некоторая структура данных указанному образцу.
Например, список ((a b) c (ab)) соответствует образцу (?x c ?x) при значении переменной ?x, равном (a b).Этот же список соответствует образцу (?x ?y ?z) при значениях переменных ?x и418Глава 4. Метаязыковая абстракция?z, равных (a b) и значении ?y, равном b. Однако он не соответствует образцу (?xa ?y), поскольку этот образец требует, чтобы вторым элементом списка был символ a.Сопоставитель, который используется в запросной системе, принимает на входе образец, структуру данных и кадр (frame), в котором указываются связывания для различных переменных образца. Он проверяет, соответствует ли структура данных образцубез противоречия со связываниями переменных, уже находящимися в кадре.
Если да, тосопоставитель возвращает кадр, дополнив его связываниями, определенными во времясопоставления. Если нет, он указывает, что сопоставление неудачно.Например, сопоставление образца (?x ?y ?x) со списком (a b a) при пустом начальном кадре вернет кадр, в котором переменная ?x связана со значением a, а ?y созначением b. Попытка сопоставления того же списка с тем же образцом при начальномкадре, в котором указывается, что ?y связывается с a, окажется неудачной.
Попыткасопоставления с теми же данными и образцом, при начальном кадре, в котором ?y связана со значением b, а ?x несвязана, вернет исходный кадр, дополненный связываниемa для ?x.Сопоставитель — единственный механизм, необходимый для обработки простых образцов, не содержащих правил. Например, чтобы обработать запрос:(должность ?x (компьютеры программист))— мы просматриваем все утверждения в базе данных и выбираем те, которые соответствуют образцу при пустом начальном кадре. Для каждого найденного утверждения мыподставляем в образец значение ?x из кадра, полученного при сопоставлении.Потоки кадровПроверка образцов по отношению к кадрам организована посредством потоков. Получив кадр, процесс сопоставления просматривает элементы базы данных один за другим.Для каждого входа базы данных сопоставитель порождает либо специальный символ,указывающий, что сопоставление оказалось неудачным, либо расширение кадра.
Из результатов сопоставления всей базы данных собирается поток, и этот поток пропускаетсячерез фильтр, отбрасывающий неудачи. Получается поток всех кадров, которые расширяют данный кадр за счет сопоставления с каким-либо утверждением из базы67 .В нашей системе запрос принимает входной поток кадров и для каждого кадра применяет вышеописанную операцию сопоставления, как показано на рис. 4.4. А именно,для каждого кадра во входном потоке запрос генерирует новый поток, содержащий всерасширения этого кадра, порожденные сопоставлением с утверждениями из базы.
Затемвсе эти потоки собираются в один громадный поток, который содержит все возможныерасширения всех кадров входного потока. Этот поток и есть результат запроса.67 Поскольку сопоставление — в общем случае весьма дорогая операция, нам хотелось бы избежать применения полного сопоставителя к каждому элементу базы данных. Обычное решение этой проблемы — разбитьпроцесс на грубое (быстрое) сопоставление и окончательное сопоставление. Грубое сопоставление отфильтровывает базу и находит кандидатуры на окончательное сопоставление. Если действовать аккуратно, можнопостроить базу данных таким образом, что часть работы грубого сопоставителя проделывается при построениибазы, а не в момент отбора кандидатов.
Это называется индексированием (indexing) базы данных. Существует множество приемов и схем индексирования баз данных. Наша реализация, которую мы описываемразделе 4.4.4, содержит простейший вариант такой оптимизации.4.4. Логическое программированиевходной потоккадров419запросвыходной поток кадров,отфильтрованный и расширенный(job ?x ?y)поток утвержденийиз базы данныхРис. 4.4. Запрос обрабатывает поток кадроввходной потоккадров(and A B)Aвыходной потоккадровBбаза данныхРис. 4.5. Комбинация двух запросов через and осуществляется последовательной обработкой потока кадров.Чтобы ответить на простой запрос, мы применяем его к потоку, который состоитиз одного пустого кадра.
Поток на выходе содержит все расширения пустого кадра (тоесть, все ответы на наш запрос). Затем на основе этого потока кадров создается потоккопий исходного образца запроса, в которых переменные конкретизированы значениямииз всех кадров, и этот поток в конце концов печатается.Составные запросыИзящество реализации с потоками кадров по-настоящему проявляется при работес составными запросами. При обработке составных запросов мы пользуемся тем, чтонаш сопоставитель умеет требовать, чтобы сопоставление не противоречило указанномукадру. Например, чтобы обработать and от двух запросов, скажем,(and (может-замещать ?x (компьютеры программист стажер))(должность ?person ?x))(неформально, «найти всех сотрудников, способных выполнять работу программистастажера»), сначала мы находим все записи базы, отвечающие образцу(может-замещать ?x (компьютеры программист стажер))Глава 4.
Метаязыковая абстракция420(or A B)входнойпотоккадровAслияниевыходнойпотоккадровBбаза данныхРис. 4.6. Комбинация двух запросов через or осуществляется путем параллельной обработки потока кадров и слияния результатов.Получается поток кадров, каждый из которых содержит связывание для ?x. Затем длявсех кадров этого потока мы находим записи, соответствующие образцу(должность ?person ?x)таким образом, чтобы не менять уже известное связывание переменной ?x. Каждоеновое сопоставление породит кадр, в котором будут содержаться связывания для ?x и?person. And от двух запросов можно рассматривать как последовательное применениедвух составляющих запросов, как показано на рис. 4.5. Кадры, прошедшие через первыйзапрос, фильтруются и расширяются вторым запросом.На рисунке 4.6 показан аналогичный метод для вычисления or от двух запросовчерез параллельное выполнение двух составляющих запросов.
Каждый запрос отдельнорасширяет входной поток кадров. Затем два получившихся потока сливаются и образуютокончательный поток-результат.Даже из этого высокоуровневого описания ясно, что обработка составных запросовможет занимать много времени. Например, поскольку запрос может породить более одного выходного кадра для каждого входного, а каждый подзапрос в and принимаетвходные кадры от предыдущего подзапроса, в наихудшем случае число сопоставлений,которые должен произвести запрос and, растет экспоненциально с числом подзапросов(см. упражнение 4.76)68 .
Несмотря на то, что системы для обработки простых запросов вполне могут быть практически полезны, обработка сложных запросов чрезвычайнотрудоемка69 .68 Впрочем, такой экспоненциальный взрыв в запросах and происходит редко, поскольку, как правило, дополнительные условия не увеличивают, а уменьшают число порождаемых кадров.69 Имеется обширная литература по системам управления базами данных, в которой основной темой являетсяэффективная обработка сложных запросов.4.4.
Логическое программирование421С точки зрения потока кадров, запрос not работает как фильтр, уничтожающий всекадры, для которых его подзапрос можно удовлетворить. Например, имея образец(not (должность ?x (компьютеры программист)))мы для каждого кадра во входном потоке пытаемся породить расширенные кадры, которые удовлетворяют образцу (должность ?x (компьютеры программист)). Всекадры, для которых такие расширения существуют, мы изымаем из входного потока.В результате получается поток, состоящий только из тех кадров, в которых связываниедля ?x не удовлетворяет (должность ?x (компьютеры программист)). Например,при обработке запроса(and (начальник ?x ?y)(not (должность ?x (компьютеры программист))))первый подзапрос породит кадры со связанными значениями ?x и ?y.
Затем выражениеnot отфильтрует этот поток, удалив все кадры, в которых значение ?x удовлетворяетограничению, что ?x является программистом70.Особая форма lisp-value реализуется при помощи подобного же фильтра для потоков кадров. При помощи каждого кадра из потока мы конкретизируем все переменныеобразца, а затем применяем лисповский предикат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
