автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Средства и методы ускорения дедуктивного вывода в информационных системах с большим объемом данных

На правах рукописи

КАТЕРИНЕНКО РОМАН СЕРГЕЕВИЧ

СРЕДСТВА И МЕТОДЫ УСКОРЕНИЯ ДЕДУКТИВНОГО ВЫВОДА В ИНФОРМАЦИОННЫХ СИСТЕМАХ С БОЛЬШИМ ОБЪЕМОМ ДАННЫХ

Специальность:

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2013

005061084

Работа выполнена в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики на кафедре Вычислительной техники

Научный руководитель: Кандидат технических наук, доцент

Бессмертный Игорь Александрович

Официальные оппоненты: Доктор технических наук, профессор

Коробейников Анатолий Григорьевич Санкт-Петербургский филиал ФГБУН ИЗМИРАН

Кандидат технических наук, доцент Бураков Дмитрий Петрович ФГОУВПО ПГУПС

Ведущая организация: ФГУП «Санкт-Петербургское ОКБ

«Электроавтоматика» имени П.А. Ефимова»

Защита состоится «27» июня 2013 на заседании ученого диссертационного совета Д 212.227.06 в 15-30 часов по адресу: 197101, Санкт-Петербург, пр. Кронверкский, д. 49., НИУ ИТМО, конференц-зал центра интернет-образования.

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

Автореферат разослан «25» мая 2013 г.

Ученый секретарь

диссертационного совета Д 212.227.06

Лобанов И.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

3

этой цели были поставлены и решены следующие задачи:

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 Web» (2012 г., Санкт-Петербург); бая Российская мулътиконферен-ция по проблемам управления. Конференция «Информационные технологии в управлении» (2012 г., Санкт-Петербург); XLII Научная и учебно-методическая конференция (2013 г., Санкт-Петербург).

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

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

трудов конференций.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Основоположником исследований в области дедуктивного вывода методом «снизу вверх» является J. Ulman, показавший в своих работах большой потенциал для оптимизации вывода этого типа. Это дало толчок к поиску способов преодоления негативной особенности метода «снизу вверх» — генерации большого количества избыточных данных при поиске решения. Важным шагом вперед в этой борьбе стала разработка алгоритмов «Magic set», в которой большой вклад был сделан F. Bancilhon. Наряду с ростом популярности реляционных баз данных развивались теория и практические методы их применения для дедуктивного вывода (С. Zaniolo, R. Ramakrishnan, R. Colomb и др.).

Другим важным подходом к ускорению вывода являются исследования в области усовершенствования метода поиска шаблона («Pattern matching»). Были разработаны и активно совершенствуются в наше время алгоритмы TREAT (P. Miranker, D. Brant) и Rete (С. Forgy, M. Schor, R. Doorenbos, A. Gupta). Ha сегодняшний день алгоритмы на базе Rete показывают одни из лучших результатов по скорости вывода, но при этом требуют большого объема памяти.

Очень хороший результат по снижению ресурсоемкое™ был продемонстрирован системой на базе бинарных диаграмм решений (R. Bryant), разработанной группой исследователей Стэнфордского университета (J. Waley, M.

Lam, M. Carbin).

В отечественной науке большой вклад d теоретические основы дедуктивного вывода, терминологию и практическое применение был сделан в работах Д.А. Поспелова, В.И. Городецкого, В.Н. Вагина, В.К. Финна.

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

Вторая глава посвящепа разработке и реализации алгоритма дедуктивного вывода для больших баз данных па основе бинарных диаграмм решений (БДР). Под большими базами данных понимаются базы такого объема, который трудно обрабатываем для современных систем дедуктивного вывода — это, как правило, количество атомарных формул порядка 105-106. Для быстрой обработки такого объема данных предлагается использовать синонимичные логическим БДР-операции: APPLY(F,G,op), RESTRICT(F,x,c), EXIST(F,x), FORALL(F,x), UNIQUE{F, x), SAT—ALL(F), SAT-COUNT{F), алгоритмическая сложность которых зависит лишь от количества узлов в диаграмме. Поскольку БДР обладает свойством редуцируемости, то при кодировании отношения с помощью БДР не наблюдается сильного роста количества узлов от количества кортежей в отношении, благодаря чему достигается ускорение вывода и уменьшение потребления памяти. На Рисунке 1 представлена блок-схема разработанного алгоритма, реализующего эту идею. Для кодирования произвольного отношения R, определенного па п доменах Do, Dj, • ■ -, Dn, предложен алгоритм, блок-схема которого приведена на Рисунке 2. В качестве характеристической функции предложено использовать булеву функцию:

