автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование ограниченными сетями Петри динамических информационных структур

ргб оа

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ 2 ^ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ "УНИВЕРСИТЕТ им. ЯРОСЛАЗА МУДРОГО

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

СМИРНОВА ЕЛЕНА ИГОРЕВНА

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

Специальность 05.13.18 — Теоретические основы математического моделирования, численные методы и комплексы программ

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

Новгород - 1998

Диссертация выполнена в Новгородском государственном университете им. Ярослава Мудрого.

Научный руководитель:

доктор технических наук, профессор Емельянов Геннадий Мартинович. Официальные оппоненты:

- доктор технических наук, профессор Немярко Анатолий Павлович;

- кандидат технических наук, доцент Колногоров Александр Валерьянович.

Ведущая организация:

Научно-исследовательский институт прикладной математики и кибернетики при Нижегородском государственном университете им. Н.И.Лобачевского.

Защита состоится ".У/1 " декабря 1998 г. в; часов на заседании диссертационного совета. К 06.4.32.05 при Новгородском государственном университете им. Ярослава Мудрого (173003, Россия, г. Великий Новгород, ул. Б. Санкт-Петербургская, 41).

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан " . " октября 1998 г.

Ученый секретарь

диссертационного совета К 064.32.05

к.ф.-м.н., доцент

Беляев К.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы. Развитие и доступность средств компьютерной обработки изображений, упрощающих использование изображений в качестве информационных объектов базы данных (БД), позволили эффективно решать задачу совместного или комплексного хранения и использования разнотипной информации в одном контексте. Развитие мультимедиа (ММ-)технологи'й, предполагающих связывание и комплексное использование сложных по организации разнотипных объектов, вместе с увеличением количества информации, используемой одним приложением, и усложнением структурных взаимосвязей между информационными элементами, привело к необходимости определения новой логической модели данных, отличающейся от традиционных динамичностью информационной структуры.

Характерной особенностью динамической информационной структуры (ДИС) является тот факт, что не все связи между элементами подобной структуры заданы исходно (статически), а могут устанавливаться динамически в процессе функционирования информационной системы (ИС). Сисгема управления базой комплексированных данных (СУБКД), поддерживающая динамическую визуализацию данных, функционирует переводя систему из состояния в состояние, каждое из которых определяется неким активным подмножеством информационных элементов. Такая идеология логической схемы ИС удобна для организации и формального определения операции контекстного поиска.' Однако, современные ИС, ориентированные на динамичность представления данных, проектируются либо на уровне байтового обмена и не имеют какой-либо научной идеологии, либо имеют в своем аппарате различные модификации статических ме-' тодов, имитирующих эту динамичность. Это в значительной степени сужает потенциальные возможности ИС, как в смысле эффективности поиска информации в одном приложении или интегрированной среде нескольких приложений, так и в смысле разнообразия функциональных возможностей СУБКД.

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

Анализ работ, посвященных формализации ДМД,' позволяет выявить ряд существенных недостатков их использования в качестве аппарата моделирования ДИС.

1. Попытка имитировать динамичность информационной структуры в рамках традиционных подходов (сетевой, иерархический, реляционный) приводит к нарастающей сложности описания структуры и аппарата манипулирования данными.

2. Моделирование ДИС сетевыми моделями с объектно-ориентированными свойствами не достаточно эффективно из-за отсутствия хорошо разработанного формального аппарата манипулирования данными.

3. Формализация ДИС в рамках гипертекстовой технологии сложна из-за отсутствия набора формальных методов описания гипертекстовой структуры и аппарата манипулирования данными.

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

Цель диссертационной работы состоит в разработке и исследовании формальной математической модели ДИС для улучшения эффективности СУБКД за счет упорядочения структуры данных и расширения функциональных возможностей СУБКД посредством динамической визуализации информационных взаимосвязей. Достижение указанной цели предполагает решение следующих задач. Основные задачи:

1. Построение математической модели комплексированных данных, позволяющей оперировать неким активным подмножеством объектов с учетом статики и динамики оперирования с ними.

2. Исследование свойств построенной модели в аспекте ее адекватности моделируемой структуре, устранения аномалий доступа, синтеза принципов и алгоритмов.

3. Построение алгебры (исчисления) активных подмножеств информационных объектов с определением объектов информационного пространства и набора операций манипулирования объектами, исследованием свойств предложенных операций и полноты информационного пространства.

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

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

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

- определены понятия ограниченных сетей Петри и их подкласса, ограниченных ТЭ-

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

