Средства и методы ускорения дедуктивного вывода в информационных системах с большим объемом данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Катериненко, Роман Сергеевич

• Катериненко, Роман Сергеевич
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Катериненко, Роман Сергеевич

СОДЕРЖАНИЕ

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ,

СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ

ВВЕДЕНИЕ

1 Анализ дедуктивного вывода методом

«снизу вверх»

1.1 Актуальность исследования дедуктивного вывода

1.2 Основные определения

1.3 Анализ основных принципов, особенностей и тенденций

в области дедуктивных систем

1.4 Анализ теоретических основ метода «снизу вверх» —

Теорема Эрбрана

1.5 Анализ подходов к реализации дедуктивного вывода

методом «снизу вверх»

1.6 Анализ алгоритма Rete

1.7 Выводы

2 Применение бинарных диаграмм решений для

ускорения дедуктивного вывода

2.1 Анализ применимости бинарных диаграмм решений для дедуктивного вывода

2.2 Разработка общей стратегии применения

бинарных диаграмм решений

2.3 Разработка характеристической функции отношения

с применением булевых операций

2.4 Анализ операций над бинарными диаграммами решений

для дедуктивного вывода

2.5 Анализ сложности операций над бинарными диаграммами решений для дедуктивного вывода

2.6 Разработка бинарной диаграммы решений для отношения

2.7 Разработка бинарной диаграммы решений для дизъюнкта

2.7.1 Назначение доменов переменным

2.7.2 Переименование переменных в теле правила

2.7.3 Построение бинарной диаграммы решений для

тела правила

2.7.4 Построение бинарной диаграммы решений для

головы правила

2.8 Выводы

3 Разработка метода верификации систем отслеживания задач и его применение для экспериментального исследования

производительности дедуктивного вывода

3.1 Анализ актуальности верификации систем отслеживания задач

3.2 Постановка задачи верификации систем отслеживания задач

3.3 Основные обозначения

3.4 Построение дедуктивной модели для верификации

систем отслеживания задач

3.5 Разработка алгоритма верификации систем отслеживания задач

3.6 Реализация алгоритма в виде программного приложения

3.7 Постановка эксперимента исследования

производительности дедуктивного вывода

3.8 Проведение экспериментального исследования

производительности дедуктивного вывода

з

3.9 Выводы

63

4 Применение модели вертикальных баз данных для ускорения

дедуктивного вывода

4.1 Анализ применимости вертикальных баз данных для дедуктивного вывода

4.2 Применение модели вертикальных баз данных для ускорения дедуктивного вывода

4.3 Экспериментальное исследование дедуктивного вывода на основе

баз данных с вертикальной архитектурой

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ

ДИССЕРТАЦИИ

ЛИТЕРАТУРА

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ

Бинарная диаграмма решений — представление булевой функции / = (xi, Х2,

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

Q.

Вертикальная база данных (Column-oriented data base) — база данных, в основе архитектуры которой лежит постолбцовый способ хранения данных и организации таблиц (в русскоязычной литературе известна как «колоночная» база данных).

Голова правила — часть правила, соответствующая заключению импликации.

Граф зависимости предикатов — ориентированный граф, вершинами ко-

торого являются предикаты интенсиональной базы данных, а дуга от произвольной вершины Ni к вершине iV2 проводится в том случае, если предикат Ni зависит от предиката Л^.

Дедуктивные базы данных — информационные системы, сочетающие методы логического программирования и баз данных. Основным методом вывода является дедуктивный вывод.

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

Интенсиональная база данных — часть базы данных, состоящая из правил. Литерал — в логике предикатов формула вида Р{х) или ->Р(х), где Р — предикатный символ.

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

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

Предикатный символ — символьное обозначение предиката. Например, для одноместного Р(х) предикатным символом является «Р».

Пример предиката — в русскоязычной литературе — атомарная формула с

этим предикатом (например, Р(1 + 3) — пример предиката Р). Продукционная модель — модель, основанная на правилах, позволяющая представить знание в виде предложений вида «если А , то В», что означает: если выполняется условие А, то верно заключение В. Под В может подразумеваться некоторое действие.

Разделенная переменная — в логике предикатов — переменная, которая встречается в нескольких литералах дизъюнкта.

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

Система управления бизнес-правилами (СУБП) — информационная система, используемая для ведения, поддержки и исполнения бизнес-правил компании.

Словарь столбцов — структура данных в вертикальной базе данных. Тикет — в данной работе — атомарная единица представления информации в системе отслеживания задач.

Тело правила — часть правила, соответствующая условию импликации. Факт — в данной работе и в области экспертных систем — минимальная единица информации, соответствующая атомарной формуле логики предикатов. Формула общезначима — в логике предикатов первого порядка — формула ф, истинная на модели Л4, что обозначается как Л4 |= ф. Если М. \=3 ф для всех подстановок в, то такая формула общезначима.

Формула выполнима — в логике предикатов первого порядка формула ф истинная на модели Л4, что обозначается как Л4 (= ф. Если ЗЛЛ\Л4 |=5 ф, то формула ф выполнима.

Экстенсиональная база данных — часть базы данных, состоящая из фактов.

Введение диссертации (часть автореферата) на тему «Средства и методы ускорения дедуктивного вывода в информационных системах с большим объемом данных»

ВВЕДЕНИЕ

Актуальность темы. В последнее время все шире применяются интеллектуальные системы на основе дедуктивного вывода, такие как экспертные системы, нашедшие применение в областях от медицины до финансов, системы поддержки принятия решений, системы управления сложными технологическими объектами, системы научного моделирования. Важным компонентом таких систем, скорость которого напрямую влияет на общую скорость работы, является машина логического вывода. По принципу действия машины логического вывода могут быть разделены на два больших класса: использующие метод «снизу вверх» и использующие метод «сверху вниз». Метод «снизу вверх» обладает рядом преимуществ, но отмечается недостаток — в процессе работы генерируется большой объем вспомогательных данных, что приводит к снижению скорости работы и увеличению потребления памяти. При этом отчетливо прослеживаются две тенденции, которые делают скорость вывода краеугольным камнем, — это постоянное увеличение объема обрабатываемых данных и стремление к анализу в режиме реального времени. Кроме того, с ростом количества обрабатываемых данных также растут и требования к точности и времени обработки. На фоне этого исследователи дедуктивного вывода методом «снизу вверх» отмечают, что современные машины вывода характеризуются либо недостаточной скоростью работы, либо колоссальным потреблением памяти, поэтому ускорение дедуктивного вывода на базах данных большого объема является актуальной задачей и позволит расширить область применения и повысить качество систем, использующих дедуктивный вывод.

Областью исследования являются модели и методы разработки программных средств обработки данных и знаний в вычислительных машинах, комплексах, сетях, а также программные средства для машин логического вывода.

Объектом исследования являются системы дедуктивного вывода, сочетающие в себе методы баз данных для хранения данных и методы логического

программирования для выполнения логических запросов. Чаще всего такие системы используются в качестве основного элемента экспертных систем и систем верификации.

Предметом исследования являются процесс дедуктивного вывода в модели дизъюнктов методом «снизу вверх» и связанные с ним вопросы хранения отношений, ускорения дедуктивного вывода, уменьшения объема генерации промежуточных данных.

Цель и задачи исследования. Целью диссертационной работы является сокращение затрат вычислительных ресурсов (памяти и процессорного времени) при дедуктивном выводе на большом объеме данных. Для достижения этой цели были поставлены и решены следующие задачи:

1. Анализ результатов, полученных по основным направлениям исследований ускорения дедуктивного вывода методом «снизу вверх», с целью выявления особенностей и принципов построения алгоритмов;

2. Разработка и исследование алгоритма дедуктивного вывода на основе бинарных диаграмм решений;

3. Экспериментальное исследование производительности дедуктивного вывода на задаче с практической сложностью;

4. Разработка алгоритма дедуктивного вывода на основе модели баз данных с вертикальной архитектурой.

Научная новизна работы.

1. Разработан алгоритм представления произвольного отношения в виде бинарной диаграммы решения, обладающий линейной сложностью от количества кортежей в отношении;

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

3. Впервые предложен метод верификации систем отслеживания задач с помощью дедуктивного вывода.

Основные положения, выносимые на защиту:

1. Алгоритм преобразования произвольного отношения в бинарную диаграмму решений;

2. Алгоритм дедуктивного вывода с применением бинарных диаграмм решений;

3. Метод верификации систем отслеживания задач с помощью дедуктивного вывода;

4. Метод дедуктивного вывода на основе модели баз данных с вертикальной архитектурой.

Практическая значимость. Основные результаты работы внедрены в проведенном в НИУ ИТМО НИР №610481 «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем с распределенной архитектурой» кафедры ВТ. Разработанное программное обеспечение для верификации систем отслеживания задач внедрено в производственный процесс «ООО Система—Сервис».

Степень достоверности и апробация результатов исследования. Система на основе разработанного алгоритма дедуктивного вывода получила диплом конкурса научно-исследовательских проектов студентов и аспирантов НИУ ИТМО «The Big Bang — 2» (2013 г.). Основные положения диссертационной работы представлялись и обсуждались на 13-ти международных и всероссийских конференциях: «Майоровские чтения» (2009 г., Санкт-Петербург); XLVIII Международная научная студенческая конференция «Студент и научно-технический прогресс» (2010 г., Новосибирск); 12th IACEE World Conference On Continuing Engineering Education (2010 г., Сингапур); Всероссийская конференция «Управление знаниями и технологиями Semantic-Web» (2010 г., Санкт-Петербург); VII Всероссийская конференция Молодых Ученых (2010 г., Санкт-

Петербург); XXXIX научная и учебно-методическая конференция СПбГУ

ю

ИТМО (2010 г., Санкт-Петербург); VIII Всероссийская межвузовская конференция Молодых Ученых (2011 г., Санкт-Петербург); Конгресс по интеллектуальным системам и информационным технологиям (2011 г., Дивноморское); Международная конференция KMSW-2011 «Управление знаниями и технологии Semantic Web» (2011 г., Санкт-Петербург); IX Всероссийская межвузовская конференции Молодых Ученых (2012 г., Санкт-Петербург); Международная научно-практическая конференция «Инженерия знаний и технологии Semantic Weh» (2012 г., Санкт-Петербург); бая Российская мультиконферен-ция по проблемам управления. Конференция «Информационные технологии в управлении» (2012 г., Санкт-Петербург); XLII Научная и учебно-методическая конференция (2013 г., Санкт-Петербург).

Теоретическую и методологическую основу исследования составляют методы системного анализа; математические и формально-логические методы; метод сравнений; методы структурного анализа; методы математического моделирования; методы объектно-ориентированного программирования, анализа и проектирования; методы функционального программирования, а также общенаучные методы.

Публикации. Результаты диссертационной работы были представлены в 17-ти публикациях: одной монографии, 13 научных статьях, в том числе 3 статьи в журналах из списка периодических изданий, рекомендованных ВАК, 1 статья в международном журнале на английском языке, а также в сборниках трудов конференций.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка. Общий объем диссертации 90 страниц. Библиография включает 91 наименование. Работа содержит 26 иллюстраций и 4 таблицы.

1 Анализ дедуктивного вывода методом «снизу вверх»

1.1 Актуальность исследования дедуктивного вывода

В наши дни мы имеем возможность наблюдать огромную скорость компьютеризации всех областей жизнедеятельности человека. Вычислительная техника становится эффективнее, надежнее, миниатюрнее и, как следствие, проникает во все новые области быта и производства. Это способствует увеличению доли интеллектуальных и адаптивных систем, использующих ту или иную разновидность логического вывода, таких как экспертные системы, системы поддержки принятия решений, системы диагностики, системы поддержки проектирования и т.д.[1, 2, 3, 4] Технологии «Semantic Web» и технологии, использующие «(9Ж£-онтлоггш»(формализованное описание предметной области на основе языка OWL), постулируют в качестве одного из своих методов логический вывод. При этом рост числа потребителей логического вывода происходит на фоне хорошо заметной общемировой тенденции увеличения количества данных в цифровом виде, пригодных для осуществления логического вывода. Сама по себе задача логического вывода характеризуется большой алгоритмической сложностью, поэтому, в контексте вышеуказанных тенденций, становится актуальным снижение ресурсоемкости дедуктивного вывода на базах данных больших объемов. Достижению этой цели посвящена данная диссертационная работа.

Анализ современных систем дедуктивного вывода показывает, что они либо не способны обрабатывать большой объем данных (миллионы атомарных формул), либо потребляют колоссальное количество памяти в процессе работы. На Рисунке 1.1 приведен график времени вывода и времени загрузки данных

для хорошо известной в университетских кругах системы DES при различном количестве исходных атомарных формул. Из графика видно, что система не способна осуществлять вывод, когда количество формул превосходит 46000, и загружать более 185000 формул. Более совершенная и широко распространенная система Jess на основе алгоритма Rete справляется с таким объемом данных, но затрачивает при этом колоссальный объем памяти, как показано на Рисунке 1.2. Быстрый рост занимаемой оперативной памяти приводит к невозможности осуществлять вывод на средних персональных компьютерах, имеющихся в лабораториях ученых.

Рис. 1.1: Время дедуктивного вывода DES Рис. 1.2: Объем занимаемой оперативной памяти

Косвенно об актуальности выбранной темы свидетельствует рост числа публикаций по специфичным ключевым словам. На Рисунке 1.3 представлены графики количества публикаций в авторитетной системе ScienceDirect по ключевым словам «D eduction »(дедукция), «Deductive systems »(дедуктивная система), «1Ш1)»(бинарные диаграммы решений). Хорошо заметно, что в области, выделенной серым прямоугольником, соответствующей 2010-2012 годам, наблюдается резкий прирост числа публикаций. Также из графика видно увеличение интереса к бинарным диаграммам решений (Binary Decision Diagram,

BDD). Автором на основе этой модели был разработан алгоритм дедуктивного

13

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

2000 1800 1600

*

ь 1400 х

X

2 1200 х с

о >•

О 1000

ю у

| 800

о *

600 400 200

1994 1996 1998 2000 2002 2004 2006 2008 2010 2012 Года

Рис 1 3 Количество публикаций в системе БаепсеБиес!

1.2 Основные определения

Введем основные необходимые определения. Существует много разновидностей логического вывода, основными являются дедуктивный, индуктивный и абдуктивный выводы [5, 6]. В данной работе рассматривается только дедуктивный вывод. Модель такого вывода состоит из множества аксиом, множества правил вывода и логического запроса — некоторой формулы, истинность или ложность которой требуется определить в контексте данных аксиом.

В данной работе под аксиомой имеется в виду дизъюнкт — формула логики предикатов первого порядка вида

\/аГь ..., хп(^А1(х\)Ч,..., М^Ак{хк) V Ак+1(^+1)V,..., \/Ап(хп)),

где А(х) — атомарная формула. Воспользовавшись известной формулой раскрытия импликации А —>• В -¡А V В, преобразуем вышеуказанный литерал в импликацию:

А\(х1)Л,..., 1\Ак(хк) —> Ак+\{хк+\)У • • •, У А

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

Аш(х^+1)У,..., VAn{xn) <- Ai(ifi)A,..., ЛАк(хк)

или в более простой общепринятой записи, заменяя логические операции запятыми:

Ak+1(xk+i),.. .,Ап(хп) <- Ai(fl),.. .,Ак(хк).

Если правая часть правила {тело) пустая, то такую формулу будем называть фактом. Формулу с пустой левой частью (головой) будем называть логическим запросом, по аналогии с терминологией баз данных. Множество правил принято называть Интенсиональной базой данных, ИБД (Intensional Data Base, IDB), a множество фактов или атомарных формул — Экстенсиональной базой данных, ЭБД (Extensional Data Base, EDB).

1.3 Анализ основных принципов, особенностей и тенденций в области дедуктивных систем

Первыми успешно применяемыми дедуктивными системами принято называть семейство систем OPS (0PS4, OPS5, OPS83), разработанных группой университета Carnegie Mellon в главе с С. Forgy [7, 8] в конце 1970 годов. Эти системы успешно применялись в качестве экспертных систем и уже тогда использовали метод «снизу вверх» и алгоритм Rete [9]. Усовершенствованные алгоритмы Rete II и Rete III встроены в систему CLIPS, используемую и по сей день для создания экспертных систем различного назначения. Алгоритм Rete II превосходит своего предшественника по скорости работы в 50-100 раз. Скорость работы Rete III такая же, как у Rete II. Алгоритм Rete является одним из самых быстрых и поэтому был выбран в качестве сравнительного образца для экспериментального исследования ресурсоемкости предлагаемого в работе алгоритма. Проведение сравнительного эксперимента изложено в пункте 3.8.

Интересен тот факт, что С. Forgy со своей группой после разработки алгоритма Rete стали работать в направлении распараллеливания вывода, а не

15

разработки новых моделей. В процессе работы в этом направлении был сделан ряд публикаций [10, 11, 12, 12, 13, 14].

Анализируя историю развития дедуктивных систем, можно выделить еще одну особенность — соотношение количества атомарных формул и правил всегда произвольное. Наряду с системами, содержащими десятки атомарных формул и тысячи правил, существуют системы, содержащие миллионы атомарных формул и десятки правил [15]. Соотношение объема ИБД и ЭБД является особенностью, присущей предметной области, в которой эксплуатируется система дедуктивного вывода. Несмотря на вариативность этого соотношения, хорошо прослеживается тенденция увеличения суммарного объема данных [16]. Этому способствует развитие технологий, использующих дедуктивный вывод как основное средство: Semantic Web и системы управления бизнес-правилами

Система управления бизнес-правилами (СУБП) — информационная система, используемая для ведения, поддержки и исполнения бизнес-правил компании. Согласно информации журнала InfoWorld, на сегодняшний день средним объемом для таких систем является 20000-30000 правил, а максимальным — 100000 правил и миллионы фактов. Справиться с таким объемом данных под силу немногим системам, что объясняет небольшое количество фирм-производителей подобного программного обеспечения: Oracle, Sun, Red Hat.

Существует еще феномен дедуктивных систем, основанных на правилах, созданных с нуля для нужд конкретной предметной области. Примеров подобных систем существует большое множество для различных отраслей: для биржевой торговли [17, 18], для компьютерного зрения [19], для сенсорных сетей [20], для анализа программ [21], для туризма [22], для добывающей промышленности [23], для образования [24], для банковской сферы [25], для систем поддержки принятия решений [26], для вэба [27].

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

или модифицироваться. Этому направлению посвящено большое количество современных статей, например [28, 29, 30, 31, 32].

Другой тенденцией, оказавшей сильное влияние на способы реализации дедуктивного вывода методом «снизу вверх», является появление дедуктивных баз данных (ДБД). ДБД — это информационные системы, сочетающие методы логического программирования и баз данных. На заре развития реляционных баз данных параллельно с ними развивались дедуктивные базы данных [33], но последние оказались менее востребованными в то время. ДБД являются комбинированными системами — они способны осуществлять дедуктивный вывод методом «снизу вверх» и выполнять реляционные операции, в том числе и над результатом вывода. Дедуктивные, как и реляционные, БД обладают транзак-ционностью [34]. Важным преимуществом ДБД по сравнению с ранними реляционными базами является возможность рекурсивных запросов, которую ДБД унаследовали от систем логического программирования [35, 36]. Благодаря такой взаимосвязи дедуктивных систем и реляционных БД, были разработаны методы дедуктивного вывода с помощью трансляции правил в реляционные запросы [37, 38, 39] и алгоритмы Magic Sets [40, 41].

В 70-ых годах D. Maier был разработан язык для дедуктивных систем, названный Datalog. Datalog в своем классе систем занимает такое же важное место, как SQL в области баз данных — большинство систем базируется на его синтаксисе, но существуют и такие, которые используют совсем иной синтаксис. Несмотря на то, что со дня его создания прошло не одно десятилетие, появляются новые системы, совершенствующие вычисление Datalog или добавляющие новые возможности, например, поддержку темпоральных типов данных или параллельное вычисление. Также не являются редкостью современные публикации с Datalog в заглавии. Здесь приведены основные публикации, использовавшиеся для изучения Datalog [42, 43, 44, 45, 46].

Среди современных публикаций по Datalog появляются исследования, посвященные повышению производительности вывода. В статье [47] .предлагается использовать стандартный для Datalog алгоритм Query-Sub-Query(QSВQ) [48,

49], но оптимизированный для работы с жестким диском. В статьях [50, 51, 52] предлагается другой способ ускорения на основе таблиц и динамического программирования.

Рассмотрим основные свойства языка Datalog, оказавшие сильное влияние на развитие дедуктивных систем, в частности на те из них, которые используют вычисления методом «снизу вверх». Некоторые хорошо известные современные базы данных используют идеи и алгоритмы, разработанные для Datalog. Например, в стандарт SQL-99 добавлена поддержка рекурсивных запросов, а алгоритм Magic Set, изначально разработанный для ускорения вычисления запросов в Datalog, реализован в DB2 от IBM.

Datalog является декларативным языком программирования. Его синтаксис представляет собой подмножество синтаксиса языка логического программирования Prolog. Основные отличия Datalog от Prolog: команды могут быть записаны в любом порядке, он не содержит оператор «cut» и гарантируется завершение вычисления программы. Кроме того, Datalog отличается от Prolog тем, что:

1. Запрещены сложные термы в качестве аргументов предикатов, например, Р(/(1),2,3);

2. Наложены ограничения на использование отрицания и рекурсии;

3. Требуется, чтобы всякая переменная из головы дизъюнкта встречалась хотя бы в одном положительном литерале тела дизъюнкта;

4. Требуется, чтобы всякая переменная, встречающаяся в отрицательном литерале в теле дизъюнкта, также встречалась и в некотором положительном литерале в теле дизъюнкта.

Эти свойства делают Datalog по-настоящему декларативным языком программирования. Хрестоматийным примером простой программы на Datalog является следующая, состоящая из двух команд, определяющих два интуитивно понятных факта:

parent(Tom, Bob).

18

parent(Tom, Kate).

и двух правил:

ancestor(X, Y) : —parent(X,Y).

ancestor(X, Y) : —parent{X, Z), ancestor(Z, Y).

Эти два правила определяют понятие «предок» через понятие «родитель». Ниже приведен запрос в синтаксисе Datalog, вычисляющий всех предков для терма «Тот»:

? — ancestor {Bill, X).

Исчерпывающее перечисление созданных дедуктивных систем и их свойств выходит за пределы данного пункта. Более подробно этот вопрос изложен в [53, 54, 55]. Целью данного пункта является выявление в исторической перспективе тенденций, основных методов и идей в области дедуктивных систем, оказывающих влияние на современные разработки. С этой целью были выделены основные классы алгоритмов для реализации дедуктивного вывода методом «снизу вверх»:

1. Семейство алгоритмов Rete;

2. Алгоритмы на основе трансляции в реляционную алгебру;

3. Модификации алгоритма Magic Set;

4. Прочие алгоритмы.

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

19

большое количество работ посвященных, визуальному представлению дедуктивных систем. Это дает пользователю возможность самостоятельно анализировать правила. Таким образом, можно считать, что основной объем заключен в атомарных формулах. Кроме того, было выявлено сильное влияние идей и алгоритмов, реализованных в Ба1ак^, на современные дедуктивные системы. В следующем пункте указанные методы будут подробно проанализированы с целью поиска подходов к решению поставленных в диссертации задач.

1.4 Анализ теоретических основ метода «снизу вверх» —

Теорема Эрбрана

Метод «снизу вверх» — это общее название алгоритмов, принцип которых заключается в генерации всевозможных логических моделей и последующем поиске среди них модели, выполняющей заданную формулу (удовлетворяющей логическому запросу). Формальным основанием для этого метода является процедура Эрбрана, заключающаяся в построении Эрбрановской интерпретации. Согласно теореме Эрбрана, Ух\,... , хпР(х\,... ,хп) выполнима тогда и только тогда, когда ее выполняет Эрбрановская интерпретация. Эта теорема позволяет свести поиск интерпретации, выполняющей формулу, к Эрбрановским интерпретациям. Для определения этого понятия необходимо ввести понятия Эрбрановской базы и Эрбрановского универсума.

Пусть Но — множество констант, появляющихся во множестве дизъюнктов 5. Нг+\ = Нг и {/"(¿1,¿2, • • • 5 ¿п)Ь гДе /п ~ все ^-местные функциональные символы, встречающиеся во множестве Б, а ¿1, ¿2,..., £п ~ элементы множества Н(. Тогда Н = Яоо называют универсумом Эрбрана для Б. Например, пусть Я={Р(/(а))У<ЗМа,у)),},тогда:

Щ = а,

#1 = а,/(а), Н2 = а, /(а), д(а, а),д(а, /(а)),

Множество атомарных формул вида Рп(Ь 1,^2, • • •, ¿п)> где Рп — все п-местные предикатные символы из множества 5 и ¿1, ¿2, • • •, ¿п — элементы универсума Эрбрана, называется Эрбрановской базой для Б. Эрбрановская интерпретация на универсуме Эрбрана называется отображением для множества дизъюнктов 5, если выполнены следующие соответствия:

1. Каждому предикатному символу Рп соответствует некоторое п-местное отношение в Н;

2. Каждому функциональному символу /п соответствует некоторая п-местная функция в Н (т. е. функция, отображающая Нп в Н);

3. Каждой предметной константе а,{ из 5 соответствует некоторая константа из Н (т. е. все константы отображаются на самих себя).

Из приведенных выше теоретических основ метода «снизу вверх» следует корректность этого метода и свойство генерации избыточных данных при поиске Эрбрановской интерпретации. Для борьбы с этой особенностью метода «снизу вверх» в данной работе будут разработаны эффективные алгоритмы.

1.5 Анализ подходов к реализации дедуктивного вывода

методом «снизу вверх»

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

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

Я: —В.

Графом зависимости предикатов (ГЗП) называют ориентированный граф, вершинами которого являются предикаты ИБД, а дуга от произвольной вершины

N1 к вершине N2 проводится в том случае, если предикат N1 зависит от предиката N2 [56, 57, 58]. Например, для множества правил

Н : — В\, В2

Вг : -<21

можно построить граф зависимости предикатов, изображенный на Рисунке 1.4. Вычисление множества правил (программы) с такой структурой выполняется по следующему алгоритму:

1. Для каждого предиката Р, взятого в топологическом порядке, заданном ГЗП, выполнить все правила, в которых Р встречается в голове;

2. Взять объединение атомарных формул, полученных от каждого правила;

3. Удалить формулы-дубликаты.

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

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

2. Поскольку ЭБД содержит конечное число формул, то вычисления завершатся через конечное число шагов;

3. Полученное множество является наименьшей моделью.

Описанный метод итерации также известен как «наивное вычисление» благодаря своей простоте и неэффективности. Однако этот метод можно значительно улучшить, воспользовавшись соображением, что для того чтобы получить

22

новые формулы на текущей итерации, нужно использовать только формулы, полученные на предыдущей итерации, а не на более ранних. Улучшенный метод носит название Полунаиваная итерация (Seminaive iteration). В этом алгоритме для каждого предиката Р хранятся два множества формулу и Ар. Последнее содержит только формулы, появившиеся на ближайшем шаге итерации. Алгоритм может быть записан так:

1. Для каждого предиката из ИБД инициализировать соответствующее ему множество р, выполнив только те правила, в теле которых нет предикатов из ЭБД;

2. Для каждого предиката положить Ар = р;

3. В цикле для каждого предиката Р из ИБД:

(a) Посчитать Ар, выполнив правила для Р, взяв для одного предиката из головы правила Д-множество, а для остальных — просто множество. Перебрать все возможные комбинации множеств и Д-множеств;

(b) Удалить из Ар формулы, встречающиеся в р\

(c) р = р U Ар;

4. Повторять шаг 3, пока меняются Д-множества.

В случае наличия отрицательных литералов дедуктивный вывод может не закончить свою работу. Неразрешимость может быть выявлена при анализе правил до начала вывода — если отрицательный литерал участвует в рекурсии, то метод итерации до фиксированной точки может не закончить свою работу. Для вычисления таких программ в ГЗП вводятся помеченные дуги. Если дуга ведет в некоторый предикат с отрицанием, то такая дуга помечается. Например, для следующего множества правил

Н : —В\. В2

В\ : — Ql

В2 : -Qi, Q2

23

Рис. 1.4: Граф зависимости пре- Рис. 1.5: Граф зависимости пре-

дикатов дикатов с отрицанием

ГЗП приведен на Рисунке 1.5.

Используя ГЗП с помеченными дугами, можно определить, являются ли правила вычислимыми. Если ответ положительный, множество правил разбивается на слои (Stratification) алгоритмом:

1. Инициализировать массив stratum[H] = 1;

2. Для каждого правила с предикатом H из головы выполнить следующие шаги;

3. Для каждого отрицательного литерала с предикатом В из тела правила

stratum[H] = Max(stratum[H], stratum[B] + 1);

4. Для каждого положительного литерала с предикатом В из тела правила

stratum[H] = Max(stratum[H], stratum[B])\

5. Вычислить maxstratum = Max(VHstratum[H]);

6. Если maxstratum не превосходит количество предикатов и номер слоя поменялся в текущей итерации, то перейти в пункт 2.

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

Выделим основные свойства метода итерации до неподвижной точки:

24

1. Является базовым для большого числа алгоритмов;

2. Является итеративным, а не рекурсивным;

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

Метод итерации до неподвижной точки оптимизируется в двух направлениях — ускорение каждой отдельно взятой итерации и снижение генерации количества формул, не нужных для ответа на логический запрос. Для решения первой задачи применяется трансляция правил в операции реляционной алгебры для запросов к реляционным базам данных. Выигрыш достигается за счет эффективного исполнения запросов современными СУБД. Для решения второй задачи разработан алгоритм Magic sets [59]. За счет переписывания исходных правил и добавления специальных предикатов, не содержащихся ни в ЭБД, ни в ИБД, этот метод позволяет уменьшить количество избыточных формул до сопоставимого с методом «снизу вверх».

Особняком стоят алгоритмы семейства Rete : Rete, Rete II, Rete III. Они не используют идею итерации до неподвижной точки. Вместо этого происходит построение сети, в узлах которой находятся формулы, являющиеся промежуточным решением. Для ответа на логический запрос требуется совершить обход сети и собрать промежуточные решения. Эти алгоритмы являются очень быстрыми, но отличаются огромными затратами памяти.

1.6 Анализ алгоритма Rete

Алгоритм Rete обычно обсуждается в терминах фактов, правил и шаблонов [60, 61, 62, 63, 64]. Фактом называется атомарная формула, правилом называется утверждение вида импликации, а шаблоном — формула со свободными переменными. Соответственно, тело правила может рассматриваться как набор шаблонов. Как и разработанный автором алгоритм дедуктивного вывода на основе вертикальных баз данных, описанный в последней главе, алгоритм Rete базируется на эмпирических закономерностях:

1. При срабатывании некоторого правила изменяется лишь несколько фактов, и это может повлиять лишь на несколько других правил;

2. Обычно один и тот же шаблон встречается в теле нескольких правил.

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

Узлы графа бывают трех видов (Рисунок 1.6):

1. Корневой узел, не имеющий входных дуг;

2. Узел с шаблоном с одной входной дугой;

3. Узел соединения (Join) с двумя входными дугами.

Каждому предикату сопоставляется свой узел, который выбирает из всех входных атомарных формул только формулы, соответствующие предикату. Каждый такой узел связан с узлами-шаблонами с таким же предикатом. Граф Rete формируется по следующему принципу. Для каждого правила вида:

Н В\ Л i?2, • • •, вп

для каждого Bi создается узел с шаблоном, называемый а-узлом. Для каждого а-узла создается отношение, куда записываются кортежи, соответствующие шаблону в узле. Таким образом, для каждого литерала^ будет создан аг-узел. Все вместе а-узлы образуют так называемую a-память (ск-Метогу). Каждой операции конъюнкции сопоставляется узел соединения, для которого создается отдельное отношение, содержащее кортежи, полученные применением операции соединения соответствующих отношений изо-узлов. Такие узлы называются (3-узлами, а соответствующая им память — ^-памятью (/^-Memory). За последним

/3-узлом следует а-узел с шаблоном из Н. На Рисунке 1.7 изображен граф для

26

правила

Н Bi Л В2 Л В3.

Рис. 1.6: Виды узлов в графе алгоритма Rete

В1 В2 ВЗ

-ж Соединение

Рис. 1.7: Пример графа Rete

Анализируя алгоритм, можно предположить большое потребление памяти из-за многократного дублирования кортежей в узлах графа. Для количественной оценки потребляемой памяти был проведен эксперимент, в котором измерялся максимальный объем оперативной памяти для системы Jess, реализующей алгоритм Rete. Результаты эксперимента, приведенные на Рисунке 1.8, подтверждают гипотезу о быстром росте потребляемой памяти алгоритмов типа Rete на базах данных большого объема. Следовательно, этот подход не может быть использован для достижения цели данной диссертационной работы.

370 1482 2963 5926 11852

Количество атомарных формул (тыс очи штук)

Рис. 1.8: Объем занимаемой оперативной памяти 27

1.7 Выводы

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

1. Простота и ясность основной единицы — правила;

2. Независимость правил и, как следствие, легкость модификации модели;

3. Строгость, простота и изученность механизма дедуктивного вывода;

4. Эффективность дедуктивного вывода. Недостатки:

1. Малая степень структурированности базы знаний;

2. Порождение большого объема избыточных данных при дедукции.

Проанализированы теоретические основы метода «снизу вверх», откуда следует присущее этому методу свойство — генерация большого числа избыточных формул. Несмотря на это свойство, вычисления не могут зациклиться в отличие от метода «сверху вниз». Проанализированы основные подходы к реализации дедуктивного вывода, в числе которых алгоритм Rete, методы итерации до неподвижной точки. Основываясь на приведенном анализе, сформулированы основные способы решения задач данной диссертационной работы:

1. Оптимизация хранения атомарных формул;

2. Повышение скорости сходимости итерации до неподвижной точки и уменьшение генерации избыточных атомарных формул;

3. Увеличение скорости выполнения операций итерации.

2 Применение бинарных диаграмм решений для ускорения дедуктивного вывода

Специфика дедуктивного вывода методом «снизу вверх» {«bottom-up») в сравнении с методом «сверху вниз» заключается в генерации огромного количества промежуточных данных [33]. Это свойство, следующее из описанной ранее процедуры построения Эрбрановской базы, лежит в основе предлагаемого метода. При увеличении объема исходных данных объем генерируемых данных растет экспоненциально, из-за чего увеличиваются время работы дедуктивного вывода и потребляемая память. Для улучшения этих характеристик автором разработан алгоритм дедуктивного вывода с применением бинарных диаграмм решений («Binary Decision Diagrams», «BDD»).

2.1 Анализ применимости бинарных диаграмм решений для дедуктивного вывода

Бинарная диаграмма решений (БДР) является представлением булевой функции / = (х\, Х2, •■■хп) от п переменных в виде ориентированного графа, состоящего из внутренних узлов решений (помеченных хг) и терминальных узлов, каждый из которых имеет по два потомка (помеченных 0 и 1). Терминальные узлы соответствуют одному из двух значений булевой функции. Каждый внутренний узел решений на уровне г имеет левого и правого потомка. Переход от узла хг к левому или правому потомку выполняется в зависимости от значения переменной хг (0 или 1 соответственно). Для заданных значений Х\,Х2, ...хп путь от корневого узла до 1-терминального узла соответствует тому факту, что на этих входных значениях булева функция / = (x\, Х2, ■■■хп) принимает значение 1.

Чаще всего под бинарной диаграммой решений понимают редуцированную

упорядоченную диаграмму решений [65]. Свойство упорядоченности подразумевает выбранный фиксированный порядок переменных-решений при движении от корня к терминальным узлам по любым направлениям. Редуцированной диаграмма становится после применения операции редукции:

1. Узлы, оба потомка которых являются одним и тем же узлом, должны быть удалены;

2. Изоморфные подграфы должны быть объединены.

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

Основной идеей для создания БДР послужило разложение Шеннона: /(х) = хг Л/|а;г=1 VЛ/|Хг=0- Пользуясь разложением Шеннона, любую булеву функцию можно разделить на две подфункции, называемые положительным и отрицательным дополнением, с меньшим на 1 количеством переменных. Затем из них выбирается только одна подфункция в зависимости от значения переменной, по которой выполнялось разложение. Представляя каждую такую подфункцию в виде поддерева и продолжая разложение по оставшимся входным переменным, можно получить бинарную диаграмму решений.

Разложение Шеннона для произвольной булевой функции/(х) с помощью г/-йеп-е/5е оператора [66, 67, 68] выглядит следующим образом:

х /о) Л = (я Л /1) V (~>х Л /о), (2.1)

где х - переменная, по которой производится разложение, /1 = /(1,х2)

/о = /(О, Х2, ...,£«). В качестве примера приведен Рисунок 2.1, где изображена

БДР для булевой функции

/(¿) = (iiVi2)A(i3Vi4), (2.2)

построенная по операторному разложению, которое приведено ниже.

/ = xi -> /о, Л /о = Х2 —»• /оо, /о1

/1 = —/lO, /и

/оо = ^3 /ооо, /ooi

/oi ^3 —/ою, /он

/lu = х3 /юо, /loi

/11 = ж3 —>• /по, /ш

/ооо = -> 0,0

/ooi = х4 0,0

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Катериненко, Роман Сергеевич

4.4 Выводы

При использовании СУБД для дедуктивного вывода происходит генерация запросов, особенностью которых является большое количество операций соединения по равенству и операций объединения. В основном, в запросах используется обращение только к небольшому количеству атрибутов. Для эффективного использования этих особенностей является целесообразным использование вертикальной базы данных вместо традиционной стороко-ориентированной БД. Преимущество заключается в эффективной реализации требуемых операций, исключающих считывание нерелевантных столбцов и оптимизации занимаемого объема хранилища. На сравнительных экспериментах система, использующая вертикальную базу данных, продемонстрировала лучшее время при значительно меньшем потреблении памяти, но СУБД Oracle llg предоставляет большие возможности по оптимизации. Этими средствами можно значительно улучшить производительность, но при этом будет затрачена память на дополнительные структуры. Следовательно, можно говорить о преимуществе в скорости вывода вертикальной базы данных для дедуктивного вывода, если обе СУБД взяты с настройками по умолчанию. Объем занимаемой память в случае вертикальной базы данных будет всегда меньше.

74

ЗАКЛЮЧЕНИЕ

В заключении приведены основные результаты работы:

1. Разработан алгоритм трансляции произвольного отношения в бинарную диаграмму решений за время, линейно зависящее от количества кортежей в отношении. При таком подходе достигается компактность представления отношения;

2. Разработан алгоритм дедуктивного вывода на больших базах данных с помощью бинарных диаграмм решений, который подходит для логической модели, состоящей из произвольных дизъюнктов, а не только из Хорнов-ских. При работе алгоритма занимаемый объем памяти меньше в среднем на 20 % по сравнению с BDDBDDB — другой реализацией дедуктивной системы на основе бинарных диаграмм решений, и на порядок меньше по сравнению с Jess — реализацией алгоритма Rete. Скорость дедуктивного вывода выше в среднем на 19 %, чем BDDBDDB, и на порядок, чем у Jess. В дополнение, в отличие от других дедуктивных систем, предложенный подход на основе бинарных диаграмм решений позволяет подсчитать количество кортежей, удовлетворяющих логическому запросу, не находя сами кортежи, что позволяет сократить время работы;

3. Реализован алгоритм дедуктивного вывода с применением вертикальных баз данных, демонстрирующий в 2-12 раз меньшее потребление памяти при большей в 1.3 раза скорости вывода по сравнению с системой, реализованной на реляционной базе данных;

4. Разработан метод верификации данных в системах отслеживания задач с помощью дедуктивного вывода. Используемая для этого модель дизъюнктов позволяет формулировать сложные ограничения на данные, в том числе рекурсивные правила. Созданная система подходит для широкого круга систем отслеживания задач и позволяет легко формулировать правила в декларативном стиле.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Катериненко, P.C. Верификация данных в системах отслеживания задач с помощью продукционных правил / P.C. Катериненко, И.А. Бессмертный // Научно-технический вестник информационных технологий, механики и оптики. - 2013. Т.83, К0-1. - С. 86-90.

2. Катериненко, P.C. Эффективный логический вывод в продукционной модели с помощью баз данных с вертикальной архитектурой /P.C. Катериненко // Научно-технический вестник информационных технологий, механики и оптики. - 2012. - Т.77, №1. - С. 58-62.

3. Катериненко, P.C. Метод ускорения логического вывода в продукционной модели знаний / P.C. Катериненко, H.A. Бессмертный // Программирование. - М., 2011. - Вып. 4. - С. 76-80.

В англоязычных журналах:

1. Katerinenko, R.S. Inference accélération in production model of knowledge / R.S. Katerinenko, I.A. Bessmertniy // Programming and Computer Software. - 2011. - Vol.42, № 4. - P. 197-199.

В монографии:

1. Катериненко, P.C. Дедуктивные базы данных / Катериненко P.C.

Saarbrucken: LAP Lambert Academic Publishing GmbH Co. KG, 2012. - 63 P

В других изданиях:

1. Катериненко, P.C. Верификация информационного наполнения систем управления проектами с помощью продукционных правил / P.C. Катериненко.

77

И.А. Бессмертный // Информационные технологии в управлении : сборник трудов бой Российской мультиконференции по проблемам управления, Санкт-Петербург, 9-11 окт. 2012.

2. Пичугин, Н. Разработка онтологического описания технических индикаторов / Н. Пичугин, И.А. Бессмертный, P.C. Катериненко // KESW-2012 "Инженерия знаний и технологии Semantic Web": сборник трудов Всероссийской конференции, Санкт-Петербург, 2012.

3. Катериненко, P.C. Верификация информационного наполнения систем отслеживания дефектов с помощью продукций / P.C. Катериненко, И.А. Бессмертный, Н. Пичугин // KESW-2012 "Инженерия знаний и технологии Semantic Web": сборник трудов Всероссийской конференции, Санкт-Петербург, 2012.

4. Катериненко, P.C. Эффективный логический вывод в продукционной модели с помощью баз данных с вертикальной архитектурой / P.C. Катериненко // KESW-2011 "Инженерия знаний и технологии Semantic Web" : сборник трудов Всероссийской конференции, Санкт-Петербург, 2011. - С.150-157.

5. Бессмертный, И.А. Компетентностная модель искусственного интеллекта / И.А. Бессмертный, P.C. Катериненко // Конгресса по интеллектуальным системам и информационным технологиям : сборник трудов, Дивноморское, 2011. - С. 11-16.

6. Катериненко, P.C. Ускорение логического вывода в продукционной модели знаний с помощью реляционных СУБД / P.C. Катериненко // VIII Всероссийской межвузовской конференции молодых ученых : сборник тезисов докладов, Санкт-Петербург, 2011. - С. 256-257.

7. Катериненко, P.C. Построение продукционной модели знаний в реляционных СУБД / P.C. Катериненко // VII Всероссийской межвузовской конференции молодых ученых : сборник тезисов докладов, Санкт-Петербург, 2010. - С. 105-106.

8. Катериненко, P.C. Semantic Web и продукционная модель знаний / P.C. Катериненко, И.А. Бессмертный // Управление знаниями и технологиями Semantic-Web : сборник трудов Всероссийской конференции, Санкт-Петербург, 2010. - С.183-185.

9. Катериненко, P.C. Построение продукционной модели знаний в реляционных СУБД / P.C. Катериненко, И.А. Бессмертный // XLVIII Международная научная студенческая конференция "Студент и научно-технический прогресс": сборник тезисов докладов, Новосибирск, 2010. - С.275-276.

10. Катериненко, P.C. Реляционный логический вывод / P.C. Катериненко // Сборник трудов молодых ученых и сотрудников кафедры ВТ. Выпуск 2, Санкт-Петербург: СПбГУ ИТМО, 2011. - С.85-86.

И. Катериненко, P.C. Построение продукционной модели знаний в реляционной СУБД / P.C. Катериненко // Аннотированный сборник выпускных квалификационных научно-исследовательских работ магистров, Санкт-Петербург: СПбГУ ИТМО, 2010. - С.16-17.

12. Катериненко, P.C. Реляционная алгебра как инструмент логического вывода в системах искусственного интеллекта / P.C. Катериненко, Бессмертный И.А. // Сборник трудов молодых ученых и сотрудников кафедры ВТ. Выпуск 1, Санкт-Петербург:СПбГУ ИТМО, 2009.

Список литературы диссертационного исследования кандидат технических наук Катериненко, Роман Сергеевич, 2013 год

ЛИТЕРАТУРА

[1] Катериненко, Р. Компетентностная модель искусственного интеллекта / Р. Катериненко, И. Бессмертный // Труды конгресса по интеллектуальным системам и информационным технологиям. — Россия, Дивноморское, 2011,- С. 11-16.

[2] Катериненко, Р. Semantic web и продукционная модель знаний / Р. Катериненко, И. Бессмертный // Труды всероссийской конференции «Управление знаниями и технологиями Semantic-Web». — Санкт-Петербург: 2010. — С. 183-186.

[3] Katerinenko, R. Дедуктивные базы данных / R. Katerinenko. — Heinrich-Bocking-Str. 6-8 66121, Saarbrucken, German: LAP LAMBERT Academic Publishing GmbH & Co. KG, 2012. - C. 63.

[4] Катериненко, Р. Разработка онтологического описания технических индикаторов / Р. Катериненко, И. Бессмертный, Н. Пичугин // Труды конференции KESW-2012 «Инженерия знаний и технологии Semantic Web». — Санкт-Петербург: 2012.

[5] Рассел, С. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг,- Вильяме, 2006. - С. 1408.

[6] Вагин, В. Н. Достоверный и правдоподобный вывод в интеллектуальных системах / В. Н. Вагин, Е. Ю. Головина, А. А. 3. М. В. Фомина; Под ред. В. Вагина, Д. Поспелов. - М.: ФИЗМАТЛИТ, 2004. - С. 704.

[7] Forgy, С. Ops, a domain-independent production system language / С. Forgy, J. P. McDermott // IJCAL- 1977. - Pp. 933-939.

[8] Problems in building an instructable production system / M. D. Rychener, C. Forgy, P. Langley et al. // IJCAI. - 1977. - P. 337.

[9] Forgy, C. Rete: A fast algorithm for the many patterns/many objects match problem / C. Forgy // Artif. Intell. - 1982. - Vol. 19, no. 1. - Pp. 17-37.

[10] Initial assessment of architectures for production systems / C. Forgy, A. Gupta, A. Newell, R. G. Wedig // A A AI. - 1984. - Pp. 116-120.

[11] Parallel algorithms and architectures for rule-based systems / A. Gupta, C. Forgy, A. Newell, R. G. Wedig // ISCA.- 1986. - Pp. 28-37.

[12] Parallel implementation of ops5 on the encore multiprocessor: Results and analysis / A. Gupta, M. Tambe, D. Kalp et al. // International Journal of Parallel Programming. - 1988. — Vol. 17, no. 2. - Pp. 95-124.

[13] Gupta, A. Static and run-time characteristics of ops5 production systems / A. Gupta, C. Forgy // J. Parallel Distrib. Comput.— 1989.- Vol. 7, no. 1.— Pp. 64-95.

[14] Gupta, A. High-speed implementations of rule-based systems / A. Gupta, C. Forgy, A. Newell // ACM Trans. Comput. Syst.— 1989,- Vol. 7, no. 2.-Pp. 119-146.

[15] Colomb, R. M. Deductive Databases and Their Applications / R. M. Colomb. — 1st edition. - Bristol, PA, USA: Taylor & Francis, Inc., 1998.

[16] Abdelguerfi, M. Emerging trends in database and knowledge-base machines: the application of parallel architectures to smart information systems / M. Abdelguerfi, S. Lavington. — IEEE Computer Society Press, 1995. — P. 303.

[17] Dymova, L. A new approach to the rule-base evidential reasoning: Stock trading expert system application / L. Dymova, P. Sevastianov, P. Bartosiewicz // Expert Systems with Applications. — 2010. — Vol. 37, no. 8. — Pp. 5564 - 5576.

http://www.sciencedirect.com/science/article/pii/S0957417410000953.

[18] Dymova, L. A stock trading expert system based on the rule-base evidential

reasoning using level 2 quotes / L. Dymova, P. Sevastianov, K. Kaczmarek //

81

Expert Systems with Applications. — 2012. — Vol. 39, no. 8. — Pp. 7150 - 7157.

http://www.sciencedirect.com/science/article/pii/S0957417412000905.

[19] Foo, S. Y. A rule-based machine vision system for fire detection in aircraft dry bays and engine compartments / S. Y. Foo / / Knowledge-Based Systems. - 1996,- Vol. 9, no. 8.- Pp. 531 - 540.

http://www.sciencedirect.com/science/axticle/pii/S0950705196000056.

[20] Chang, N.-B. Comparisons between a rule-based expert system and optimization models for sensor deployment in a small drinking water network / N.-B. Chang, N. P. Pongsanone, A. Ernest // Expert Systems with Applications.- 2011,- Vol. 38, no. 8.- Pp. 10685 - 10695.

http://www.sciencedirect.com/science/article/pii/S0957417411003198.

[21] Context-sensitive program analysis as database queries / M. S. Lam, J. Whaley, V. B. Livshits et al. // Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. - PODS '05.- New York, NY, USA: ACM, 2005,- Pp. 1-12.

http://doi.acm.org/10.1145/1065167.1065169.

[22] An asp-based system for e-tourism / S. Ielpa, S. Iiritano, N. Leone, F. Ricca // Logic Programming and Nonmonotonic Reasoning / Ed. by E. Erdem, F. Lin, T. Schaub. — Springer Berlin Heidelberg, 2009. — Vol. 5753 of Lecture Notes in Computer Science.— Pp. 368-381. http://dx.doi.org/10.1007/978-3-642-04238-63i.

[23] Iterative learning belief rule-base inference methodology using evidential reasoning for delayed coking unit / X. Yu, D. Huang, Y. Jiang, Y. Jin // Advanced Control of Industrial Processes (ADCONIP), 2011 International Symposium on. - 2011.- Pp. 96-101.

[24] Zaldivar, V. A. R. Meta-mender: A meta-rule based recommendation system for educational applications / V. A. R. Zaldivar, D. Burgos // Procedia Computer Science. - 2010. - Vol. 1, no. 2. - Pp. 2877 - 2882. - <ce:title>Proceedings of the 1st Workshop on Recommender Systems for Technology Enhanced Learning (RecSysTEL 2010)</ce:title> <xocs:full-name>Proceedings of the 1st Work-

shop on Recommender Systems for Technology Enhanced Learning (RecSysTEL

2010)</xOCS:full-name>. http //www sciencedirect com/science/article/pn/S1877050910003273.

[25] Lee, G. H. Rule-based and case-based reasoning approach for internal audit of bank / G. H. Lee // Knowledge-Based Systems2008.— Vol. 21, no. 2.—

Pp. 140 — 147. http//www sciencedirect com/science/article/pn/S0950705107000433.

[26] Iassznovski, S. Builder: A production rules-based tool for on-line simulation, decision making and discrete process control / S. Iassinovski, A. Artiba, C. Fag-nart // Engineering Applications of Artificial Intelligence,— 2008.— Vol. 21,

nO. 3.— Pp. 406 - 418. http //www sciencedirect com/science/article/pii/S0952197607000723.

[27] Kim, W. Web enabled expert systems using hyperlink-based inference. / W. Kim, Y. U. Song, J. S. Hong. - 2005. - Pp. 79-91.

[28] Caniupan, M. Repairing inconsistent dimensions in data warehouses / M. Caniupan, L. Bravo, C. A. Hurtado // Data & Knowledge Engineering.— 2012,— Vol. 79-80, no. 0,- Pp. 17 - 39.

http //www sciencedirect com/science/article/pn/S0169023X12000596.

[29] Ranise, S. On the verification of security-aware e-services / S. Ranise // Journal of Symbolic Computation. — 2012. — Vol. 47, no. 9. — Pp. 1066 - 1088.— <ce:title>First-Order Theorem Proving</ce:title>.

http //www sciencedirect com/science/article/pn/S0747717111002264.

[30] Bistarelli, S. A semiring-based framework for the deduction/abduction reasoning in access control with weighted credentials / S. Bistarelli, F. Martinelli, F. Santini // Computers & Mathematics with Applications. — 2012. — Vol. 64,

no. 4 — Pp. 447 - 462. http //www sciencedirect com/science/article/pn/S0898122111010728.

[31] Declarative secure distributed information systems / W. Zhou, T. Tao, B. T. Loo, Y. Mao // Computer Languages, Systems & Structures. — 2013. —

Vol. 39. no. 1. — Pp. 1 - 24. http //www sciencedirect com/science/article/pn/S1477842412000358.

[32] Call, A. A general datalog-based framework for tractable query answering over ontologies / A. Cali, G. Gottlob, T. Lukasiewicz //In Proc. PODS-2009. ACM. - Press, 2009.

[33] Ullman, J. D. Principles of Database and Knowledge-Base Systems, Volume II / J. D. Ullman. — Computer Science Press, 1989.

[34] Bertino, E. A bottom-up interpreter for a database language with updates and transactions. — 1993.

[35] Foundations of rule-based query answering / F. Bry, N. Eisinger, T. Eiter et al. //IN REASONING WEB, INT. SUMMER SCHOOL, LNCS. - Springer, 2007,- Pp. 117-128.

[36] Iltchev, V. Bottom-up method for processing recursive sets of rules / V. Iltchev // Proceedings of the 4th international conference conference on Computer systems and technologies: e-Learning. — CompSysTech '03. — New York, NY, USA: ACM, 2003. - Pp. 178-183. http://doi .acm.org/10.1145/973620.973650.

[37] Bry, F. Query evaluation in recursive databases: bottom-up and top-down reconciled / F. Bry // Data & Knowledge Engineering. — 1990.— Vol. 5.— Pp. 289-312.

[38] Chandramouli, B. On-the-fly progress detection in iterative stream queries. — 2009.

[39] Houtsma, M. A. W. Algebraic optimization of recursive queries / M. A. W. Houtsma, P. M. G. Apers // Data Knowl. Eng. - 1992. -. - Vol. 7,

no. 4. — Pp. 299-325. http://dx.doi.org/10.1016/0169-023X(92)90029-B.

[40] Magic sets and other strange ways to implement logic programs (extended abstract) / F. Bancilhon, D. Maier, Y. Sagiv, J. D. Ullman // Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems.- PODS '86,- New York, NY, USA: ACM, 1986,- Pp. 1-15.

http://doi.acm.org/10.1145/6012.15399.

[41] Brass; S. Magic sets vs. sld-resolution / S. Brass // Advances in Databases and Information Systems / edited byJ. Eder, L. Kalinichenko. — Springer London, 1996. — Workshops in Computing. — Pp. 185-203. http://dx.doi.org/10.1007/978-1-4471-

1486-4i3.

[42] Liu, M. Relationlog: A typed extension to datalog with sets and tuples (extended abstract) / M. Liu // Journal of Logic Programming. — 1995.— Vol. 36.— Pp. 83-97.

[43] Porter, H. Early deduction. - 1986.

[44] Lisovsky, K. Deviser:datalog evaluator integrated with scheme. — 2005.

[45] The deductive database system ldl++ / F. Arni, K. Ong, S. Tsur et al. // THEORY AND PRACTICE OF LOGIC PROGRAMMING. - 2003. - Vol. 3, no. 1,- Pp. 61-94.

[46] Ceri, S. What you always wanted to know about datalog (and never dared to ask / S. Ceri, G. Gottlob, L. Tanca // IEEE Transactions Knowledge and Data Engineering. — 1989. — Pp. 146-166.

[47] Yahya, M. D2r2: disk-oriented deductive reasoning in a rise-style rdf engine / M. Yahya, M. Theobald // Proceedings of the 5th international conference on Rule-based modeling and computing on the semantic web. — RuleML'll. — Berlin, Heidelberg: Springer-Verlag, 2011,— Pp. 81-96.

http://dl.acm.org/citation.cfm?id=2075505.2075523.

[48] Madalinska-bugaj, E. Generalizing the qsqr evaluation method for horn knowledge bases / E. Madalinska-bugaj, L. A. Nguyen // New Challenges in Applied Intelligence Technologies, volume 134 of Studies in Computational Intelligence. — Springer, 2008. — Pp. 145-154.

[49] Vieille, L. Recursive axioms in deductive databases: The query/subquery approach / L. Vieille // Expert Database Conf. - 1986. - Pp. 253-267.

[50] Theil Have, C. Efficient tabling of structured data using indexing and program transformation / C. Theil Have, H. Christiansen // Proceedings of the 14th international conference on Practical Aspects of Declarative Languages. - PADL'12. — Berlin, Heidelberg: Springer-Verlag, 2012. — Pp. 93-107.

http://dx.doi.org/10.1007/978-3-642-27694-lg.

[51] Dietrich, S. W. Extension tables: Memo relations in logic programming. / S. W. Dietrich 11 SLP. - 1987,- Pp. 264-272. http://dbip.uni-

trier.de/db/conf/slp/slp87.htmlDietrich87.

[52] Zhou, N.-f. Linear tabling strategies and optimizations / N.-f. Zhou, T. Sato, Y.-d. Shen // Theory Tract. Log. Program. - 2008. - . - Vol. 8, no. 1. - Pp. 81109. http://dx.doi.org/10.1017/S147106840700316X.

[53] Minker, J. Logic and databases: a 20 year retrospective. — 1996.

[54] Ramakrishnan, R. A survey of research on deductive database systems / R. Ra-makrishnan, J. D. Ullman // JOURNAL OF LOGIC PROGRAMMING.-1993.

[55] Kumar, S. Deductive Databases and Logic Programming / S. Kumar. — Addison-Wesley, 1992.

[56] Катериненко, P. Реляционная алгебра как инструмент логического вывода в системах искусственного интеллекта / Р. Катериненко, И. Бессмертный // Сборник трудов молодых ученых и сотрудников кафедры ВТ. — СПб: СПб-ГУ ИТМО: д.т.н., проф. Т.И.Алиев, 2009.

[57] Катериненко, Р. Построение продукционной модели знаний в реляционной субд / Р. Катериненко // Аннотированный сборник выпускных квалификационных научно-исследовательских работ магистров. — СПб: СПбГУ ИТМО: д.т.н., проф. В.О. Никифоров, 2010. - С. 16-17.

[58] Катериненко, Р. Построение продукционной модели знаний в реляционных субд / Р. Катериненко, И. Бессмертный // Сборник тезисов докладов XLVIII Международной научной студенческой конференции «Студент и научно-технический прогресс». — Новосибирск: 2010.

[59] Magic sets for disjunctive datalog programs / M. Alviano, W. Faber, G. Greco, N. Leone // CoRR. - 2012. - Vol. abs/1204.6346.

[60] Advances in rete pattern matching / M. I. Schor, T. Daly, H. S. Lee, B. Tib-

bitts // AAAI. - 1986. - Pp. 225-232.

86

[61] Nayak, P. The soar papers (vol. 1) / P. Nayak, A. Gupta, P. S. Rosenbloom / Ed. by P. S. Rosenbloom, J. E. Laird, A. Newell. - Cambridge, MA, USA: MIT Press, 1993. — Pp. 621-626. http //dl acm org/citation cfm?id=162580 162620.

[62] Scales, D. J. The soar papers (vol. 1) / D. J. Scales / Ed. by P. S. Rosenbloom, J. E. Laird, A. Newell. - Cambridge, MA, USA: MIT Press, 1993. - Pp. 406456. http //dl acm org/citation cfm?id=162580 162603.

[63] Doorenbos, R. B. Production matching for large learning systems: Ph.D. thesis. — Pittsburgh, PA, USA: Carnegie Mellon University, 1995. — UMI Order No. GAX95-22942.

[64] Soar/psm-e: investigating match parallelism in a learning production sytsem / M. Tambe, D. Kalp, A. Gupta et al. // SIGPLAN Not. - 1988. - . - Vol. 23, no. 9. — Pp. 146-160. http//doi acm org/10 1145/62116 62130.

[65] Bryant, R. E. Graph-based algorithms for boolean function manipulation / R. E. Bryant // IEEE Transactions on Computers.— 1986.— Vol. 35.— Pp. 677-691.

[66] Andersen, H. Boolean Expression Diagrams / H. Andersen, H. Hulgaard. — Department of Information Technology, Technical University of Denmark.

[67] Henrik, A. An introduction to binary decision diagrams, lecture notes. — Department of Information Technology, Technical University of Denmark, Lyngby, Denmark. - 1998.

[68] Hachtel, G. ITE operator and complement edges / G. Hachtel, F. Somenzi. — Logic Synthesis and Verification Algorithms, Kluwer, 1996. — Pp. 233-243.

[69] Whaley, J. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams / J. Whaley, M. S. Lam // Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation. - PLDI '04,- New York, NY, USA: ACM, 2004,- Pp. 131-144.

http //doi acm org/10 1145/996841 996859.

[70] Using datalog with binary decision diagrams for program analysis / J. Whaley, D. Avots, M. Carbin, M. S. Lam // Programming Languages and Systems / Ed. by K. Yi. - Springer Berlin Heidelberg, 2005. - Vol. 3780 of Lecture Notes in Computer Science. — Pp. 97-118. http://dx.doi.org/io.ioo7/ii5 7 5 4 6 78.

[71] Iwaihara, M. Bottom-up evaluation of logic programs using binary decision diagrams / M. Iwaihara, Y. Inoue // Data Engineering, 1995. Proceedings of the Eleventh International Conference on. — 1995. — Pp. 467-474.

[72] Bryant, R. E. Symbolic boolean manipulation with ordered binary-decision diagrams / R. E. Bryant // ACM Computing Surveys.— 1992.— Vol. 24.— Pp. 293-318.

[73] Катериненко, P. Верификация данных в системах отслеживания задач с помощью продукционных правил / Р. Катериненко, И. Бессмертный // Научно-технический вестник информационных технологий, механики и оптики. - 2013. - Т. 1(83). - С. 86-90.

[74] Катериненко, Р. Верификация систем управления проектами с помощью продукционных правил на основе двоичных диаграмм решений / Р. Катериненко, И. Бессмертный, Н. Пичугин // Труды конференции KESW-2012 «Инженерия знаний и технологии Semantic Web». — Санкт-Петербург: 2012.

[75] Катериненко, Р. Верификация информационного наполнения систем управления проектами с помощью продукционных правил / Р. Катериненко, И. Бессмертный // 5ая Российская мультиконференция по проблемам управления. Конференция информационные технологии в управлении. — Санк-Петербург: 2012.

[76] Катериненко, Р. Верификация информационного наполнения систем отслеживания дефектов с помощью продукций / Р. Катериненко // Сборник тезисов докладов IX Всероссийской межвузовской конференции Молодых Ученых. — Санкт-Петербург: 2012.

[77] C-store: a column-oriented dbms / М. Stonebraker, D. J. Abadi, A. Batkin et al. // Proceedings of the 31st international conference on Very large

data bases.- VLDB '05.- VLDB Endowment, 2005.- Pp. 553-564.

http://dl.acm.org/citation.cfm?id=1083592.1083658.

[78] One size fits all? - part 2: benchmarking results / M. Stonebraker, C. Bear, U. Cetintemel et al. //In CIDR. - 2007.

[79] Катериненко, P. Построение продукционной модели знаний в реляционных субд / Р. Катериненко // Сборник тезисов докладов VII Всероссийской конференции Молодых Ученых. — Санкт-Петербург: 2010. — С. 105-106.

[80] Katerinenko, R. Inference acceleration in production model of knowledge / R. Katerinenko, I. Bessmertniy // Programming and Computer Software. — 2011. - Vol. 42. - Pp. 197-199.

[81] Катериненко, P. Метод ускорения логического вывода в продукционной модели знаний / Р. Катериненко, И. Бессмертный // Программирование. — 2011.-Т. 4.-С. 76-80.

[82] Катериненко, Р. Реляционный логический вывод / Р. Катериненко // Сборник трудов молодых ученых и сотрудников кафедры ВТ. Выпуск 2. — СПб: СПбГУ ИТМО: редактор д.т.н., проф. Т.И.Алиев, 2011,- С. 85-86.

[83] Катериненко, Р. Ускорение логического вывода в продукционной модели знаний с помощью реляционных субд / Р. Катериненко // Сборник тезисов докладов VIII Всероссийской межвузовской конференции Молодых Ученых. - Санкт-Петербург: 2011.- С. 256-257.

[84] SaEnz-PeRez, F. Outer joins in a deductive database system / F. SaEnz-PeRez // Electron. Notes Theor. Comput. Sci. - 2012. - . - Vol. 282. - Pp. 7388. http://dx.doi.org/10.1016/j.entcs.2011.12.007.

[85] Marileo, M. C. The consistency extractor system: Answer set programs for consistent query answering in databases / M. C. Marileo, L. E. Bertossi // Data Knowl. Eng. - 2010. - Vol. 69, no. 6. - Pp. 545-572.

[86] Ludwig, S. A. Comparison of a deductive database with a semantic web reasoning engine / S. A. Ludwig // Knowledge-Based Systems. — 2010. — Vol. 23,

ПО. 6. — Pp. 634 - 642. http://www.sciencedirect.com/science/article/pii/S095070511000064X.

[87] Pérez- Urbina, H. Tractable query answering and rewriting under description logic constraints / H. Pérez-Urbina, В. Motik, I. Horrocks //J. Applied Logic. — 2010. - Vol. 8, no. 2. - Pp. 186-209.

[88] Baumeister, J. Anomalies in ontologies with rules / J. Baumeister, D. Seipel // Web Semantics: Science, Services and Agents on the World Wide Web.- 2010.- Vol. 8, no. 1,- Pp. 55 - 68.

http://www.sciencedirect.com/science/article/pii/S1570826809000778.

[89] Emerging "vertical" database systems in support of scientific data / P. Svensson, P. Boncz, M. Ivanova et al. // . // Scientific data management : challenges technology, and deployment. — 2009. — Vol. 1. — P. 235-281.

[90] Катериненко, P. Эффективный логический вывод в продукционной модели с помощью баз данных с вертикальной архитектурой / Р. Катериненко, И. Бессмертный // Труды конференции KESW-2011 «Инженерия знаний и технологии Semantic Web». — Санкт-Петербург: 2011. — С. 150-157.

[91] Катериненко, Р. Эффективный логический вывод в продукционной модели с помощью баз данных с вертикальной архитектурой / Р. Катериненко // Научно-технический вестник информационных технологий, механики и оптики. - 2012. - Т. 1(77). - С. 58-62.