xD\ ■ ■ ■, xD") = V[A[-DJVF(£f')]],

Vt Vfc

где DNFQ — дизъюнктивная нормальная форма от булева вектора xfk, сопоставленного элементу Х{ домена Dk методом логарифмического кодирования. При замене логических операций синонимичными БДР-операторами получается следующее выражение для алгоритма построения БДР для отношения:

XR0Dq, xDl,---, xDn) = Vi APPLYV [Vfc APPLY^ (.DNF{xf*))\.

Принадлежность кортежей домену характеризуется не одной функцией, а набором функций DNF(xf"). Это позволяет добавлять и удалять элементы из домена, меняя истинность отдельно взятой функции, что является важным свойством для создания динамической дедуктивной системы. Кроме того, каждая

_±_

Представшим отношений * виде БДР -1

Применение операций БДР для рвота головных частей правил иа ВДР-отношений

/

Ввод отношения

Кодирование элементов отношения двоичными числами

г

Построение характеристической функции отношения .. с применением булевых операций

г

Построение БДР для булевой характеристической функцт с помощью применения БДР-олераций

г

о

о

Рис. X: Блок-схема алгоритма преобразования от- Рис. 2: Блок-схема алгоритма дедуктивного вы-ношения в БДР вода па основе БДР

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

Для построения БДР для правила и расчета головной части правила разработан алгоритм, представленный на Рисунке 3.

Следует отметить, что разработанный алгоритм обладает важным для дедуктивного вывода на больших базах данных свойством — сложность не зависит от количества кортежей в отношениях, а зависит от количества узлов в БДР.

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

Рис. 3: Блок-схема алгоритма построения БДР для правила

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

1. Построение дедуктивной модели, состоящей из фактов и правил. Часть данных СОЗ, подлежащая верификации, должна быть представлена в виде фактов ЭБД. Ограничения, которым должны удовлетворять данные, формализуются в виде правил ИБД:

2. Для задания ЭБД вводятся следующие обозначения. Тикетом в СОЗ называется минимальная атомарная единица информации. Пусть множество тикетов обозначается Т, множество связей между тикетами L, множество свойств тикетов Р, а множество значений свойств V. Если два тикета ti,t2 6 Т связаны между собой произвольной связью I € L, то будем записывать это так: l(ti,t2)\l G L;h,t2 £ Т. ЭБД определяется исходя из

9

следующих правил:

• Каждому свойству р, € Р сопоставляется двухместный предикат вида Рг(*|';)|Р» € Р'Л € Т;г/ € V такой, что

рДТ, V) = Т О ЗЙг^.р; = V; * € Т; и € У;

• Каждому типу связей ^ € / сопоставляется двухместный предикат вида /¿(¿ь^Ж € € такой, что = Т <=> соединенные связью /,.

3. Вторая часть дедуктивной модели состоит из правил двух типов.

К первому чипу правил относятся условия, которым должны удовлетворять данные в СОЗ. Они имеют вид:

где Р, <2г - литералы с предикатными символами как принадлежащими ЭБД, так и введенными пользователем. Срабатывание этих правил соответствует корректному состоянию СОЗ.

Второй тип правил — это диагностические. Срабатывание диагностических правил говорит об обнаружении некорректных данных, то есть данных, не соответствующих правилам первого типа. Они имеют вид: Р <— <2 А ->Р или Р ч- -1<3 А Р, где ф-литерал с предикатным символом из ЭБД, а /"-литерал, заданный правилами первого вида. Построение дедуктивной модели является одним из шагов алгоритма верификации СОЗ. который является частью метода. Блок-схема алгоритма изображена на Рисунке 4.

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

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

1. Время загрузки интенсиональной и жстенситшльноП баз данных. Загрузка ИБД и ЭБД — достаточно редкая операция, происходящая при

запуске системы, поэтому эта характеристика не является критичной, по

10

Рис. 4: Блок-схема алгоритма верификации СОЗ

важна для целостном оценки системы. На этапе загрузки обычно происходит построение внутренних структур данных, »под исходных данных и преобразование их во внутреннее представление для последующего вывода. На этом этапе в нашей системе дедуктивного вывода, на основе предложенного алгоритма, базирующегося на бинарных диаграммах решений (БДР), происходит построение БДР для введенных отношений.

2. Время дедуктивного вывода;

3. Бремя выдача ответа на логический запрос. После процедуры вывода требуется выдать результат логического запроса. В разработанной системе на этом этапе происходит декодирование результирующей БДР.

4. Используемая оперативная память максимальный объем оперативной памяти, занимаемой процессом во время работы системы.

Испытательный стенд представляет собой персональный компьютер под управлением 04-разрядной операционной системы Windows 7, на базе 4-х ядерного процессора Intel Core i5 2410М 2.31) ГГц с оперативной памятью 4Гб.

11

В исследовании участвовало по одной системе от каждого класса систем, реализующих дедуктивный вывод. DES является реализацией "наивного"подхода; BDDBDDB, как и разработанная автором система Panda, использует БДР; Jess использует алгоритм Rete. На графиках на Рисунке 5, Рисунке 6, Рисунке 7, Рисунке 8, Рисунке 9, Рисунке 10, Рисунке 11, представлены результаты замеров. Каждой точке соответствует усредненная величина пяти последовательных замеров, для получения более объективных результатов при наличии других процессов операционной системы. Масштаб выбран логарифмический.

Рис. 5: Время вывода Рис. 6: Отношение времени вывода

Как видно из графиков на Рисунке 5 и Рисунке 6, система DES способна только на загрузку базы данных объемом не более 185000 атомарных формул и выполнение вывода на объеме не более 46000 атомарных формул. Отсюда можно сделать вывод, что «наивная» реализация дедуктивного вывода в условиях большого количества данных неприемлема. Система Jess показывает лучшее время загрузки вплоть до 11852 тыс. фактов, но это не является критичной характеристикой, поскольку загрузка выполняется один раз при инициализации системы. Jess демонстрирует лучшее время вывода на объеме до 370 тыс., а потом время вывода начинает расти по крутой траектории. Система Panda, являющаяся реализацией разработанного автором алгоритма на базе БДР, демонстрирует лучшее на порядок по сравнению с Jess и лучшее в среднем на 20% по сравнению с BDDBDDB время вывода. Схожая ситуация и с потреблением оперативной памяти. У разработанной системы при значительном росте количества кортежей не наблюдается катастрофического роста потребляемой

памяти и времени вывода, в отличие от других систем. На Рисунке 9 и Рисун-

12

3 185 370 741 14В2 2963 592« 11852 Количество атомарных формул (тысячи штук)

370 741 1482 2963 5926 11852 Количество атомаршх формул (тысячи штук)

Рис. 7: Время выдачи ответа на логический запрос

Рис. 8: Отношение времени выдачи ответа на логический запрос

. Оперативная память BbDBDOB/Pand* -Оперативная память JCSS/Panda -

■ I.....i-

2в5 370 741 1482 2963 5926 11852 Колмчастао атомарных формул (тысячи штук)

741 1482 2963 5976 Количество атомарных формул (тысячи иггук)

Рис. 9: Потребляемая оперативная память Рис. 10: Отношение потребляемой оперативной

памяти

ке 15 хорошо заметна особенность систем Panda и BDDBDDB, базирующихся на БДР, — между 185 и 2963 тыс. фактов происходит незначительный рост памяти, при увеличении объема данных в 10 раз. Такое поведение обусловлено особенностью БДР — сжатием данных.

Четвертая глава посвящена исследованию применения модели вертикальных баз данных (ВБД) (Column-oriented data base) для дедуктивного вы-

13

Рис. 11: Время загрузки ЭБД и ЙБД

вода. Как было показано в предыдущих главах, применение БДР для дедуктивного вывода дает значительный прирост скорости вывода и сокращает потребляемую память, но БДР — это достаточно сложная структура данных по сравнению с линейным списком или деревом. Операции доступа при работе с БДР имеют низкую локальность, поэтому подходят больше для систем, вычисляющих логический запрос по данным, загруженным в оперативную память, а не расположенным на диске. В последнем случае предлагается использовать модель ВБД на базе векторного языка программирования Q.

Одним из направлений в области исследования способов ускорения дедуктивного вывода является метод преобразования логической модели в реляционную, одним из основоположников которого является J. Ulman. Автор предлагает модифицировать этот метод с целью применения модели ВБД вместо реляционной. Основанием для этого является специфический вид возникающих реляционных запросов, в которых преобладает операция JOIN по равенству термов. При постолбцовом способе хранения, применяемом в модели ВБД, соединения такого рода выполняются очень эффективно, при этом исключается загрузка в оперативную память нерелевантных столбцов. Кроме того, значительно сокращается количество модифицируемых при удалении (добавлении) данных структур и повышается скорость вычисления запроса. Базовым элементом модели ВБД на основе векторного языка Q является список. Словарь представляет собой список пар вида «ключ — значение», частным видом которого является словарь столбцов вида «ключ — столбец». Аналогом таблицы реляционных БД является транспонированный словарь. Учитывая вышеска-

занное, автором предложен следующий способ применения модели ВБД для ускорения дедуктивного вывода:

1. Для каждого предиката экстенсиональной базы данных (ЭБД) создается транспонированный словарь и сохраняется на диск;

2. Для каждого предиката из интенсиональной базы данных (ИБД) создается транспонированный словарь в оперативной памяти;

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

Ниже приведены результаты сравнительного эксперимента для дедуктивного вывода с помощью реляционной СУБД Oracle llg и вертикальной базы данных KDB+. На Рисунке 12 и Рисунке 13 видно, что время вывода при использовании ВБД в среднем больше. Особенно это заметно на базах, содержащих меньше 110 или больше 305 тыс. кортежей. В интервале между этими значениями время отличается незначительно. Автор считает, что это связано с накладными затратами на создание хэш-таблицы системой Oracle. Зависимость по потребляемой оперативной памяти, представленная на Рисунке 14 и Рисунке 15, более ярко выражена. Система на базе Oracle llg занимает объем 100-200% от изначального размера таблиц, в то время как ВБД резервирует не больше 10%.

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

Заключение. В заключении сформулированы основные результаты работы:

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

Рис. 12: Среднее время вывода Рис, 13: Отношение среднего времени вывода

Рис. 14: Занимаемая оперативная память Рис. 15: Отношение занимаемой оперативной памяти

2. Разработан алгоритм дедуктивного вывода на больших базах данных с помощью бинарных диаграмм решений, который подходит для логической модели, состоящей из произвольных дизъюнктов, а не только из Хорнов-ских. При работе алгоритма занимаемый объем памяти меньше в среднем на 20% по сравнению с ДОДШЭДВ — другой реализацией дедуктивной системы на базе бинарных диаграмм решений, и на порядок меньше по

сравнению с Jess — реализацией алгоритма Rete. Скорость дедуктивного вывода выше в среднем на 19%, чем у BDDBDDB, и на порядок, чем у Jess. В дополнение, в отличие от других дедуктивных систем, предложенный подход на основе бинарных диаграмм решений позволяет подсчитать количество кортежей, удовлетворяющих логическому запросу, не находя сами кортежи, что позволяет сократить время работы. Единственным ограничением при использовании данного алгоритма являются накладные расходы на преобразование отношений в бинарные диаграммы, решений и декодирование результата, поэтому его использование оправдано в тех системах, где доля вычислений больше, чем доля операций ввода-вывода. К таким, безусловно, относится дедуктивный вывод методом «снизу вверх», где операции многократно применяются к одним и тем же отношениям;

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

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

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

В научных журналах, рекомендованных ВАК:

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

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

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

17

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

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

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

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

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

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

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

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

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

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Кронверкский пр., д. 49. Тел, (812) 233 46 69 Объем 1 пл.

Тираж 100 экз.

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики»

На правах рукописи

0420135^331

КАТЕРИНЕНКО РОМАН СЕРГЕЕВИЧ

СРЕДСТВА И МЕТОДЫ УСКОРЕНИЯ ДЕДУКТИВНОГО ВЫВОДА В ИНФОРМАЦИОННЫХ СИСТЕМАХ С БОЛЬШИМ

ОБЪЕМОМ ДАННЫХ

Специальность:

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: Бессмертный И.А.

Санкт-Петербург 2013

СОДЕРЖАНИЕ

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

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

ВВЕДЕНИЕ 8

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

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

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

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

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

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

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

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

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

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

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

1.7 Выводы..................................................................28

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

тела правила....................................................46

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

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

2.8 Выводы..................................................................49

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

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

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

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

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

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

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

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

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

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

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

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

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

з

3.9 Выводы

63

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

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

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

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

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

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

4.4 Выводы..................................................................74

ЗАКЛЮЧЕНИЕ 75

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

ДИССЕРТАЦИИ 77

ЛИТЕРАТУРА 80

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

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

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

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), постулируют в качестве одного из своих методов логический вывод. При этом рост числа потребителей логического вывода происходит на фоне хорошо заметной общемировой тенденции увеличения количества данных в цифровом виде, пригодных для осуществления логического вывода. Сама по себе задача логического вывода характеризуется большой алгоритмической сложностью, поэтому, в контексте вышеуказанных тенденций, становится актуальным сниж