- сформулированы и доказаны теоремы, следствия и утверждения, раскрывающие особые свойства ограниченных сетей Петри и ограниченных Т8-сетей Петри, главными из которых являются:

* теорема о разрешимости задачи определения достижимости любого сценария и о принадлежности этой задачи классу ОТ- полных комбинаторных задач для ограниченных сетей Петри;

* теорема о существовании достаточного признака определения достижимости любого сценария и ограниченности разметки в ограниченной сети Петри;

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

* теорема о свойствах ограниченных Т5-сетей Петри;

- построена алгебра (исчисление) над множеством ограниченных ТЭ-сетей Петри, порожденном из класса примитивных ограниченных сетей единственного типа, с доказательством полноты информационного пространства;

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

Достоверность научных положений подтверждается результатами синтеза логической схемы мультимедийного медицинского атласа «Система кроветворения» выполненного по методам и алгоритмам, предложенным в диссертации.

Практическая значимость. Использование математического аппарата ограниченных сетей Петри для моделирования ММБД позволяет легко и наглядно представлять структуру динамического информационного пространства такой БД и сводит многие проблемы ДИС (алгоритмы контекстного поиска, выявление возможных аномалий доступа, реструктуризации БД и т.п.) к известным задачам теории сетей Петри. Введенное понятие ограниченной ТЭ-сети, отражающее специфику ДИС, предполагает возможность формального описания процессов функционирования и модификации ММБД. Построенная алгебра ТЗ-сетей позволяет осуществлять тождественные преобразования сетевых моделей ДИС, что предполагает формальное определение правил конструирования сетей. Алгоритм построения ярусного макета и разработанный на его' основе символьный язык описания данных позволяют эффективно решать задачи проектирования и администрирования ММБД автоматически х использованием компьютерной обработки. Все теоретические положения диссертации доведены до вида алгоритмов, позволяющих синтезировать логические схемы БД, поддерживающих динамические

информационные структуры.

Апробация результатов. Полученные результаты апробированы в докладах на конференциях: Республиканской научно-технической конференции «Биомедицинские приборы и системы» (Рязань, 1994), 2-ой Всероссийской с участием стран СНГ конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-95) (Ульяновск, 1995), в докладах на научных конференциях в рамках Дней Науки в НовГУ (Новгород, 1995), (Новгород, 1996), (Новгород, 1997).

Публикации: По теме диссертации написано 5 работ, из них 2 опубликовано и 3 депонировано в ВИНИТИ.

Все научные и практические результаты получены соискателем самостоятельно.

Структура: Диссертационная работа состоит из введения, 4 глав, заключения и списка использованных источников, включающего 72 наименования. Она изложена на 117 страницах машинописного текста и содержит 31 рисунок .

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

Во введении дается краткое изложение проблемы логического проектирования ММБД, ориентированных на динамическую визуализацию активных подмножеств информационного пространства. Отмечается актуальность задачи моделирования ДИС и целесообразности ее формализации.

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

- традиционная задача хранения изображений с сопутствующей информацией в рамках некой открытой системы;

- визуализация динамических срезов информационного пространства с возможностью их перебора;

- реализация контекстного поиска, при котором пользователь сам определяет маршрут поиска;

- поддержка независимости методик, используемых в рамках модели от внутренних форматов информационных элементов;

- наличие простых средств реструктуризации базы данных;

- интегрированный поиск, позволяющий пользователю извлекать информацию одновременно из нескольких приложений;

- построение не только справочных, но и тестовых систем.

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

Далее предлагается следующее формальное определение ДИС.

Пусть множество V - множество информационных элементов, порождающих информационное пространство, есть объединение множеств VltV2 ,-- Vn: V = Vl vjV2Kj..xjVn, где Vt - множество информационных элементов определенйого типа, V} п V2C\...r\Vn = 0 .

Множество v, = jv^,v,2 ,... v"| определяется, как кортеж из декартова произведения множеств Vx, V2,...Vn: vi eV, x V2 X-x.Vn> где v,1 eV:> vf eV2>..., v" eV„.

Динамический срез информационного пространства или сценарий формально определено в работе, как любое подмножество (сочетание) s' кортежа v,, кроме пустого

sf cv, \fk = 1,2 • (2п - 1) и sj s", если Ыг.

Множество Syi>ty2X х)/ = , ^ ,...), где S: - множество всех возможных сценариев кортежа v,, определено автором как полное множество сценариев, определенное на декартовом произведении множеств V! х V2 х ...х Vn.

