2. М

   Табельный номер сотрудника

   Должность сотрудника

   1

   2

   :1 – многие к одному – множество значений 1го элемента данных соответствует не более одного значения 2го элемента

3. 1:М – один ко многим – одному значения первого элемента данных соответствует множество элементов второго, где

Должность сотрудника

Табельный номер сотрудника

1

2

4. М:М – многие ко многим – множеству значений 1го элемента данных соответствует множество значений 2го элемента данных

Должность сотрудника

Разряд по ЕДС

1

2

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

Табельный номер сотрудника

Должность сотрудника

Разряд по ЕДС

Связь от С является избыточной и подлежит удалению.

Пример неправильно установленной связи:

Табельный номер сотрудника

Должность сотрудника

владеет

улучшен

Правила склейки записей.

Если от элемента данных А к элементу В имеется связь 1го или 2го типа (в элемент В приходит одиночная стрелка от А), то элемент В присоединен к элементу А, образуя таким образом логическую запись ключом, которой является А.

Замечание: Наличие других входящих стрелок к элементу В является препятствием применением правила.

Раздел 2. Классификация моделей данных.

В БД традиционно выделяются следующие модели данных:

1. Сетевой (сетевая модель данных)

2. Иерархическая модель

3. Реляционная модель

Из которых наибольшей общностью обладает сетевая. Частным случаем сетевой является иерархическая. Частной иерархической является реляционная.

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

Отправной причиной преобладание реляционной СУБД на рынке ПО является наличие алгоритмов преобразования сетевой модели к иерархическому виду, иерархические модели к реляционному виду и сетевой модели к реляционному виду.

Раздел 2.1. Иерархическая модель данных.

Множество узлов называется деревом (иерархией), если:

1. имеется 1 узел, называемый корнем

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

1 – корень

2, 3, 4, 5, 6, 7, 8, 9 – семейства

Узел 3 – предок узла 8

Узел 8 – порожденный узлом 3

1,2,5 максимальные пути

1,3,7

1, 4 – минимальный путь

4, 5, 6, 7, 8, 9 – листья

Узел 7 является левым соседом узла 8

Узел 9 является правым соседом узла 8

У узла 7 нет левого узла

Левый сосед узла 3 – узел 2

В иерархии подразумеваются связи 1:М от предка к потомку.

Дерево называется сбалансированным, если:

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

2. разница между минимальным и максимальным путем в дереве не превышает 1

Несбалансированное дерево Сбалансированное дерево

Дерево называется бинарным, если каждый узел имеет не более 2х потомков

Замечание: очень малое количество прикладных областей имеют схему данных в виде бинарных и сбалансированных деревьев.

Пример: Родословная собаки – это бинарное сбалансированное дерево.

Основное назначение рассмотренных структур – это организация поиска данных на физическом уровне, реализованном в виде индексных файлов.

Зависимость данных от структуры

Пример иерархии:

Свойство:

По экземпляру записи из отношения сотрудники. Мы не можем сказать в каком отделе он трудится и какую работу выполняет без использования связей на схеме БД. Это и есть зависимость данных от структур.

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

Правило преобразования

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

После преобразования по экземпляру записи из отношения «сотрудники» мы можем определить в каком отделе он трудится.

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

Рассмотренное преобразование не добавляет новой информации (только дублирует).