Структура данных и диаграммы отношения компонентных данных

 

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

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

2. конкретные структуры – используются для представления данных в программах

 

Все абстрактные структуры делятся на 3 группы:

1. Не связанные – элементы которых не связаны между собой. К ним относятся множества и кортежи.

2. С не явными связями. К ним относятся вектор, матрица, массив, запись, строка и т.д.

3. С явными связями (графы). К ним относятся цепь, цикл, дерево, ориентированный граф, взвешенный граф, мультиграф.

 

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

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

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

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

 

Диаграмма Джексона.

В основе диаграмм Джексона лежит предположение о том, что структуры данных, так же как и программ можно строить из элементов с использованием всего 3х основных конструкций (последовательности, выбора, повторения). Каждая конструкция представляется в виде 2х уровней иерархии. На верхнем расположен блок конструкция, на нижнем блоки элементов. Конструкции различают специальными символами в правом верхнем углу блоков элементов. При изображении последовательности символ не указывается. При изображении выбора ставится символ «О» - сокращённое от OR «ИЛИ». Конструкции последовательности и выбора обязательно должны содержать по 2 или более элементов 2го уровня. При изображении повторения в блоке единственного (повторяющегося) элемента ставится значок *

 

 

 

Скобочные диаграммы Орра

 

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

Пример: Описанить структуру данных файла «Электронная ведомость» которая отображает

№ группы, записи об успеваемости студентов (ФИО, предмет, оценка)

 

Сетевые модели данных

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

1. Модель П.Чена

2. модель Баркера

3. модель IDEF1

 

Модель Баркера является наиболее распространённой.

Базовыми понятиями сетевой модели данных являются: сущность, атрибут и связь.

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

1. уникальное имя

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

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

 

Сущность представляет собой множество экземпляров реальных или абстрактных объектов (людей, событий, предметов и т.д.). Имя сущности должно отражать тип или класс объекта, а не его конкретный экземпляр. На диаграмме Баркера сущность изображается прямоугольником с закруглёнными углами. Каждая сущность обладает одним или несколькими атрибутами. Атрибут – любая характеристика сущности, которая является значимой для рассматриваемой предметной области и предназначена для квалификации, идентификации, количественной характеристики или выражения состояния сущности. Атрибуты делятся на ключевые и описательные. Ключевые – это те которые входят в состав уникального идентификатора, описательные – все прочие. Все …… перемещают в начало списка и обозначают решёткой.

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

 

1. сущность без атрибутов

2. сущность с атрибутами

3. сущность с уточнением атрибутов

 

Для сущности определены 2 понятия:

1. Супер-тип – сущность обобщающая некоторую группу сущности (подтипов). Он характеризуется общими для подтипов атрибутами и отношениями. Например: супертип - учащийся
2. Подтип

 

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

Необязательная связь предоставляет собой условное отношение между сущностями.

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

Ассоциативная сущность представляет данные, которые ассоциируются с отношением между 2мя или более сущностями.

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

 

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

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

Рекурсивная связь:

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

 

Неперещаемая

 

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

 

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

 

Схемы отношений между сущностями (копия).