Тогда динамическое информационное пространство S, порожденное множеством информационных элементов V.= Vj u V2 и.. \JV„, есть конечное подмножество полного множества сценариев, определенного на декартовом произведении

Сценарии S1 и Sj являются смежными, если существует событие х еХ , где X - множество допустимых событий системы, такое что из состояния S, система переходит в состояние Sj посредством функции перехода f{xtJ): S, —> Sг

Функция перехода определена как преобразование, позволяющее при определенных условиях (если существует разрешающее событие xtJ е.AT, где X - множество допустимых событий) перейти из состояния S, в состояние Sj:

Операция контекстного поиска определена как конечная цепочка преобразований Ф = {fim\ > /m,m2 >■■■ fmkj j: —^> позволяющая перевести систему из состояния Si в состояние >S где сценарии 5, и Sj могут быть не< смежными.

Предложенное определение информационного пространства позволяет ввести one-

рацию выборки по множеству /I а V, результат которой можно определить как множество сценариев # = {.У, | // с: } ■

Не ключевые требования к СУБКД вытекают из ключевых определений и, следовательно^ влияют на определение адекватности формализуемой модели,т.е.фор-мально определенные ключевые требования мог^т быть предложены в качестве критериев адекватности искомой логической модели целям и задачам моделирования ДИС.

Анализ существующих подходов к моделированию ДИС позволяет выделить три основных класса БКД: базы образных данных, ММ и гипертекстовые системы и объектно-ориентированные базы данных (ООБД). К первому типу БД относятся системы, появившиеся "назаре" возникновения проблемы комплексного хранения разнотипных данных. Концепция их построения базируется на классическом реляционном подходе и не отвечает требованиям, предъявляемым к базам с комплексированной информацией, поддерживающим динамическую визуализацию объектов. ММ и гипертекстовые системы решают задачу комплексного хранения и динамической визуализации данных, но для них характерна жесткость структуры связей и затруднительность реструктуризации и селекции данных. Объектно-ориентированный подход позволяет избежать указанных недостатков, но отличается недостаточной формализованностью, отсутствием общепринятой терминологии и стандартов.

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

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

множество объектов, не существует,

В качестве решения возникшей проблемы автором предложена концептуальная модель ДИС: мультимедиа-приложение А есть совокупность А = В,Р,Щ, где V -множество информационных элементов, объединяющее разные множества элементов разного типа V = УХ У1 пУ2г^...глУп - 0; В-множества разрешенных переходов; 5-множества сценариев; ^иН-отображения Т7:^ —> В) Н:Б —>

Информационное наполнение сосредоточено в информационных элементах множества V. Совокупность одновременно активных элементов названа автором сценарием 5,. При наступлении какого-либо системного события (при срабатывании одного из переходов) или сразу после запуска приложения подмножество активных информационных элементов с: V, названное сценарием, вызывает определенную реакцию пользователя, выражающуюся в инициализации одного из равновероятно разрешенных (для данного подмножества ^) переходов. Разрешенное подмножество переходов из всего множества вычленяет функция F. Наконец, каждый переход, в свою очередь, посредством отображения Н, определяет свое подмножество активных (видимых) элементов, определенное как сценарий.

Введенная модель хорошо согласуется с критериями, определенными ранее Динамическое информационное пространство, порожденное множеством информационных элементов V, есть множество сценариев 5. Сценарий есть множество активизированных в некоторый момент времени разнотипных элементов, используемых в одном контексте. Контекстный поиск определяется как множество переходов

г = К таких, что ——Функция перехода с множеством воз-

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

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

Ограниченная сеть Петри N есть пятерка N = {Р,Т,Р,Н,М0}, где Р = {р, }, г = 1 ,п - множество позиций, Т = |, у' = \,т - множество переходов, причем РпТ = 0, и Н - отображения .Р:Р —> Т\ Н:Т —> Р, задаваемые матрицами инцидентности Р :Р х Г -V {ОД} и Н:Тх Р—> (ОД), Мв:Р-> {0,1} - начальная маркировка или разметка.

В рамках данной модели информационные элементы мультимедиа-приложения

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

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

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

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

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

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

действий в гиперсегментной структуре.

В рамках предложенной модели мультимедиа-приложения имеет место теорема.

Теорема 1. Задача достижимости переходов для ограниченной сети Петри разрешима и по крайней мере не менее трудна, чем задачи класса №-полных комбинаторных задач.

