Лекции.ИНФО


Формальные модели систем продукций



Среди наиболее известных формальных моделей СП следует указать ре­ляционную модель А.С. Клещева, К-системы В.Е. Кузнецова, ре­ляционные модели S.Vere и модель управляемой СП M.Georgeff. Яхно Т.М. была предложена алгебраическая модель СП, которая обобщает перечисленные выше модели и позволяет описывать поведение СП в самом общем виде [67,69,70].

Алгебраическая модель

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

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

Введем понятия из теории моделей в том объеме, в котором они пона­добятся для дальнейшего изложения. Согласно терминологии работы [129], многосортная алгебра A = <(sA)sÎS, (fA)fÎF> состоит из семей­ства множеств-носителей sA и семейства частичных функций fA:

fA : s1A ´ s2A ´ ... ´ sn-1A® snA, n³0,

Сигнатура S = (S, F) состоит из непустого множества S — символов для обозначения индексов множеств-носителей, называемых также сор­тами, и непустого множества F функциональных символов, каждому из которых приписана схема отображения

f : s1 ´ s2 ´ ... ´ sn-1® sn, n³0,

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

Для сигнатуры S = (S,F) многосортная алгебра A = <(sA)sÎS, (fA)fÎF> называется S-алгеброй, если схемы отображений для всех fÎ F согла­сованы с соответствующими отображениями fA.

Пусть задана сигнатура S = (S,F). С каждым сортом s Î S свяжем счетное множество Xs переменных и определим множество термов TR и функцию тип : TR —> S следующим образом:

- всякая переменная х Î Xs есть терм, причем тип(х) = s;

- всякий нульарный функциональный символ (константа) fÎ F со схемой отображения f: х ® s есть терм, причем mun(f) = s;

- если fÎ F имеет схему f : s1 ´ ... ´ sn-1 ® sn и t1, t2, …, tn-1 — термы, где mun(t1) = s1, ..., mun{tn-1} = sn-1, то f(t1, t2,... , tn-1) — терм, mun(f(t1, t2,..., tn-1)) = sn.

Заметим, что везде в дальнейшем предикатные символы рассматри­ваются как функциональные со схемой отображения в специальный вы­деленный сорт BOOLA = {0,1}.

В дальнейшем считаем заданными сигнатуруΣ = (S, F) и ΣалгебруA=<(sA)sÎS, (fA)fÎF>.

Определение 1. Назовем фактом упорядоченный список вида (fA,e1,...,en),

где fÎ F, f : s1 ´ s2 ´ ... ´ sn-1 ® sn, ei Î TR, mun(ei) = si, i = 1...n.

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

Проиллюстрируем введенные понятия простым примером. Рассмо­трим алгебраическую систему

A = < (R, BOОLA), (+, -, *, ³) >,

где R — множество вещественных чисел, BOOLA={0,1}; +, —, *, ³ — обычные операции и отношения над числами. Переменные будем обо­значать буквами x, у, z. Тогда уравнение х+у =5 запишется в виде следующего факта: (+, x, y, 5), а система соотношений х+y=5,y³ 0, х £ 3 в виде ситуации:

d0 = (+, x, y,5) Ù (³, у, 0,1) Ù (³, 3, x, 1)

Если все еi, (i = 1... n) в факте суть константы, то факт назовем терминальным. Поскольку среди фактов ситуации могут быть нетерми­нальные, то, в общем случае, ей соответствует неединственный набор множеств носителей алгебраической системы.

Для простоты изложения в дальнейшем ограничим термы в опре­делении факта константами и переменными, что не нарушает общности изложения, поскольку термы с функциональными символами могут быть записаны в ситуации без них увеличением числа переменных. Например, отношение х+ у ³ 2 запишется в виде (+, х, у, z) Ù (³, z, 2,1).

Определенная таким образом ситуация представляет собой множество конъюнктивно-связанных фактов, и поэтому в дальнейшем будем обра­щаться с нею как с множеством, используя операции объединения È, пересечения Ç, разности \ и отношение включения Ê.

Обозначим через var{d) множество имен переменных, входящих в си­туацию d, а через T(d) = {mun(x)½x Î var(d)} — множество типов пере­менных, входящих в факты ситуации d.

Традиционным образом введем понятие подстановки

q= {t1/v1, t2/v2, ..., tm/vm},

где ti термы, vi — переменные, mun(ti) = mun(vi), i = 1...т. За­пись dq означает результат одновременной замены каждого вхождения переменной vi, в d на соответствующий терм ti.

