ПРОГРАММИРОВАНИЕ, 2011, No 3, с. 76-80
БАЗЫ ДАННЫХ И ЗНАНИЙ
УДК 004.822
МЕТОД УСКОРЕНИЯ ЛОГИЧЕСКОГО ВЫВОДА В ПРОДУКЦИОННОЙ МОДЕЛИ ЗНАНИЙ
© 2011 г. Р.С. Катериненко, И.А. Бессмертный Санкт-Петербургский государственный университет информационных технологий,
механики и оптики 197101 Санкт-Петербург, Кронверкский пр., 49 E-mail: igor_bessmertny@hotmail.com Поступила в редакцию 15.12.2010 г.
В статье рассматривается проблема комбинаторной сложности логического вывода в базах знаний, построенных на основе продукционной модели. Описывается метод логического вывода с помощью реляционной алгебры из фактов, размещенных в среде СУБД. Приводятся результаты экспериментов на тестовых базах знаний, демонстрирующие ускорение логического вывода.
1. ВВЕДЕНИЕ
Концепция Глобальной семантической сети (Semantic Web) разработана для автоматического поиска данных и предполагает хранение фактов в форме триплетов вида субъект-предикат-объект, а также правил для порождения новых фактов [1]. Таким образом, Semantic Web реализует продукционную модель знаний, доступ к которым сопряжен с комбинаторной сложностью задачи логического вывода. Для Semantic Web эта проблема усугубляется потенциально неограниченными объемами хранимых фактов и распределенным хранением на Интернет-ресурсах.
В продукционной модели знаний применяют две основные стратегии вычислений сверху-вниз" („top-down") и „снизу-вверх" ("bottom-up"). В работе Хинца [2] показано, что стратегия вычислений снизу-вверх имеет больше перспектив для применения оптимизаций, чем и обусловлен наш выбор в пользу данной стратегии для исследования методов ускорения логического вывода.
2. МОДЕЛЬ ЗНАНИЙ
В данной работе рассматривается классическая продукционная модель знаний со следующими свойствами и ограничениями:
• база знаний не может быть модифицирована в процессе логического вывода;
• запрещено использование рекурсивных продукций;
• вывод осуществляется на основе фактов, записанных в виде RDF-триплетов субъект-предикат-объект [3];
• для хранения фактов используется среда систем управления базами данных (СУБД), а для извлечения фактов - язык запросов SQL, как показано в работе [7].
Данные свойства позволяют работать со знаниями, представленными в Semantic Web, как с дедуктивной базой знаний и использовать все преимущества эффективной реализации современных СУБД. Возможно комбинирование SQL запроса с указанием цели для извлечения фактов из базы знаний. Например, следующее выражение:
SELECT * FROM Fathers f
WHERE f.name IN Goal [hasBrother(?x, ?y) AND
hasSister(?x, ?z) ][?x]
является запросом вывода всей информации об отцах (таблица ,, Fathers"), у которых есть братья и сестры. Далее будут рассмотрены две основные стратегии применения реляционной СУБД.
МЕТОД УСКОРЕНИЯ ЛОГИЧЕСКОГО ВЫВОДА
77
3. СТАТИЧЕСКАЯ БАЗА ЗНАНИЙ
В статической базе знаний логический вывод осуществляется на этапе создания базы знаний. Сначала должны быть загружены первичные факты и правила [3]. К первичным относятся такие факты, которые не могут быть выведены из других фактов. Например, для отношений родства первичными являются отношения родитель-ребенок и супруг-супруга. Все остальные отношения являются вторичными или производными. Затем ко всем первичным фактам последовательно применяется каждое правило. Каждый порожденный при этом факт добавляется в базу знаний. Так, путем перебора всех правил порождаются «вторичные», «третичные» и др. факты.
При выполнении пользовательского запроса к статической базе знаний логический вывод не требуется. Достаточно сделать селекцию фактов, удовлетворяющих условию запроса, как это делается в базах данных.
Недостатки этой модели очевидны:
• Невозможно изменять факты в базе знаний, поскольку ранее выведенные из них производные факты могут оказаться некорректными. При этом, как правило, производные факты в базе знаний никак не привязаны к первичным фактам, из которых они выведены, тем более что цепочка логического вывода может быть длинной. Таким образом, базу нельзя пополнить новыми знаниями и актуализировать ее состояние.
• Тот же недостаток относится и к правилам. Новое правило может вступать в конфликт с фактами, полученными путем применения других правил, что приводит к накоплению противоречий в базе знаний.
• Требуется постоянное хранение всех порожденных фактов, а их количество, как правило, бывает очень большим. Например, в родственных отношениях число первичных фактов - величина одного порядка с числом членов семьи, а число возможных отношений на порядок больше, так как в семье каждый член связан с каждым.
Даже при отсутствии логического вывода на этапе обработки пользовательского запроса, время ожидания может оказаться большим, поскольку требуется сделать операцию селекции к таблице, содержащей все выведенные факты.
Несмотря на очевидные недостатки, статическая база знаний может использоваться для хранения и быстрого извлечения знаний, не подверженных изменениям, аналогично тому, как запомненная таблица умножения однозначных чисел существенно ускоряет устный счет.
4. ДИНАМИЧЕСКАЯ БАЗА ЗНАНИЙ
Работа с динамической базой знаний состоит из следующих этапов:
• загрузка первичных фактов;
• загрузка продукций (правил);
• логический вывод при получении пользовательского запроса.
Все этапы могут чередоваться в любом порядке и повторяться любое число раз. Динамическая база знаний лишена недостатков, присущих статической базе знаний. Логический вывод может выполняться как «сверху-вниз» (от цели к фактам), так и «снизу-вверх» (от имеющихся фактов к цели). Вывод «сверху-вниз» при наличии вложенных вызовов правил приводит к очень длительному поиску на дереве решений; при этом не существует эффективных алгоритмов ускорения поиска. В этой связи чаще используется логический вывод «снизу-вверх», для которого гораздо проще применить методы ускорения вывода, подобные методам, предложенным в работах [6, 7, 8, 9].
Существенным недостатком, присущим всем стратегиям класса «снизу-вверх», является вывод избыточных фактов, не требующихся для ответа на запрос пользователя. Для уменьшения числа избыточных фактов предлагается использовать граф зависимости правил.
5. ГРАФ ЗАВИСИМОСТЕЙ ПРАВИЛ
Идея графа зависимостей правил очень проста, но позволяет существенно ограничить множество правил, которые необходимо
78
КАТЕРИНЕНКО, БЕССМЕРТНЫЙ
использовать для вывода фактов, удовлетворяющих пользовательскому запросу. Рассмотрим ее на примере. Пусть даны следующие правила, представленные в нотации языка Prolog:
r1 p(x) : —a(x), b(x).
r2 a(y): —a1(y), a2(y)
r3 c(z): —b1(z), a1(z).
r4 a1(t) —a2(t).
r5 a1(q) : —a3(q).
r6 b1(k) —g(k), h(k).
Для ответа на пользовательский запрос выдать все факты с предикатом р имеет смысл использовать только правила, в левых частях которых имеется искомый предикат. В данном случае это правило г1. Правило г1 выполняется при наличии фактов а и Ъ, удовлетворяющих условию из правой части правила г1. Необходимые факты могут быть найдены либо в базе знаний, либо после применения правила г2. Для правила г2 применяется та же самая процедура нахождения правил, которые порождают факты с предикатами из условия (антецедента) г2. Далее эта процедура рекурсивно применяется к найденным фактам, пока не будут просмотрены все правила. В результате для всех имеющихся в базе знаний правил получается граф правил (см. рис.):
• Каждой вершине графа соответствует правило.
• Два правила А и В называются зависимыми и между ними существует ребро, если выполняется хотя бы одно условие:
1. предикат из условия правила А совпадает с предикатом из следствия правила В;
2. предикат из следствия правила А совпадает с предикатом из условия правила В.
Информация в графе обновляется при изменении правил. В нашей модели при вставке очередного правила граф проверятся на ацикличность.
6. АЛГОРИТМ ВЫВОДА
Алгоритм вывода с использованием графа зависимости предикатов и правил состоит из следующих шагов:
• При добавлении факта происходит его вставка в базу знаний.
• При добавлении правила происходит обновление информации в графе зависимостей правил.
• При получении запроса пользователя происходит поиск необходимого подграфа правил. Это подграф задает множество, обладающее тем свойством, что оно содержит все необходимые правила для вычисления пользовательского запроса.
• По найденному подграфу генерируется SQL выражение. Продукции транслируются в запрос на языке SQL, который затем передается для выполнения в базу данных.
Например, рассмотрим поиск всех фактов с предикатом p в базе знаний из пункта 4. Для этого из графа зависимостей правил будет выбрано поддерево из четырех правил - r1, r2, r4, r5, обозначенное на рисунке полужирными линиями.
7. ГЕНЕРАЦИЯ SQL ЗАПРОСОВ
Каждому правилу предложенной модели вычислений можно сопоставить SQL выражение следующим образом.
• Каждый предикат b(x) определяет множество фактов S0 = {SELECT * FROM facts WHERE predicate LIKE 'b'};
• Если предикаты a1 и a2 задают конъюнкцию множеств фактов S1 и S2, то правило r2 : a(y) : — a1(y), a2(y) задает множество вида S = {SELECT*FROM S1 JOIN S2};
• Если правила
r4 : a1(t) : —a2(t), r5 : a1(t) : —a3(t)
задают дизъюнкцию множеств фактов S3 и S4, то они объединяются в одно множество фактов с предикатом a1: S1 = {SELECT * FROM S3 UNION S4}
• Если правила являются смежными вершинами в графе зависимостей продукций,
МЕТОД УСКОРЕНИЯ ЛОГИЧЕСКОГО ВЫВОДА
79
Рис. 1. Граф зависимости правил.
то используется вложенный SQL-запрос. Например, правило
r 1 : p(x) : — a(x), b(x)
зависит от r2, тогда, используя ранее заданные множества, получаем:
{SELECT * FROM S JOIN S0} = {SELECT * FROM
{SELECT * FROM S1 JOIN S2} JOIN S0}.
• Раскрывая S1, приходим к окончательному виду
{SELECT * FROM {SELECT * FROM
{SELECT * FROM S3 UNION S4} JOIN S2} JOIN S0}.
Аналогичное по структуре SQL-выражение передается для исполнения в СУБД. СУБД, используя различные техники, генерирует планы выполнения запросов и выбирает оптимальный вариант. Современные СУБД способны строить эффективные планы исполнения запросов и в случ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.