Доказательство разрешимости задачи сразу следует из введенного ограничения на количество фишек в каждой позиции и конечности дерева достижимости. Доказательство второго утверждения проводится через сведение известной ЯР-трудной задачи о выполнимости КНФ к задаче достижимости перехода в ограниченной сети Петри.

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

Теорема 2. Пусть дана сеть Петри N = [Р, Т, Р, Н, М0} , где Р - множество позиций, Т- множество переходов, Р и Н - отображения Р:Р->Т; Н:Т Р, М0 - начальная разметка: где Утк е М0 тк <1.' •

Тогда если считать матрицы инцидентности ? « Я логическими функциями., то для того чтобы любой переход V* еТ был достижим из .разметки М0 и разметка любого места Р1 была ограничена при функционировании сети, т.е.\/р( а Р т^р^ < 1

т м+1 п I ч ..

достаточно выполнения условия: п и О Кк )= {гие>

7=1 1=1 ' 1*1

где П,и,—> - логические функции конъюнкции, дизъюнкции и импликации, соответственно; /¡у е Р',кЛ ей"* - соответствующие элементы матриц инцидентности, причем расширенная матрица Н * получена из матрицы Я путем дополнения строкой следующим образом: 1 =1, если вершина р- имеет начальную разметку; /гт+1 = 0, в противном случае.

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

Это сужение класса рассматриваемых сетей является не существенным, поскольку имеет место следующая теорема.

Теорема 3. Всякую сеть Петри N о, все переходы которой достижимы из разметки Ма молено представить позиционно эквивалентной из разметки М0 сетью Л^, с топологией удовлетворяющей условиям теоремы 2 о достаточных условиях достижимости.

Для доказательства теоремы строится алгоритм, модифицирующий топологию сети

А/0 в сеть Л^, а затем доказывается, что и А^ имеют одинаковые деревья достижимости.

Сформулированная и доказанная теорема означает, что введенные ограничения на топологию сети не сужают класс приложений, моделируемых ограниченными сетямк Петри с достижимыми переходами, что позволяет использовать их в качестве адекватного аппарата моделирования ДИС.

В третьей главе предлагается алгебра ограниченных ТБ-сетей Петри.

Состояние системы в некий момент времени определяется сценарием. Сценарий есть набор активизированных в данный момент информационных элементов из допустимого множества всех информационных элементов Р = ,р2>---рп), т.е. сценарий

^ есть помеченное подмножество вершин из множества Р: ¡---Р^ |, где

р( Р, У, с Р, т{{р[) = 1.

Сценарии связаны между собой символами-переходами. Система функционирует переходя от сценария к сценарию: сценарий 5*,, описывающий состояние системы в некий момент времени, подразумевает возможность посредством перехода г перехода системы в другое состояние, описываемое сценарием Б}. Переходов по сценарию 5, может быть несколько, выбор любого из них зависит от действий пользователя, наблюдающего на экране визуализированные элементы, но каждый из переходов однозначно переводит систему в состояние, соответствующее данному переходу.

Определение(операция связывания сценариев) Сценарий связывается через переход ?со сценарием Б] (5, —-—> Б; ) , если некоторое подмножество л* , состоящее из вершин, входящих в сценарий : = |р^ , р^2,... р*г | с. инициализирует активизацию некоторого подмножества вершин, входящих в сценарий SJ :

Сеть, порожденная связыванием посредством перехода сценария ^ со сценарием 8 определенных на множестве всех допустимых сценариев, названа примитивной ограниченной Т8-сетъю, для которой Р = и Б] , Т = функции инцидентности формируются следующим образом: . .

Р:РхТ^> {1} УреЯ,, РхГ^{0} VpGSJ, H:TxSl^{0},TxSJ-^{1}.

Начальная разметка М0 :Р—» |0Д], причем гп^{рк) = 1, если рк

И то{Рк)=°>йс™ рк

Подкласс ограниченных сетей Петри, порожденный множеством символов-переходов Т на множестве сценариев определен как класс ограниченных ГУ-сетей.

Теорема 4. Выделенный класс ограниченных Г^-сегей обладает рядом свойств.

Свойство 1 Ограниченная ТБ-сеть Петри в процессе функционирования переходит от состояния к состоянию в результате последовательного срабатывания цепочки переходов, равновероятно выбираемых пользователем из разрешенного для данного состояния системы подмножества переходов. Смена состояний системы обуславливает смену сценариев. Причем, все фишки, пометившие вершины сценария Sj в результате срабатывания перехода перейдут к вершинам сценария в результате срабатывания перехода 1к, разрешенного в рамках сценария 8}. Другими словами, для любого перехода ( все инцидентные ему вершины {р,]...р,к ], определяющие его срабатывание: а) либо являются размеченными изначально, б) либо существует хотя бы один другой переход такой, что вершины рл...р1к приобретают разметку все одновременно в результате срабатывания .

