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

МОСКОВСКИ» ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫМ ШКТНТУТ

( чехинчсскни униперсшгг)

На правах рукописи СЕМЕНОВ Александр Сергеевич

Разработка и исследование методов и ср

информационных объектов на основе модели "Система Взаимодействующих Таблиц"

Специальность 05.13.11 " Математическое и программное обеспечение вычислигсльнмх машин, комплексов, систем и сетей"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1996

Работа выполнена в Московском государственном авиационном институте.

Научный руководитель: кандидат физико-математических наук,

доцент Черныншв Л.II.

Официальные онноненты: академик Международной

академии информатизации, доктор технических наук, профессор Юдицкий С. А.

кандидат физико-математических наук, доцент Головачев А.Г.

Ведущая организации: Московский государственный технологический университет "СТАНКИН"

а?

Защита состоится » 2} ~ уд а и 1996 г. в ¡з- _ часов на заседании днссертацнонного Сове! а К 053.18.09 в Московском государст венном авиационном институте.

С диссертацией можно ознакомиться в библиотеке МАИ.

Адрес института: 125871, Москва, А-80, Волоколамское ш., 4. Автореферат разослан " 2 2- " ot r^jz/ij^ 1996 г.

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

кандидат физико-математических наук, г

доцент Потанина

Общая характеристика работы

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

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

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

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

Цель н задачи работы. Основными целями и задачами диссертации являются:

• исследование существующих методов и средств анализа информационных объектов;

• разработка единой формальной модели (СВТ-модели) и исследование ее свойств;

• сравнительный анализ СВТ-модели с сетями Петри;

• разработка представления СВТ-модели в виде автомата параллельной обработки зрапзакций (элеметарных целостных операций над данными);

• разработка методологии анализа информационных объектов на основе СВТ-модели.

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

Научная ншинпа. Научная новизна и тсорешчсская значимость исследования заключается в следующем.

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

2. Исследовано соошошение между классом СВ ¡'-моделей н раскрашенных сетей Пефи.

3. Разработана меюдологпя анализа информационных объектов на основе СВТ-модели, в том числе разрабокш подход к анализу и конструированию произволе! вешних объектов (механосборочного производства) ю типовых блоком СВ ¡'-модели и введена классификация блоков.

Практическая ценное!ь. Разработанная метдология анализа информационных объектов на основе СВТ-модели была использована при проектировании распределенного программно-технического комплекса оперативного управления производством и позволила наглядно представить распределенную структуру комплекса, объединить статическую и динамическую спецификацию проема, что в совокупноеш повлияло па качество создаваемого программного обеспечения и снизило сроки его разработки.

