Ю. А. Григорьев, Г. И. Ревунков - Банки данных

2. Модели данных

25 символов; 01, 02 — номера уровней в схеме структуры (в данном случае в схеме структуры записи); КЛЮЧ означает, что данное поле является первичным ключом записи;

4)экземпляр сущности моделируется экземпляром записи;

5)набор экземпляров сущностей одного типа моделируется одной БД, на­ пример, БД Служащие, представляющей совокупность записей типа Служащий.

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

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

Например, связь Работает_в между сущностями Служащий и Отдел предста­ вим как самостоятельную сущность с атрибутами Шифротдела и Табельныйномер, которую можно смоделировать следующим типом записи:

01 Работаетв

02 Табельный_номер;ШАБЛОН 9999;КЛЮЧ

02 Шифр_отдела;ШАБЛОН 99;КЛЮЧ

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

Служащий:

01 Служащий

02 Табельный_номер;ШАБЛОН 9999;КЛЮЧ

02 Шифр_отдела;ШАБЛОН 99

02 Фамилия;ШАБЛОН А(25)

02 Год_рождения;ШАБЛОН 9999

02 Образование;ШАБЛОН А(10)

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

Чем больше конструкций инфологической модели ПО может быть представлено прямым моделированием при датологическом проектирова­ нии БД, тем более удачной считается рассматриваемая модель данных.

Кроме анализа возможностей прямого моделирования проектировщик оценивает и такие свойства модели данных СУБД, как:

•сложность модели для изучения пользователями;

•простота и элегантность (возможность представления структуры данных в наглядной форме);

50

2.3.Структуры, операции, ограничения

•сложность и трудоемкость написания определении данных и про­ грамм для манипулирования структурами данных и пр.

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

2.3. Структуры, операции, ограничения

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

Структуры данных

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

•поле — наименьшая поименная единица данных;

•запись — поименованная совокупность полей;

•файл — поименованная совокупность экземпляров записей одного типа;

•набор файлов (или библиотека) — поименованная совокупность файлов, обрабатываемых в системе.

В этой модели агрегация используется для композиции полей в за­ пись, а обобщение — для представления множества экземпляров записей одного типа одной общей структурой более высокого уровня — файлом. В ряде систем допускается объединение в файл экземпляров записей несколь­ ких заданных типов. Обобщение также используют для выборки из файла ПП некоторого подмножества экземпляров записей, удовлетворяющих за­ данному критерию выборки.

Существует много терминов, используемых для обозначения опре­ деленных типов структур данных. Широко распространена терминоло­ гия, предложенная КОДАСИЛ (CODASYL — the Conference on Data Systems Languages) — Ассоциацией no языкам систем обработки данных

51

2. Модели данных

Рис. 2.1. Структура данных в модели КОДАСИЛ

(рис. 2.1). Схема рисунка определяет порядок композиции структур дан­ ных этой модели.

Элемент данных — наименьшая поименованная единица данных (аналог «поля» в файловых системах), к которой СУБД может адресоваться непосредственно и с помощью которой выполняется построение всех ос­ тальных структур. Имя элемента данных используют для его идентифика­ ции в схеме структуры данных высокого уровня. Значение элемента данных может быть числового (целый, вещественный) и нечислового (символьный, логический) типа. В некоторых приложениях используется «неопределен­ ное» значение элемента данных, свидетельствующее о том, что значение соответствующего свойства объекта еще не введено в БД, а ряд других свойств, описывающих объект, уже представлены значениями.

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

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

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

52

2.3. Структуры, операции, ограничения

владельца и типы записей-членов, присваивают имя набору. Тип набора является основным композиционным элементом, с помощью которого стро­ ится структура всей базы данных в модели КОДАСИЛ. Заметим, что в дан­ ном случае термин не является аналогом набора файлов.

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

Выше рассмотрены структуры модели данных КОДАСИЛ. Однако не во всех СУБД используют рассмотренную терминологию. Поэтому при рас­ смотрении МД часто бывает удобным использовать следующую терминоло­ гию: элемент данных; группа; групповое отношение; БД.

Элемент данных соответствует определению, приведенному в терми­ нологии КОДАСИЛ.

Понятие «группа» одновременно соответствует и понятию «агрегат», и понятию «запись». Различают простую, составную и повторяющуюся группы.

Групповое отношение используют для задания связей между группами (эта структура подобна набору) в БД. Групповое отношение определяется как поименованное бинарное отношение, заданное на двух множествах экземпля­ ров рассматриваемых групп. Различают групповые отношения видов 1:1, 1:М, М: 1, М:М. В групповом отношении один тип группы назначается владельцем отношения, а второй — членом отношения. Экземпляр группового отношения представлен одним экземпляром группы типа владельца и совокупностью связанных с ним экземпляров группы типа члена отношения.