Свойство 2 Класс является подклассом ограниченных сетей Петри, поскольку количество фишек, помечающих вершину, не может быть больше 1.

Свойство 3 Ограниченные 75-сети являются подклассом сетей Петри, обладающих свойством ¿-ограниченности, при к= 1, что является именно свойством топологии, приобретенным благодаря особой структуре ТЯ-сетя (свойство 1).

Свойство 4. Для ограниченной Т5-сети условие теоремы 2 выполняется для любого множества элементов, названного сценарием, и для любого перехода, разрешенного в рамках соответствующего сценария, если какой-либо сценарий определен (размечен) как начальный, т.е. ТЭ-сеть является живой сетью.

Свойство 5. Множество допустимых переходов однозначно связано с множеством сценариев, определяющих множество состояний системы. Однозначность связи не является взаимной, поскольку в рамках одного сценария возможно существование нескольких разрешенных переходов. Множество переходов есть множество пар

(8, —где трактуется как некая функция перехода, однозначно связанная с

парой , Б] ), причем, если (5, ——> ^) и —> ), то ? SJ о tк ^ .

Следствие. Мощность множества сценариев не больше, чем мощность множества переходов, увеличенное на 1: < [Г| + 1.

Свойство 6. Множество всех допустимых разметок (сценариев) в Т8-сети конечно, и его мощность ограничена сверху числом 2п+1 - 1.

Свойство 7. Множество переходов в ограниченной ГУ-сети Петри есть множество, динамически формируемое в процессе конструирования или формирования струкгурь сети. Множество это конечно, поскольку определяется бинарным отношением

р= ,У; , где Я,, SJ - сценарии из допустимого множества сценариев У, г ф /.

Бинарное отношение является подмножеством декартова произведения множества £ само на себя: /?с:УхУ. Отсюда следует конечность множества Т, поскольку

|/з| < к(к - 1), где А = |>5|. Тогда |Г| = |/?| < 2"(т." -1)<22".

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

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

Операция напожения{(®)}. С помощью этой операции сети объединяются или накладываются одна на другую. Операция имеет смысл, если обе объединяемые сети определены на одном и том же множестве информационных элементов Р :

Рх сР, Р2^Р, Р}глР2*0.

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

Операция разметки{1( )} Унарная операция, помечающая головные места перехода £ в сети N, Операция позволяет дополнить множество изначально размеченных вершин множеством входных вершин перехода г, если объявлено, что данный переход разрешается из начального состояния системы.

Операция итерации (зацикливания) Д/,Унарная операция, связывающая

множество хвостовых мест перехода и головных мест перехода tJ сети N через переход г'.

Операция присоединения {(;)}. Операция объединяет две сети и А^, определенные на разных множествах информационных элементов Р,г^Р2 = 0, в одну сеть, сливая вершины из бинарного отношения р = (Х,¥)={(х1>у]) | л, б Р2} ■

Операция выделения подсети {(\)} Унарная операция, результатом которой является несвязная сеть, состоящая из исходной сети с разорванным г-переходом и примитивной сети; образованной этим'же переходом.

Введенные операции позволяют конструировать ограниченные ГУ-сети из примитивных ограниченных ГУ-сетей и раскладывать исходные сети на примитивы. При этом

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

Утверждение. Множество ограниченных ГЗ-сетей Петри является замкнутым относительно введенных операций.

Для доказательства этого утверждения вводится условие, которое позволит определять, является ли порождаемая сеть ограниченной га-сетью. Таким достаточным и необходимым условием является условие свойства 1 ограниченных га-сетей. Необходимость этого условия заложена в самом свойстве: любая ограниченная 75-сеть обладает свойством 1. Вместе с тем, можно показать, что любая ограниченная сеть, обладающая этим свойством является ограниченной га-сетью.

Доказательство самого утверждения проводится через рассмотрение по отдельности каждой из введенных операций на предмет замкнутости множества ограниченных Т8-сетей Петри относительно рассматриваемой операции.

Сформулированное утверждение позволяет ввести формальное определение ограниченных Г^-сетей Петри.

1 .Сценарий есть ограниченная га-сеть Петри.

2.Если и являются сценариями, то сеть, порожденная операцией связывания есть ограниченная га-сеть Петри.

