Древовидные иерархические структуры широко используются в повседневной деятельности. Это – всевозможные классификаторы, ускоряющие поиск требуемой информации, иерархические функциональные структуры управления и т.п. Иерархические модели данных базируются на использовании графовой и табличной форм представления данных.
В графической диаграмме схемы БД вершина графа используется для интерпретации типов сущностей, а дуги – для интерпретации типов связей между типами сущностей. При реализации иерархической БД вершины представляют таблицами описаний экземпляров сущностей соответствующего типа, а связи между вершинами – адресными ссылками.
Для иерархических моделей данных существуют внутренние ограничения:
все типы связей должны быть функциональными, т.е. 1:1, 1: М, M:l;
структура связей должна быть древовидной.
Результатом действий этих ограничений является ряд особенностей процесса структуризации данных в иерархической модели.
Древовидная структура, или дерево, – это связный неориентированный граф, который не содержит циклов. Обычно при работе с деревом выделяют какую-то конкретную вершину, определяют ее как корень дерева и рассматривают особо – в эту вершину не заходит ни одно ребро. В этом случае дерево становится ориентированным. Ориентация обычно определяется от корня. Корневое дерево как ориентированный граф определяется следующим образом:
• имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;
• во все остальные вершины заходит только одно ребро, а исходит произвольное количество ребер;
• нет циклов.
В программировании используют другое определение дерева – рекурсивное дерево, – позволяющее при решении задач рассматривать дерево как структуру, состоящую из меньших деревьев (поддеревьев), т.е. как рекурсивную структуру. Рекурсивное дерево определяется как конечное множество Т, состоящее из одного, двух (или более) узлов (вершин), таких, что:
• существует один специально выделенный узел, называемый корнем;
• остальные узлы разбиты на т непересекающихся подмножеств T 1, T 2,..., Tm,каждое из которых в свою очередь является деревом.
Из определения следует, что любой узел дерева является корнем некоторого поддерева, содержащегося в полном дереве. Число поддеревьев узла называется степенью узла. Узел называется концевым, если он имеет нулевую степень. Иногда концевые узлы называются листьями, а ребра -ветвями. Узел, не являющийся ни корнем, ни концевым узлом, называется узлом ветвления.
Таким образом, иерархическая древовидная структура, ориентированная от корня, должна удовлетворять следующим условиям:
• иерархия всегда начинается с корневого узла;
• на первом уровне иерархии находится только корневой узел;
• на нижних уровнях находятся порожденные (зависимые) узлы;
• каждый порожденный узел, находящийся на уровне i, связан только с одним непосредственно исходным узлом (непосредственно родительским узлом), находящимся на более верхнем (i - 1)-м уровне иерархии дерева;
• каждый исходный узел может иметь один или несколько непосредственно порожденных узлов, называемых подобными;
• доступ к каждому порожденному узлу выполняется через его исходный узел;
• существует единственный иерархический путь доступа к узлу, начиная от корня дерева.
Иерархический путь включает все связанные между собой узлы. Узел, находящийся на иерархическом пути выше рассматриваемого узла, называется для последнего исходным узлом, а ниже – порожденным. Если между узлами нет других узлов, то это будут соответственно непосредственно исходный и непосредственно порожденный узлы.
В иерархических МД используется ориентация древовидной структуры от корня, т.е. дуги, соответствующие функциональным связям, направлены от корня к листьям дерева. Графическая диаграмма схемы БД для иерархической БД называется деревом определения.
Вершины дерева определения БД соответствуют введенным типам групп записей, с помощью которых выполнена интерпретация типов сущностей. Допускаются только простые типы групп, т.е. группа, представляющая вершину дерева определения, не должна включать составные и повторяющиеся группы, так как их можно представить как самостоятельные вершины дерева определения. Корневой вершине дерева определения соответствует тип корневой группы, остальным вершинам – типы зависимых групп. Дуга дерева определения, соответствующая групповому отношению, представляет некоторый тип связи между рассматриваемыми типами сущностей, которые представлены соответствующими типами групп. Дуга исходит из родительской группы и заходит в порожденную группу. Дуги обычно называют связью исходный–порожденный. Поскольку между двумя типами групп существует одна связь, на графической диаграмме схемы иерархической БД связи могут специально не именоваться. Тип зависимой группы можно идентифицировать соответствующей последовательностью связей исходный–порожденный.
Иерархический путь в дереве определения представляется последовательностью групп, начинающейся типом корневой группы и заканчивающейся типом заданной группы.
Следствием внутренних ограничений иерархической модели является тот факт, что каждому экземпляру зависимой группы в иерархической БД соответствует уникальное множество экземпляров родительских групп (по одному экземпляру каждого типа родительской группы).
На внутреннем уровне древовидные структуры представляются различными способами. Например, отдельный экземпляр структуры, соответствующий схеме БД, можно определить как экземпляр записи файла. В этом случае иерархическая БД на внутреннем уровне будет представлена одним экземпляром этого файла. Многие иерархические СУБД поддерживают несколько различных БД. В этом случае каждая БД на внутреннем уровне представляется одним файлом, который объединяет экземпляры записей одного типа со структурой, соответствующей схеме этой базы данных.
Если данные имеют естественную древовидную иерархическую структуру, то применение иерархической МД не вызывает проблем. Однако для многих практических приложений требуется реализовать структуры данных, отличные от древовидных. Поэтому в модели данных конкретных СУБД, поддерживающих иерархическую модель, могут вводится дополнительные средства для представления структур данных, отличных от древовидных.
Одними из широко распространенных СУБД, поддерживающих иерархическую модель, являются СУБД IMS, OKA. Структурными единицами в этих СУБД являются поле, сегмент, физическая связь, физическая БД.
Поле – наименьшая поименованная единица данных, она может принимать символьные и числовые значения. Поля в каждом экземпляре сегмента имеют постоянную длину. Повторяющиеся поля не допускаются. При описании поля ему присваивается уникальное в сегменте имя, указывается тип допустимых значений, размер в байтах и его расположение в сегменте.
Сегмент – это поименованная совокупность полей (соответствует термину «группа»). Каждому типу сегмента присваивается имя, идентифицирующее его в схеме БД. В одном сегменте может определяться до 255 полей (это внутреннее ограничение). Сегмент является единицей обмена между СУБД и программой.
Физическая связь и логическая связь соответствует понятию «групповое отношение». Главный сегмент группового отношения объявляется исходным, детальный – порожденным. Экземпляры одного и того же типа порожденного сегмента, подчиненные одному и тому же экземпляру исходного сегмента, называются подобными.
Физическая БД представляет собой поименованную совокупность экземпляров сегментов и физических связей, образующих иерархическую структуру максимум 15-го уровня. Типов сегментов в БД должно быть не более 255, а полей – 1000.
Логические связи могут связывать сегменты не только в одной, но и в нескольких физических БД и позволяют при необходимости определять сетевые структуры.
Сетевая модель данных
Сетевые МД используют графовую форму представления данных. Вершины графа используются для интерпретации типов сущностей, а дуги – типов связей. При реализации модели в различных СУБД применяют различные способы представления в памяти системы данных, описывающих связи между сущностями.
Большое влияние на развитие сетевой модели данных и соответствующих СУБД оказали предложения РГБД – Рабочей группы по базам данных (DBTG – Data Base Task Group) Ассоциации по языкам систем обработки данных – КОДАСИЛ. Эта модель считается наиболее развитой сетевой МД. Она постоянно развивается, совершенствуются средства формальной спецификации элементов модели, исследуются аспекты возможной стандартизации.
Основные типы структур модели Кодасил: элемент данных, агрегат, запись, набор, БД (см. § 2.3).
Типы наборов используются для представления типов связей между типами сущностей, представленных соответствующими типами записей. На графической диаграмме схемы БД тип набора изображают поименованной дугой от записи-владельца к записи-члена.
В основе создания структур БД лежат следующие композиционные правила:
• БД может содержать любое количество типов записей и типов наборов;
• между двумя типами записей может быть определено любое количество типов наборов;
• тип записи может быть одновременно и владельцем, и членом нескольких различных типов наборов.
Модель реализует только связи 1:1, 1: М, М:1, причем набор нельзя описывать атрибутами – это внутренние ограничения модели. В случае необходимости представления связей типа М: М вводят вспомогательный тип записи и две связи – 1: М и М:1 (рис. 2.3).
Кроме указанных видов наборов в модели существуют еще так называемые «сингулярные наборы». У сингулярного набора владельцем является система. Сингулярный набор обычно объявляется для некоторой записи-владельца, чтобы получить доступ ко всем экземплярам этого типа записи, а следовательно, и ко всем экземплярам набора соответствующего типа (владельцем которого является данный тип записи-владельца).
Любой вводимый в схему БД тип набора предоставляет программисту соответствующий путь доступа к записям, специфицированным в этом наборе.
Описание схемы БД, выполненное на ЯОД КОДАСИЛ состоит из четырех статей.
1. Статья схемы. Состоит из одного предложения SCHEMA NAME IS имя-схемы.
2. Одна или несколько статей областей. Область – это поименованный раздел адресуемого пространства памяти, в котором выполняется размещение экземпляров записей БД. Каждая область разбита на страницы. Записи приписываются к области независимо от их участия в наборах. При
разделении БД на области появляется возможность распределять БД по различным запоминающим устройствам. Однако, если АБД не желает по каким-либо причинам использовать концепцию областей, то назначается одна область для всей БД. Для каждой области статья состоит из предложения:
AREA NAME IS имя-области.
3. Одна или несколько статей записей. Число статей определяется числом типов записей. Статья записи начинается предложением
RECORD NAME IS имя-записи.
Затем задается способ выбора страницы области для записи:
Вариант DIRECT указывают, если номер страницы области для размещения записи будет поступать из программы, т.е. программист сам управляет размещением экземпляров записей в БД.
Вариант CALC задают, если предполагается, что при помещении экземпляра записи в БД специальная процедура по значению calc-элемента вычисляет значение ключа БД – адрес размещения этого экземпляра записи в БД. Если в качестве ключа указывается первичный ключ записи, то следует указать фрагмент DUBLICATES ARE NOT ALLOWED. Если указывается другой элемент данных записи и он может иметь повторяющиеся значения (например, фамилия сотрудника отдела), то указывается фрагмент DUBLICATES ARE ALLOWED.
Вариант VIA SET задают, если необходимо, чтобы помещаемая в БД запись оказалась физически no-возможности ближе к тому экземпляру набора, в который она должна быть включена.
Вариант SYSTEM задают, если не предполагается использовать рассмотренные выше варианты и размещение экземпляра записи отдается на усмотрение системы.
Предложением
WITHIN имя-области AREA.
тип записи приписывается к некоторой области БД.
Далее следует описание внутренней структуры записи. Каждое данное (элемент данных или агрегат) записи описывается предложением, которое начинается с номера уровня, затем следует имя данного:
номер-уровня имя-данного.
Если описываемое данное является элементом данных, то указывается его шаблон:
номер-уровня имя-данного; PICTURE IS шаблон.
Например:
02 Номер телефона; PICTURE IS 999X99X9.
.
Шаблон – это средство для описания формата значений элемента данных. Цифра 9 означает, что в данной позиции допускается любая десятичная цифра. X – что может содержаться любой символ. А – буквенный символ; символ «.» – десятичная точка. Если символ шаблона повторяется несколько раз, то можно использовать указатель числа повторений:
02 фамилия; PICTURE IS A (35)
Для элемента данных вместо PICTURE IS шаблон можно указывать следующими типами данных: BINARY; DECIMAL; FIXED; FLOAT; TYPE IS REAL; COMPLEX; BIT; CHARACTER; DATA-BASE-KEY.
Если описываемое данное – повторяющаяся группа, то его описание должно заканчиваться фразой:
OCCURS количество-повторений TIMES.
4. Статья набора. Описание каждого набора, представленного в схеме БД, выполняется следующими предложениями:
Фраза OWNER IS задает тип записи-владельца; фраза ORDER IS – способ включения экземпляров записей-членов в экземпляры описываемого типа набора.
Предложение MEMBER IS описывает запись-член набора. Различают AUTOMATIC (автоматический) и MANUAL (ручной) способы включения экземпляра записи-члена в набор при выполнении оператора ЯМД STORE (поместить). При ручном способе включения экземпляр записи помещается в БД, но в набор не включается. При автоматическом способе включения одновременно с вводом в БД экземпляр записи подключается и к набору. Выборка экземпляра набора для автоматического включения в него помещаемой в БД записи выполняется СУБД по индикатору текущей записи соответствующего типа набора, обрабатываемого в программе (индикатор указывает либо на владельца, либо на одного из членов экземпляра набора заданного типа). Кроме того, в модели имеется возможность указания для автоматического способа включения записей условия выбора (селекции) экземпляра набора.
С помощью фрагмента MANDATORY (ОБЯЗАТЕЛЬНЫЙ) или OPTIONAL (НЕОБЯЗАТЕЛЬНЫЙ) определяется вид исключения экземпляра записи из экземпляра набора. Если членство в наборе объявлено для записи-члена как обязательное – MANDATORY, то экземпляр записи-члена при удалении из набора удаляется из БД. При необязательном членстве в наборе экземпляр записи-члена при удалении из набора отсоединяется от соответствующего экземпляра набора, но остается в БД.
Фрагмент ASCENDING/DESCENDING задают в случае использования варианта SORTER предложения ORDERS. С его помощью указывается также ключ сортировки (упорядочения) набора.
На рис. 2.4 приведен пример описания схемы БД, диаграмма которой представлена на рис. 2.5.
В модели РГБД КОДАСИЛ внешний уровень реализуется введением понятия подсхемы (ПС). Концепция подсхемы реализует «взгляд» на БД прикладного программиста. Она позволяет ограничить его ознакомление с БД только той ее частью, которая имеет отношение к разрабатываемой программе. В модели подсхема рассматривается как некоторая часть схемы БД. Для одной и той же схемы БД может быть специфицировано несколько подсхем, причем они могут перекрываться. В крайних случаях подсхема может либо соответствовать всей схеме БД, либо специфицировать элементы, принадлежащие одной записи. Каждая подсхема соответствует только одной схеме.
Обычно какая-либо ПС составляется в соответствии с задачами конкретной ПП, однако одна и та же ПС может использоваться и несколькими различными программами, если удовлетворяет их требованиям. Исходный текст ПС составляется из предложений ЯОД подсхемы. Объектная ПС (объектный модуль) создается в результате трансляции исходного текста ПС соответствующим транслятором СУБД. При этом для получения объектной ПС требуется наличие оттранслированного описания схемы БД, т.е. объектная схема всей БД уже должна быть сформирована.
С одной стороны, ЯОД ПС предназначен для спецификации в ПС элементов схемы БД, которые требуются ПП, составляемой на некотором алгоритмическом языке. А с другой стороны, он должен отражать внутреннюю структуру записи, принятую в используемом алгоритмическом языке. Поэтому говорят о ЯОД ПС КОБОЛа, ЯОД ПС ПЛ/1 и т.д. Система управления БД должна быть обеспечена соответствующими трансляторами ЯОД подсхем.
В каждой программе в соответствии с используемой ПС резервируется рабочая область оперативной памяти. Каждый тип записи, объявленный в ПС, имеет в этой области свой участок – область записи. В эти области будут считываться экземпляры записей из БД для последующей обработки командами программы либо программа должна в них подготавливать данные для последующего вывода в БД операторами ЯМД. Обращение к данным, находящимся в рабочей области, выполняется по именам, объявленным в ПС.
В подсхеме могут использоваться имена, представленные в схеме БД (имена областей, записей, элементов данных), но могут быть определены и собственные имена. В последнем случае в подсхеме должно быть специфицировано соответствие между именами подсхемы и схемы.
Элементы данных, специфицированные в записях подсхемы, могут иметь тип, отличный от типа, специфицированного для этих элементов данных в записях схемы БД. В записях подсхемы могут отсутствовать элементы данных, присутствующие в соответствующих записях схемы; может быть изменен порядок элементов в записи.
Возможны и другие отличия, часть которых определяется возможностями конкретной СУБД.
При выполнении программы каждому процессу назначаются индикаторы текущего состояния. Количество назначаемых индикаторов (текущих программы) определяется ПС программы. Состав «текущих» программы следующий:
• текущая запись процесса – один экземпляр для выполняемой программы;
• текущая запись в типе набора – один экземпляр для каждого типа набора в подсхеме;
• текущая запись в типе записи – один экземпляр для каждого типа записи в подсхеме;
• текущая запись в области – один экземпляр для каждой области подсхемы.
Например, если ПС включает два типа набора, три типа записи и две области, то процессу, который использует эту ПС, будет назначено 8 индикаторов текущего состояния:
1 (процесса) + 1 × 2 (по типам наборов) + 1 × 3 (по типам записей) +
+ 1 × 2 (по количеству областей) = 8.
В начале выполнения программы все индикаторы имеют нулевое значение. Установку требуемых значений индикаторов (значением индикатора является ключ БД некоторой записи, т.е. адрес этой записи) программист может выполнить оператором FIND (найти) или STORE (поместить) ЯМД. Установленное значение может далее использоваться в программе другими операторами ЯМД.
Кроме индикаторов текущего состояния вводятся так называемые регистры БД, через которые резидентный модуль СУБД сообщает программе об успешном или аварийном выполнении оператора ЯМД. Регистры БД могут быть, например, следующие:
СОСТОЯНИЕБАЗЫДАННЫХ;
ИМЯ ОБЛАСТИ БАЗЫДАННЫХ;
ИМЯ НАБОРА БАЗЫДАННЫХ;
ИМЯ ЗАПИСИ БАЗЫДАННЫХ.
Рассмотрим основные операторы модели, с помощью которых осуществляется манипулирование данными модели. Запись является основной единицей обмена данными между процессом и БД в модели.
Оператор READY (ГОТОВНОСТЬ). Этот оператор в программе выполняет открытие области БД, к которой планируется обращение. По смыслу этот оператор соответствует оператору открытия файла (OPEN) в традиционных файловых системах.
Оператор FINISH (ЗАКОНЧИТЬ РАБОТУ). Оператор выполняет закрытие области (областей) БД, которые были открыты в программе, и поэтому должен быть последним выполняемым ЯМД-оператором в программе. По своему смыслу оператор аналогичен оператору закрытия файлов (CLOSE) в файловых системах.
Оператор FIND (НАЙТИ). Этот оператор выполняет поиск записи в БД, поэтому он является основным оператором модели. Он также определяет место расположения существующего в БД экземпляра записей, который удовлетворяет заданным условиям поиска, и назначает этот экземпляр записи «текущей записью процесса». При этом также выполняется обновление соответствующих индикаторов текущего состояния: типа записи, области и всех наборов, участником которых является найденный экземпляр записи. Для реализации различных вариантов поиска существует несколько форматов оператора FIND. Возможен поиск записи по значению CALC-ключа записи. Можно выполнять позиционный поиск в заданном наборе или области – найти следующую, предыдущую, первую или последнюю запись. Также можно выполнить поиск записи-владельца текущего экземпляра набора указанного типа.
При неуспешном выполнении оператора FIND система вырабатывает соответствующий код исключительного состояния для его последующего анализа в программе.
Оператор GET (ПОЛУЧИТЬ). Оператор осуществляет выборку текущей записи процесса.
Оператор STORE (ЗАПОМНИТЬ). Перед выполнением оператора STORE программист должен сформировать данные, которые требуется поместить в БД, в соответствующей области записи рабочей области программы.
Оператор MODIFY (ИЗМЕНИТЬ). Оператор обновляет текущую запись процесса.
Оператор ERASE (СТЕРЕТЬ). С помощью этого оператора из БД удаляется экземпляр-запись, соответствующий индикатору текущей записи процесса. Перед его выполнением требуется предварительно оператором FIND определить наличие соответствующего экземпляра записи в БД. Однако, если удаляемая запись является записью-владельцем некоторого непустого набора, то удаление не выполняется, а вырабатывается код соответствующего исключительного состояния.
Чтобы удалить запись-владелец непустого набора, в операторе ERASE специфицируется одно из следующих слов:
ALL
PERMANENT
SELECTIVE.
При указании варианта ALL удаляется текущая запись процесса, а также удаляются все связанные с нею записи-члены соответствующего экземпляра набора. Если одна из этих записей-членов, в свою очередь, является владельцем непустого набора, то удаляются записи-члены и этого набора и т.д. в порядке иерархии.
При указании варианта PERMANENT удаляется текущая запись процесса. Все связанные с нею наборы разрушаются. При этом обязательные члены наборов удаляются из БД.
Вариант SELECTIVE аналогичен предыдущему, но при этом из БД также удаляются необязательные члены разрушенных наборов, которые не являются одновременно членами других наборов.
Оператор CONNECT (ПРИСОЕДИНЯТЬ). Оператор выполняет включение текущей записи процесса в набор.
Оператор DISCONNECT (ОТДЕЛИТЬ). Оператор выполняет исключение текущей записи процесса из набора, но при этом она остается в БД.
Кроме рассмотренных основных операторов в состав ЯМД модели КОДАСИЛ входят следующие операторы:
ACCEPT – для пересылки значений индикаторов текущего состояния в определенные пользователем элементы данных;
KEEP – для блокирования записи при попытке ее обновления параллельным процессом;
FREE – для отмены действия оператора KEEP;
ORDER – для выполнения упорядочения записей-членов текущего экземпляра указанного типа набора;
IF – для проверки, в какой тип набора и в каком качестве входит найденная запись.
Существуют и другие вспомогательные операторы. Как следует из рассмотренных операторов ЯМД, особую роль в программе играет индикатор текущей записи процесса. Именно этот индикатор во многих операторах ЯМД указывает резидентному модулю СУБД на конкретный экземпляр записи в БД, над которым следует выполнить определяемое оператором действие.
Например, в программе встретился оператор
ERASE имя-записи,
при этом в БД, с которой работает программа, имеется, например, 20 000 экземпляров записей указанного типа. Для указания системе именно того экземпляра записи этого типа, который подлежит удалению, и используется индикатор текущей записи процесса. В этот индикатор программист должен предварительно оператором FIND поместить значение ключа БД удаляемого экземпляра записи.
Индикатор текущей записи в типе набора используется обычно для выбора конкретного экземпляра набора. Например, в программе использован следующий оператор ЯМД:
CONNECT имя записи ТО имя набора.
В этом случае индикатор текущей записи в типе набора используется для определения экземпляра набора данного типа, к которому будет подключен экземпляр записи, указанный индикатором текущей записи процесса.
Существуют варианты операторов FIND и STORE, которые не изменяют значения некоторых индикаторов текущего состояния (кроме индикатора текущей записи процесса), что расширяет логические возможности программиста при составлении программ.
Выполнение операторов ЯМД может завершиться неудачно по целому ряду причин. Поэтому в программе необходим анализ результатов выполнения операторов ЯМД. При неуспешном выполнении этих операторов в программе должны быть предусмотрены определенные действия.