База данных — поименованная совокупность экземпляров групп и групповых отношений. В схеме БД задаются типы групп и групповых от­ ношений.

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

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

Другой формой представления схемы данных, удобной для пользова­ теля с точки зрения понимания и интерпретации, является табличная форма. При машинной обработке в качестве аналогов таблиц и их элементов могут выступать файлы, записи, поля.

Операции над данными

Динамические свойства МД выражаются множеством операций, ко­ торые определяют допустимые действия над некоторой реализацией БД для

53

Табельный номер. Фамилия, Образование, Адрес

Рис. 2.2. Пример графической диаграммы

ее перевода из одного состояния в другое. Это множество операций соотно­ сят с ЯМД.

Реализация любой конкретной операции над данными включает се­ лекцию данных, т.е. выделение из всей совокупности именно тех данных, над которыми должна быть выполнена требуемая операция, и действие над выделенными данными, которое определяет характер операции. Условие селекции специфицируется в виде некоторого критерия отбора данных, над которыми должно быть произведено требуемое действие. Использование для селекции логической позиции данного базируется на упорядоченности данных в памяти системы. В соответствии с этим можно выполнить селек­ цию данного, находящегося на первой, последней, следующей, предыдущей или П'И позиции. Этот тип селекции еще называют селекцией посредством «текущей». В качестве текущих выступают специальные дополнительные объекты — индикаторы текущего состояния. При выполнении ПП СУБД автоматически поддерживает ее индикаторы текущего состояния. Количе­ ство и состав индикаторов определяется подсхемой, используемой ПП. Ин­ дикатор указывает на некоторый экземпляр записи в БД. В некоторых моде­ лях данных «текущие» задаются явно, в других — неявно.

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

<ИМЯ АТРИБУТАхОПЕРАТОР УСЛОВИЯ><ЗНАЧЕНИЕ АТРИБУТА> Оператор условия

Из простых условий можно построить булевы условия с использова­ нием операций И (AND), ИЛИ (OR), НЕ (NOT), например:

Образование = высшее AND Стаж = 12.

54

2.3. Структуры, операции, ограничения

При необходимости изменений в условии селекции порядка предше­ ствования можно использовать круглые скобки.

По характеру проводимого действия различают следующие виды опе­ раций:

•идентификация данного и нахождение его позиции в БД;

•выборка (чтение) данного из БД;

•включение (запись) данного в БД;

•удаление данного из БД;

•модификация (изменение) данного в БД.

По характеру способа получения результата различают навигацион­ ные и спецификационные операции. Если результат операции получается путем прохождения по связям, реализованным в структуре БД, то операции называются навигационными. Навигация в БД основывается на манипули­ ровании значениями «текущих» (или курсоров, текущих указателей и т.п.), хотя это манипулирование в некоторых языках может быть неявным. Теку­ щий указатель — это специальный объект, значением которого является адрес считанного экземпляра записи. Результат навигационной операции — это единичный объект БД, например экземпляр записи.

Если в операции определяются только требования к результату, но не задается способ его получения, то такие операции называют спецификациоными. Спецификация требований может выполняться, например, по форму­ лам исчисления предикатов, что имеет место в реляционной МД. Поэтому результату спецификационной операции, в общем случае, соответствует некоторое множество объектов БД. Следует отметить, что на внутреннем уровне спецификационные операции также выполняются с помощью «те­ кущих», хотя они и не видны для пользователя.

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

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

55

2. Модели данных

Ограничения целостности

Логические ограничения, которые накладываются на данные, получи­ ли название ограничений целостности. Ограничения используют в моделях данных для поддержания адекватности отображения ПО хранимыми в базе данными и для обеспечения непротиворечивости данных при переводе базы данных из одного состояния в другое (выполнение любой из рассмотренных выше операций переводит БД в новое состояние) при функционировании СУБД:

Различают внутренние и явные ограничения целостности. Внутренние ограничения целостности представлены в МД правилами композиции до­ пустимых структур данных и в конкретной схеме БД находят свое отраже­ ние в структурных спецификациях и в правилах выполнения операций. Яв­ ные ограничения целостности специфицируются в схеме БД явным образом с помощью специальных конструкций языка описания данных.

Например, для записи типа Служащий атрибут Табельный номер оп­ ределен как первичный ключ. Это означает, что множество экземпляров записей типа Служащий, хранящихся в БД, не может содержать двух (или более) экземпляров с одинаковым значением атрибута Табельный номер.

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

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

2.4. Иерархическая и сетевая модели данных

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

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

56

2.4. Иерархическая и сетевая модели данных

Для иерархических моделей данных существуют внутренние ограни­ чения:

все типы связей должны быть функциональными, т.е. 1:1, 1 :М, М: 1; структура связей должна быть древовидной.

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

Древовидная структура, или дерево, — это связный неориентирован­ ный граф, который не содержит циклов. Обычно при работе с деревом вы­ деляют какую-то конкретную вершину, определяют ее как корень дерева и рассматривают особо — в эту вершину не заходит ни одно ребро. В этом случае дерево становится ориентированным. Ориентация обычно определя­ ется от корня. Корневое дерево как ориентированный граф определяется следующим образом:

•имеется единственная особая вершина, называемая корнем, в кото­ рую не заходит ни одно ребро;

•во все остальные вершины заходит только одно ребро, а исходит произвольное количество ребер;

•нет циклов.

Впрограммировании используют другое определение дерева — рекурсивное дерево, — позволяющее при решении задач рассматривать дерево как структуру, состоящую из меньших деревьев (поддеревьев), т.е. как рекурсивную структуру. Рекурсивное дерево определяется как конечное множество Г, состоящее из одного, двух (или более) узлов (вершин), таких, что:

•существует один специально выделенный узел, называемый корнем;

•остальные узлы разбиты на т непересекающихся подмножеств Г], Ti, ..., Т,„, каждое из которых в свою очередь является деревом.

Из определения следует, что любой узел дерева является корнем не­ которого поддерева, содержащегося в полном дереве. Число поддеревьев узла называется степенью узла. Узел называется концевым, если он имеет нулевую степень. Иногда концевые узлы называются листьями, а ребра — ветвями. Узел, не являющийся ни корнем, ни концевым узлом, называется узлом ветвления.

Таким образом, иерархическая древовидная структура, ориентирован­ ная от корня, должна удовлетворять следующим условиям:

•иерархия всегда начинается с корневого узла;

•на первом уровне иерархии находится только корневой узел;

•на нижних уровнях находятся порожденные (зависимые) узлы;

•каждый порожденный узел, находящийся на уровне /, связан только

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

57

2.Модели данных

•каждый исходный узел может иметь один или несколько непосред­ ственно порожденных узлов, называемых подобными;

•доступ к каждому порожденному узлу выполняется через его исход­ ный узел;

•существует единственный иерархический путь доступа к узлу, начи­ ная от корня дерева.

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

В иерархических МД используется ориентация древовидной структу­ ры от корня, т.е. дуги, соответствующие функциональным связям, направ­ лены от корня к листьям дерева. Графическая диаграмма схемы БД для ие­ рархической БД называется деревом определения.

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

Иерархический путь в дереве определения представляется последова­ тельностью групп, начинающейся типом корневой группы и заканчиваю­ щейся типом заданной группы.

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

На внутреннем уровне древовидные структуры представляются раз­ личными способами. Например, отдельный экземпляр структуры, соответ­ ствующий схеме БД, можно определить как экземпляр записи файла. В этом случае иерархическая БД на внутреннем уровне будет представлена одним экземпляром этого файла. Многие иерархические СУБД поддерживают

58

2.4. Иерархическая и сетевая модели данных

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

Если данные имеют естественную древовидную иерархическую структуру, то применение иерархической МД не вызывает проблем. Однако для многих практических приложений требуется реализовать структуры данных, отличные от древовидных. Поэтому в модели данных конкретных СУБД, поддерживающих иерархическую модель, могут вводится дополни­ тельные средства для представления структур данных, отличных от древо­ видных.

Одними из широко распространенных СУБД, поддерживающих ие­ рархическую модель, являются СУБД IMS, ОКА. Структурными единицами в этих СУБД являются поле, сегмент, физическая связь, физическая БД.

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

Сегмент — это поименованная совокупность полей (соответствует термину «группа»). Каждому типу сегмента присваивается имя, идентифи­ цирующее его в схеме БД. В одном сегменте может определяться до 255 полей (это внутреннее ограничение). Сегмент является единицей обмена между СУБД и программой.

Физическая связь и логическая связь соответствует понятию «группо­ вое отношение». Главный сегмент группового отношения объявляется ис­ ходным, детальный — порожденным. Экземпляры одного и того же типа порожденного сегмента, подчиненные одному и тому же экземпляру исход­ ного сегмента, называются подобными.

Физическая БД представляет собой поименованную совокупность эк­ земпляров сегментов и физических связей, образующих иерархическую структуру максимум 15-го уровня. Типов сегментов в БД должно быть не более 255, а полей — 1000.

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

Сетевая модель данных

Сетевые МД используют графовую форму представления данных. Вершины графа используются для интерпретации типов сущностей, а дуги — типов связей. При реализации модели в различных СУБД применяют раз­ личные способы представления в памяти системы данных, описывающих связи между сущностями.

59