3.Если и ■ ограниченные га-сети Петри, то сети, порожденные //, и 7У2 с помощью операций наложения, разметки, сливания позиций, итерации и выделения, являются таюке ограниченными га-сетями Петри.

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

1 .Сеть из () - формула.

2.Еслиу4 - формула и то 1(А, Г,,) и АМ1 - формулы.

3.Если А - формула и £,, - допустимые символы-переходы, то + ])-тоже формула.

4 .Если А и В - формулы, то (А® В) и (А;В) - тоже формулы.

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

дистрибутивности и рефлексивности введенных'Операций. Тождественные преобразования формул позволяют конструировать Т$-сети из подсетей и проводить первоначальный анализ свойств получаемых сетей.

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

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

1 .Макетируемая сеть N дополняется корневой парой "вершина - переход" с целью переноса начальной маркировки в одну вершину. Вспомогательная вершина рь образует нулевой ярус.

2. Любая вершина исходной сети N представлена в макете И' столько раз, сколько дуг входит в данную вершину.

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

Ярусный макет обладает рядом свойств.

Свойство I Ярусный макет является ациклическим графом.

Свойство 2 Количество ярусов конечно:

количество ярусов < количества переходов исходной сети N

Свойство 3 Деревья достижимости сети N и ее ярусного макета Ы' совпадают.

Свойство 4. Если исходная сеть N удовлетворяет условиям достижимости, то во все переходы 7с -го яруса идут дуги из вершин, принадлежащих только к - 1 -му ярусу.

Свойство 5 При осуществлении "стягивания" множества экземпляров' каждой вершины обратно в одну позицию, топология получаемой из макета И' новой сети Аг" будет совпадать с топологией исходной сети , т.е. N" = N .

Введенное понятие ярусного макета позволяет ввести язык описания ограниченных сетей Петри. Базовым понятием ограниченной Г5"-сети является сценарий, описывающий состояние системы в некоторый момент времени. Переходов от одного сценария к другому может быть несколько, но каждый инициируемый сценарий однозначно связан с символом-переходом.

На рис. а) представлен фрагмент сети, являющийся примитивной ограниченной ГУ-

сетью, связывающий сценарий со сценарием .

Рис. а) Фрагмент сети, связывающий сценарий 51, со сценарием . б) Ярусный макет примитива, представленного на рис.а)

Построим ярусный макет представленного на рисунке примитива. К вершинам ,р,2,.. .р11 е будет добавлена корневая пара "вершина - переход". Назовем добавленную вершину 5,-. Вершины из сценария SJ можно заменить на его имя, поскольку подмножество вершин, составляющих сценарий SJ будет, в свою очередь, представлено корневой парой "вершина - переход" в соответствующем ярусном макете. Тогда ярусный макет представленного на рис.а). примитива будет выглядеть следующим образом (рис.б)).

Символьное описание подобной структуры может быть предложено следующее:

]>р\ где элементы, составляющие,, сценарий 5,:

Р^;} = 1 с Р - есть подмножество вершин, помечаемых в результате

срабатывания инцидентного им перехода, I) - символ-переход из множества разрешенных символов-переходов в рамках данного сценария. В одном сценарии один и тот же информационный элемент не может быть активизирован дважды, те. все информационные элементы встречаются в таком описании только один раз: р\ Ф V/ / у . Каждый переход I} из множества разрешенных символов-переходов жестко связан со сценарием, соответствующим состоянию системы , в которое она переходит .посредством данного перехода. Тогда переход tJ в описании сценария может быть заменен ссылкой на сценарий , соответствующий состоянию системы после срабатывания перехода £ , при этом описание ярусного макета сценария упрощается:

Очевидно, что как сам ярусный макет примитива , так и все конструкции с дру-

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

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

Тогда ограниченная Т^-сеть Петри Е есть пара массивов: £ = где г

персегментная структура Е^ описывается последовательностью записей разной дл ны = ,У£ = |, где элемент - запись типа (*), элемент описыва

начальное состояние системы и соответствует начальной разметке' М0.

Подобная структура, описывая последовательность изменений состояний систем будет, очевидно, -конечной в силу конечности множества символов-переходс

< ¡Т| + 1 < 22" (свойство7 ограниченных Т8-сетей).

Информационный массив = = \_р],р2 >- -Рп} хранится отдельно от опис ния структуры, что тоже удобно для различных модификаций как структуры, так и < мих информационных массивов. Кроме того, описанная таким образом структура зависит от формы представления и внутреннего формата информационного объек базы данных, поскольку формат информационных элементов может быть внутренш свойством каждого сценария или самого элемента.

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

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

