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

⇐ ПредыдущаяСтр 19 из 32Следующая ⇒

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

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

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

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

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

f^A: s₁^A ´ s₂^A´ ... ´ s_n-1^A® s_n^A, n³ 0,

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

f: s₁ ´ s₂´ ... ´ s_n_-1® s_n, n³ 0,

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

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

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

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

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

- если fÎ F имеет схему f: s₁ ´ ... ´ s_n_-1 ® s_n и t₁, t₂, …, t_n_-1 — термы, где mun(t₁) = s₁, ..., mun{t_n_-1} = s_n_-1, то f(t₁, t₂,..., t_n_-1) — терм, mun(f(t₁, t₂,..., t_n_-1)) = s_n.

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

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

Определение 1. Назовем фактом упорядоченный список вида (f^A, e₁,..., e_n),

где fÎ F, f: s₁ ´ s₂ ´ ... ´ s_n-1 ® s_n, e_i Î TR, mun(e_i) = s_i, i = 1...n.

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

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

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

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

d₀ = (+, 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= {t₁/v₁, t₂/v₂, ..., t_m/v_m},

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

Подстановку q = {x₁/y₁, x₂/y₂, ..., x_m/y_m}, где x_i, у_i, (i = 1...m) — переменные, назовем алфавитным вариантом. Для каждого алфавитного варианта определена обратная к нему подстановка q^-1 при условии, что между переменными определено взаимно - однозначное соответствие.

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

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

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

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

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

d₀ 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, во-вторых, если две программы 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₁ pr ® d₂

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

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

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

d₀ * ® d₁

d₀ pr₁, …, pr_k ¾ ¾ ® d₁

то говорим, что 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] сформулированы три достаточных в совокупности локальных условия конфлюэнтности асинхронных моделей вычислений. Для систем продукций эти условия примут вид:

pr ®

d''

pr ®

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

pr₁pr₂ ¾ ®

pr₂pr₁ ®

d'',

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

pr₂pr₁ ¾ ®

d''';

pr₁pr₂ ¾ ®

d'''

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

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 не выполнены. Это означает, что в этой системе результат зависит от состояния базы, т.е. от выбора подстановки.

⇐ Предыдущая 14 15 16 17 181920 21 22 23 Следующая ⇒