Книги по разным темам Pages:     | 1 |   ...   | 48 | 49 | 50 | 51 | 52 |   ...   | 54 |

Information Systems Построение математической модели Для построения алгоритмов работы CASE-системы METAS необходимо формализовать описание используемых в ней метаданных всех уровней. Приведем формальное определение систем метаданных физического и логического уровней в виде графовой модели. В качестве примера ее использования опишем один из алгоритмов верификации предметной области.

Физический уровень Пусть Fields - некоторое абстрактное множество. Элементы этого множества назовем полями. Множество Tables взаимно не пересекающихся подмножеств полей назовем множеством таблиц, а его элементы - таблицами. Для каждой таблицы множество ее полей назовем F(t) Fields.

Определим бинарное отношение RFieldsTables. Это отношение назовем множеством связей между таблицами. Будем использовать следующую запись:

rR r=(f,t), fFields, tTables.

Таким образом, каждая связь rR проводится между каким-то полем fFields, принадлежащим одной из таблиц, и другой таблицей целиком (то есть целому подмножеству множества Fields). При этом возможна ситуация, что rR, r=(f,t), tTables, fF(t), то есть связь проходит от поля некоторой таблицы к этой же таблице.

огический уровень Пусть Attr - некоторое абстрактное множество. Элементы этого множества назовем атрибутами.

Разобьем все множество атрибутов на группы, каждую из которых назовем сущностью. Множество всех сущностей Ent должно быть дизъюнтктивным, Это означает, что с одной стороны, каждый атрибут множества Attr должен принадлежать какой-либо сущности, с другой стороны, сущности не пересекаются.

Если обозначить за A(e)Attr - множество всех атрибутов, принадлежащих сущности eEnt, то формально справедливы следующие соотношения:

A(e) =, A(e) = Attr.

eEnt eEnt В каждой сущности все атрибуты можно разбить на 3 непересекающихся множества. Для любой сущности eEnt назовем множество O(e)A(e)Attr множеством собственных атрибутов сущности, S(e)A(e)Attr - множеством атрибутов справочников, V(e)A(e)Attr - множеством внешних атрибутов. Таким образом, справедливы условия непересечения этих множеств:

eEnt O(e)S(e)=, V(e)S(e)=, O(e)V(e)=, и условие обязательной принадлежности каждого атрибута сущности одному из этих множеств:

eEnt aA(e) aO(e) aS(e) aV(e).

Подмножество атрибутов сущности, используемое при построении презентационного атрибута, обозначим P(e). В нем могут присутствовать атрибуты из любых множеств O(e), S(e), V(e).Таким образом, eEnt P(e)A(e), P(e).

Отсюда получим более строгое определение понятия сущности. Сущность определяется пятеркой e = (A, O, S, V, P), где каждое из последних четырех множеств есть подмножество множества атрибутов с описанными выше свойствами.

Fourth International Conference I.TECH 2006 На всех приводимых ниже рисунках будем использовать следующие графические обозначения введенных понятий. Графически все элементы множества Attr будем обозначать кружками, а каждый элемент множества Ent большим кругом. Если атрибут принадлежит какой-либо сущности, то он будет расположен на ее круге. Цвет закраски атрибута будет обозначать, к какому из множеств O(e), S(e) или V(e) он принадлежит. Соответственно, это будут цвета белый, серый и черный. Множество атрибутов, составляющих презентационный атрибут, будем обводить пунктирной линией.

Имея фиксированное множество атрибутов, можно различными способами выделить сущности так, чтоб они удовлетворяли условию дизъюнтктивности. В каждой выделенной сущности можно различными способами выделить множества O(e), S(e), V(e), P(e). Построенной модели это противоречить не будет.

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

Обозначим - множество всех внешних атрибутов всех сущностей. Тогда Y = V(e). Введем eEnt отображение W, которое каждому vY ставит во взаимно однозначное соответствие некоторую сущность eEnt. Другими словами:

wW w=(v,e), vV(e ), e,e Ent.

1 Таким образом, каждая связь wW проводится между одним из внешних атрибутов одной сущности и некоторой другой сущностью. При этом возможна ситуация, что wW, w=(v,e), eEnt, vV(e), то есть связь проходит от сущности к ней самой. Графически такая связь будет обозначаться направленной дугой от внешнего атрибута к сущности.

Второе бинарное отношение MEntEnt назовем множеством связей M:M (лмногие-ко-многим) между сущностями. Так как в предметной области между двумя сущностями может быть несколько связей M:M, ее модель будет представлена мультиграфом или графом с параллельными ребрами, то есть графом, в котором между вершинами может быть несколько параллельных дуг [9]. Для их идентификации предлагается каждой паре ставить в соответствие пометку, ее уникальное имя. Это имя в дальнейшем будет использоваться при реализации, например при построении дерева объектов, используемого для навигации пользователя по системе [6]. Следовательно, каждая связь М:М представляет собой тройку (e,e,name), где e,e - связываемые сущности, а name - уникальное имя этой связи. Будем использовать 1 2 1 следующую запись:

mM m=(e,e name), e,e Ent, nameString.

1 2, 1 Таким образом, каждая связь mM проводится между двумя сущностями целиком. Графически такие связи будем изображать ненаправленными дугами между сущностями.

Рассмотрим пример. Пусть у нас есть сущности Школа с собственным атрибутом Номер и Ученик с атрибутами ФИО (собственный атрибут), Пол (атрибут справочника), Школа ученика (внешний атрибут), со следующими атрибутами. Они связаны как л1:М через атрибут Школа ученика.

У ученика можно в качестве презентационного атрибута можно использовать выражение ФИО+Т С+Школа ученика, а для школы - значение ее атрибута Номер.

В этом примере множество Attr состоит из четырех элементов, Ent - из двух. При этом если e Ent - это сущность Ученик, e Ent - это сущность Школа, то A(e ) состоит из трех элементов, A(e ) - из одного.

2 1 O(e ), S(e ), V(e ) содержат по одному атрибуту ученика, а множество P(e ) - два атрибута: ФИО и 1 1 1 Information Systems Школа ученика. Для школы множества S(e ) и V(e ) пусты, а множества O(e ) и P(e ) содержат 2 2 1 единственный атрибут Номер.

Ученик Школа Тройку L=(Ent, W, M) назовем полным графом предметной области. Под термином полный подразумевается, что в модель включена вся информация о предметной области. В дальнейшем мы будем рассматривать также упрощенные графы, полученные из полного с помощью какого-либо преобразования. Например, если в какой-то задаче нас не интересуют связи М:М, то в полном графе необходимо заменить множество M на пустое множество. Полученный упрощенный граф может быть удобнее для решения этой задачи.

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

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

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

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

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

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

Тогда при попытке запросить информацию о первой сущности, необходимо узнать значение презентационного атрибута второй сущности. Но так как в него входит внешний атрибут, для этого надо запросить информацию о презентационном атрибуте первой сущности. В результате образуется циклическая ссылка, и система не сможет выполнить запрос. Естественно, что такой цикл может включать Fourth International Conference I.TECH 2006 и более двух сущностей и быть менее очевидными. Поэтому подобные циклы необходимо исключать еще на этапе проектирования.

Рассмотрим формальную модель этой ситуации.

В графе предметной области в этом случае нас не интересуют ни связи М:М, ни собственные атрибуты, ни атрибуты справочника. Поэтому в упрощенном графе в множестве Attr будут присутствовать только внешние атрибуты. Сущности и множества их презентационных атрибутов P и внешних атрибутов V останутся те же. Не изменится и множество W (то есть связи л1:М). При этом надо учесть, что нарушится условие P(e), но это не является существенным для данной задачи.

Получим граф L =(Ent,W,), где Ent ={e}, e=( Attr(e) \ O(e) \ S(e),,, V(e), P(e)), то есть 1 1 1 i i i i i i i L =(Ent,W,), Ent ={e}, e=(V(e),,, V(e), P(e)).

1 1 1 i i i i i Введем формальное определение цикла.

Пусть RV(e,e ) - множество атрибутов, удовлетворяющих следующему соотношению:

1 aRV(e,e ), aV(e ), aP(e ), w W, w=(a,e ), e,e Ent.

1 2 1 1 1 2 1 Пусть выполняется следующее условие:

a RV(e,e ), a RV(e,e ), Е, a RV(e,e ), a RV(e,e ), eEnt, i=1..n.

1 1 2 2 1 2 n-1 n-1 n n n 1 i В этом случае будем говорить, что в графе предметной области присутствует цикл.

Пример графа предметной области, содержащий цикл, приведен на рисунке.

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

L =(Ent,W,), Ent ={e}, W =(v,e), eEnt, e=({v },,, {v }, P(e)), v V(e), v P(e).

2 2 2 2 i 2 ij i ij ij i ij i ij i Далее этот граф можно свести к классическому направленному графу, если принять, что все внешние атрибуты - это вершины графа, а дуги от одной вершины к другой присутствуют тогда и только тогда, когда внешний атрибут, соответствующей первой вершине, связан с сущностью, содержащей внешний атрибут, соответствующий второй вершине:

G=(GV,GE), GV={v}, vAttr, GD={(v,v)}, vA (e), w=(v,e)W, e Ent i i 2 i j j 2 i 2 Здесь под Attr подразумевается множество всех атрибутов графа L, а под A (e), 2 2 e Ent 2 - его подмножество для сущности e.

Далее можно использовать любой алгоритм поиска циклов в графе.

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

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

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

Список литературы [1] Борисова Д.А. Компонент реструктуризации CASE-системы METAS. // Межвуз. сб. науч. трудов / Математика программных систем. Пермь: Перм. ун-т., 2003. c. 34-42.

[2] Дейт К., Дж. Введение в системы баз данных, 7-е издание.: пер. с англ. М.: Издательский дом Вильямс, 2001. - 1072 с.

[3] Еремина М.Е. Генерация SQL-выражений на основе метаданных. // Межвуз. сб. науч. Трудов / Математика программных систем. Пермь: Перм. ун-т., 2003. c. 43-50.

[4] Еремина М.Е. Использование метаданных для генерации SQL-запросов к базе данных // Современные проблемы механики и прикладной математики: Сборник трудов международной школы-семинара. Воронеж: ВГУ, 2004. с.

216-219.

[5] Еремина М.Е. Реализация запросов в распределенных неоднородных системах, управляемых метаданными // 5ая Всероссийская научно-практическая конференция молодых ученых, аспирантов и студентов. Молодежь.

Образование. Экономика. Сборник научных статей участников конференции. Часть 4. Ярославль: Ремдер, 2004.

с. 65-71.

[6] Куделько Е.Ю. Генерация и настройка экранных форм на основе метаданных. // Межвуз. сб. науч. трудов / Математика программных систем. Пермь: Перм. ун-т., 2003. c. 51-59.

[7] Лядова Л.Н., Рыжков С.А. CASE-технология METAS // Математика программных систем / Межвуз. сб. науч.

трудов. Перм. ун-т. Пермь, 2003. C. 4-18.

[8] Рыжков С.А. Концепция метаданных в разработке информационных систем // Математика программных систем / Межвуз. сб. науч. трудов. Перм. ун-т. Пермь, 2002. C. 36-44.

[9] Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. - 454 с.

Pages:     | 1 |   ...   | 48 | 49 | 50 | 51 | 52 |   ...   | 54 |    Книги по разным темам