Завершает главу алгоритм синтеза логической схемы динамической базы данных пример его возможной реализации.

ЗАКЛЮЧЕНИЕ

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

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

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

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

3 .Сформулированы и доказаны теоремы, следствия и утверждения, раскрывающие обые свойства ограниченных сетей Петри и ограниченных Т8-сетей Петри, главными которых являются: 1)теорема о разрешимости задачи определения достижимости )бого сценария и о принадлежности этой задачи классу ОТ- полных комбинаторных зач для ограниченных сетей Петри; 2)теорема о существовании достаточного призна-определения достижимости любого сценария в ограниченной сети Петри; 3)теорема юзможности преобразования любой ограниченной сети Петри с достижимыми передами в позиционно эквивалентную сеть, удовлетворяющую достаточному признаку стижимости; 4)георемао свойствах ТБ-сетей.

4.Построена алгебра (исчисление) над множеством ограниченных Т5-сетей Петри, рожденном из класса примитивных ограниченных сетей единственного типа, с дока-гельством полноты информационного пространства;

5.Разработан символьный язык, описывающий динамическую информационную )уктуру средствами ограниченных Т8-сетей Петри, с формальным аппаратом мани-тирования комплексированными данными, с доказательством полноты языка и под-зжки физической и логической независимости описания данных;

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Смирнова Е.И. Вопросы моделирования биомедицинских систем с комплексными данными //Биомедицинские приборы и системы: Тез.докл.Респ.научн,-гехн.конф. Рязанск.гос.радио-техн.акад. 12-15 апреля 1994г. - Рязань, 1994. С.13-14. Гузеев С.А., Смирнова Е.И. Организация интерактивных взаимодействий в щециализированной системе управления шперсегментяой базой графической гнформации //Распознавание образов и анализ изображений: перспективные информационные технологии: Тез.докл.Респ.научн.-техн. конф.РОАИ-2-95 В 4-х частях. Часть2.-Ульяновск, 1995.- С.51-54.

Смирнова Е.И. Моделирование динамических информационных структур. НовГУ.

- Новгород, 1998 - 20с.-Деп.в ВИНИТИ

4. Смирнова Е.И. Ограниченные сети Петри и проблема.достижимости переход« НовГУ. - Новгород, 1998 -20с.-Деп.в ВИНИТИ

5. Смирнова Е.И. Алгебра ограниченных TS-сетей Петри. НовГУ. - Новгород, 199! 14с.-Деп.в ВИНИТИ

Лицензия ЛР№ 020815 от 21.09.98.

Подписано в печать 19.11.98. Формат 60x84 1/ 16. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № Издательско-полиграфический центр

Новгородского государственного университета им. Ярослава Мудрого. 173003, Новгород, ул. Б. Санкт-Петербургская, 41. Отпечатано в ИПЦ НовГУ. 173003, Новгород, ул. Б. Санкт-Петербургская, 41.

/

НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. ЯРОСЛАВА МУДРОГО

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

Специальность 05.13.18 - Теоретические основы математического моделирования, численные методы и комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

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

СМИРНОВА ЕЛЕНА ИГОРЕВНА

УДК 681.3

Научный руководитель: д.т.н., проф. Г.М.Емельянов

Новгород - 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ....................................................................................................4

1. МОДЕЛИРОВАНИЕ ДИНАМИЧЕСКИХ ИНФОРМАЦИОННЫХ СТРУКТУР. ПОСТАНОВКА ЗАДАЧИ..................................................11

1.1. Постановка задачи на функциональном уровне............................12

1.2. Критерии адекватности формальной модели................................15

1.3. Анализ предлагаемых подходов и выбор метода моделирования..........................................................................................19

1.4. Концептуальная модель и общая формальная постановка задачи .........................................................................................................25

1.5. Выводы по главе...............................................................................32

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИНАМИЧЕСКИХ ИНФОРМАЦИОННЫХ СТРУКТУР И ИССЛЕДОВАНИЕ СВОЙСТВ ПОСТРОЕННОЙ МОДЕЛИ.......................................................................34

2.1. Моделирование гиперсегментных структур ограниченными сетями Петри ...........................................................................................36

2.2. Комбинаторная сложность задачи достижимости сценариев......42

2.3. Регуляризация структуры ограниченной сети Петри и достижимость переходов ........................................................................48

2.4. Эквивалентность сетей с полным множеством достижимых переходов ..................................................................................................55

