■ var.attr. где var - имя свободной переменной соответствующей формуле, a attr - имя атрибута отношения, на котором определена переменная var;
■ var, что эквивалентно наличию подсписка var.attrl, var.attr2, .... var.attn,
где attrl, attr2. ... attrn включает имена всех атрибутов определяющего отношения;
■ new name = var.attr; new name - новое имя соответствующего атрибута результирующего отношения.
Последний вариант требуется в тех случаях, когда в формуле используются несколько свободных переменных с одинаковой областью определения.
В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к БД СТУДЕНТЫ-ГРУППЫ можно говорить, например, о доменных переменных ИМЯ (значения домена - допустимые имена) или НОМ_СТУД (значения домена - допустимые номера студентов).
Основным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов (см. ниже), позволяющих выражать так называемые условия членства. Если R - это n-арное отношение с атрибутами a1, а2, .., ап, то условие членства имеет вид
R (ai1: vi1, ai2:vi2, ..., aim:vin) (m <= n) ,
где vij - это либо литерально задаваемая константа, либо имя кортежной переменной. Условие членства принимает значение ИСТИНА только в том случае, если в отношении R существует кортеж, содержащий соответствующие значения указанных атрибутов. Если vij - константа, то на атрибут аij задается жесткое условие, не зависящее от текущих значений доменных переменных; если же vij - имя доменной переменной, то условие членства может принимать различные значения при разных значениях этой переменной.
. Предикатом принято называть некую логическую функцию, которая для некоторого аргумента возвращает значение ИСТИНА или ЛОЖЬ. Отношение может быть рассмотрено как предикат с аргументами, являющимися атрибутами рассматриваемого отношения. Если заданный конкретный набор кортежей присутствует в отношении, то предикат выдаст истинный результат, в противном случае - ложный.
Во всех остальных отношениях формулы и выражения исчисления доменов выглядят похожими на формулы и выражения исчисления кортежей. Реляционное исчисление доменов положено в основу большинства языков запросов, основанных на использовании форм.
2.4Иерархический и сетевой подходы
Вреляционном исчислении и алгебре полностью отсутствуют указания на то, каким образом производить поиск необходимых данных. Оперирование отношениями (таблицами) предполагает просмотр всех записей. Когда БД велика,
116
то невозможно производить полный просмотр всех ее записей. Поэтому необходимо предварительное упорядочивание и объединение в группы записей по признакам поиска.
Для упорядочивания записей и организации поиска нужных записей используется ключ и связи.
Ключ – это уникальное имя записи, в качестве которого может выступать как один какой-либо атрибут записи (простой ключ), так и совокупность нескольких атрибутов (составной ключ). С помощью ключа производится идентификация каждой конкретной записи, а также упорядочение записей в файле. Упорядочение по ключу может быть либо прямым, либо выполнено с помощью хеш-функции.
Прямое упорядочение предполагает лексикографическое расположение записей: записи могут располагаться либо в порядке увеличения значения ключа, либо в алфавитном порядке.
Хеш-функция производит пересчет ключа в адрес записи в файле. Эта операция выполняется СУБД всякий раз при поиске нужной записи по ключу.
Связи позволяют осуществить группирование записей во множества (сегменты записей), а так же указывать взаимоотношения между этими множествами (сегментами). На практике связь реализуется, как правило, в виде указателя.
Так, если необходимо указать связь между записью а1 в отношении А с записью в1 отношения В, то в состав записи а1 необходимо включить указатель на запись в1. В случае присутствия и обратной связи запись в1должна так же содержать указатель на запись а1.
При построении иерархических и сетевых баз данных используются все перечисленные ранее типы связей. Графически разным типам связей соответствуют обозначения в виде различных стрелок: «→» - связь с одной записью; «→→» - с несколькими записями. Взаимные связи имеют следующие названия: «←→» - «один к одному», «←→→» - «один ко многим», «←←→→» - «многие ко многим». На рис.2.10 записи изображены в виде прямоугольников, а сегменты представлены кружками. Например, обозначение, приведенное на рис.2.10, в следует понимать так: каждая запись сегмента А связана с некоторой группой записей сегмента В, а каждая запись из сегмента В связана лишь с одной записью сегмента А.
117
Рис.2.10. Типы и обозначения связей а-«один к одному»; б, в-«один ко многим»; г-«многие ко многим»
С помощью указанных обозначений строится граф логической схемы БД, вершины которого – сегменты, а дуги – обозначения типов связей между сегментами.
2.4.1 Иерархический подход.
Иерархическая БД имеет граф логической схемы в виде дерева, а тип связей соответствует «один ко многим» (рис.2.10,б). Пример логической схемы иерархической БД приведен на рис. 2.11. В иерархической БД связи направлены только от верхних сегментов к нижним, обратные указатели отсутствуют. Это объясняется принципиальным свойством иерархического представления данных: каждая запись приобретает смысл лишь тогда, когда она рассматривается в своем контексте, т. е. любая запись не может существовать без предшествующей ей записи по иерархии.
Таким образом, БД, основанная на иерархической модели, состоит из упорядоченного набора деревьев. Каждое дерево состоит из одного "корневого" (предок) и упорядоченного набора из нуля или более связанных с ним поддеревьев (потомки). Целостность связи между ними поддерживается автоматически.
При поиске в иерархической БД необходимо указывать значение ключа на каждом уровне иерархии.
118
Рис.2.11. Пример логической схемы иерархической базы данных
Так, для доступа к записи из множества G (рис.2.11) должны быть последовательно указаны ключи записей из множеств А, С и G.
В таких БД поддерживаются следующие операторы манипулирования данными:
■найти дерево БД по заданному признаку;
■перейти от одного дерева к другому;
■перейти к записи внутри дерева или в порядке обхода иерархии (сверху вниз, слева направо):
■вставить новую запись в указанную позицию.
■удалить текущую запись.
Реляционная БД всегда может быть преобразована в иерархическую. Однако конкретный вид логической схемы будет зависеть от типа запросов.
Пусть имеется реляционная база представленная следующими отношения-
ми.
Пациент:
ФИО |
Пол |
Возраст |
Рост |
Вес |
1. |
|
|
|
|
2. |
|
|
|
|
3. |
|
|
|
|
4. |
|
|
|
|
Участок:
№ участка |
ФИО врача |
Улица |
Номера до- |
|
|
|
мов |
1 |
Курильчик |
Руссиянова |
Нечетные |
2 |
Кураева |
Руссиянова |
Четные |
3 |
Коваленко |
Руссиянова |
Нечетные |
4 |
… |
Никифорова |
Четные |
5 |
… |
Никифорова |
Нечетные |
119
|
6 |
… |
Никифорова |
Четные |
|
7 |
… |
Шагаева |
Нечетные |
|
8 |
… |
Шугаева |
Четные |
|
9 |
… |
Шугаева |
Нечетные |
Посещения: |
|
|
|
|
|
№ участка |
ФИО пациента |
Дата посещения |
Вид заболе- |
|
|
|
|
вания |
|
|
|
|
|
У
Уч
П
Рис. 2.12.Логическая схема для данного запроса: У – улица; Уч – участок; П – посещения.
Тогда для запроса типа «Найти номера участков, расположенных на улице … », или «Перечислить ФИО пациентов, проживающих на данном участке и посещающих поликлинику» можно построить иерархическую БД (Рис.2.12). Для этого из записей, содержащие данные об участках, расположенных на определенной улице, образуем сегмент «улица». В этом случае реализация связей между двумя первыми сегментами будет следующая (Рис.2.13).
120