2014-02-12
850
Рис.21
Рис.20
Рис.18
Элемент данных - наименьшая поименованная единица данных (аналог поля в файловых системах). Элемент данных - это минимальная единица данных, к которой может СУБД адресоваться непосредственно и с помощью которой осуществляется построение всех остальных структур. Примеры элементов данных: ТАБЕЛЬНЫЙ-НОМЕР, ШИФР-ДЕТАЛИ, ГОД-РОЖДЕНИЯ. Имя элемента данных используется для его идентификации в схеме структуры данных более высокого уровня. Значение элемента данных может быть числовым (целым, вещественным), нечисловым (символьным, логическим. В некоторых приложениях может использоваться “неопределенное” значение элемента данных и говорит о том, что значение соответствующего свойства объекта не определено в БД.
Агрегат данных - поименованная совокупность элементов данных внутри записи, которую можно рассматривать как единое целое. Имя агрегата используется для его идентификации в схеме структуры данного более высокого уровня. Агрегат данных может быть простым (рис19.),если состоит только из элементов данных, и составным (рис.20.), если включает в свой состав другие агрегаты.
|
|
|
| Дата | ||
| Число | Месяц | Год |
Рис.19
| Предприятие | |||
| Название | Адрес | ||
| Почто-вый индекс | Город | Улица_номер дома |
Различают агрегаты типа “вектор” и типа “повторяющаяся группа”. Агрегат, повторяющаяся компонента которого является простым элементом данных, называется “вектором”. Например агрегат ЗАРАБОТНАЯ-ПЛАТА, в котором экземпляр элемента данных может повторяться до 12 раз (за каждый месяц года). Агрегат, повторяющаяся компонента которого представлена совокупностью данных, называется повторяющейся группой. В повторяющуюся группу могут входить отдельные элементы данных, векторы, агрегаты или повторяющиеся группы. На рис.21 представлен агрегат ЗАКАЗ-НА-ПОКУПКУ, имеющий в своем составе повторяющуюся группу ПАРТИЯ-ТОВАРА.
| Заказ_на_покупку | |||||||||||||||||||||||||||
| Номер_за-каза | Дата_заказа | Партия_товара | |||||||||||||||||||||||||
| Ч и с л о | М е с я ц | Г о д | Ш и ф р т о в а р а | К о л и ч е с т в о | Ц е н а | Ш и ф р т о в а р а | К о л и ч е с т в о | Ц е н а | ... | Ш и ф р т о в а р а | К о л и ч е с т в о | Ц е н а | ||||||||||||||
Максимальное количество экземпляров для вектора и повторяющейся группы ограничено и задается при спецификации схемы записи.
Запись - поименованная совокупность элементов данных или элементов данных и агрегатов. Имя записи используется для идентификации типа записи в схемах типов структур более высокого уровня. Запись - это агрегат, не входящий в состав никакого другого агрегата. Запись может иметь сложную иерархическую структуру, поскольку допускается многократное применение агрегации.
|
|
|
Набор - поименованная совокупность записей, образующая двухуровневую иерархическую структуру. Каждый тип набора представляет собой отношение (связь) между двумя или несколькими типами записей. Для каждого типа набора один тип записи может быть объявлен “владельцем”, тогда остальные типы записей - его “члены”, т.е. различают “запись - владелец” и “запись - член набора”. Каждый экземпляр набора должен содержать один экземпляр записи, имеющий тип “запись - владелец”, и может содержать любое количество экземпляров записей типа “запись - член”.
Основное назначение набора - представление связей между записями. Если запись используется для представления сущности, то набор - для представления связей между рассматриваемыми сущностями. Термин набор не является аналогом набора файлов.
На графической диаграмме схемы БД тип набора изображается поименованной дугой между соответствующими типами записей. Дуга исходит из типа записи-владельца набора и заходит в тип записи-член набора. Тип набора - это основной структурный элемент, с помощью которого выполняется построение структуры базы данных. Структуры БД строятся на основании следующих основных композиционных правил:
База данных может содержать любое количество типов записей и типов наборов;
Между двумя типами записи может быть определено любое количество типов наборов;
Тип записи может быть владельцем и одновременно членом нескольких типов наборов.
В модели КОДАСИЛ основным внутренним ограничением целостности является функциональность связей, т.е. с помощью наборов можно реализовать непосредственно связи типа 1:1, 1:М, М:1. В модели это внутреннее ограничение выражается утверждением: в конкретном экземпляре набора экземпляр записи-члена набора может иметь не более одного экземпляра записи-владельца набора. Следовательно, число экземпляров набора некоторого типа в точности равно числу экземпляров записей-владельцев этого типа набора в БД. При этом экземпляр набора может быть и пустым, т.е. состоять из экземпляра записи-владельца (экземпляры записей-членов могут отсутствовать в некоторые моменты времени при функционировании системы). Из функционального характера реализуемых в МД связей следует второе внутреннее ограничение целостности - экземпляр записи может быть членом только одного экземпляра среди всех экземпляров набора одного типа (он может входить в состав двух и более экземпляров наборов, но различных типов).
Функциональный характер реализуемых связей не позволяет непосредственно представлять в модели связи типа “многие-ко-многим” (рис.22). Для представления связи типа М:N вводят вспомогательный тип записи и две функциональные связи типа 1:М. На рис. 23 это показано для связи СПЕЦИФИКАЦИЯ между сущностями ИЗДЕЛИЕ и ДЕТАЛЬ. Каждый экземпляр вспомогательной записи типа ИЗДЕЛИЕ-ДЕТАЛЬ имеет по одному экземпляру записей-владельцев типа ИЗДЕЛИЕ и типа ДЕТАЛЬ в одном экземпляре набора типа ИМЕЕТ-В-СОСТАВЕ и в одном экземпляре набора типа ВХОДИТ-В-СОСТАВ. Введение вспомогательной записи позволяет при необходимости ввести данные, характеризующие рассматриваемую связь. В запись типа ИЗДЕЛИЕ-ДЕТАЛЬ можно добавить, например, элемент данных типа КОЛИЧЕСТВО-ТРЕБУЕМЫХ-ДЕТАЛЕЙ, которые характеризует связь между сущностями ИЗДЕЛИЕ и ДЕТАЛЬ.
Специфи-
кация
|
|
|
Рис.22
Невозможность непосредственного представления данных, описывающих рассматриваемые связи между сущностями, выступает в качестве еще одного внутреннего ограничения модели. В модели непосредственно с помощью наборов можно представить типы связей (между сущностями), не имеющие собственных атрибутов. Если необходимо представлять связи, имеющие атрибуты, то при конструировании схемы базы данных требуется вводить вспомогательный тип записи, с помощью которого и представляются совокупности атрибутов, описывающих связь. Пример такого представления показан на рис. 12,а,б.
Рис.23.
Обычно тип набора задается между двумя типами записей. Однако в модели можно представлять типы связей, заданных между несколькими типами сущностей. Для этого используют многочленные наборы, которые представляют собой отношение между тремя или более типами записей, один из которых назначается владельцем набора, а остальные - членами набора. На рис. 24 показан пример многочленного набора НАУЧНЫЕ-ТРУДЫ, владельцем которого является запись типа НАУЧНЫЙ-СОТРУДНИК, а членами-записи типа НАУЧНЫЙ-ОТЧЕТ, ДОКЛАД-НА-КОНФЕРЕНЦИИ, СТАТЬЯ В ЖУРНАЛЕ, МОНОГРАФИЯ. Экземпляр некоторого типа многочленного набора включает в себя один экземпляр записи-владельца и все связанные с ним экземпляры записей-членов заданных типов. В конкретных СУБД концепция многочленного набора может быть не реализована.
Кроме указанных видов наборов в модели КОДАСИЛ существуют сингулярные наборы. Сингулярный набор - это особый набор, поскольку владельцем его является система. При его реализации возможен только один экземпляр этого типа. Это тип набора без записи-владельца. Пример сингулярного набора приведен на рис. 25 Сингулярный набор можно использовать для создания традиционного файла, состоящего из однотипных записей. Количество объявляемых сингулярных наборов произвольно. Один и тот же тип записи может быть объявлен членом сингулярного набора и одновременно владельцем либо членом других наборов.
 |
|
|
|
Рис.24.
 |
Рис.25.
Представим в виде сетевой модели БД “Футбол”. Создадим типы логических записей ИГРОКИ, КОМАНДЫ и ПОЗИЦИИ. - По причинам, указанным ниже, при рассмотрении связи СЕЗОН не существует типа логической связи, соответствующего набору объектов СРЕДНЯЯ ОЦЕНКА.
Для представления связи “многие ко многим” ИГРЫ между наборами объектов ИГРОКИ и ПОЗИЦИИ необходим новый тип записи, который назовем ИП (ИГРОКИ ПОЗИЦИИ). Формат записи типа ИП состоит из порядкового номера ИП ИД. Существует две связи в сетевой модели - связь ИП ИГРОКИ от типа записей ИП к типу записи ИГРОКИ и связь ИП ПОЗИЦИИ от типа записей ИП к типу записей ПОЗИЦИИ.
Для представления связи СЕЗОН между наборами объектов ИГРОКИ, КОМАНДЫ, СРЕДНЯЯ ОЦЕНКА создадим новый тип логической записи ИКС (ИГРОКИ КОМАНДЫ СРЕДНЯЯ ОЦЕНКА) с полем порядкового номера ИКС ИД, а также связь ИКС ИГРОКИ от типа записи ИКС к типу записи ИГРОКИ и связь ИКС КОМАНДЫ от типа записи ИКС к типу записи КОМАНДЫ. Связь СЕЗОНА однозначно определяет среднюю оценку для каждого игрока, можно включить атрибут ЗНАЧЕНИЕ ОЦЕНКИ в формат записи ИКС, что позволяет обойтись без типа записи СРЕДНЯЯ ОЦЕНКА.
Перечислим определенные выше типы логических записей, обозначив тип записи R с форматом A1, Aa,..., Ak как для схем отношения R(A1, Aa,..., Ak):
ИГРОКИ (ИМЯ, МЕСТО РОЖДЕНИЯ, ДАТА РОЖДЕНИЯ)
КОМАНДЫ (СПОРТКЛУБ, ГОРОД, ГОД)
ПОЗИЦИИ (НАЗНАЧЕНИЕ ПОЗИЦИИ, НОМЕР ПОЗИЦИИ) ИП (ИП ИД)
ИКС (ИКС ИД, НАЗНАЧЕНИЕ ОЦЕНКИ)
Кроме того, для данной БД имеем связи: ИП ИГРОКИ - от ИП к ИГРОКИ ИП ПОЗИЦИИ - от ИП к ПОЗИЦИИ ИКС ИГРОКИ - от ИКС к ИГРОКИ ИКС КОМАНДЫ - от ИКС к КОМАНДЫ
На рис.26 представлена полученная сетевая модель.
 |
Рис.26
На рис.27 показаны некоторые экземпляры логических записей.
| Звезда | Каменск |
 Торпедо
| Новогорск |
 Трактор
| Холмск |
|
 |
 Петров Сергей Юрьевич
| Павлово, Горьковская область | 23.03.1954 | ||
 Смирнов Виктор Павлович
| Валжай, Новгородская область | 31.01.1957 | ||
| Тимофеев Юрий Иванович | Рудня, Смоленская область | 12.06.1960 |
|
1 2 3 4...
 | |||||
 | |||||
| |||||
| Правый полузащитник | |
| Правый защитник | |
 Центральный нападающий
|
Рис.27
Древовидные иерархические структуры широко используются в повседневной человеческой деятельности. Это всевозможные классификаторы, ускоряющие поиск требуемой информации, иерархические функциональные структуры управления и т.п. Иерархические модели данных, так же как и сетевые, базируются на использовании графовой формы представления данных. В графической диаграмме схемы базы данных вершины графа также используются для интерпретации типов сущностей, а дуги - типов связей между типами сущностей. При реализации каждая вершина графа представляется совокупностью описаний экземпляров сущности соответствующего типа.
Однако в иерархической модели данных действуют более жесткие внутренние ограничения на представление связей между сущностями, чем в сетевой модели. Основные внутренние ограничения иерархической модели данных:
Все типы связей функциональные, т.е. 1:1, 1:М, М:1;
Структура связей древовидная.
Результатом действия этих ограничений является ряд особенностей процесса структуризации данных в иерархической модели.
Древовидная структура, или дерево, - это связный неориентированный граф, который не содержит циклов, т.е. петель из замкнутых путей. Обычно при работе с деревом выделяют какую-то конкретную вершину, определяют ее как корень дерева и рассматривают особо - в эту вершину не заходит ни одно ребро. В этом случае дерево становится ориентированным. Ориентация на корневом дереве определяется либо от корня, либо к корню. На рисунках корень дерева указывают либо с помощью стрелок, либо с помощью наглядного расположения (самая верхняя вершина рисунка). Корневое дерево как ориентированный граф можно определить следующим образом:
Имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;
Во все остальные вершины заходит только одно ребро, а исходит произвольное (0, 1, 2,..., n) количество ребер;
Нет циклов.
Если в полученном определении ориентацию всех ребер поменять на противоположную, то получим также определение корневого дерева.
В программировании используется другое определение дерева, позволяющее при решении задач рассматривать дерево как структуру, состоящую из меньших деревьев (или поддеревьев), т.е. как рекурсивную структуру.
Рекурсивно дерево определяется как конечное множество T, состоящее из одного или более узлов (вершин), таких, что:
Существует один специально выделенный узел, называемый корнем дерева;
Остальные узлы разбиты на m>=0 непересекающихся подмножеств T1, T2,..., Tm, каждое из которых в свою очередь является деревом.
Деревья T1, T2,..., Tn называются поддеревьями корня. Из определения следует, что любой узел дерева является корнем некоторого поддерева, содержащегося в полном дереве. Число поддеревьев узла называют степенью узла. Узел называется концевым, если он имеет нулевую степень. Иногда концевые узлы называют листьями, а ребра - ветвями. Узел, не являющийся ни корнем, ни концевым узлом, называется узлом ветвления.
Таким образом, иерархическая древовидная структура, ориентированная от корня, удовлетворяет следующим условиям:
* иерархия всегда начинается с корневого узла;
на первом уровне (i=1, самый верхний уровень иерархии дерева) может находиться только один узел - корневой; - на нижних уровнях (i=2,3,...,n) находятся порожденные (зависимые) узлы; - каждый порожденный узел, находящийся на уровне i, связан только с одним непосредственно исходным узлом (непосредственным родительским узлом), находящимся на более верхнем уровне (i-1) иерархии дерева;
· каждый исходный узел может иметь один или несколько непосредственно порожденных узлов, которые называются подобными;
· доступ к каждому порожденному узлу выполняется через его непосредственно исходный узел;
· существует единственный иерархический путь доступа к любому узлу, начиная от корня дерева (рис.28), например,путь ABEI.
Иерархический путь включает все связанные между собой узлы, начиная с корневого узла и кончая заданным. Поскольку узлы, входящие в иерархический путь, могут встретиться не более одного раза, следовательно, в древовидной структуре иерархические пути линейные. Любой узел, находящийся на иерархическом пути выше рассматриваемого узла, является для последнего исходным узлом (родительским). Любой узел, находящийся на иерархическом пути ниже рассматриваемого узла, является для него порожденным узлом. Если между рассматриваемыми узлами нет других узлов, то тогда это будет соответственно непосредственно исходный и непосредственно порожденный узлы.
Рис.28
В иерархических моделях данных используется ориентация древовидной структуры от корня, т.е. дуги, соответствующие функциональным связям, направлены от корня к листьям дерева.
Графическая диаграмма схемы базы данных для иерархической базы данных называется деревом определения.
Вершины дерева определения БД соответствуют введенным типам групп записей, с помощью которых выполнена интерпретация типов сущностей.
Обычно допускают только простые типы групп, т.е. группа, представляющая вершину дерева определения, не должна включать составные и повторяющиеся группы, поскольку их можно представить как самостоятельные вершины дерева определения. Корневой вершине дерева определения соответствует тип корневой группы, остальным вершинам - типы зависимых групп. Дуга дерева определения, соответствующая групповому отношению, представляет некоторый тип связи между рассматриваемыми типами сущностей (которые представлены соответствующими типами групп). Дуга исходит из типа родительской (исходной) группы и заходит в тип порожденной группы. Дуги обычно называют связью исходный-порожденный. Поскольку между двумя типами групп может быть не более одной такой связи, то на графической диаграмме схемы иерархической базы данных связи могут специально не помечаться. Тип зависимой группы можно идентифицировать соответствующей последовательностью связей исходный-порожденный. Иерархический путь в дереве определения представляется последовательностью групп, начинающейся типом корневой группы и заканчивающейся типом заданной группы.
Следствием внутренних ограничением иерархической модели является то, что каждому экземпляру зависимой группы в иерархической БД соответствует уникальное множество экземпляров родительских групп (по одному экземпляру каждого типа родительской группы).
На внутреннем уровне древовидные структуры могут быть представлены различными способами. Например, отдельный экземпляр структуры, соответствующий схеме базы данных, можно определить как экземпляр записи файла. В этом случае иерархическая база данных на внутреннем уровне будет представлена одним экземпляром этого файла.
Многие иерархические СУБД могут поддерживать несколько различных баз данных. В этом случае каждая БД на внутреннем уровне представляется одним файлом, который объединяет экземпляры записей одного типа со структурой, соответствующей схеме этой базы данных. На рис.29 приведен пример схемы иерархической базы данных и ее возможной реализации на внутреннем уровне
Если данные имеют естественную древовидную иерархическую структуризацию, то применение иерархической модели данных не вызывает проблем. Однако для многих практических приложений требуется реализовывать структуры данных, отличные от древовидных. Поэтому в модели данных конкретных СУБД, поддерживающих иерархическую модель, могут вводиться дополнительные средства для представления структур данных, отличных от древовидных.
Иерархия - это разновидность сети, являющаяся совокупностью деревьев (лесом), в которой все связи направлены от отца к сыну.
Рассматривая этот тип моделей, будем использовать терминологию сетевых моделей, введя дополнительное понятие - тип виртуальной логической записи (необходим, когда хотим поместить какой-либо тип записи в два или более деревьев иерархии или в нескольких местах в одном дереве). Такая запись представляет собой указатель на логическую запись некоторого типа и устраняет избыточность.
С помощью типов виртуальных записей можно преобразовать любую сеть в иерархию.
 |
Рис.29
Преобразуем в иерархию сеть, представленную на рис. 26. Начнем с типа записи ИГРОКИ, который имеет связи с ИП и ИКС. Последние два типа не имеют связей (входящих дуг), поэтому создание первого дерева завершено. Оно имеет корень ИГРОКИ и сыновей ИП и ИКС (рис.30).
Второе дерево начинаем конструировать с типа записи КОМАНДЫ, который имеет одну связь из типа записи ИКС, уже включенного в иерархию. Поэтому в качестве сына для типа записи КОМАНДЫ создаем тип виртуальной записи “указатель на ИКС”. Третье дерево состоит из корня ПОЗИЦИИ с типом виртуальной записи ИП в качестве сына. Полная иерархия (лес), состоящая из трех деревьев, представлена на рис. 30.
 |  | ||||
 | |||||
Рис.30
Иногда удобно представлять каждое дерево с фиктивным корнем, сыновьями которого являются экземпляры записей корневого типа. На рис.31 представлена часть дерева с корнем ИГРОКИ (рис. 30) с использованием фиктивного корня. Числа от 1 до 5 являются порядковыми номерами, идентифицирующими записи ИП и ИКС. В реализации такие порядковые номера исчезают.
 |
Рис. 31
Иерархические модели, построенные непосредственно из сети, часто оказываются неудобными для обработки запросов. Причина заключается в том, что связи в сети являются, по существу, двунаправленными, а при переходе к иерархической модели они нарушаются. Например, надо выяснить, на какой позиции играл Смирнов. В сетевой модели (рис.26) можно непосредственно перейти от записи ИП к записи ПОЗИЦИИ. При преобразовании сети в иерархическую структуру непосредственная связь типа ИП с типом ПОЗИЦИИ разрушается. Поэтому появляется необходимость просматривать тип записи ИГРОКИ, затем тип ИП и от него переходить к типу ПОЗИЦИИ. Недостатком является также необходимость перехода от одного дерева к другому, в то время как в сетевой модели навигация осуществляется полностью внутри нее.
Другой подход к построению иерархической модели состоит в том, что при наличии, например, наборов объектов Е1 и Е2 со связью “многие ко многим” типы записей, состоящие из ключей для Е1 и(или) Е2, заменяются указателями на записи Е1 или Е2 соответственно. Создадим новую иерархию для БД “Футбол”. Связь ИГРЫ можно выразить деревом, корнем которого является тип логической записи ИГРОКИ: (ИМЯ, МЕСТО РОЖДЕНИЯ, ДАТА РОЖДЕНИЯ).
У корня есть сын - тип логической записи (ПОРЯДКОВЫЙ НОМЕР 1, НАЗВАНИЕ ПОЗИЦИИ), представляющий названия позиций, в которых играет каждый игрок. Атрибут ПОРЯДКОВЫЙ НОМЕР 1 используется для идентификации записей. Он исчезнет в реализации при представлении адресом записи.
Для представления связи между названиями позиций и их номерами существует второе дерево, содержащее только корневой тип логической записи: (НАЗВАНИЕ ПОЗИЦИИ, НОМЕР ПОЗИЦИИ). В качестве корня третьего дерева выберем тип логической записи, состоящий только из атрибута СПОРТКЛУБ. Корень третьего дерева имеет одного сына - тип логической записи:(ПОРЯДКОВЫЙ НОМЕР 2, ГОРОД, ГОД), который, в свою очередь, имеет сына - тип логической записи: (ПОРЯДКОВЫЙ НОМЕР 3, ИМЯ, ЗНАЧЕНИЕ ОЦЕНКИ). Атрибуты ПОРЯДКОВЫЙ НОМЕР 2, и ПОРЯДКОВЫЙ НОМЕР 3 являются фиктивными и могут исчезнуть при реализации. Полная иерархическая модель представлена на рис. 32.
 |
Рис.32
