графическое изображение в виде чего изображается иерархическая структура базы данных
—> Электронный кабинет преподавателя Емельяновой М.С.
Ядром любой базы данных является модель данных. Модель данных представляет собой множество структур данных, ограничений целостности и операций манипулирования данными. С помощью модели данных могут быть представлены объекты предметной области и взаимосвязи между ними.
СУБД основывается на использовании иерархической, сетевой или реляционной модели, на комбинации этих моделей или на некотором их подмножестве [1].
Рассмотрим три основных типа моделей данных: иерархическую, сетевую и реляционную.
Иерархическая модель данных
Иерархическая структура представляет совокупность элементов, связанных между собой по определенным правилам. Объекты, связанные иерархическими отношениями, образуют ориентированный граф (перевернутое дерево), вид которого представлен на рис. 15.8.
К основным понятиям иерархической структуры относятся: уровень, элемент (узел), связь. Узел – это совокупность атрибутов данных, описывающих некоторый объект. На схеме иерархического дерева узлы представляются вершинами графа. Каждый узел на более низком уровне связан только с одним узлом, находящимся на более высоком уровне. Иерархическое дерево имеет только одну вершину (корень дерева), не подчиненную никакой другой вершине и находящуюся на самом верхнем (первом) уровне. Зависимые (подчиненные) узлы находятся на втором, третьем и т.д. уровнях. Количество деревьев в базе данных определяется числом корневых записей.
К каждой записи базы данных существует только один (иерархический) путь от корневой записи. Например, как видно из рис. 15.8, для записи С4 путь проходит через записи А и В3.
Рис. 15.8. Графическое изображение иерархической структуры БД
Пример 15.4. Пример, представленный на рис. 15.9, иллюстрирует использование иерархической модели базы данных.
Для рассматриваемого примера иерархическая структура правомерна, так как каждый студент учится в определенной (только одной) группе, которая относится к определенному (только одному) институту.
Сетевая модель данных
В сетевой структуре при тех же основных понятиях (уровень, узел, связь) каждый элемент может быть связан с любым другим элементом.
На рис. 15.10 изображена сетевая структура базы данных в виде графа.
Пример 15.5. Примером сложной сетевой структуры может служить структура базы данных, содержащей сведения о студентах, участвующих в научно-исследовательских работах (НИРС). Возможно участие одного студента в нескольких НИРС, а также участие нескольких студентов в разработке одной НИРС. Графическое изображение описанной в примере сетевой структуры, состоящей только из двух типов записей, показано на рис. 15.11. Единственное отношение представляет собой сложную связь между записями в обоих направлениях.
Рис. 15.9. Пример иерархической структуры БД
Рис. 15.10. Графическое изображение сетевой структуры
Рис. 15.11. Пример сетевой структуры БД
Реляционная модель данных
Понятие реляционный (англ. relation – отношение) связано с разработками известного американского специалиста в области систем баз данных Е. Кодда.
Эти модели характеризуются простотой структуры данных, удобным для пользователя табличным представлением и возможностью использования формального аппарата алгебры отношений и реляционного исчисления для обработки данных.
Реляционная модель ориентирована на организацию данных в виде двумерных таблиц. Каждая реляционная таблица представляет собой двумерный массив и обладает следующими свойствами:
«каждый элемент таблицы – один элемент данных;
все столбцы в таблице однородные, т.е. все элементы в столбце имеют одинаковый тип (числовой, символьный и т.д.) и длину;
каждый столбец имеет уникальное имя;
одинаковые строки в таблице отсутствуют;
порядок следования строк и столбцов может быть произвольным.
Пример 15.6. Реляционной таблицей можно представить информацию о студентах, обучающихся в вузе (рис. 15.12).
Рис. 15.12. Пример реляционной таблицы
Отношения представлены в виде таблиц, строки которых соответствуют кортежам или записям, а столбцы – атрибутам отношений, доменам, полям.
Поле, каждое значение которого однозначно определяет соответствующую запись, называется простым ключом (ключевым полем). Если записи однозначно определяются значениями нескольких полей, то такая таблица базы данных имеет составной ключ. В примере, показанном на рис. 15.12, ключевым полем таблицы является «№ личного дела».
Чтобы связать две реляционные таблицы, необходимо ключ первой таблицы ввести в состав ключа второй таблицы (возможно совпадение ключей); в противном случае нужно ввести в структуру первой таблицы внешний ключ – ключ второй таблицы.
Пример 15.7. На рис. 15.13 показан пример реляционной модели, построенной на основе отношений: СТУДЕНТ, СЕССИЯ, СТИПЕНДИЯ.
Рис. 15.13. Пример реляционной модели
СТУДЕНТ (Номер, Фамилия, Имя, Отчество, Пол, Дата рождения, Группа);
СЕССИЯ (Номер, Оценка1, Оценка2, Оценка3, Оценка4, Результат);
СТИПЕНДИЯ (Результат, Процент).
Таблицы СТУДЕНТ И СЕССИЯ имеют совпадающие ключи (Номер), что дает возможность легко организовать связь между ними. Таблица СЕССИЯ имеет первичный ключ Номер и содержит внешний ключ Результат, который обеспечивает ее связь с таблицей СТИПЕНДИЯ.
Модели организации баз данных
2. Сетевая модель данных. В сетевых БД наряду с вертикальными реализованы и горизонтальные связи. Однако унаследованы многие недостатки иерархической и главный из них, необходимость четко определять на физическом уровне связи данных и столь же четко следовать этой структуре связей при запросах к базе.
3. Реляционная модель. Реляционная модель появилась вследствие стремления сделать базу данных как можно более гибкой. Данная модель предоставила простой и эффективный механизм поддержания связей данных.
Рассмотрим более подробно эти модели данных далее.
Иерархическая модель базы данных
Корневая запись каждого дерева обязательно должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальное значение только в рамках группового отношения. Каждая запись идентифицируется полным сцепленным ключом, под которым понимается совокупность ключей всех записей от корневой, по иерархическому пути.
Пример
Рассмотрим следующую модель данных предприятия (см. рис. 4.2): предприятие состоит из отделов, в которых работают сотрудники. В каждом отделе может работать несколько сотрудников, но сотрудник не может работать более чем в одном отделе.
Поэтому, для информационной системы управления персоналом необходимо создать групповое отношение, состоящее из родительской записи ОТДЕЛ (НАИМЕНОВАНИЕ_ОТДЕЛА, ЧИСЛО_РАБОТНИКОВ) и дочерней записи СОТРУДНИК (ФАМИЛИЯ, ДОЛЖНОСТЬ, ОКЛАД). Это отношение показано на рис. 4.2 (а) (Для простоты полагается, что имеются только две дочерние записи).
Из этого примера видны недостатки иерархических БД :
Частично дублируется информация между записями СОТРУДНИК и ИСПОЛНИТЕЛЬ (такие записи называют парными), причем в иерархической модели данных не предусмотрена поддержка соответствия между парными записями.
Иерархическая модель реализует отношение между исходной и дочерней записью по схеме 1:N, то есть одной родительской записи может соответствовать любое число дочерних.
Операции над данными, определенные в иерархической модели :
В операции ИЗВЛЕЧЬ допускается задание условий выборки (например, извлечь сотрудников с окладом более 10 тысяч руб.)
Как видим, все операции изменения применяются только к одной «текущей» записи (которая предварительно извлечена из базы данных ). Такой подход к манипулированию данных получил название «навигационного».
Ограничения целостности
Поддерживается только целостность связей между владельцами и членами группового отношения (никакой потомок не может существовать без предка). Как уже отмечалось, не обеспечивается автоматическое поддержание соответствия парных записей, входящих в разные иерархии.
IT-блог о веб-технологиях, серверах, протоколах, базах данных, СУБД, SQL, компьютерных сетях, языках программирования и создание сайтов.
Иерархическая база данных. Иерархическая модель данных
Здравствуйте, уважаемые посетители моего скромного блога для начинающих вебразработчиков и web мастеров ZametkiNaPolyah.ru. Продолжаем рубрику Заметки о MySQL, в которой уже были публикации: Нормальные формы и транзитивная зависимость, избыточность данных в базе данных, типы и виды баз данных, настройка MySQL сервера и файл my.ini, MySQL сервер, установка и настройка, Архитектура СУБД и архитектура баз данных, Сетевая база данных, сетевая модель данных. Я продолжаю рассматривать различные модели данных, и сегодня мы поговорим про иерархическую модель данных или иначе – иерархическую базу данных.
Стоит сказать, что иерархическая база данных является частным случаем сетевой модели данных, о которой мы говорили в предыдущей публикации. Но дело все в том, что и иерархическая модель данных, и сетевые базы данных являются мало эффективными, и постепенно от их использования отказываются. Иерархические и сетевые СУБД остались только в некоторых крупных фирмах, которые наполняли такие базы годами. И сейчас основной проблемой для таких фирм является проблема совместимости иерархических и сетевых баз данных с реляционными базами данных. Ну а сегодня мы просто поговорим про иерархическую базу данных.
Иерархическая модель данных
Иерархическая модель данных является частным случаем сетевой модели данных, структура иерархической базы данных немного проще сетевой и, соответственно, иерархические базы данных даже менее эффективны, чем сетевые. Иерархическая модель данных, как и сетевые БД опирается на теорию графов.
Иерархическая база данных. Иерархическая модель данных.
В основе иерархической модели данных лежит один главный элемент (главный узел), с которого все и начинается, такой элемент называет корневым элементом, в теории графов это называется корнем дерева. Вообще, по сути, что сетевая база данных, что иерархическая база данных имеет древовидную структуру. Все элементы или узлы, которые находятся ниже корневого узла иерархической модели, являются потомками корня. Стоит сказать, что и иерархическая база данных, и сетевая база данных оптимизированы на чтение информации из БД, но не на запись информации в базу данных, эта особенность обусловлена самой моделью данных.
Узлы дерева, которые находятся на одном уровне, обычно называются братьями. Узлы, которые находятся ниже какого-то определенного уровня, являются дочерними узлами по отношению к нему. Иерархическую модель данных можно сравнить с файловой системой компьютера. Компьютер умеет очень быстро работать с отдельными файлами: удалять конкретный файл, редактировать файл, копировать или перемещать файл. Но операция проверки компьютера антивирусом может происходить достаточно длительное время.
Точно такие же особенности присуще иерархической СУБД, то есть базы данных, имеющие иерархическую структуру, умеют очень быстро находить и выбирать информацию и отдавать ее пользователю. Но структура иерархической модели данных не позволяет столь же быстро перебирать информацию. Ну, это видно из рисунка, представленного выше. Допустим, что нам необходимо найти все записи, содержащие слово «сотрудник». Как будет поступать иерархическая СУБД в этом случае? А поступать она будет следующим образом: свой поиск она начнет с корневого элемента иерархической модели данных, проверив его, она начнет проверять его связи, если связей будет несколько, то она пойдет проверять в крайний левый дочерний элемент, расположенный на уровень ниже.
Затем иерархическая СУБД проверит содержимое этого элемента и его связи, если связей опять будет несколько, то она отправится опять-таки в крайний левый дочерний элемент, чтобы проверить его содержимое, проверив его содержимое она увидит, что у этого узла нет дочерних элементов и вернется в родительский узел этого узла, чтобы проверить, есть ли у него еще дочерние элементы. И так постепенно, узел за узлом, спуская и поднимаясь по иерархии узлов СУБД переберет все узлы и выдаст нам все записи, в которых есть слово «сотрудник». Ну, думаю, что с иерархической моделью данных мы более-менее разобрались (если не разобрались, то пишите в комментарии), можно приступить к рассмотрению структуры иерархической базы данных.
Структура иерархической базы данных
Самые первые в мире СУБД использовали иерархическую модель данных, иерархические базы данных появились даже раньше, чем сетевая модель хранения данных. Поэтому структура иерархической базы данных немного проще, чем структура сетевой БД. И так, основными информационными единицами иерархической модели данных являются сегмент и поле. Поле данных является наименьшей неделимой информационной единицей иерархической базы данных, доступной пользователю. У сегмента данных можно определить его тип и экземпляр сегмента.
Иерархическая база данных. Иерархическая модель данных.
Экземпляр сегмента образуется из конкретных значений полей данных. Тип сегмента – это именованная совокупность всех типов полей данных, входящих в данный сегмент. Если ориентироваться по рисунку выше, то тип сегмента – это родительский элемент и все его дочерние элементы. Как я уже говорил: иерархическая модель данных базируется на теории графов, но если структура сетевой БД описывается ориентированным графом (графом со стрелочками), то структура иерархической базы данных описывается неориентированным графом. Характерной особенностью структуры иерархической модели данных является то, что у любого потомка или дочернего элемента может быть только один предок или родительский элемент.
Каждый узел иерархического дерева или каждый элемент иерархической базы данных является сегментом данных. Линии, соединяющие сегменты – это связи между информационными объектами иерархической базы данных. Рисунок должен внести дополнительную ясность:
На концептуальном уровне иерархическая база данных является частным случаем сетевой модели данных.
Преобразование концептуальной модели в иерархическую модель данных
Преобразование концептуальной модели в иерархическую модель данных происходит аналогично преобразованию в сетевую модель данных, но существую некоторые тонкости, о которых мы и поговорим. Эти тонкости связаны с тем, что структура иерархической базы данных должна быть представлена в виде дерева, то есть данные иерархической модели должны быть организованы в виде дерева.
Как вы помните: дуги, соединяющие узлы между собой, – это связи. Связи бывают один к одному и один ко многим. Преобразование связей один ко многим происходит автоматически в том случае, если потомок иерархического дерева имеет только одного предка. Происходит это следующим образом: Каждый объект с его атрибутами, участвующий в такой связи, становится логическим сегментом. Между двумя логическими сегментами устанавливается связь типа «один ко многим». Сегмент со стороны «много» становится потомком, а сегмент со стороны «один» становится предком. Согласитесь, что преобразование в иерархическую модель данных похоже на преобразование в сетевую модель.
Ситуация значительно усложняется, если потомок в связи имеет не одного, а двух и более предков. Так как подобное положение является невозможным для иерархической модели, то отражаемая структура данных нуждается в преобразованиях, которые сводятся к замене одного дерева, например, двумя (если имеется два предка). В результате такого преобразования в базе данных появляется избыточность, так как единственно возможный выход из этой ситуации — дублирование данных.
Управление иерархическими данными
У иерархической модели данных существует два средства управления данными: языковые средства описания данных (ЯОД) и языковые средства манипулирования данными (ЯМД). Физическая структура иерархической базы данных описывает: логическую структуру иерархической модели данных и саму структуру хранения базы данных.
При этом способ доступа устанавливает способ организации взаимосвязи физических записей. Определены следующие способы доступа:
Помимо того, что обязательно должно быть задано имя иерархической базы данных и способа доступа к каждому элементу иерархической модели данных, описание иерархической БД должно содержать определение типов каждого сегмента данных, входящих в базу данных, в соответствие с выстроенной иерархией. Описание типов сегмента следует начинать с корня иерархической модели. Особенностью иерархических баз данных является то, что каждая физическая база данных может содержать только один корень, но в одной иерархической системе может находиться несколько физических баз данных.
Среди операторов манипулирования данными для иерархической базы данных можно выделить операторы поиска данных, операторы поиска данных с возможностью модификации, операторы модификации данных. Набор операций манипулирования данными в иерархической модели данных не так уж обширен, но этого набора вполне достаточно для управления и поддержания иерархических баз данных. Примеры типичных операторов поиска данных:
Примеры типичных операторов поиска данных с возможностью модификации:
Примеры типичных операторов модификации иерархически организованных данных, которые выполняются после выполнения одного из операторов второй группы (поиска данных с возможностью модификации):
Модели организации баз данных
2. Сетевая модель данных. В сетевых БД наряду с вертикальными реализованы и горизонтальные связи. Однако унаследованы многие недостатки иерархической и главный из них, необходимость четко определять на физическом уровне связи данных и столь же четко следовать этой структуре связей при запросах к базе.
3. Реляционная модель. Реляционная модель появилась вследствие стремления сделать базу данных как можно более гибкой. Данная модель предоставила простой и эффективный механизм поддержания связей данных.
Рассмотрим более подробно эти модели данных далее.
Иерархическая модель базы данных
Корневая запись каждого дерева обязательно должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальное значение только в рамках группового отношения. Каждая запись идентифицируется полным сцепленным ключом, под которым понимается совокупность ключей всех записей от корневой, по иерархическому пути.
Пример
Рассмотрим следующую модель данных предприятия (см. рис. 4.2): предприятие состоит из отделов, в которых работают сотрудники. В каждом отделе может работать несколько сотрудников, но сотрудник не может работать более чем в одном отделе.
Поэтому, для информационной системы управления персоналом необходимо создать групповое отношение, состоящее из родительской записи ОТДЕЛ (НАИМЕНОВАНИЕ_ОТДЕЛА, ЧИСЛО_РАБОТНИКОВ) и дочерней записи СОТРУДНИК (ФАМИЛИЯ, ДОЛЖНОСТЬ, ОКЛАД). Это отношение показано на рис. 4.2 (а) (Для простоты полагается, что имеются только две дочерние записи).
Из этого примера видны недостатки иерархических БД :
Частично дублируется информация между записями СОТРУДНИК и ИСПОЛНИТЕЛЬ (такие записи называют парными), причем в иерархической модели данных не предусмотрена поддержка соответствия между парными записями.
Иерархическая модель реализует отношение между исходной и дочерней записью по схеме 1:N, то есть одной родительской записи может соответствовать любое число дочерних.
Операции над данными, определенные в иерархической модели :
В операции ИЗВЛЕЧЬ допускается задание условий выборки (например, извлечь сотрудников с окладом более 10 тысяч руб.)
Как видим, все операции изменения применяются только к одной «текущей» записи (которая предварительно извлечена из базы данных ). Такой подход к манипулированию данных получил название «навигационного».
Ограничения целостности
Поддерживается только целостность связей между владельцами и членами группового отношения (никакой потомок не может существовать без предка). Как уже отмечалось, не обеспечивается автоматическое поддержание соответствия парных записей, входящих в разные иерархии.
Иерархические модели данных. Деревья в СУБД Cache
Иерархии так широко распространены в моделях окружающей нас действительности, что профессионал в области баз данных не может без них обойтись. Если вы не будете работать с иерархическими моделями данных, то уж моделировать иерархии в рамках используемых моделей вам придется обязательно.
3.1 Иерархическая и сетевая модели
Возможно, где-нибудь вы прочли о том, что иерархическая модель была первой реализованной в базах данных моделью. Это так. Обычно за этой фразой следует утверждение о том, что иерархическая модель представляет только исторический интерес, или о том, что иерархические базы данных в настоящее время не существуют. Вот это уже неправда. Давайте разберемся.
Прежде всего, иерархии настолько распространены, что трудно представить игнорирующую их модель сколько-нибудь интересного фрагмента Мира.
Во-вторых, в информатике иерархические структуры данных встречаются на каждом шагу. Достаточно вспомнить структуру каталогов нашего компьютера или любого сайта Интернет.
В этом разделе будут бегло рассмотрены не иерархические и сетевые модели вообще, а те ограниченные их варианты, которые доминировали на рынке баз данных в 60-е и 70-е годы прошлого века. В настоящее время иерархии чаще всего связаны с XML, либо эмулируются в других моделях, например, реляционной, а сетевые модели это скорее всего семантические сети.
Помня о том, что само понятие модели данных появилось в связи с разработкой реляционной модели, перечислим основные особенности реализаций ранних моделей данных:
Конечно, перечисленные особенности относятся скорее к реализациям, чем к самим моделям. Тем не менее, классические сетевая и иерархическая модели вошли в историю именно с такими недостатками.
3.1.1 Сетевая модель
Существовало несколько определений сетевой модели данных. В некоторых допускались бинарные связи «многие ко многим». В варианте, предложенном CODASYL, допускаются только связи типов 
и следовательно 
. Это представление и будет рассмотрено.
Сетевая модель строится из элементов данных, типов записей и типов наборов. Как станет понятно в следующих главах, их аналогами в реляционной модели являются атрибут, отношение и связь между отношениями, соответственно.
Графически такая сеть представляется диаграммами, в которых прямоугольники изображают типы записей, а стрелки, имеющие наименования, типы набора. Для связи типа 1 : n между двумя типами записей стрелка должна исходить от типа, называемого владельцем набора, к типу, называемому членом набора (рисунок 3.1).
Заметим, что аналоги типа набора известны и в языках программирования общего назначения. Это записи с повторениями значений элемента данных. Существуют многочленные наборы, у которых на одного владельца набора приходится более одного члена набора (рисунок 3.2), выделен класс сингулярных типов набора (рисунок 3.3), которые используются для объединения записей, не имеющих естественного владельца, либо для включения записей, которые при вводе в базу не имеют естественного владельца, но могут приобрести его впоследствии (при этом, запись перемещается из сингулярного набора в экземпляр набора с новым владельцем записи).
Наборы реализуются программно с помощью указателей, устанавливающих связь между владельцем и членом набора. Для создания связи 
в запись-владелец отношения включается дополнительное поле, представляющее указатель на запись-член отношения. Для организации связей и 
вводится дополнительный тип записей, полями которого являются указатели.
В сетевой модели тип записи может быть членом нескольких наборов. В одних он может играть роль владельца набора, а в других — роль члена набора. В этом случае вводится несколько дополнительных групп указателей, а в типе-владельце набора добавляют несколько полей, указывающих на эти группы.
В итоге множество типов записей и типов связей между ними образует сетевую структуру представляемую ориентированным графом. Вершины этого графа —типы записей, его дуги, направленные от владельца к члену набора, — связи между типами записей. Операции над данными в сетевой модели реализуются через действия со списковыми структурами.
Для того чтобы понять, какие проблемы возникают при работе со списковыми структурами рассмотрим два варианта реализации указателей: с указателем следующей записи и с массивом указателей.
Вариант с указателем следующей записи (рисунок 3.4) обеспечивает последовательный доступ к записям-членам набора. По экземпляру записи-владельца набора обеспечивается последовательный просмотр записей-членов наборов.
Если удалить запись, то в предыдущей записи необходимо скорректировать указатель. Это недостаток. Достоинство —экономия памяти.
Вариант с массивом указателей отличается независимостью указателей, но увеличивает их число (рисунок 3.5).
Из-за общности сетевой модели в ней может быть представлена любая ER-диаграмма. К недостаткам сетевой модели можно отнести сложность получаемой на её основе концептуальной схемы и трудность её восприятия пользователем.
3.1.2 Иерархическая модель
Реализация наборов в иерархической модели, как и в сетевой, может осуществляться с помощью указателей. Иерархическая модель отличается от сетевой модели рядом особенностей. Многочленные наборы определяют отношения соподчиненности. Тип —владелец набора называется предком, подчиненный тип —потомком. Особенности иерархической модели:
Пример иерархической модели приведен на рисунках 3.6 и 3.7. Штриховыми линиями выделены виртуальные узлы и связи, которые обеспечивают физическое хранение единственного экземпляра записи, воспринимаемого на логическом уровне одновременно как экземпляр типов «Руководитель» и «Работник».
Иерархическая база данных может представлять совокупность нескольких деревьев. В частности, некоторые из них могут описывать структуры данных, а другие — сами данные, размещённые в этих структурах. Дополнительные горизонтальные ссылки могут существовать между узлами нескольких уровней, в том числе находящихся в разных деревьях. Такие ссылки позволяют использовать один набор записей в нескольких деревьях, не дублируя его. Широкое распространение иерархической модели было обусловлено, в частности тем, что большинство организационных систем в то время имели иерархическую структуру.
Программы, реализующие операции иерархической модели, существенно проще, чем аналогичные программы для сетевой модели. При выполнении операций манипулирования данными в иерархической модели следует учитывать, что узел потомка не может существовать при удалении предка. Недостатки у иерархической модели те же, что у сетевой, плюс недостатки, связанные с ограниченностью связей.