2.2. Древовидные модели данных

В БД рассматриваются три классических модели данных: древовидные (иерархические), сетевые, реляционные. После применения правила склейки в общем случае будет получена сетевая схема БД, реже – иерархическая и еще реже – реляционная.

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

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

В древовидной схеме данных предполагается, что между узлом (схемой отношения) предком и узлом потомком установлена связь типа 1:М и каждый узел имеет не более одного предка.

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

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

Примечание. Малое количество информации может быть записано сбалансированным и бинарным деревьями. Например: родословная собаки – сбалансированное бинарное дерево, а потомки собаки – несбалансированное и не бинарное дерево. Особое значение сбалансированные и бинарные деревья имеют для представления информации на физическом уровне (организация индексных файлов). Записи во всех узлах однотипны, а связи-ссылки не имеют содержательного смысла. Используются только для представления лексикографического порядка узлов. Такие деревья называют иерархическими файлами.

Зависимость данных от структуры. Если в структурированном представлении данных для получения каких-либо сведений требуется воспользоваться связями, то такое представление называется зависимым от структуры.

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

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

Свойство. Если схема данных содержит связь типа М:М, то она является сетевой.

Определение. Схема данных, в которой явно присутствует связь типа М:М, называется сложной сетевой схемой, в противном случае – простым.

Правило преобразования сложной сетевой схемы к простой сетевой. Допустим, что схема данных содержит две схемы отношений (типов записей) со связью М:М. A и B ‑ ключи этих записей. Создается новое отношение с ключом A+B. Со схемы удаляется связь типа М:М, а от нового отношения устанавливается связь М:1 к исходным отношениям.

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

Общие данные, данные пересечения, изолированные данные:

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

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

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