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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ ИНСТИТУТ АВТОМАТИКИ И ПРОЦЕССОВ УПРАВЛЕНИЯ

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

Чернойгад Константин Геннадьевич

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

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

Автореферат . диссертации на соискание ученой степени кандидата технических наук

Владивосток 1997

Работа выполнена в Институте автоматики и процессов управления Дальневосточного отделения РАН.

Научный руководитель - доктор физико-математических наук,

профессор А.С.Клещев

Официальные оппоненты - доктор тхжгавдекнх наук

НА. А1ШСНМ0В

кандидат технических наук А.Я. Лифпшц

Ведущее предприятие: Институт прикладной математики

Дальневосточного отделения РАН (г.Владивосток) /

Защита состоится " / " 1997г. в_часов на заседании

Специализированного совета Д003.30.01 в Инстшуге автоматики и процессов управления Дальневосточного отдаления РАН по адресу: 960041, гБладиросток, улРадио, 5

С диссертацией можно ознакомится в библиотеке Института автоматики VI процессов управления Дальневосточного отделения РАН.

Автореферат разослан" " 1997г.

Ученый секретарь Специализированного совета д.т.н. С—' /У Б.И. Коган

-j"

ОБЩАЯ АРА1(ТЕРИСШ1СА РАБОТЫ

Акгуапьаоетт- ппоблелгн. В нестоящее гргмя системы продукций яагшогся oc:iociiUM. глдссо.и языков ^ргдстаг.лекчя г\т:?Л; используемых для реализации эгсспзрптьг: систем (ЭС). ЭС, прсдказязчетгке для решения реальны.", задач, содержат бат зпаннй объемом э исяи и десятки тысяч красил. В то га ергмя,' вез авторы, эзяимйзткеся реализацией систем продукций, отмечали такую скорость выгода в -лях системах, что связало с пзобхолшоспыо перебора большего числя впрпантов. Для бояыкях баз знаний это обстоятельстзо г.здзт к неприемлемо большим затратам времени, В сгязи с этим, с начал? "О-*: годсп началжь исследования методов ускорещш шзодя я системах продукций. Fcrgy С., Gupta А., Kelly М. и другими исследователями Сил предложен ряд мзтодоо оптимизации вывода, среди которых кзкослее известен Не'е-гягсритм ¡з его различные модифютцяи. Зтч методы позволяют получать реализации систем продукций, которые для баз зиаглй и данных средних разнероз. d ряде случаез дают приемлемую скорость вкьодэ. Однако, авторы Rete-алгеритма отвечают, что о.ч не является эффективным, когда з процессе зывода сосгсякнс вывода изменяется значительно,. а тагохе когда правила содержат произвольные св.тзп между образцами. Последнее приводит к перебору всех возможных rv\m?<{ic.> звзчгакЯ обрэзцоъ, а также требует наличия в Rete-сетн Еерашп с произвольным числом входов, что делает трудной эффективную реализацию адгор'гшз.

Деклпргтивнье продукция являются зажшм л хорошо ксследовшшын классом систем продукций. Вывод в декларативных продухциях обладает свойствами моногенности к конфлюзнтносги. Деклзраттпгные подукции являются математической моделью входных язнкоп оболочек Синап, РЕПРО, которые использовались для построения многих прикладных ЗС. Применительно к декоративным продукциям Rete-asropiro.i обладает теми же недоетэ-п.ачи, что и а случае других видоз продукций. Поэтому в работах И.Л. Артемьевой, A.C. Клещеза, Т.О. Мзтаеяой, B.C. Сорокина и других исследователей рп ссштрхвались и mis метода оптимизация вывода в дсклзраз гтродузгцня;;. Однако зга метода ко были строго описаны я

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

ШяШ_диссертационной работы яаляетсл исследование методоз

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

■ц-

Для достижения поставленной цели к диссертационной работе необходимо решить следующие зада«:-!:

- формально описать и исследовать различные методы опткмшацчн логического выгода в системах декоративных продукт^;

- исследовать возмаааюсп. есдмсэтного npiiM«uciBU различных оптльшзацлп;

- на основе получгнных результатов разработать проект оптимизирующего компилятора языка крадставлекия знаний РЕПРО;

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

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

Иручтоя ногмзт работ состоит в следующем:

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

- показана возиойгнсеть совместного использопаши различных оптимизаций, щкдло&ящ.раткачиые вариант совместного использования этих оптимизаций;

- предложена такаа г.смбншфОзяшш' сатйагоацня, коюраз о5ъедш1.:ст ссс оласашше п работе ¿ктоды онтямазгкмй.

Практически пенпозтг» работы захлючгсгсд а следующем:

- из основ» пэлучамгых тсоретвчгаахх результатов по исследованию оптимизаций яошчзского вывода в системах декларативных прод/кций реализован оап.-мизлруюш'гн компилятор языка подставления знакш: PEIIPO;

- оэтишаирроищй-койш&тэтор языка РЕПРО позволил в ир&сгачсски паленых случаях усг.яр;пь работу некоторых экспертах систем и других процэдш, рсатизола' mix на РЕПРО, в несколько раз, а л ряде случаев - в сотни и тысячи раз;

- разртботашше датодц оттшшцш метут бшв полезли в других областях системного гфогршашрозшиа, в частности, для оптимизации выполнения запросов к реляционным базам данных. -

Оптиыизирукжцнй ко;<шкллтср языка представления знаний РЕПРО используется б ИАПУ ДБО РАН для исследований и разработок экспертных систем, а такзет в учебно;.: процессе ДВГУ.

Апробация работы. Основные лоложяшя диссертации догадывались и обсуждались ¡¡а совместных семинарах отдела экспертных систем ИАПУ ДВО РАН is Бгзоьой эфедры программного обеспечения ЭВМ ДВГУ при ИАПУ ДВО РАН.

Основные результаты диссертации опубликованы в 5 работах.

Структура и объем рзбспт-т. Диссертационная работа -состоит из введения, пята г ля а и заключения.

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

Первая глаю диссертации содержит обзор литератур». В пей вводтгся оснорнме понята? и рассматриваются различные подходы к' проблеме ускорен:!;! вывода з системах продукций.

- Do второй глоте вводится операционный подход к оптимизации программ, этот нодчзд сравтгаается с трансформационным. Далее определяются системы декяатгптокых продукций и вводится мера сложности шага лолтессодго вызола. Зйтем ¿¿»игл определенно пошаговой оптимизации п исследуются некоторой пошаговые опг.к'кззцта.

Определим систему деюпрзтитгых продуя-цн:" как исчисление со входом порождающей модели

(ibr ,Z,„.4!>,K,V>},

где Vor - MKCBKCcrso'uepskcinsfiK;. г, - множесгво предикатных символов;

= (lj,fl,i} - алгебраическая система, £, - сиг iaiypa (¿, = 1ииЗ;аиЕа, причем SM - икожеетго копстаэт, - множество знаков операций и функций, S.j - множество зтоксч отношений, О - носитель, 1 - интерпретация символов из Z2); К - кикг.сстро продукций; SP - множество правил вшБОда.

Продукция в системе декларативных продукции - это выражение вкда .....}-.' а/;(*,'„..,г;r-](v!,... )Ä...Ü/•;(v;,...,vj) =>

где l>0, iäö, л>0; />, );...,г- атомарные формулы, причем

Р, <=z,(l<iüfy, а xf *Var (все переменные xf попарно различии); ^('i.-.'Iv).-»^.^",-.^) - этомгрнме формулы, причем Л', с?:, О <(<«), tj -термы языка сигнатуры I,, /^(v,',...,vj),...,/v(vf - атомарные

(логические) формулы языка сигнатуры причем /•] е Zi3(l <(<&), -термы языка сигнатуры I,. Каждая продукция должна удовлетворять условиям:

2. »'({/•;(»-;.....v;)..........ф\„. ,<})), гле по) -

множестзо переменных, пходящих в О (О может быть любой конструкцией). Часп. продукции до символа пашвается условием продукции, и часть после символа ' - >' - се следствием.

Рабочая среда - эго множество Н всех конечных шгозкеств атомарных формул вида скскстйгггаьи; (Ре!,,«, е11:.....е1„).

Правило вывода в системе декиврзгшшшх продукций {Ге.4 5, Л', Л'/') есть любое частичио-опрзделйьнге ■отобрххзкяг ПВ:КхН-*Н, причем для любых П е/С,<5 еН долгою вылодшггься условие: если ПВ(П,5) определено, то ¿еШ?(П,<5).

Рассмотрим: следующее правило вывода. УЛ{П,(У).еслк Л{Гг(Т1),<5,о^(П)) * 0,тоУЛ(П,5) = <5^ /Л, гдг

М = и ¡ьф, /К(П), ТЯ£!ч'{и), 0(П)).

»¿{иадлип!)

Здесь используются следунмциз обозначения:

- £>_,(П) - состояние кьгеода перед посяедаии пр:шктсш;ем Г1 (перед первым применением П £,(0) - 0);

- В{Р,6) = (/-(Л)]/(,';) Е1?) - миомжстео всех формул вида Р{Н) из IУ;

- А/|х:..хА/.-{{а,}и...и{о.}Ц еА/1,...,аеЛ/„};

- Х>({Р„...,Р,},<?) = в{рио)гЛЕ{р„8)-,

- !Г(П) ~ (р,(/,),..Р, (•',)) - множество Еггог,парных формул из условия продукции П;

- 7Я£Л'(п)={.?,({.-,),..,, ^)} - множество атомарных формул из следствия продукции П; "

- Ф(П)= {/¡{у,),...,/^^,)} - множество логических формул из условия продукции П;

- йЦх, {/>,(г,),..Р,(г,)),{$,{«,),...,¿'.(и,)},Мр) - шкшество формул вида

получезмыхиз основе *сл{{р„...,!>,},<$,(П)).

При фиксированных <У,П в качестве спадам сложности шага вывода для правила выбодз УП ■ в работе принята величина, равная Оя(П,£Ш) = (п)Д|1,(п))), где /¿{А/) -обозначаетмощностьмножеегьа А/.

Назовем пошаговой отташзацигй системы дс&тараттиных и|.юдуеднй Ж, - (Уаг, 1,, ЛЛ\ А',¿У',) другую систему декларативных продухций

ЯО, = {Каг,1,,/15, А'.Л'Р,) такую, что для любых фиксированных ПеА',й еЯД,(Н) имеет место следующее:

1.если существует ПВ,е5Р, такое, что определено /7#,(П,£), то существует ПВ2 такое, что определено //Й,(П,<>), причем

Яв,(П,<$)--=ЯЯ,(П,£) и офЛОД) 3: Сп.{П,6,Щ), гдо - Сп{П,8,т) - оценка сложности шага вывод?, для правил»вывод® /Ж;

2. если существует Яй, тгяое, пго опредедено ЯЯ,(П,<5), то существует П!\ еЛТ* такое, что определено ПВ,(П,5), причем Яг1(П,о')--Я/?1(№,.-) ¡г 0/;(П',¿>,ПН,)> СЦГГ,5,Ш2)•,

В работе рассматриваются пошантге оггшмгпацнн только для систем дскларатьглтых продукций (г^.^./^Д'ДУЯ)}.

Оспогп: -м источником уггеныаенкт слгшиостн вывода при использовании пошаговых оптимизаций декларагизеных продукций служат связи между переменными, задгт-аемые. логическими формулам» множества <*(П). Исхода га этого, большинство пошаголих оптимизаций д?каарзтивнмх продукций иожпо рззбягь на две группы. К первой группе относятся оптимизация, используюэд'.з связи между перененнымп в пределах одной етокяой формулы (з продукции II сушесп-уют /еФ(п) и рг!Г(П) такяе, что У{/)сУ(р)). Ко второй группе - оптимизации, использутопше связи тлелду перемстпчми кз рззных формул (а продуктн П

существуют /еФ(П) и {р......р,)с/Г(П) тахта, »сто к ¿2, к(/)сР({а.->л}).

у(/)пУ(г,)*0,..., У{/)г>1'(рк)^0). Рассмотрим каждую группу опгимтшцнй отдел; :;о.

Введем обозначен::тг.

[ /, -А, [НЙ ^

- ¿¡(р.Мр) - система ургвне'ш?! < ... , з которой переменные,

входящие" в 1,,-,'щ являются неизвестными (здесь Мр = {/',(/,),.••/'„(<„)}" множество ато,>,«арныхформул, р-{/;(/.•,),..,/,г,(^„}}

- х(дф,р)= {(*1,о',),...,(.г6,а1}} - подстановка, глз

(а,,..,,«,) - пешенкз системы ь\р,М~р);

- - результат выполнения подстановки Д к /;

истина),

- Я/-(П)={(Л/}!;.е=//<П),/ еФ(П},К(/)сФ)};

С помощью введенных обозначений определим следующие два правила вывода.

ОП 1\(П,5).если л(/г(П).г,<5.|(П))^0,Р/;(П) = а, то ОЯ1.1{П,5) = 5иА/, где

м = у&*(х;7г(п),7?/до(п),о(п))

ОП12(П,5). если (П)) * 0,(/>,/) е №,(11), то ОП\ 2{П,8)где

М = и Яа$(х, /Р(П), ТЖЛ'(П). ф* п))

млвл/мпщмлмп))

"При фиксированных П, 5, (/>,/)е№1(П) сложность шага вывода для правила вывода 0/212 оценивается величиной

Теорема. Огстешдеклщшишых продукций (Уаг,Ъ,,АЗ,К,{0П\.\,0П\.2}) является пошаговой оптимизацией системы (уаг,Ъ^АЗ,К,{У^\) ■

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

1 .Фильтратая по образцу (/ имеет вид х = о, где х- переменная, а-константа);

2.Фильтраиия по равенству между переменными одной Формулы (/ имеет вид х=у, где х,у- переменные)»

3.Фильтрашш по неравенству с константой (/ имеет вид х*а, где непеременная, о-константа, » - произвольное отношение из {<,>,¿,¿,54});

. 4.Сокрашение петебора за счет фунмшоиальпой связи ыехеду < переменными из одной формулы (/ имеет вид х = , где х,у- векторы переменных, % еЕ„ - функциональный символ);

б.Филътрвшя по отношению неравенства между переменными из одной формулы (/ имеет вид где х- переменная, ^-переменная, » -пронзвйльное отнотпенке из {<,>,:£, £,*}).

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

- РРг(П)= {(МР,р,/)\МР<=/Р(П),р 6^F(П)\AЙ0>/ еФ(П), ('(/) с (р),у(/)г,Г(МР) * 0,к(/) г* У{р) * 0) (множество МР будем

называть "базой", а формулу р - "хеостом");

~ А(({Л.-.Р-|}Л./).{Р»1.-.Л}'<У) = ({л.....Ли.АмА*!.-,Р,}|

{А*.....Р1,} ....../>►.}.«). р. *™<г(ря\дх\б)\р'т>1,...,р1} е/)({/>„,,.4.

-13В качестве материала для проведения измерительного эксперимента были взяты шесть баз правил на языке РЕПРО:

1. неогсгамизированиая версия экспертной системы "Консультант-2";

2. Моделирующая Экспертная Система Оптимизации Программ;

3. компилятор баз знгний "Коллапс";

4. оптимизированная версия экспертной системы "Консультант-2";

5. программа анализа сцен;

6. компилятор баз знании "Коллапс-О".

Данные, отражающие некоторые количественные характеристики баз правил приведены в табл.1.

Таблица 1

Количественные характеристики исследованных баз праанл

№ базы правил 1 2 3 4 5 6

Число продукций 1934 537 404 5525 4233 86

Число входов 2233 1442 1627 6058 4374 159

Каждая из частных оптимизаций 1-8 может применяться к любой продукции при наличии в ее условии атомных формул (входов) определенного типа. Между типом входа и частной оптимизацией существует взаимно однозначное соответствие, поэтому основной информацией, полученной для каждой базы правил, было соотношение числа входов каждого.типа к общему числу входов. Эти данные представлены в табл.2.

Таблица 2

Данные об отношении числа входов каждого типа к общему числу входов

правил № оптимизаций^^ ] 2 3 4 5 6

1 71.80% 26.9% 70.7% 98% ' 1.23% 43.71%

2 0% 0.2% 0.06% 0% 0.022% 0%

3 41.19% 1.2% 0.7% 78% 0% 3.01%

4 0% ' 0% 0% 0% 0% 0%

5 0.13% 0.62% 3.07% 0.04% 0.16% 2.01%

6 11.61% 79.6 81.9% 4.2% 4.29% 73.36%

7. 0% 0% 22.4% 0% - 0.86% 0%

8 10.58% 14.6% 35.5% 12.2% 0.96% 12.56%

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

1. компилятор баз знаний "Коллапс";

2. экспертная система "Консультант-2";

-143. интерпретирующая зкспертьая система диагностик!; заболеваний (база знаний включает описание 1-го заоолзваьяя);

4. интерпретирующая экспертная система диагностики заЗолсзашш (база знаний ш:лгэчает описание 6-ти заболеваний);

5. синтаксический анализатор с подьтожесггвзязьгхаШаскагк.. Результаты сравнения представлены в табл.3\

Время работы некоторых баз прашш в условиях гсюг'ракя:-оптпмизированион и кгопташирэкяшсй объектной- прегреши

Программа Вре;.мра5ош безелпшвдздк! В;\:ил рз.Зсш-с слти.яоадаей

Компилятор баз знашн! "Коялалс-О" (база знаний описывает б заболеваний) 146 сек 62 сек

Экспертная система Консультант^ 20 сек ■ 19 сек

интерпретирующая ЭС (база знаний списывает 6 заболевании) более 2 часов 4 см

птеркрепфугещай ЭС (база знаний описывает 1 заболевание) 1567 сек 2 сек

Сиитаксичссннй анализатор с подмножества ьзыка Паскаль (размер тестовой крогрзшш -ISO строк текста) 434 сек 3 сск

Все программы выпол1шшоь на машине класса Fcntiicn-100, под управлением MS Windows 95.

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

Кроме того, оптимизирующий компилятор с языка РЕПРО сравнивался с СУБД реляционного типа. Такое ерзгиение коррестко, поскольку декларативные продукции и языки запросов к базам данных нмегот общую реляционную модема дашых. Дш сравнения выбирались коммерческие СУБД для персональных ЭВМ класса IBM PC. Время выполнения различных запросов на разных СУБД пргвоачеднло в сотни, а иногда и в тысячи раз вр^мя работы соответствующих правил. Несомненно, скорость работы многих запросов можно значительно увеличить путем явного создания индексов и написания запросов специального вида (так называемые запросы с планами), однако многие не очень сложные запросы принципиально не поддавались оптимизации (это происходило тогда, когда связи между полями таблиц не ограничивались простым равенством). Такое сравнение позволят сделать вывод, что предложенные методы оптимизации декларативных

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

Ркс.2.Время работы сиитздгапссхого анализатора з зазношосга от размера входной программы (без оптямяэр!?!?«)- Обсаютеяия: по осп абсцисс - размер входной программы в строках, по оси ординат - время работы программы в секундах

'Лгс-З.Время работы синтакспчесхого анализатора в зависимости от размера входной программы (с оптимизацией). Обозначения прежние.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты работы заключаются в следующем: 1.В рамках ог.ерациолдего подхода к оптимизации программ формально ояисаны и исследованы ;:ге грушш оптщлгозцш! логического вывода в системах декларативных продукций: оптпм;?за1"'-н, сокращающие перебор За счет связей мезкду переменными в пределах одной атомной формулы; оптимизация, сокращающие перз5ср за счет связен недзду переменными из разных атомных формул. Дня кювдой из групп оптимизаций доказана теорема о корректности и предложена оценка сложности шага вывода при применении оптимизаций. В этих группах описаны частные случаи оптимизаций: "Фильтрация по образцу", "Фильтрация по равенству между переменными одной формулы", ■ "Фильтрация по неравенству с константой", "Сокращение перебора за счет функциональной связи между

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

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

3. Реализован ои гимгшрующиБ вомсиллор языка представления знаний PEIIPO.

4. Проведеао нсслсД'Жагаас-чггтиых оптимизаций и полученной версии оптимизирующего компилятора на реальных базач знаний. Наиболее применимыми частными оптимизациями язлкотся "Фильтрация по образцу" и "Сокращение перебора за счет равенства переменных в разных формулах". Оптимизирующий компилятор языка РЕПРО позволил ускорить работу большинства экспертных систем и лругих программ, реализованных на РЕПРО, в несколько раз, а в ряде случаев - в сотни и тысячи раз. Показано, что предложенные методы могут быть также полезны и при. проектировании СУБД реляционного типа.

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

1. Клсщев A.C., Чернойван Ii.Г. Исследование методов оптимизации выгода е системах декларативных продукции // Теория и практика систем с базами знаний. Владивосток: ДВОРАИ, 1994. с. 36-55.

2. Черноййаи К.Г. Взаимодействие некоторых оптимизации логического вывода в системах декларативных продукций: Препраят. Владивосток: КАПУ ДВО РАН, 1994. 35 с.

3. Матвеева Т.О., Чернойван К.Г. Экспериментальное исследование оптимизаций декларативных продукций: Препринт. Владивосток: ИАПУ ДВО РАН, 1994.21 с.

4. Чернойван К.Г. Поиск наилучшего варианта совместного использования ошчмкзаций в системах декларативных продукций: Препринт. Владивосток: ПАПУ ДВО РАЛ, 1996.19 с.

5. Чернойван К.Г. Особенности реализации оптимизирующею компилятора языка представления знаний РЕПРО: Препринт. Владивосток: ИАПУ ДВО РАН, 1997. 23 с.