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

Определим основные преобразования ситуации, к которым относятся ис­ключение и добавление фактов. Для фиксированного 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, во-вторых, если две программы r₁, r₂ Î R, то программа (r₁; r₂) определенная равенством (r₁; r₂) (d) = r₂(r₁(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⁺) = Æ и, если d₂ = r⁺(d₁), то d₂ Ê d₁.

Через rq, где q = [t₁ /x₁, ... , t_m /x_m} — произвольная подстанов­ка, обозначим программу r, во всех операциях которой аргументы-переменные x_i заменены на сопоставленные им в q термы t_i, i = 1...m. Переменные программы, которым не сопоставлены в подстановке q ни­какие термы, заменяются на новые, еще неиспользованные переменные из множества X_s , s Î S.

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

var(q) Ê out(r).

d₂=r(qq)È (d₁\qq).

Если найдется последовательность продукций рr₁, рr₂, ..., pr_k, pr_i Î Pr, i = 1...k, k³ 0, и состояний базы d₀, d₁, …, d_k таких, что

то говорим, что d_k выводимо из d₀, и пишем или , a pr₁, рr₂, ..., pr_k назовем последовательностью применимых к d₀ про­дукций.

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

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

MgO + Н₂ ® Mg + Н₂O ,

СиО + Н₂ ® Си + H₂O,

Zn + H₂S0₄ ® ZnS0₄ + Н₂.

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

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

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

газ={Н₂, 0},

соль = {ZnSO₄},

кислота = {H₂S0₄},

вода= {Н₂О},

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

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

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

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

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

1) pr₁ =< q₁, r₁ >,

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

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

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

2) рr₂ =< q₂, r₂ >,

где q₂ = (тип, x, металл) Ù (формула, х, Zn) Ù (формула, z, H₂SО₄) Ù (тип, z, кислота),

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

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

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

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

d₀=(mun, e₁, окись) Ù (основание, e₁, Mg) Ù (тип, е₂, окись) Ù (основание, е₂, Сu) Ù (формула, e₁, MgO) Ù (формула, е₂, CuO) Ù (тип, е₃, металл} Ù (формула, е₃, Zn) Ù (тип, е₄, кислота) Ù (формула, e₄, H₂SО₄).

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

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

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

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

q₁ = {Mg/y,e₁/x}, q₂ = {Сu/у, е₂/х},

что дает в первом случае ситуацию, описывающую наличие веществ {Mg, H₂0, CuO, ZnS0₄}, а во втором — {MgO, Н₂0, Си, ZnS0₄}.

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

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

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

Рr = {рr_i = < q_{i ,} r_i >}, i=1...n, n ³ 0

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

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

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

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

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

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

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

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

- d' Ç d" ¹ Æ.

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

Пусть d'Ç d" — общая часть фрагментов d' и d", к которым применимы pr₁ =< q₁, r₁>,рr₂ = < q₂, r₂>, соответственно. Если программы r₁ и r₂ не исключают элементы из d¢ и d", то такие продукции можно применять к d' и d" в любом порядке.

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

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

1)

2)

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

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

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

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

,

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

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

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

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

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

d'Í d₁\ d", d"Í d₁\d'.

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

d₃= r₁q₁ ( d') È r₂q₂( d")È ((d₁\d')\d"),

d'₃ = r₂q₂(d") È r₁q₁(d') È ((d₁\ d")\d'), откуда следует, что d₃ = d .

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

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

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

Теорема 3. Пусть Pr = {pr_i} — система продукций, для которой выполнены условия теоремы 2. Если дополнительно для любых рr_i =< q_i,r_i>,pr_j =< q_j,r_j>,i, j = 1 . . . n

T(q_i) Ç T(in(r_j)) =Æ для исходного состояния базы d₀ выполнено условие: для всех под­становок q_i, q_j, если q_iq_I Í d₀ и q_jq_j Í d₀, то q_iq_i Ç q_jq_j =Æ. Тогда Pr на d₀ корректна.

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

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