Структура данных аспектного подхода

2005

НАУЧНЫЙ ВЕСТНИК МГТУ ГА серия Информатика. Прикладная математика

№ 92

УДК 621.396

СТРУКТУРА ДАННЫХ АСПЕКТНОГО ПОДХОДА М.В. ВИНОГРАДОВА

Статья представлена доктором технических наук, профессором Черненьким В.М.

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

1. Введение

Эффективность процесса построения информационных систем, а также используемых при этом методологий и СЛБЕ-средств зависит от особенностей информационных систем и области их применения.

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

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

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

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

2. Модель данных аспектного подхода

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

Структура данных в аспектном подходе задается множеством отношений (Я. }, 1=1. .I.

Каждое отношение состоит из множества атрибутов. Множество атрибутов формируется на основании реквизитов предметной области. Можно выделить три типа отношений:

1. Первый тип отношений - это отношения вида Я. =< ггк, г.а >, 1=1 ..I., где г.а - это атрибут, соответствующий реквизиту предметной области, а гк - это атрибут, являющийся идентификатором атрибута гг2. При этом имеет место функциональная зависимость: гк  гга.

2. Второй тип отношений - это отношения вида Я'] =< гкх,гк2 >, ]=1..1, где гкх - это атрибут, являющийся идентификатором данного отношения, а гк2 - это атрибут, являющийся идентификатором другого отношения, то есть внешний ключ. В отношении Яj имеет место функциональная зависимость: гкх  гк2.

3. Третий тип отношений - это отношения вида Як =< ,{гк} >, к=1..К, к1=1..к1, где г/

- это атрибут, являющийся идентификатором данного отношения Як, а множество атрибутов (гкк} - это множество внешних ключей и, одновременно, альтернативный составной ключ. В отношении Як имеют место функциональные зависимости г*  {гк } и (гкк }  .

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

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

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

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

Условные обозначения, используемые в табл.: 1.

• # имя атрибута - атрибут, являющийся первичным ключом;

• имя атрибута # - атрибут, являющийся внешним ключом;

• (#) имя атрибута - атрибут, являющийся альтернативным ключом;

• (имя атрибута 1, имя атрибута 2,...) - составной атрибут.

Таблица 1

Примеры отношений

Отношение Атрибуты Обозначение

Отношения первого типа

Названия факультетов # Идентификатор названия факультета, Название факультета Инф НФ

Аббревиатуры факультетов # Идентификатор аббревиатуры факультета, Аббревиатура факультета Иаф АФ

Направления факультетов # Идентификатор направления факультета, Направление факультета Инпф НПФ

Год основания факультетов # Идентификатор года основания факультета, Год основания факультета Игф ГОФ

Индексы кафедр # Идентификатор индекса кафедры, Индекс кафедры Иик ИК

Названия кафедр # Идентификатор названия кафедры, Название кафедры Инк НК

Отношения второго типа

Факультет - направление # Идентификатор факультета, Идентификатор направления факультета # Иф Инпф

Факультет - год основания # Идентификатор факультета, Идентификатор года основания факультета # Иф Инф

Отношения третьего типа

Индекс кафедры - аббревиатура факультета # Идентификатор индекса кафедры и аббревиатуры факультета, (#)(Идентификатор индекса кафедры #, Идентификатор аббревиатуры факультета #) Иикаф Иик Иаф

Вырожденные отношения третьего типа

Факультет - название # Идентификатор факультета, (#) Идентификатор названия факультета # Иф Игоф

Факультет - аббревиатура # Идентификатор факультета, (#) Идентификатор аббревиатуры факультета# Иф Иаф

Кафедра - индекс и аббревиатура факультета # Идентификатор кафедры (#)Идентификатор индекса кафедры и аббревиатуры факультета # Ик Иикаф

Кафедра - название # Идентификатор кафедры (#) Идентификатор названия кафедры # Ик Инк

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

• прямоугольник (узел схемы) обозначает атрибут;

• линия обозначает связь между атрибутами, при этом;

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

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

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

Рис. 1. Пример графической схемы для описания структуры данных

Таблица 2

Правила построения графической схемы структуры данных

Элемент структуры данных

Элемент(ы) графической схемы

Пример

Атрибут

Узел схемы

НК

Атрибут «Название кафедры»

Реквизитное отношение

Сплошная линия, направленная от ключа реквизита к реквизитному атрибуту

НК

I

Инк

Отношение «Названия кафедр»

Понятийное отношение

Сплошная линия, направленная от ключа понятия к атрибуту понятия

Отношение «Направления факультетов» (#Иф, Инпф)_______________

Ключевое отношение

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

Иик

Иаф

Иикаф

Отношение «Индекс кафедры -аббревиатура факультета» (#Ии-каф, (#)(Иик, Иаф))______________

Вырожденное ключевое отношение

Сплошная двунаправленная линия, соединяющая два ат-

Инф

рибута.

Иф

Отношение «Факультет - название»

3. Построение структуры данных

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

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

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

Структура данных задается множеством атрибутов и множеством отношений:

Я = (Я. } - множество отношений,

А = (г. } - множество атрибутов.

Перед проектированием структуры данных задачи множества атрибутов А и множества отношений задачи Я пусты: Я=0, А=0. На основе объектов реального мира выделяются понятия. Также понятия могут быть получены из исходного описания задачи. Каждое понятие определяется множеством его реквизитов. Необходимое множество реквизитов понятия может быть получено из исходного описания задачи. На основе множества реквизитов задачи формируется множество реквизитных атрибутов структуры данных. Атрибут определяется как элементарный (не декомпозируемый на составные) реквизит. Реквизитный атрибут определяется уникальным названием, семантическим описанием и областью допустимых значений (доменом). На основе реквизитных атрибутов формируется множество реквизитных отношений, которое добавляется к множеству отношений структуры данных ИС. Каждое реквизитное отношение задается названием и определяющим его реквизитным атрибутом. Семантическое значение для реквизитного отношения не задается, поскольку совпадает с семантическим значением реквизитного атрибута.

Реквизитное отношение записывается как Я. =< ггк,туа >, ггк  гга, V/ = 1..1, где гга - реквизитный атрибут 1-го отношения, гк - ключевой атрибут 1-го отношения.

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

a) если характеристика понятия, соответствующая реквизитному отношению с ключом реквизита гк 2, является возможным ключом понятия (на основе сведений о предметной области), то создается вырожденное ключевое отношение Я. Атрибутом ключа в вырожденном ключевом отношении будет ключ реквизита гк2.

Я] =< гк1, гк2 >, гк1  гк2, гк2  гк1.

^ . у . У У .

b) если характеристика понятия, соответствующая реквизитному отношению с ключом