Анализ информационных объектов с использованием методологии на основе СВТ-модели позволяет решить комплекс задач проектирования (в том числе имитационного моделирования) информационных объектов: верификацию (доказа1ельс1во правильности) ("/¿'/'-модели; определение ошммаль-но1 о размещения таблиц (посредством трансформации ('/¿'/'-модели и исследования ее структурных свойсш); исследование си 1уаций тупика и взаимного влияния (при обращении п изменении данных таблиц несколькими процессами); прогнозирование поведения ('/¿'/'-модели (определение возможною целевого состояния таблиц на дереве достижимых состоянии при определенных начальных значениях таблиц).

Разработано эксперимешальное инсгруметалыюе средство, позволяющее проводить имитационное моделирование на основе СВТ-модели.

Резуль тат 1.1 диссертации могут бы и» использованы при анализе сложных информационных объектов.

Апробации работы. Основные результаты диссертации докладывались и обсуждались па

• второй международной конференции "Проблемы упраплення в чрезвычайных ситуациях" (г. Москва, 1994 г.);

• научно-исследовательском семинаре в МАИ (1993-1994 г.);

• научно-исслсдочатсльском семинаре п И11У (1994-1995 г.);

• научно-техническом семинаре в МАПО (1994 г.);

• межвузовской научно-технической конференции "Динамика нелинейных дискретных электротехнических и элскфонных систем". ( г. Чебоксары, 1995 г.).

Публикации. По теме диссертации опубликовано 7 научных статей.

Структура и объем работы. Диссертация состоит нз введения, пяти глав, заключения, библиографии и приложений, отражающих инструментарий исследования. Основной текст работы изложен на 130 страницах, содержит 34 рисунка, 1 таблицу, бнблиофафию из 60 наименований. Приложение содержит 7 страниц.

Содержание работы

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

В первой главе рассматриваются известные методологии анализа информационных объектов: объектно-ориентированного анализа, структурного анализа, системного проектирования и анализа на основе сетей Петри, анализа на основе новых интегрированных методологий и методы разработки экспертных систем (рис. I). Обосновывается целесообразность разработки и место методологии анализа на основе СВТ-модели.

В рамках методологии объектно-ориентированного анализа (С. Шлеер и С. Меллор) используются три уровня описания: информационная модель (объекты описываются реляционной ER-моделью, где ER - аббревиатура Entity-Relationships -"cyuinocmi,-связь" ), модель жизненных циклов объектов (выражаемых моделями состояний) и модель потоков данных действий (совокупность действий образует процессы, описываемые DF-моделыо, где DF- аббревиатура Data Flow - модель потоков данных).

В рамках методологии структурного анализа существуют два двухуровневых подхода.

Первый подход предложен Д. Россом и предполагает последовательное применение на первом уровне S А-модели, на втором - реализацию описания алгоритмов в виде входо-выходных преобразователен. Два уровня интегрированы п методологию структурного анализа и проектирования SADT (где SADT- аббревиатура Structured Analysis and Design Technique).

, Мсю.1(хк>1ня шинш ;

1 (Гсинс-Сирсона) !

: _ -. I

I'uc. I. Уровни моделей в методологиях анализа информационных объектов

Другой подход и рамках структурного анализа предложен К.Гейп и Т.Сареоном. Первый уровень подхода предс1авлен DF-моделыо, второй описанием алгоритмов.

Системное проекшрованпе и анализ на основе сетей Пегри: классических сетей Пегри и их модификаций, раскрашенных С'/'-сетей (где CP аббревиатура - Colored I'etri). предикашых I'rt-cenicti (где Pit аббревиатура -Predicate transition) - представляется одним уровнем описания (моделью состояний), что позволяет исследовать свойства системы путем аналитического и имитационного моделирования.

Метод!,1 разработки экспертных систем базируются па одноуровневых подходах, в основу которых положена модель знаний. Процесс разработки модели экспертной системы может быть рассмофсн в два взаимосвязанных этапа. На первом описывается представление знаний (ЕЯ-моделью, семантической сетыо, фреймами, продукционными правилами, логикой предикатов, моделью доски объявлений). На втором этапе к описанным знаниям применяются правила вывода.

Интеграция различных уровней методологий (на рис. 1 обведены овалом) позволяет создавать новые двухуровневые меюдологии с расширенными возможностями. Например, интеграции SA-Moi)<vwii и Сl'-сетсй, интегра-

цнн DF-модели и coin lleipit n l'ROT-сспш (где /7Ш/'аббревпа íypa PROcess -Translated - coin преобразованных процессом).

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

Во второй глапс дасгси формальное определение СНГ-модели и рассматриваются се свойства.

В силу сложности С ИТ-модели она вводится поэтапно и формируется в результате выполнения двух формальных процедур преобразования.

Первая процедура выполняет преобразование статического табличного описания (информационной модели) в описание взаимодействия таблиц (в потоковую модель). Взорая процедура преобразует полученное описание взаимодействия таблиц (1И'-о11исание)ныюсрсяс'1ъсшю в СВТ-модель, имеющую графическое представление.

На примере "Поставщик-Потребитель" (поставщик продает заказанный товар потребителю) рассматриваются зри описания, используемые для формирования СВТ-модели: статическое табличное описание, описание взаимодействия таблиц и описание СВТ-модели.

Статическое табличное оннсаннс. Статическое табличное описание определяется множеством сущностей, которые имеют табличную форму представления, соответствующую ER-модели.

ER-модель данных - это кортеж ER = < Е,R, a, L, [i >, где

E = {Ei|i = l,n} - конечное множество сущностей (сущность Е, имеет схему отношения по Мейеру и рассмазривается как объект). D = DlU D2U ... U Dn - множество доменов, областей определения для множества сущностей Е , где D, - область определения сущности Е,, i=l,..n.

Ei = {eij, j = I,di} - конечное множество атрибутов. Каждому азрибуту е,, соответствует область значения D.j, причем D,, е D,. Значения таблицы Е, представляются в виде конечного множества отображений - кортежей,

Ki - (kip: Ei ( Dil U ■■• U Ö id j) I р = 1 ,(J j} • Каждое отображение

должно удовлетворять ограничению ki(eij) е Dij. Таким образом, сущность Е, представляется таблицей со столбцами, соответствующими атрибутам, и строками, являющимися значениями отображений к,р. Для сущности Е, можег быть определено конечное множество ключей

B¡ = {bis| s - 1, V(}. Каждый ключ, задаваемый набором атрибутов bis с Ei, должен удовлетворят!» условию: для любых двух различных

к

кортеже» kip, и kipi существуй aipnOyi e,,e b,,, шкой чн kip, (eij ) * kiP2(eij )•

R <r E x E - конечное множество связен между сушнооимн R=(ri,...,rk}.

a: R I—» { 1:1. 1:N } - отображение, которое снят - упорядоченном riapi (Ei,Ed) ставит и однозначное «ннветепше MciKy 1:1 или l:N. Отображе мне определяется н том случае, если Ei и E,i hmcioi cooiiicichichho kmiiomi bisi 11 bds2 > c общими атрибутами b = l)is| П biK-> * 0. Если для любой кортежа kip, е Ki существуем единсшснный kdp eK.il, причем kip, (b = kdp,(b), то функция ciaiuir it coot ne ici пне связи мсп<у 1:1, иначе - меп<\ 1:N.

L={li| i=l.k }- множество меток (названий связей), где к-колнчеепк связен в множестве R.

р : R —> L - функпня, ставящая в однозначное cooibcicibiic связи из R мет ку из L.

Примечание, n, d,, q,, v,, k - натуральные числа, н-> - частичное отображе ние, —> - полное отображение.

На рис. 2 изображен фаф ER-модели для примера "Поставщик потребитель". Сущности "Поставщик" (Ei) и "Потребитель"^) представ ляются в виде таблиц, содержащих обозначения атрибутов н имена атрибу тов. Для удобства изображения имена атрибуюв на рисунке расположен! вертикально.

Отображение между сущностями определяется связью "Продажа" i изображается дугой со стрелками, связывающей таблицы. Формальное они санне связи включает идентификатор-ключ для каждой таблицы. Связ "Продажа" определяется ключом таблицы "Поставщик" - атрибут en i ключом таблицы "Потребитель" атрибуты си, езз. Ключи на рис. 2. выделе ны прямоугольниками. Отображение между таблицами изображается в вид метки (1:N) - один-ко-мнопци и соответствующими стрелками. Атрибуты ci е24 будут использоваться для описания взаимодействии таблиц и могут при нимать значения. Атрибут eu - сделка определена ('О'), не определена ('Н' Атрибут е24 - сделка определена ('О'), не определена ('П') и произведена ('П') Статическое табличное описание может иметь известные свойства рсл> ционных отношений: функциональную зависимость атрибутов, нормалнзе ванность таблиц (таблица нормализована, если она находится в одной из m ти нормальных форм).

Описание взаимодейепшн таблиц. В СВТ-модели взаимодействие межл сущностями определяется переходами (Т). Переход описывает процесс мш рации (передачи и/или преобразования) значении данных одних сущносте!

Е| - Поставщик

Е> - По греби гаи

обозначение атрибута имя атрибута

поставляемый товар

ен

е12 количество товара

ей срок поставки

С14 возможность сделки с Е2

Продажа

£

обозначение азрибута

С21

С22

С23

С24

имя

атрибута

требуемый товар

количество товара

срок

получения

возможность сделки с Е1

РЖ-модель для примера "Поставщик-потребитель"

Рис. 2. Сзатическое табличное описание.

в зависимости от состояния значений данных других сущностей. В частном случае в взаимодействии может участвовать одна сущность. ВТ-описание - з го кортеж ВГ-< Е,£Г,Т,Р,$,(р> , где

Е = {Е|) ¡ = 1,п}- конечное множество сущностей (таблиц), определенных для статического табличного описания, где п - натуральное число.

£ = (еу ! 1 = 1,п , ]= 1,(1 ¡}- конечное множество атрибутов сущностей, где п - число таблиц, а (1, - число азрибутов в таблице.

'Г ={1)| ] = 1,т}- конечное множество переходов (взаимодействий

между таблицами), где т - натуральное число. I7: Е х ти Тх Е —> Л11{0}- функция ннцидентностен, задающая

множество Л = {а! | I = 1,р} дуг, где р - натуральное число. Р(Е,1) - задает дугу чтения. Р(1,Е) - задаст дугу записи.

ц/ : Л —> с* - функция, сопоставляющая каждой дуге подмножество

атрибутов (с* - множество всех подмножеств множества к). ц/ (Р(П,л,))с Е, для дуг чтения. ц> (Г(^,Е,))с: II, для дуг записи.

ё~ {&и= I-41}- множество логических условии (предикатов над атрибутами).

1 = I, "1}- множество операторов, описывающих операции над таб-

лицами).

ф : Т —> Г ху - функция, ставящая в однозначное соответствие переходу из Т условие из g и оператор из Г.

Для спецификации условий и операторов переходов ИТ-описания можно использовать формулы подобные формулам в теории реляционных баз данных (Д. Мсйср). Такие формулы являются прототипами языка запросов. Обозначим результат выполнения оператора Г как Р5^ и будем представлять его в виде условий, накладываемых на значения атрибутов. Задачу "Поставщик-потребитель" опишем, используя импликацию для каждого перехода g => Г*". Будем считать, что в таблице "Потребитель" каждый товар встречается один раз. Выполнение поставки разбиваеия на два перехода "Определение возможности сделки" (и) и "Сделка" (1г).

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

Переход 11 может быть запущен, если выполняется условие его запуска Для требуемою товара е21=сц со сроком получения си<Т5(Тяу8) (меньше некоторого вычисляемого значения функцией ТБ с аргументов Т.чуя, где Тьу^ - время моделирования), у поставщика есть в наличии товар егг^си, не определена возможность сделки Ег с Е] е24='Н' и ем='Н'. При срабатывании перехода Ь определяется возможность сделки Е| с Ег см='0' и С24='0', устанавливается срок поставки ец=ТР(С2з, Тбуб) (где, ТР- функция, определяющая срок поставки).

(С23< ТЯС'Гьуь))л(С21=Сп)л(С22^С|2)л(С24=,Н')л(С|4=,Н,)=>

(еы='0')л (С24='0')л (еи=ТР(с2з, ТвуБ) )

Условия запуска перехода 12 следующие. Для требуемого товара с21=сп, если определена возможность сделки ем='0\ наступил срок поставки С1з=Т5у5, то срабатывает переход 1г и изменяются: количество товара у поставщика С|2- ей - с21', устанавливается состояние возможности сделки с Ег

как неопределенное Си='1Г, а С2(='ГГ в состояние поставленный товар, ану-лируется срок поставки е|з=0. (с21=еи)А(сы='0')л(е|}=Т$у$) (с^еи-сзг^лСе^'О^лСсм^ОлО^'П')

Переход (| "Определение возможности сделки"

Переход "Сделка"

Описание взаимодействии таблиц для примера "Поставщик-потребитель".

Гис.З. ВТ-описание.

Декларативная запись не даст представления о том, какими должны бы и, алгоритмы операторов Г. Для описания условий g и алгоритмов операторов Г в процедурной форме вводятся операции чтения и записи. Каждой дуге чтения соответствует операция чтения. Каждой дуге записи - операция записи. Операция записи изменяет только тс атрибуты, которые указаны на дугах записи. Приводятся алгоритмы операторов (П.Гг) с условиями их выполнения ^1^2) на языке Ада.

м

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

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

СВТ-модель.СВТ-модель - это кортеж C/i7-</j7',M,P,Tn\Ara,r/,Tsys, In >,

где BT-< Е,£,Т, F, l//,g, >-ВТ-описание,

M = {Mi| i = l,n } - конечное множество множеств маркеров, где М,-множество маркеров сущности Ei е Е, где п - число сущностей. Каждый маркер m, е М,- это таблица, получаемая в результате выполнения перехода. Множество таблиц М, образует историю изменения сущности Е,.

P = {pv| v=l,h}- конечное множество позиций (накопителей) для сохранения значений данных обновляемых маркеров из М, где h - натуральное число.

jm- j(m i j_| u } . множество мультипереходов. Мультнпереход объединяет все переходы связанные с одной и той же парой таблиц Е',Е", то есть для любого t е V (F(E',t) v F(t,E'))A( F(E",t) v F(t,E")).

Am={am|z=l,c } - множество мультидуг, araz ={F(Ei,tj), F(tj,Ei)}.

//: E x P—> { истина, ложь }- предикат размещения сущностей. Определяет для позиции р еР множество сущностей из Е (т.е. позиции приписывается одна или несколько сущностей).

Tsys = [0,l,...,v]- упорядоченное в порядке возрастания, множество шагов выполнения СВТ-модели, где v - натуральное число. Если на каком-либо шаге моделирования маркер m,e Mi изменяется, то маркер с обновленными значениями добавляется в множество М„ Каждому добавляемому маркеру присваивается индекс, соответствующий шагу выполнения модели. Маркер, имеющий последний индекс шага выполнения модели, будем называть маркером находящимся в головном месте позиции из Р. Число головных мест в позиции реР соответствует числу сущностей Е, которые приписаны р.

n

Iп: VI i—> D- частичная функция инициализации, отображает множество маркеров m"i a Mi, .... т°пе М„ с индексом шага моделирования Tsys = [0] в множество доменов.

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

Выполнение СВТ-модели. Обозначим для оператора Я, соотистствущему переходу U, входные параметры I ^ = U4'0'(Hi,tk)), вы-

I'(l'n,tk) ф 0

ходные параметры 0(V = U^O'O1^''-1))-

I'(tk, lii) * 0

Обозначим композицию операторов f j fj как П^-

i el

Правило изменения маркировки при выполнении СВТ-модели следующее, для реР и для М, е М, размещенного в р (то ее п. //(Е,,р)=истина), новая маркировка М', вычисляется согласно правилу:

М', = M,U П 'к , где Mi-предыдущее множество маркеров. &(lfi) aOivRh,* 0

Причем оператор fk действует на таблицу т., расположенную в головном месте позиции. Композиция операторов PJ fk предоавляет собой последовательное применение операторов fk к маркеру т,. Результатом действия операторов является маркер. Для данной сущности Е, добавляется всегда один маркер ггь е М,в головное место позиции.

Если операторы fk действуют на одни и теже атрибуты, то их порядок существенен. В этом случае вводится расписание.

СВТ-модель изображается в виде двудольного ориентированного маркированного графа.

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

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

На рис. 4 изображена СВТ-модель, полученная в результате выполнения процедуры преобразования ВТ-описания.

Выполнение СВТ-модели заключается в следующем. Допустим, потребителю зрсбуется дна пнда товара и они есть у поставщика. Срабатывает переход "Определение возможности сделки" (1|). При срабатывании перехода Ь выполняется оператор П н заносятся обновленные маркеры в головное место позиции р| и рг. Допустим, что на следующем шаге модслирования'значеиня атрибута си (срок поставки) соответствуег времени моделирования Тбуб (выполняется условие срабатывания перехода 1г) и выполняется условие срабатывание перехода В этом случае одновременно запускаются переходы 1| и 12. После изменения данных в позиции р| и рг добавляются обновленные маркеры.

Мультипереход "Продажа"

СВТ-модель для примера "Поставщик-потребитель".

Рис.4. Описание СВТ-модели.

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

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

Для описания СВТ-модели определяются агрегирующие конструкции: мультидуга (ат) и мультипереход (У").

Миожсспш переходов, определяющих взапмодейспше между нарами таблиц, » С ИТ-модели может быть иредсгаилепо в ннде одного мулыипере-хода. Например, мультипереход "Продажа" определяется двумя переходами: "Определение возможности сделки" н "Сделка" (см. рис. 4). Мультидуге может быть приписан оператор-функция вида - ГР<П>, а переходу условие его выполнения Угловые скобки в операторе < Е> указывают, что перемеп-п[,10 связываются с их значениями (анало1 ично переменным в функциональных языках программирования).

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

СВТ-модель может иметь свойства: агрсгпровапность, ограниченность и живость, а также свойства статического табличного описания ( функциональную зависимость атрибутов, нормализованность июлиц) и свойства ИТ-описания (связываемость, ординарность, рефлексное 1Ь, однородность).

В третьей главе проводится сравнительный анализ класса СН Г-моделей и раскрашенных сетей Петри (СР-сетей). Сравниваются основополагающие структурные элементы СПТ-модели и СР-сетей: маркер, позиция, переход и дуга.

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

Делается вывод, что при моделировании аналогичной задачи СР-сети по сравнению с СНТ-моделыо требуют введения дополнительных конструкций (переходов, позиций, операторов и дуг). Делается вывод, что классы не рав-помощны. Класс СИТ-моделей включает класс СР-сетей.

В четвертой главе подробно рассматривается процесс вычисления новых значений таблиц в СВТ-модели. Для представления вычислительной модели вводится СИТ-автомат. СВТ-автомат комплексно решает задачи связанные с обработкой транзакций.

Определение 1. Транзакция рассматривается как процесс, выполняющий операции чтения, преобразования данных, записи данных и удовлетворяющий свойствам - атомарности, изолированности, непротиворечивости, восстанавливаемости. В СНГ-модели транзакции соошегсшуег операюр из Г.

Определение СВТ-автомата. СВТ-автомат - это кортеж СВТЛ= < Е, IV f,g, S, Мо>, где

Е = {ei | i = l.n} - конечное множество таблиц, где п - пагуральнс число.

М = {Mi| i = l.n } - множество множеств состояний таблиц. М,- множеств состояний таблицы с, е Е.

f = {0 lj= !•"!}- конечное множество транзакций (т - натуральное число Для каждой транзакции f, е f, определен набор входных (читаемых) та( лиц Е,г = {с г 1..... с г pj} с Е, и набор выходных (записываемых) таблп

Ejw = ¡e\v|, ..., cwqj} с Е, при этом fj : Mr|x...xMrpj -M\v| х...х Mwqj. Множество состояний таблицы epj е Е/ есть Mrj

где i=l.....pj. Множество состояний таблицы Cwj е Ejw есть М w i > 1 ^

i=l,..., q,. Cpj, - натуральные числа, причем р, <n, q, <n, l<r,<t I <w,<n).

&={&!j= 1-'"}- конечное множество условий запуска транзакций, пре/ц катов: Mf| х ...х Mrpj —> {ложь, истина}.

S = [si.....Sk] - расписание, задаваемое в виде последовательности троек s

(tj, reacij. с), или s = (Г,, writCj, е), где ^-транзакция, с -таблица, причем с Ejr, если s = (Г,, readj, с), се Ejw, если s=(fj, write,, с), (k-натуральпос число)

Расписание определяет последовательность выполнения операций Ч1снн и записи в случае пересечения множеств входных Ег и выходных Г> таС лиц.

Мо= {mi| i= l.n }- конечное множество начальных состояний таблиц, \п in, е М|являегся начальным состоянием таблицы е,е Е.

Определение 2. Будем называть транзакцию f, допустимой (ДТ), если услс вие запуска для транзакции истинно а=истина. fd = {fje Г | &=истнна} множество ДТ. Множество ДТ может изменяться динамически. Taicr СДГ-авгомата. Такт автомата определяет новое состояние таблш Допустимые транзакции, отсутствующие в расписании S, выполняются Последовательно просматривается расписание S. Если в очередной тройк s=(fj,read,,e) пли s=(ij,writej,e) fj е fd, то выполняется заданная операция гса< или write,.

Автома! останавливается, если им одна из транзакций не является доп\ стнмой, то есть множество допустимых транзакций fd= 0.

Для СВТ-авпюлмпю приводятся разработанные алгоритмы иараллел! ною выполнения транзакций (по расписанию и независимо от пего) с ш пользованием механизма рандеву реализованного в языке Ада. Алгорпп

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

Общий ход вычислений в СНГ-автомате определяйся достижимыми

о Г Я

значениями таблиц СВТ: Мпх...хМгр ——М и | х ...х М •

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

В 11яюн главе определяются этапы методологии анализа информационных обьекгов на основе СВ'Г-модели и рассматривается пример применения метдолопш.

Статическое табличное описание для рассматриваемого примера нред-счавляе] собой схему базы данных реляционного типа. Этан размещения 1аблнц в позициях СВ /'-модели может быть связан с представлением распределенной базы данных в абонентских пунктах. На этапе преобразования В'Г-описанин в С В'¡'-модели используются операции реляционной алгебры, дополненные операциями обновления.

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

'Этап I. Определение нредмсгныч областей. Предметным областям рассматриваемого примера ставится в соответствие множество I' позиций СВ'Г-модели:

• р| - ОМТС (Отдел Мак'риалыю-Техннческого Снабжения);

• р. - БУХГАЛТЕРИЯ ;

• р.,-ПОСТАВЩИК;

• р,-СКЛАД;

. р> - ЦЕХ.

'Эти 2. Определение конфшурацин. Выделяются предметные области, оIносящиеся к организационной структуре: р|(ОМТС), р;>(БУХГАЛ'ПгРИЯ), р?(1 ЮСТАВЩИК), и предметные области, относящиеся к обьектам управления: р^СКЛАД), р5(ЦЕХ), которые расположены соответственно в верхней и нижней части трафпческого изображения СВ'Г-модели (рис. 5).

Эган 3. Определение втанмодсйствин нредмешых областей. Определяются мулыпиереходы между предметыми областями: (| - ПОС ТАВКА , \г - ВЫДАЧА СО СКЛАДА. Мультипереходы, позиции и направленные муль-тидугп, связывающие их, н совокупности образуют структуру СВ'Г-модели. Мультипереходы 1|,1г изображены прямоугольниками на графе. Позиции Р(чредмешые области) - кружками.

Этап 4. Определение сущностей предметных областей. Для предмет областей определяются сущности, множество атрибутов, и схемы табл сущностей. Ключевое слово еШку (см. рис. 5) аналогично объявлению пни языках программирования.

Этап 5. Опре; ленке размещен!

Процедура размен ния определяет свя сущностей с пот пиями.

Эгаи 6. Онре; ленке операторов

УСЛОВИЙ НХ ВМПОЛ!

пня. Для переходов мультппереходов определяются опер торы и условия С]1 батывания перех дов. Каждой мул тидуге приписывас ся функция, а мул типереходам услов: их выполнения. Вв дится расписание д. одновременно к пользуемых данны> Этап 7. Имнт ШЮ11НОС моделнроп пне. В работе прив дятся резуль га 1 имитацпоного м делирования СП модели для рассма ривасмого примера виде дерева дост жимых состояний временных ¡рафике

Б = 1 SFR. Qp. Qd, Qs. Qn. D. NM, SCRb, PRC ) SFR - шифр комплектующею;

Qp • количество комплектующих, поставляемых по плану; Qd - возможное количество комплектующих у поставщика; Qs - количество комплектующих lia складс; Qn - количество комплектующих требуемых в цехе; QP - количество комплектующих поставленных на склад; QN- количество комплектующих выданных со склада; D - время (дата); -NM - название счета:

-SCRb - сумма в денежном вира лени и план-счс1 а; -PRC - нена комписк [> книнк

cnlilv Г (STR.Qp.D) : р cnlity В (NM.SCRb) : b cnlilv D (SFR.Qd.D) :d cnlilv S {SFR.Qs.PRO.QP.QN! s cnlity N (SrR,Qn,I>| n

pi. P - план-i рафик п ос та яки

p?; В - план-счсг производства.

р*: D - т рафик возможности поставщика.

р4: S - список комплектующих склада.

pj: N -1 рафик изменения потребностей цеха.

Фрагмсн | с и с i с м ы оперативного управления производством, CBT-Mot\cih поставки и выдачи комплектующих в цех.

Рис.5. Пример применения методологии проектирования.

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

екюн ни основе nmonux блоков, которые могут бы реализованы в вн.и* профаммиых модулем. Каждым типовой блок представляет собой СИ I-людель. где мультнпереход ннтерпретпрует некоторый экономический процесс, позиции интерпретируют объекты управления м вмените объекты, обладающие некоторыми ресурсами, моделируемыми табличным представлением.

Дастся классификация типовых блоков. Рассматривается пример производственной системы механосборки, сконструированной из типовых блоков.Анализируется конфигурация СВТ-модели и результат имитационно!о моделирования при расчете краткосрочного плана выпуска продукции.

В заключении сформулированы основные результаты, полученные в диссертационном работе. '

Приложения содержат краткое описание экспериментального программного средства на основе СВТ-модели и акт внедрения системы оперативного управления производством. Системы разработаны на инструментальном средстве Clarion (IBM/PC, среда DOS). Объем зафузочного модуля экспериментального средства - 412 Килобайт, системы оперативного управления производством -9 Мегабайт.

Основные результаты работы

1. Разработана новая формальная модель "Система взаимодействующих таблиц" (СВТ-модель). Дано ее формальное определение. Определены м исследованы свойства СВТ-модели. Разработано представление вычисления новых значений таблиц СВТ-модели в виде СВТ-автомата и алгоритмы параллельной обработки транзакций. Определено свойство автомата "СВТ-достижимость".

2. Проведен сравнительный анализ классов раскрашенных сетей Петри н СВТ-модели.

3. Разработана методология анализа информационных объектов на основе СВТ-модели и подход к анализу и конструированию производственных объектов из типовых блоков СВТ-модели. Проведена классификация блоков.

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

5. Разработано экспериментальное профаммное средство, поддерживающее СВТ-модель.

Опубликованные работы по теме диссертации

Первая версия СВТ-модели называлась "Вычислительная модель с разделяемыми информационными ресурсами".

in

1. ('сменон A.C. Анапа информационных объектов на основе модели "Система взаимодействующих таблиц" II Автоматика н телемеханика, N 9. 1996.

2. Семенов A.C. Применение имитационного моделирования для анализа устойчивости экономических процессов II Тезисы докладов второй международной конференции "Проблемы управления в чрезвычайных ситуациях". Москва, ЦПУ РАН, 1994.

3. Семенов A.C. Имитационное моделирование информационных объектов на основе модели "Система взаимодействующих таблиц"// Тезисы докладов межвузовской паучно-техннческой конферсицшГДНДС-95". Чебоксары, 1995.

4. Семенов A.C. Вычислительная модель с разделяемыми информационными ресурсами // Рукопись дел. в ВИНИТИ 05.07.1993 г. 31 е., N1854-В93 Деп.

5. Семенов A.C. Применение имитационного моделирования для анализа экономических процессов // Рукопись деп. в ВИНИТИ 03.11.1993 г. 49 е., N 2739-В93 Деп.

6. Семенов A.C. Сравнительный анализ новой модели "система взаимодействующих таблиц" и раскрашенных сетей Петри// Рукопись деп. в ВИНИТИ 25.06.1995 1.31 е.. N I773-B95 Деп.

7. Семенов A.C. Вычислительная модель обновления распределенных данных на основе автомата взаимодействующих таблиц // Рукопись деп. п ВИНИТИ 25.06.1995 г. 17 е., N 1774-В95Деп.

Автор: