Материал: 500_Goncharov_S._A._Informatsionnye_tekhnologii_v_mediaindustrii_Upravlenie_dannymi_

Диаграмма дерева имеет высоту 4(число уровней), момент 22 (число узлов), вес 16 (число листьев), основание 1 (число корней).

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

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

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

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

Несбалансированные деревья

Рисунок 4.2 – Примеры сбалансированных и несбалансированных деревьев

26

Схема:

Основная запись Экземпляр схемы: клиента банка

Рисунок 4.3 – Пример иерархического файла

Иерархическим файлом называется файл, в котором записи связаны в виде древовидной структуры. На рисунке 4.3 приведен файл типа «основная запись – детальная запись», представляющая собой общий вид иерархического файла с двумя типами записей.

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

Контрольные вопросы к разделу 4

1.Что такое деревья?

2.Что такое исходный узел дерева?

3.Что такое порожденный узел дерева?

4.Что такое корень дерева?

5.Что такое уровень дерева?

6.Что такое сбалансированное дерево?

7.Что такое диаграмма пути дерева?

5.Сетевые структуры

Если порожденный элемент в отношении между данными имеет более одного исходного элемента, то это отношение описывают в виде сетевой структуры.

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

27

3

4

5

Рисунок 5.1 – Сетевые структуры

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

Структура на одной из линий схемы, которой сдвоенные стрелки, указывающие в разные стороны, называется сложной сетевой структурой, а схему, в которой ни на одной из линий нет сдвоенных стрелок, в обоих направлениях – простой сетевой структурой. На рисунке 5.2 показана простая сетевая структура.

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

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

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

Оказание услуг

Рисунок 5.2 – Простая сетевая структура

28

Рисунок 5.3 – Сложная сетевая структура

Представление этих отношений и образует цикл. Но не все СУБД способны представлять циклы. Специальным типом цикла является цикл, состоящий из одного только типа записи, то есть тип порожденной записи совпадает с типом исходной записи. Эта ситуация называется петлей.

Представление однородного дерева простой схемой с петлями

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

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

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

2 2 3

3 3

Рисунок 5.4 – Преобразование древовидной структуры в сетевую

29

Контрольные вопросы к разделу 5

1.Что такое сетевая структура?

2.Что такое цикл?

3.Как можно упростить сетевую структуру?

6. Реляционные БД

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

Впринципе, требуется найти такой способ описания данных, который:

1)понятен пользователю, не имеющему особых навыков в программировании;

2)позволяет подсоединять новых пользователей без изменения существующей логической структуры и ПП-й;

3)допускает максимальную гибкость при формировании непредсказуемых или случайных запросов с терминалов.

Один из самых естественных способов представления данных для

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

1)каждый элемент таблицы представляет собой один элемент данных, повторяющиеся группы отсутствуют;

2)все столбцы в таблице однородные, то есть элементы столбца имеют одинаковую природу;

3)столбцам однозначно присвоены имена;

4)в таблице нет двух одинаковых строк;

5)в операциях с такой таблицей ее строки и столбцы могут просматриваться в любом порядке и в любой последовательности безотносительно к их

информационному содержанию и смыслу.

Таблица такого вида, как на рисунке 6.1, называется отношением. БД, построенная с помощью отношений, называются реляционной БД.

30