Банк данных (стр. 7 )

Правила изображения схемы

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

Один из способов представления схемы, приведенной на рис. 15, в соответствии с этими правилами (стрелки не являются обязательными).

Рис. 15

Тема: Модели данных.

Совокупность данных, изображенных на рис. 7, описывается как двумерный (плоский) файл.

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

Деревья.

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

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

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

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

Рис. 16

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

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

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

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

Рис.17

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

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

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

Рис.18

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

Иерархическая модель данных лежит в основе таких СУБД, как Ока и ИНЕС.

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

В системе ИНЕС существует три категории типов данных:

Элементарные; Структурные; Ссылочные.

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

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

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

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

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

В дополнение к словарям типа идентификатор могут существовать словари типа код. Эти данные имеют форму: код – текст – синонимы. Пример: шифр предприятия – полное наименование предприятия – краткое наименование предприятия.

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

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

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

Рис.19

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

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

Рис.20

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

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

Рис.21

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

Генеалогическое дерево можно представить схемой, приведенной на рисунке 23. Большинство других однородных структур можно упростить аналогично, но в большинстве СУБД петли не допускается.

Рис.22                                Рис. 23

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

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

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

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

Преобразование сети с рис. 21

Рис. 24

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

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

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

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