книги / Структурный подход к организации баз данных

1. Прямой указатель (рис. 7.15), который включает действительный адрес блока на диске, содержащего «указываемую» запись V; он хранится в за­ писи X, «указывающей» на запись V.

Цилиндр 20

XДорожка 15 блок 5

Рис. 7.15. Прямой указатель: действи­ тельный адрес блока на диске, содержа­ У щего V. Преимущества и недостатки

указаны в табл. 7.1

2.Относительный указатель (рис. 7.16) представляет собой логический указатель. Это идентификатор, который может быть отображен в действи­ тельный адрес блока на диске. Первой частью указателя такого типа является номер страницы базы данных. Его можно преобразовать в значе­ ние смещения $той страницы относительно начала области. Вторая часть указателя содержит значение смещения относительно нижней границы страницы, определяющее действительное положение на странице.

3.Символический указатель (рис. 7.17). Ключ «указываемой» записи V хранится в «указывающей» на нее записи X. Поиск записи осуществляется методом доступа внутренней модели.

У

Преимущества

Эффективность доступа — наилучшая. Если известен прямой адрес записи, для ее поиска достаточно одного обращения. В большинстве случаев прямой указатель короче соответствующего символического адреса.

Недостатки

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

Все эти указатели — прямой, относительный и символический — имеют свои недостатки и преимущества, перечисленные в табл. 7.1, 7.2 и 7.3.

Т а б л и ц а 7.2. Преимущества и недостатки относительного указателя

Преимущества

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

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

Недостатки

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

Т а б л и ц а 7.3. Преимущества и недостатки символического указателя

Преимущества

Символический указатель не зависит от устройства. При пересылке записи нет необ­ ходимости в обновлении указывающих на нее символических указателей.

Недостатки

Эффективность доступа может и не быть наивысшей. Адрес искомой записи должен определяться из значения символического указателя. Символический указатель, как правило, длиннее прямого указателя.

ЛИ Т Е Р А Т У Р А

1.С и г-11 с е НоЬег! М. Эа1а Вазе Мападешеп!. — Ассезз МесЬашзтз апс! Па1а 51гис1иге

зеИз 02181.

Г л а в а 8

ПРИМЕНЕНИЕ МЕТОДОВ ДОСТУПА

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

8.1.ИЕРАРХИЧЕСКИЕ СУБД

Воснову построения некоторых наиболее ранних СУБД положена иерархическая модель данных. Одной из таких систем является система управления информацией 1М5/У5 фирмы 1ВМ. Рассмотрим используемые в ней методы доступа.

8.1.1.1М5 (Система управления информацией)

Основной компонент 1М5 — язык данных/1 ф а(а Бап^иаде/1 — ОЬ/1). Этот язык обеспечивает описание модели данных и методов доступа. В нем различаются понятия физической базы (баз) данных (называемой в гл. 1 «внутренней моделью») и логических баз данных (называемых в гл. 1 «внешними моделями»). Логические базы данных отражают представления прикладных программистов о базе данных. Они всегда иерархические. Именно поэтому 1М5 и причисляют к катего­ рии иерархических СУБД, несмотря на то, что благодаря наличию логиче­ ских взаимосвязей пользователям 1М5 доступны некоторые возможности сетевой модели данных.

Физическая база данных представляется в виде древовидной структу­ ры. Типы узлов (они обсуждались в § 4.4 при описании иерархической модели данных) называются типами сегментов. Тип корневого узла на­ зывается типом корневого сегмента. Иерархия типов сегментов определена сверху вниз и слева направо (рис. 8.1). Коды сегментов, присваиваемые

Типы сегментов В иерархической последовательности

Рис. 8.1. Структура физической базы данных для 1МЗ. Первым в иерархии физической записи располагается первый экземпляр сегмента 1. Этому экземпляру подчинен первый экземпляр сегмента 2 и все порожденные 3 и 4. Далее в иерархии идет следующий экземпляр сегмента 2 и все порожденные 3 и 4. После просмотра всех экземпляров 2 следующим в иерархии будет находящийся справа сегмент 5 и т. д. (Типы сегментов пронумерованы в иерархической последовательности.)

типам сегментов, упорядочены точно так же. Каждому экземпляру кор­ невого сегмента соответствует физическая запись (рис. 8.2 и 8.3). Экземпляры порожденного типа сегмента называются подобными. Между сегментами в физической базе данных существуют физические взаимо­ связи. В физической иерархии возможно наличие взаимосвязей: с физи­ чески исходным сегментом, с физически порожденным сегментом и с физи­ чески подобными сегментами.

Физические базы данных могут расщепляться на несколько файлов, но файл не может содержать сегментов, принадлежащих различным физическим базам данных. Физической базе данных 1М5 присущи сле­ дующие свойства:

1. В базе данных может быть только один тип корневого сегмента.

2.У корневого сегмента могут быть порожденные сегменты.

3.Каждый порожденный сегмент может в свою очередь иметь порож­

денные сегменты (максимум до 15 сегментов в любом из путей).

4.Одна физическая база данных может содержать до 255 типов сегментов.

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

Рис. 8.5. При иерархическом прямом методе доступа для связывания сегментов иерархии в 1М5 применяются прямые указатели

Н15АМ: иерархический индексно-последовательный; НЮАМ: иерархический индексно-прямой; НОАМ: иерархический прямой.

В методах доступа Н5АМ и Н15АМ сегменты связываются с по­ мощью иерархического последовательного метода, а в методах доступа НЮАМ и НОАМ — с помощью иерархического прямого метода.

Организация данных методом доступа Н5АМ подобна работе с магнитной лентой. Здесь используется только один основной метод до­ ступа— физически последовательный.

Метод доступа НЮАМ основан на сочетании двух основных методов доступа — «индексно-последовательного» и «физически последователь­ ного». Индексный доступ применяется к корневым сегментам, а последо­ вательный — к порожденным. Хранение индексного набора данных и до­ ступ к нему осуществляются с помощью индексно-последовательного метода доступа (15АМ) или метода доступа виртуальной памяти (У5АМ). Индексный набор данных содержит экземпляры корневого сегмента и столько порожденных сегментов, сколько может вместить область фиксированной длины в основном наборе данных (рис. 8.6), т. е. формируется неплотный индекс. Остальные сегменты хранятся во вторичном наборе данных. Не допускается перенос части сегмента из одной области в другую, поддержание иерархической организации осу-

Упорядоченный по входу наборданных УЗАМ или набор данных ОЗАМ

Рис. 8.7. Иерархический индексно-прямой метод доступа. 1М8 обеспечивает индексный доступ к корневому сегменту и прямой к порожденным сегментам

области корневых сегментов (АОКС), а остальные байты — в неадре­ суемой области корневых сегментов, которая является областью пере­ полнения (рис. 8.8). Для хранения и выборки корневых сегментов применяется в основном «произвольный» метод доступа.

Каждый блок АОКС содержит определенное число корневых анкер­ ных точек. С помощью исходного ключа рандомизирующий алгоритм метода доступа НОАМ формирует объектный ключ в виде номера блока и корневой анкерной точки в блоке. В том случае, если для двух корневых сегментов алгоритм хеширования формирует один и тот же адрес, строится цепочка синонимов.

100,2

Адресуемая — область — ^

Рис. 8.8. Иерархический прямой метод доступа (НОАМ) 1М5 обеспечивает произвольный доступ к корневому сегменту и прямой к порожденным сегментам

При использовании метода доступа НШАМ сегменты могут пересы­ латься, а при использовании методов доступа НШАМ и НОАМ — нет. Н15АМ предполагает, что область, занимаемая удаленным сегментом, не освобождается до следующей реорганизации, в то время как для НШАМ и НОАМ удаление сегмента связано с освобождением памяти. Организация данных в НОАМ, кроме того, позволяет осуществлять более быстрый доступ к порожденным сегментам иерархии. Единственным недостатком НОАМ по сравнению с НШАМ и НШАМ является сложность последовательной обработки корневых сегментов.

Как уже отмечалось, для хранения записей базы данных и для доступа к ним в случае иерархической модели данных методы доступа НЗАМ, НШАМ, НШАМ и НОАМ сочетают основные методы доступа и методы доступа модели данных.

Процедура доступа к записи базы данных при методах доступа НЗАМ, Н15АМ, НШАМ или НОАМ начинается на уровне корневого сегмента. Для обеспечения входа на более низкий уровень или к корневому сегменту по вторичному ключу 1М5 предоставляет возможность так назы­ ваемого вторичного индексирования. Вторичное индексирование — это предлагаемый системой 1МЗ вариант инвертированной структуры файла.

На рис. 8.9 корневой сегмент — КЛИЕНТ, а порожденные сегмен­ ты — СЧЕТ и ССУДА. Если база данных «инвертируется» относительно номера счета, то становится возможным вторичное индексирование по номеру счета. Ведение вторичного набора данных осуществляет 1М5.

Физическая структура базы банных КЛИЕНТ Запись 3 базы

Рис. 8.9. Экземпляр записи базы данных КЛИЕНТ с инверсией относительно номера счета

На рис, 8.10 показано логическое представление прикладного программи­

ста о базе данных.

Использование в 1М5 логических взаимосвязей позволяет получить некоторые свойства сетевой модели данных.

Логические взаимосвязи в 1М8. Внешние модели, о которых упоми­ налось в гл. 1, в 1М5 называются логическими представлениями. При­ кладной программист использует логические представления при составле­ нии программ. В «простых» физических базах данных взаимосвязи между сегментами устанавливаются в пределах иерархии. Наличие в 1М5 аппарата так называемых логических взаимосвязей дает возможность устанавливать взаимосвязи между сегментами, принадлежащими двум