Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

ANALYSIS OF FORMALISMS FOR VISUAL MODELLING LANGUAGES DESCRIPTION

Sukhov A.O. 1
1 Perm State University
Using of visual languages allows to present process of information systems development visually. The majority of such languages are based on formal models: algorithmic nets, graph grammars, automatic models, etc. It allows describing properties of languages, developing algorithms for horizontal and vertical transformations of the program systems models that created with their help. The approach to syntax description of visual modelling dynamically configurable languages by means of graph grammars is discussed in this article. The analysis of various representations of graph grammars has shown that the most appropriate formalism for describing the syntax of visual modelling languages are graph grammars, which are constructed on the pseudo-metagraphs. This type of graphs allows structuring model at the expense of combining the nodes in the sets, reflecting the features of modelling languages, so that the model becomes obvious and task-orientated.
meta-model
labeled graphs
graph grammars
visual modelling languages syntax

  Введение

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

Как следует из определения, модели создаются с помощью некоторого формального языка. Визуальные языки моделирования - это совокупность формализованных наборов графических символов и правил для построения визуальных моделей. В настоящее время не существует единого универсального визуального языка моделирования. Сейчас активно используются на практике такие языки визуального моделирования, как UML и ERD - для моделирования предметных областей; IDEF, DFD, EPC, BPEL и BPML - для моделирования бизнес-процессов на разных уровнях и т.п.

Визуальные языки моделирования строятся на основе определенных формальных моделей. Под метамоделью понимают модель языка моделирования. Существуют различные формализмы определения синтаксиса визуальных языков: автоматная модель [2], алгоритмические сети [1], графовые грамматики [8].

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

Графовые грамматики - обобщение грамматик Хомского на графы. Чтобы задать грамматику, требуется задать множества терминальных и нетерминальных символов, набор правил вывода, а также выделить во множестве нетерминалов стартовый символ. Для представления графовых грамматик необходимо выбрать такой вид графов, который бы предоставлял возможность рекурсивного определения метамоделей, единого представления и описания моделей и метамоделей предметной области.

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

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

Ориентированные графы

Существует несколько разновидностей графов, которые используются для представления графовых грамматик: классические графы, орграфы, мультиграфы, псевдографы, hi-графы, гиперграфы, метаграфы и др. Рассмотрим различные способы представления графовых грамматик подробнее и попытаемся представить с их помощью абстрактный синтаксис диаграмм «Сущность - Связь». Данная нотация была выбрана в качестве примера, т.к. ERD-диаграммы широко распространены, а метамодель данного языка имеет нетривиальную структуру, содержащую объекты и отношения разных типов.

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

Рис. 1. Фрагмент метамодели ERD-диаграмм, представленной с помощью помеченного орграфа.

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

Расширением орграфа, в котором отсутствует вышеупомянутое ограничение, является псевдограф.

Мультиграфы и псевдографы

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

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

Еще одним расширением определения орграфа является псевдограф.

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

Рис. 2. Фрагмент метамодели ERD-диаграмм, формализованной с помощью помеченного псевдографа.

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

Hi-графы

Hi-граф - это упорядоченная пара , где  - конечное непустое множество вершин, E - множество дуг графа. Каждая дуга , причем , ,  - иерархии вершин [7].

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

На рис. 3 представлен hi-граф, описывающий метамодель диаграмм «Сущность - Связь».

Рис. 3. Фрагмент метамодели ERD-диаграмм, представленной с помощью помеченного псевдо hi-графа.

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

Метаграфы

Метаграф - это упорядоченная пара , где  - конечное непустое множество вершин, E - множество ребер графа. Каждое ребро , причем , т.е. каждое ребро метаграфа соединяет два подмножества множества вершин [5]. Если ребро метаграфа является направленным, то граф называется ориентированным метаграфом.

Рис. 4. Фрагмент метамодели ERD-диаграмм, формализованной с помощью помеченного псевдометаграфа.

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

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

Рассмотрим еще одну разновидность орграфа - гиперграф, который позволяет одной дугой соединять сразу множество вершин.

Гиперграфы

Гиперграф представляет собой пару , где X - непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а E - семейство непустых подмножеств множества X, называемых гиперребрами [4].

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

Рис. 5. Фрагмент метамодели ERD-диаграмм, формализованной с помощью помеченного псевдогиперграфа.

 

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

Заключение

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

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

Данный формализм был использован при описании метаязыка системы MetaLanguage [3]. На основе графовых моделей были описаны свойства метаязыка, разработаны алгоритмы горизонтальной и вертикальной трансформации метамоделей и созданных на их основе моделей информационных систем, их предметных областей.

Работа подготовлена при финансовой поддержке РФФИ (проект № 10-01-00794-а).

Рецензенты:

  • Румянцев А.Н., д.ф.-м.н., профессор, генеральный директор ООО «Информационные Бизнес Системы Пермь», г. Пермь.
  • Тюрин С.Ф., д.т.н., профессор кафедры автоматики и телемеханики ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет», г. Пермь.