2.5. Выводы по главе...............................................................................60

3. АЛГЕБРА (ИСЧИСЛЕНИЕ) ОГРАНИЧЕННЫХ ТБ-СЕТШ ПЕТРИ...........................................................................................................62

3.1. Определение объектов информационного пространства..............63

3.2. Операции над ограниченными TS-сетями Петри..........................69

3.3. Полнота алгебры(исчисления) ограниченных Г5-сетей

Петри относительно введенных операций.............................................74

3.4. Тождественность преобразований ограниченных TS-сетей Петри .......................................................................................................78

3.5. Выводы по главе...............................................................................90

4. ЯЗЫКОВОЕ ПРЕДСТАВЛЕНИЕ ОГРАНИЧЕННЫХ Г5-СЕТЕЙ ПЕТРИ...........................................................................................................92

4.1. Ярусный макет как структурная единица языка оперирования данными и его свойства...........................................................................93

4.2. Символьное описание ограниченных Т^-сетей Петри................97

4.3. Администрирование гиперсегментной базы данных, описанной в терминах символьного языка .....................................104

4.4. Правила конструирования живых ограниченных Г^-сетей Петри и полнота языка описания данных...........................................111

4.5. Пример реализации программного комплекса, построенного на предложенных принципах, для построение логической схемы справочника-атласа системы «Схема кроветворения»......................117

4.6. Выводы по главе..............................................................................124

ЗАКЛЮЧЕНИЕ .........................................................................................125

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ....................................128

ВВЕДЕНИЕ

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

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

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

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

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

В настоящее время в теории баз данных приняты следующие определения [1-3]. Под базой данных (БД) понимают именованную совокупность данных, отображающую состояние объектов и их отношений в рассматриваемой предметной области. В соответствии с этим система управления базой данных (СУБД) выступает как совокупность средств, предназначенных для создания, ведения и совместного использования баз данных многими пользователями.

Под комплексированными данными [4,5] понимается совокупность разнотипных данных, используемых в одном контексте как единый объект предметной области. База комплексироеанных данных (БКД) определяется как некая поименованная структура, структурной единицей которой является такая совокупность. Тогда система управления базой комплексироеанных данных (СУБКД) есть комплекс программных, языковых, организационных и технических средств, предназначенных для централизованного накопления и коллективного использования комплексированной информации.

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

данных [1] разделяется на три основных уровня абстракции: внутренний (физический), концептуальный и внешний, связанный с пользовательскими представлениями предметной области. Центральное место по значимости занимает концептуальный уровень, представленный логической моделью данных. Логическая модель описывает предметную область средствами некоторого формализма, на нее ориентированы средства физической обработки данных и пользовательские представления об информационной среде.

Логическая схема [1,2,7-12], определяющая логическую модель, для независимости данных должна содержать определения только информационного содержания и не может каким-либо образом учитывать физическую структуру хранения данных или стратегии доступа. Таким образом задача логического проектирования имеет самостоятельное важное значение при создании базы данных.

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

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

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

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

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

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

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

Теоретические исследования по определению и формальному описанию динамических информационных структур ведутся с середины 80-х годов и берут свое начало от работ Нельсона (1965). Разработками в этой области занимались Янкелович [13,14] и Мейровиц [13-16], Дейкстра [17,18], Холас [17,19], Бейбер [20], Ленон и Маурер [21-^3], Стоттс и Фурута [26], Конклин [27] и другие.

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

1. Попытка имитировать динамичность информационной структуры в рамках традиционных подходов (сетевой, иерархический, реляционный) приводит к нарастающей сложности описания структуры и аппарата манипулирования данными.

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

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

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

разнотипную информацию, ухудшая эффективность использования таких систем.

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

разработка и исследование формальной математической модели динамической информационной структуры для улучшения эффективности системы управления базой комплексированных данных за счет упорядочения структуры данных и расширения функциональных возможностей СУБКД посредством динамической визуализации информационных взаимосвязей.

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

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

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

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

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

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

ГЛАВА 1

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

Множество связей между информационными объектами базы данных является неотъемлемой частью любой информационно-поисковой системы. Это множество позволяет найти не только отдельный объект с заданными свойствами, но и произвести выборку объектов по определенному признаку. От простоты и возможности формального описания подобной структуры связей, от ее адекватности целям и задачам поиска существенно зависит эффективность СУБД. Представление о такой структуре дает логическая модель данных, позволяющая формально определить объекты и связи между ними и описать аппарат манипулирования данными в рамках единой системы.

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

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

Гла