Подстановку q = {x1/y1, x2/y2, ..., xm/ym}, где xi, уi, (i = 1...m) — переменные, назовем алфавитным вариантом. Для каждого алфавитного варианта определена обратная к нему подстановка q -1 при условии, что между переменными определено взаимно - однозначное соответствие.

Определение 2. Две ситуации d и d' назовем эквивалентными (d º d'), если найдется алфавитный вариант q такой, что

d Ê d' q и d' Ê dq -1.

Пусть, например, задана подстановка q = {3/x, z/y}. Тогда ее при­менение к ситуации d0, приведенной выше, дает

d0 q = (+, 3, z, 5) Ù (³, z, 0,1) Ù (³, 3, 3, 1).

Очевидно, что относительно терминальных фактов, каким, например, является (³,3,3,1), в заданной алгебраической системе всегда можно говорить, истинны они или ложны. Все истинные терминальные фак­ты опускаются при дальнейшем рассмотрении, так как они являются тавтологиями. Таким образом, ситуация d0 q эквивалента ситуации

d0 q = (+, 3, z, 5) Ù (³, z, 0,1).

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

2.5.9.1.2. Операции преобразования ситуации

Определим основные преобразования ситуации, к которым относятся ис­ключение и добавление фактов. Для фиксированного d' Î D:

1. Операция исключения: elim[d'] : D ®D

elim[d'](d) = d\ d'

2. Операция добавления: аdd[d'] : D ®D

add[d'](d)=d È d'

Определим множество программ R преобразования ситуации следу­ющим образом. Во-первых, будем считать элементами R программы add[d'], elim[d'] при любых d' Î D, во-вторых, если две программы r1, r2 Î R, то программа (r1; r2) определенная равенством (r1; r2) (d) = r2(r1(d)), "d Î D, также элемент R.

Для любого r Î D введем множество in(r) переменных, добавляе­мых программой r, и множество out(r) переменных, исключаемых r, по следующим правилам: "d' Î D

- out(add[d']) = Æ, in(add [d']) = var(d');

- out(elim[d']) = var(d'), iп(еliт[d']) = Æ;

- out (r1; r2) = out(r1) È оиt(r2), in(r1; r2) = in (r1 ; r2 ) È in(r2).

Определение 3. Программу r+ , содержащую только операции типа add[d'] ("d' Î D), назовем позитивной. Заметим, что out(r+) = Æ и, если d2 = r+(d1), то d2 Ê d1.

Через rq, где q = [t1 /x1, ... , tm /xm} — произвольная подстанов­ка, обозначим программу r, во всех операциях которой аргументы-переменные xi заменены на сопоставленные им в q термы ti, i = 1...m. Переменные программы, которым не сопоставлены в подстановке q ни­какие термы, заменяются на новые, еще неиспользованные переменные из множества Xs , s Î S.

Определение 4. Продукцией назовем пару < q, r >, в которой q — си­туация, называемая условием применимости продукции, r — программа, rÎ R, называемая действием, причем q и r связаны соотношением

var(q) Ê out(r).

d1 pr ® d2

 

Системой продукций назовем конечное множество пар Рr = {< q, r >}. Будем говорить, что d2 непосредственно выводимо из d1 при помощи продукции pr = < q,r >, , если найдется такая подстановка q, что d1 Ê qq, а

d2=r(qq)È (d1\qq).

Если найдется последовательность продукций рr1, рr2, ..., prk, pri Î Pr, i = 1...k, k³ 0, и состояний базы d0, d1, …, dk таких, что

 

       
 
d0 * ® d1

 

   
d0 pr1,…, prk ¾¾® d1

 

 


то говорим, что dk выводимо из d0, и пишем или , a pr1, рr2, ..., prk назовем последовательностью применимых к d0 про­дукций.

Если и "pr ( => d' = dk), то dk назовем результирую­щей ситуацией d0.

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

MgO + Н2 ® Mg + Н2O ,

СиО + Н2 ® Си + H2O,

Zn + H2S04 ® ZnS04 + Н2.

Опишем предметную область посредством многосортной алге­бры с множествами носителями:

окись = {MgO, CuO},

металл = {Mg, Cu, Zn},

газ={Н2, 0},

соль = {ZnSO4},

кислота = {H2S04},

вода= {Н2О},

вещества = окиcь È металлÈ газ È сольÈ кислотaÈ вода

и отображениями

основание: окись —> металл (например, основание (MgO) = Mg);

формула:вещества —> вещества (тождественное пре­образование, сопоставляющее веществу его химическую фор­мулу).

Тогда химические реакции можно переписать в виде следующих про­дукций (в некотором условном синтаксисе):

1) pr1 =< q1, r1 >,

где q1 = (mun, х, окись) Ù (основание, х, у) Ù (тип, у, металл) Ù (формула, z, Н2) Ù (тип, z, газ);

ri = add[(mun, z', вода) Ù (формула, z', Н2О) Ù (mun,z", металл) Ù (формула, z",y)];

elim[(тип, x, окись) Ù (формула, z, H2) Ù (тип, z, газ)]

2) рr2 =< q2, r2 >,

где q2 = (тип, x, металл) Ù (формула, х, Zn) Ù (формула, z, H24) Ù (тип, z, кислота),

r2 = аdd[(тип, z', газ) Ù (формула, z', H2) Ù (тип, z", соль) Ù (формула, z", ZnSО4)];

elim [(тип, x, металл) Ù (формула, х, Zn) Ù {тип, z, кислота) Ù (формула, z, H24)].

Первой продукции соответствуют первые две реакции, вторая — опи­сывает третью реакцию.

Пусть имеется информация о наличии веществ {MgO, CuO, Zn, H24}, что задается следующей исходной ситуацией:

d0=(mun, e1, окись) Ù (основание, e1, Mg) Ù (тип, е2, окись) Ù (основание, е2, Сu) Ù (формула, e1, MgO) Ù (формула, е2, CuO) Ù (тип, е3, металл} Ù (формула, е3, Zn) Ù (тип, е4, кислота) Ù (формула, e4, H24).

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

Ставится задача: какие вещества могут быть получены (результиру­ющая ситуация) из заданных по продукциям pr1 — pr2.

Рассмотрим процесс вывода. На первом шаге применима продукция рr2, которая приводит к ситуации, описывающей наличие следующих веществ: {MgO, CuO, H2, ZnS04}.

На втором шаге применима лишь продукция рr1, однако для нее су­ществуют две подстановки

q1 = {Mg/y,e1/x}, q2 = {Сu/у, е2/х},

что дает в первом случае ситуацию, описывающую наличие веществ {Mg, H20, CuO, ZnS04}, а во втором — {MgO, Н20, Си, ZnS04}.

Из примера видно, что результирующая ситуация зависит в общем случае от выбора подстановки и порядка применения продукций, т.е. неоднозначна. Для СП, результат конъюнктивного вывода в которых од­нозначен, разработаны эффективные методы поиска решений (каким, на­пример, является использование смешанных вычислений [91] в реляционной модели [24]). Поэтому в этой модели СП актуальна задача выделения подклассов, в которых результирующая ситуация однозначна.

2.5.9.1.3. Условия корректности вычислений над конъ­юнктивной базой данных

Пусть дано исходное состояние d0 и система продукций

Рr = {рri = < qi , ri >}, i=1...n, n ³ 0

Определение 5. Назовем Рr корректной на d0, если не существует бесконечной последовательности применимых к d0 продукций, и для лю­бых двух результирующих ситуаций d' и d", выводимых из d0, выполнено d' = d".

Определение 6. Систему продукций назовем конфлюэнтной, если для любых состояний базы d, d', d", таких, что и , следует, что найдется d'" такое, что и [104].

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

Множество продукций < qi , ri>, для которых найдется такая подста­новка q, что d Ê qiq, называется конфликтным множеством продукций относительно d, CS{d) = {< q,r > | $qd Ê qq}, а конфликтное множе­ство фрагментов Fr(d) определяется следующим образом:

Fr(d) = {d' Í d½$q $ <q,r> d'=qq}.

Так, в описанном выше примере, на втором шаге вывода конфликтное множество фрагментов состоит из двух ситуаций, описывающих наличие следующих веществ: {{MgO,H2}, {CuO,H2}}.

Для каждой пары элементов d' и d" из Fr(d) выполнено одно из сле­дующих условий:

- d' Ç d" = Æ, либо

- d' Ç d" ¹ Æ.

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

Пусть d'Ç d" — общая часть фрагментов d' и d", к которым применимы pr1 =< q1, r1>,рr2 = < q2, r2>, соответственно. Если программы r1 и r2 не исключают элементы из и d", то такие продукции можно применять к d' и d" в любом порядке.

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

В работе [104] сформулированы три достаточных в совокупности локальных условия конфлюэнтности асинхронных моделей вычислений. Для систем продукций эти условия примут вид:

1)
d pr ® d''

 

d pr ® d'

 

детерминированность: "d ,d', d" Î D, "pr Î Рr, если и , , то d' = d";

2)
d pr1pr2 ¾® d'

 

d pr2pr1 ® d'',

 

коммутативность: "d Î D "pr1, pr2 Î Pr, если $d',d" такие, что и

d pr2pr1 ¾® d''';

 

d pr1pr2 ¾® d'''

 

то $d"' такое, чтои

3)устойчивость: "d Î D "pr1, pr2 Î Pr, если pr1 ¹ pr2 и $d',d" такие, что и , то $d"' такое, что

Очевидным следствием этих условий является следующая теорема.

Теорема 1. Пусть Рr — система продукций такая, что каждая < q,r > Î Рr имеет позитивную программу. Тогда система продукций конфлюэнтна.

Доказательство. Поскольку каждая продукция содержит програм­му, состоящую только из операций add[d], которые по определению ком­мутативны и ассоциативны, то для позитивных программ определение вывода по продукции можно заменить на эквивалентное ему в этих ограничениях, а именно, будем говорить, что d1 ® d2 по продукции рr = < q,r+>, если

,

где q ¢ = {q½di Ê qq}. При такой модификации вывода система продукций с позитивными программами обладает свойством 1. Проверка условий 2 и 3 также очевидна, откуда следует, что система продукций конфлюэнтна. Этот класс систем продукций аналогичен реляционным СП предложенным А. С. Клещевым.

Выполнение условий 1 и 2 исключает неоднозначность, связанную с выбором подстановки, выполнение условий 2 и 3 исключает неоднознач­ность, связанную с выбором продукции. Следующая теорема формули­рует достаточные условия отсутствия неоднозначности второго типа.

Теорема 2: Пусть Рr — система продукций, в которой выполнено условие: для любых pr1= <q1, r1>, pr2=<q2, r2>, pr1¹pr2 (T(q1) Ç T(q2) = Æ) Ú (T(out(r1)) Ç T(q2) = Æ). Тогда Рr — коммутативна и устойчива.

Доказательство. Пусть выполнено условие (T(q1) Ç T(q2)=Æ.

1. Проверка условия коммутативности. Пусть имеем . Так как T(q1) Ç T(q2)= Æ , то существуют d' и d" такие, что d' = q1 q1 Í d1, d" = q2q2 Í d1 для некоторых подстановок q1 и q2 причем, d' Ç d" = Æ, а, следовательно,

d'Í d1\ d", d"Í d1\d'.

Тогда, по определению вывода, имеем

d3= r1q1 ( d') È r2q2( d")È ((d1\d')\d"),

d'3 = r2q2(d") È r1q1(d') È ((d1\ d")\d'), откуда следует, что d3 = d .

2. Проверка условия устойчивости. Пусть Анало­гично выше приведенным рассуждениям можно утверждать, что существует путь , где

Доказательство теоремы для случая (T(out(r1)) Ç Т(q2) == Æ) прово­дится аналогично.

Замечание. Система продукций, для которой на каждом шаге выво­да для любой продукции <р, q> существует единственная подстановка q такая, что qq Í di где di — текущее состояние базы, удовлетворяет условию детерминированности. Однако проверка этого условия осуще­ствляется на текущем состоянии базы и, следовательно, это условие не­возможно проверить статически на множестве продукций независимо от базы.

Теорема 3. Пусть Pr = {pri} — система продукций, для которой выполнены условия теоремы 2. Если дополнительно для любых рri =< qi,ri>,prj =< qj,rj>,i, j = 1 . . . n

T(qi) Ç T(in(rj)) =Æ для исходного состояния базы d0 выполнено условие: для всех под­становок qi, qj, если qiqI Í d0 и qjqj Í d0, то qiqi Ç qjqj =Æ. Тогда Pr на d0 корректна.

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

Вернемся к примеру. Легко заметить, что условия теоремы 2 для него выполнены, т.е. различные продукции можно применить в такой системе внутри одного варианта вывода в любом порядке. Одна­ко условия теоремы 3 не выполнены. Это означает, что в этой системе результат зависит от состояния базы, т.е. от выбора подстановки.









Читайте также:

Последнее изменение этой страницы: 2016-03-17; Просмотров: 74;


lektsia.info 2017 год. Все права принадлежат их авторам! Главная