В реляционном исчислении и алгебре полностью отсутствуют указания на то, каким образом производить поиск необходимых данных. Оперирование отношениями (таблицами) предполагает просмотр всех записей. Когда БД велика, а этот случай типичен для САПР, то невозможно производить полный просмотр всех ее записей. Поэтому необходимо предварительное упорядочивание и объединение в группы записей по признакам поиска.
Если реляционное исчисление позволяет описать вид выходного документа, а реляционная алгебра — последовательность операций над отношениями, то для организации поиска нужных записей используются понятия ключа и связи.
Ключ— уникальное имя записи, в качестве которого может выступать как элемент какого-либо атрибута в записи — простой ключ, так и совокупность элементов нескольких атрибутов — составной ключ. С помощью ключа производится идентификация каждой конкретной записи, а также упорядочение записей в файле.
Например, в качестве ключа БД (см. табл. 2.2, 2.3) могут выступать код типа микросхемы в отношении ОМС и код узла в отношении ОУЗ. Упорядочение по ключу может быть либо прямым, либо выполнено с помощью хеш-функции.
Прямое упорядочение предполагает лексикографическое расположение записей: записи могут быть записаны либо в порядке увеличения значения ключа (при этом можно рассматривать простой ключ как некоторое число), либо в алфавитном порядке. Для второго случая ключи записей отношения ОМС (см. табл. 2.2) будут записаны в следующем порядке: 155ИР1, 155ЛАЗ, 155ЛА6, 155ТВ1, 155ТМ2.
Хеш-функция производит пересчет ключа в адрес записи на файле. Эта операция выполняется СУБД всякий раз при поиске нужной записи по ключу. Связи позволяют осуществить группирование записей в множества, а также указывать взаимоотношения между этими множествами. На практике связь реализуется, как правило, в виде указателя.
Так, если необходимо указать связь между записью 155ТМ2 в отношении ОМС с записью Сч50 отношения ОУЗ, то в состав записи 155ТМ2 необходимо включить указатель на запись Сч50. В случае присутствия и обратной связи запись Сч50 должна также содержать указатель на запись 155ТМ2. Однотипные записи группируются в сегменты (типы записей).
Графически при описании базы данных разным типам связей соответствуют обозначения в виде различных стрелок: «→» — связь с одной записью; «→→» — связь с несколькими записями. Взаимные связи имеют следующие названия: «←→» — «один к одному», «←→→» — «один ко многим», «←←→→» — «многие ко многим». На рис. 2.2 записи изображены в виде прямоугольников, а сегменты представлены кружками. Например, обозначение, приведенное на рис. 2.2, в, следует понимать так: каждая запись сегмента А связана с некоторой группой записей сегмента В, а каждая запись из сегмента В связана лишь с одной записью сегмента А.
С помощью указанных обозначений строится граф логической схемы, вершины которого — сегменты, а дуги— обозначения типов связей между сегментами. На рис. 2.3 представлен пример логической схемы некоторой БД.
Рис. 2.2. Типы и обозначения связей:
а — «один — к одному»; б, в — «один — ко многим» ; г — «многие — ко многим»
Рис 2.3. Пример логической схемы базы данных
Иерархический подход. Иерархическая БД имеет граф логической схемы в виде дерева, а тип связей соответствует рис. 2.2, б. Пример логической схемы иерархической БД приведен на рис. 2.4. В иерархической БД связи направлены только от верхних сегментов к нижним, обратные указатели отсутствуют. Это объясняется принципиальным свойством иерархического представления данных: каждая запись приобретает смысл лишь тогда, когда она рассматривается в своем контексте, т. е. любая запись не может существовать без предшествующей ей записи по иерархии. При поиске в иерархической БД необходимо указывать значение ключа на каждом уровне иерархии. Так, для доступа к записи из множества G (рис. 2.4) должны быть последовательно указаны ключи записей из множеств А, С и G.
Реляционная БД всегда может быть преобразована в иерархическую. Однако конкретный вид логической схемы зависит от типа запросов. В табл. 2.2...2.4 приведен пример фрагмента реляционной
БД, содержащего запись о характеристиках микросхем и узлов. Дополним базу данных, представленную в табл. 2.2...2.4, также записями о характеристиках устройств, состоящих из совокупности узлов, образовав сегмент АК. Тогда для запросов типа «Найти узлы для заданных устройств», «найти микросхемы для заданных узлов» можно построить иерархическую БД (рис. 2.5). Поэкземплярная реализация связей первых двух сегментов приведена на рис. 2.6. Каждая запись сегмента АК связана с группой записей сегмента ОУЗ. В данной конкретной реализации запись из АК ссылается на первую в группе запись из ОУЗ, сами же записи сегмента ОУЗ объединены с помощью отдельных указателей в цепные списки. Очевидно, что поиск в такой БД легко осуществляется по составному ключу. Например, составной ключ АК20. РЗ позволяет найти все сведения об узле РЗ, входящем в состав устройства АК20.
При организации связей между уровнями ОУЗ — ОМС возникает проблема избыточности, заключающаяся в необходимости повторения записей микросхем. Так, микросхема 155ЛАЗ должна быть указана во всех записях сегмента ОМС, связанных с записями ДШ10, Сч46, РЗ и СМ. 15 сегмента ОСУ. В конкретной реализации возможно избежать многократного повторения описания микросхемы 155ЛАЗ введением указателя на запись 155ЛАЗ, хранящуюся отдельно. Однако значение указателя на запись 155ЛАЗ должно быть размножено. Это не вызывает существенных затрат памяти, однако усложняет решение проблемы целостности базы данных.
Рис. 2.4. Пример логической схемы иерархической базы данных
Рис. 2.5. Логическая схема для заданного типа запроса
Трудности в использовании иерархической базы данных возникают при изменении типа запроса. Так, если в рассматриваемом примере БД появится запрос «Найти узлы, включающие заданную микросхему», то пропадают преимущества предыдущего иерархического упорядочения. Действительно, для выполнения этого запроса необходимо просмотреть все записи узлов и все связанные с ними записи микросхем. Для реализации такого запроса было бы целесообразно переупорядочить БД и построить новую иерархию: от записей о микросхемах к записям об узлах,
Рис. 2.6. Схема реализации связей АК—ОУЗ
Рис. 2.7. Пример набора (а) и экземпляров набора (б):
А, В-сегменты; а1, а2- записи сегмента А; b1, b2, …, b7 - записи сегмента В; F — имя набора
Сетевой подход. Необходимость в организации различного упорядочения записей в БД с целью удовлетворения разных типов запросов привела к разработке сетевых баз данных. В сетевой модели данных в принципе разрешены любые группирования записей и организация произвольных связей между ними. Однако на практике целесообразно введение некоторых ограничений. Рассмотрим представление сетевых моделей данных в соответствии с концепцией КОДАСИЛ.
Набор — основная конструкция сетевых моделей, представляющая собой поименное двухуровневое дерево. С помощью двухуровневых деревьев могут быть построены многоуровневые деревья и большинство сетевых структур. Если рассматривать логическую схему, то набор может интерпретироваться как имя связи между двумя сегментами записей типа «один ко многим». Экземпляр набора — конкретная реализация такой связи. На рис. 2.7 приведен пример набора и его двух экземпляров.
Рис. 2.8. Допустимые варианты построения наборов
Рис. 2.9. Представление от ношения «многие — ко многим»
Каждый экземпляр набора содержит одного владельца и нескольких членов набора. Например, на рис. 2.7 владельцем 1-го экземпляра набора является запись а1, а членами набора — записи b1, ..., b3.
Рис. 2.10. Пример сетевой логической схемы:
УПР — сегмент записей об уникальных проектных решениях; ТПР — сегмент записей о типовых проектных решениях; МС—сегмент записей о микросхемах; УЗ — сегмент записей об узлах; МСУЗ — сегмент связи между записями сегментов МС и УЗ; УЗТПР — сегмент связи между записями сегментов УЗ и ТПР; СУПР, ВМС. СУЗ, ВУЗ. С'ТПР — имена соответствующих наборов
Допустимо, чтобы записи одного сегмента были владельцами нескольких наборов, и, наоборот, записи некоторого набора могут быть членами различных наборов. На рис. 2.8 показаны соответствующие конструкции логической схемы.
В сетевых СУБД не разрешены связи в логической схеме типа «многие — ко многим». Однако с помощью вышеуказанных свойств набора 'можно описать такую связь введением дополнительного сегмента записей, задающих взаимоотношение между исходными сегментами, и определить на них два набора так, как это показано на рис. 2.9. Сегмент С содержит записи в форме адресных таблиц (аналогично отношению ОСУ). Записи сегмента С входят в различные наборы для сегментов А и В. Если необходимо найти записи в В, связанные с данной записью из А, то с помощью набора F1 находят указатели на записи в сегменте С, а затем по набору F2 находят искомые записи в В. Если же требуется выполнить обратный поиск из В в А, то необходимо воспользоваться сначала набором F2, а затем набором F1.
Пример сетевой логической схемы приведен на рис. 2.10. Из него видно, что поиск необходимых записей можно производить начиная с сегментов УПР, МС, УЗ, ТПР.
Каждый экземпляр набора содержит одного владельца и нескольких членов набора. Например, на рис. 2.7 владельцем 1-го экземпляра набора является запись а1, а членами набора — записи b1, ..., b3.