к

реквизита Т] , является частью составного возможного ключа понятия, то создаются два отно-

шения. Первое отношение - ключевое Я]. Атрибутами ключа в нем будут ключи реквизитов тк, ]=1..1, входящие в состав возможного ключа. Идентификатором ключа будет новый атрибут гк2. я] =< тк 2,(т;} >, (тк}  г;2, тк2  тк, V]=1..].

Атрибут т]2 добавляется к множеству атрибутов ИС.

Второе создаваемое отношение - понятийное Яц. Атрибутом понятия будет идентифи-

к2 к1 к1 к2 к1 к2 к2 к1

катор ключа тк] , ключом понятия атрибут т. . Я/] =< т / , тк] >, т/  т., тк]  т. .

с) если характеристика понятия, соответствующая реквизитному отношению с ключом реквизита т]2, не входит в состав возможного ключа и сама не является возможным ключом, то

создается понятийное отношение Я], задающее связь между понятием и реквизитным отношением. Атрибутом понятия будет ключ реквизита т]2, ключом понятия атрибут тк1.

Я] =< тк1, тк2 >, тк1  тк2.

1 и 1 и

Пункты а), Ь), с) выполняются по всем характеристикам всех понятий, и полученное множество ключевых и понятийных отношений добавляется к множеству отношений ИС. В результате выполнения перечисленных пунктов получается структура данных, задающая перечень понятий и их реквизиты. Зная ключ понятия, можно получить все реквизитные атрибуты, характеризующие это понятие. Реквизитные атрибуты, к которым можно обратиться через ключ некоторого понятия Я, называются «реквизитами, доступными из понятия Я».

4. Требования к структуре данных в аспектном подходе

Аспектный подход накладывает два требования к структуре данных. Первое требование

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

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

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

к

ет, что путь между композиционным понятием, заданным ключом т понятийного отношения,

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

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

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

Рис. 2. Пример структуры «АВС, АВ, ВС»

На рис. 2 структура данных задается функциональными зависимостями:

АВС  Иавс , Иавс  АВС , Иав  АВ, Ивс  ВС , АВ  Иав, ВС  Ивс ,

ИавИвс  Иавс, Иавс  ИавИвс .

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

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

Иав  Ип, Ивс  Ит, ИпИт  Ипт , Ипт  ИпИт , ИпВ  Ипв , ИтВ  Итв ,

Ипв  Иа, Итв  Ис, Ипт  Иавс, Иавс  Ипт .

5. Заключение

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

Рис. 3. Пример структуры «АВС-NM, АВ, ВС»

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

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

ЛИТЕРАТУРА

1. Дейт К. Дж. Введение в системы баз данных. - М.: ИД «Вильямс», 2003.

2. Лавров С. Программирование. Математические основы, средства, теория. - С.-Пб.: БХВ-Петербург, 2001.

3. Виноградова М.В. Аспектный подход к построению информационных систем ВУЗа // Научный вестник МГТУ ГА, серия «Информатика. Прикладная математика», №77, 2004.

THE DATA STRUCTURE OF ASPECT DECOMPOSITION APPROACH

Vinogradova M.V.

This article is about a new approach to the information system development for smaller organizations. A new data structure is offered, which is program algorithm oriented and possesses the “including all the limitations” and “the only way” properties. Some methods of data structure building and description for the aspect approach are being offered.

Сведения об авторе

Виноградова Мария Валерьевна, окончила МГТУ им. Баумана (2001), старший преподаватель МГТУ им. Баумана, автор 6 научных работ, область научных интересов - информатика.