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

Покачалов Вадим Анатольевич

Аспирант, ЛГТУ, г. Липецк

E-mail: konsul_p_v@mail.ru

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

В соответствии с принципом оптимистической репликации, приложения, выполняющиеся в распределенной среде, находятся либо на этапе изолированного исполнения, либо на этапе реконсиляции. При изолированном выполнении приложение оперирует локальной репликой разделяемых данных, приводя их в некоторые новые состояния. Все выполняемые действия записываются в журналах транзакций, являющихся упорядоченными множествами локально применяемых операций. Все действия детерминированы и обратимы. Применение всех операций, занесенных в журнал, к начальной версии данных должно приводить к той же окончательной версии. И наоборот, применение обратных операций в противоположном порядке должно возвращать данные из конечного состояния в первоначальное состояние [4].

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

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

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

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

В общем случае гиперграф можно задать различными способами. Определим гиперграф согласно [2; 5]. Гиперграф H (V, Е) есть пара, где V — множество вершин V={v_i}, iI={1, 2,…, n}, а E — множество ребер Е={e_j}, jJ={1, 2,..., m}; каждое ребро представляет собой подмножество V. Вершина v и ребро e называются инцидентными, если ve. Для vV через d(v) обозначается число ребер, инцидентных вершине v; d(v) называется степенью вершины v. Степень ребра e — число вершин инцидентных этому ребру — обозначается через r(e). Гиперграф Н является r-однородным, если все его ребра имеют одинаковую степень r.

Гиперграфы бывают ориентированные и неориентированные. В случае ориентированного гиперграфа (оргиперграфа) ребро eЕ называется гипердугой и представляется как упорядоченная пара (h, T), где hV, ТV\{h}, T≠Ø. При этом вершина h называется началом дуги e, а каждая вершина из T — конечной вершиной дугиe. Будем говорить, что дуга e исходит из вершины h и заходит в каждую из вершин множества Т [5]. Также введём обозначение h → (t₁, t_2, …,t_k), и будем называть такую гипердугу k-дугой.

Существуют разные подходы к определению веса гипердуги. В первом случае [3], вес k-дуги равен числу её концевых узлов, то есть

w(h → (t₁, t_2, …,t_k))=k                                        (1)

В другом случае, вес определяется как максимальный вес рёбер. составляющих гипердугу.

Введем понятие частично ориентированного гиперграфа. Гиперграф H=(V, Е₁, Е₂) называется частично ориентированным или квази ориентированным гиперграфом, если Е₁Е и Е₁≠Ø — множество ребер (звеньев), а Е₂Е и Е₂≠Ø множество дуг и Е₁Е₂=Е. Если Е₁=Е и Е₂=Ø, то гиперграф является неориентированным, а если Е₂=Е и Е₁=Ø, то гиперграф является (полностью) ориентированным. В зависимости от мощности множеств Е₁ и Е₂ вводятся соответствующие понятия. Если |Е₁|=|Е₂|, то гиперграф будет ориентированно-неориентированным. Если |Е₁|>|Е₂|, то гиперграф будет почти неориентированным. Если |Е₁|<|Е₂|, то гиперграф будет почти ориентированным.

Если элементам гиперграфа приписаны символы (или цепочки символов) из некоторого множества, то он является раскрашенным гиперграфом или гиперграфом с помеченными вершинами и ребрами. Цепочки символов — это имена понятий и отношений онтологии, представленной раскрашенным, частично ориентиро­ванным гиперграфом. Такой гиперграф будем называть семантическим гиперграфом.

Существует несколько подходов к определению маршрута наименьшего веса в гиперграфе. В первом из них, нам необходимо расширить решение задачи с гиперграфа на метаграф [6; 1]. Для этого используется обобщение алгоритма Дейкстры на метаграф. При использовании данного подхода подразумевается использование определение веса гипердуг через максимальный вес рёбер, составляющих гипердуге. Во втором — используется обобщённый метод поиска в ширину и глубину [3]. В нём используется итерационное расширение числа вершин в рассматриваемом гиперграфе.

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

Список литературы:

1.Блюмин С.Л. Метаграфы: матричные представления, связи с орграфами и гиперграфами, с идемпотентной математикой. // Сборник трудов ИИТО. Липецк: ЛГПУ, 2011. 3 с.

2.Визинг В.Г. О раскраске инциденторов в гиперграфе // Дискретный анализ и исследование операций, июль — сентябрь 2007. Серия 1, Том 14, № 3. С. 40—45.

3.Новиков, Ф.А. Искусственный интеллект: представление знаний и методы поиска решений // учеб. пособие. СПб.: Изд-во Политехн. ун-та, 2010. 240 с.

4.Семенов В.А. [и др.] Семантическая реконсиляция прикладных данных на основе моделей // Труды Института системного программирования РАН.: Институт системного программирования РАН, 2007. Том 13, № 2. С. 141—164.

5.Хахалин Г.К. Прикладная онтология на языке гиперграфов // Труды второй Всероссийской Конференции с международным участием «Знания-Онтологии-Теории» (ЗОНТ-09). Новосибирск, 20—22 октября 2009.: Новосибирск, 2009. 9 с.

6.Черных О.О., Попова Д.И. Алгоритмы поиска пути наименьшего веса в метаграфе и их практиче­ское применение // 13 Региональная молодежная научная и инженерная выставка «Шаг в будущее, Центральная Россия». Липецк: ЛГТУ, 2010. 15 с.