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

Рис. 6.17. Улучшенная логическая модель, в которой записи СЕМЕСТР и СЕМЕСТР + КУРС объединены в запись СЕМЕСТР+КУРС (см. рис. 6.16).

Обращаем внимание читателя на следующий факт. Между СЕМЕСТРОМ и КУРСОМ существует взаимосвязь «многие ко многим». Мы объединили записи СЕМЕСТР и КУРС в одну запись. Если приходится часто отвечать на запрос: «Какие курсы преподаются в данном семестре?», проектировщик может принять решение объединить два типа записей

не следует объединять с членом типа набора			II СЕМЕСТР + КУРС +
+ СТУДЕНТ.
Модель, приведенная на рис. 6.17, содержит два типа набора:
Тип	набора	I — ЗАЧЕТЫ-СТУДЕНТА:	владелец— СТУДЕНТ,
член — СЕМЕСТР + КУРС + СТУДЕНТ.
Тип	набора	II — ЗАЧЕТЫ-ПО-КУРСУ-В-СЕМЕСТРЕ: владелец —

СЕМЕСТР + КУРС, член — СЕМЕСТР + КУРС + СТУДЕНТ. Тип записи СЕМЕСТР + КУРС + СТУДЕНТ связывает типы наборов I и II.

Г.Упрощение имен ключей

Вконструкции набора типы записей могут иметь следующие имена ключей (см. левый рисунок):

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

После упрощения имен ключей логическая модель (рис. 6.17) приоб­ ретает вид, показанный на рис. 6.18. Здесь представлены два типа наборов:

Тип	набора	I — ЗАЧЕТЫ-СТУДЕНТА: владелец — СТУДЕНТ,
член — СЕМЕСТР + КУРС + СТУДЕНТ.
Типа	набора	II — ЗАЧЕТЫ-ПО-КУРСУ-В-СЕМЕСТРЕ: владе­

лец — СЕМЕСТР + КУРС, член — СЕМЕСТР + КУРС + СТУДЕНТ. Тип записи СЕМЕСТР + КУРС + СТУДЕНТ связывает типы наборов I и II.

Д. Реализация взаимосвязей, которые не отражены в логической

модели, но на самом деле существуют.

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

СТУДЕНТ СЕМЕСТР + КУРС

Рис; 6.18. Улучшенная логическая модель, в которой из записи СЕ­ МЕСТР + КУРС + СТУДЕНТ исключе­ ны элементы СЕМЕСТР, НОМ-КУР­ СА и НОМ-СТУДЕНТА (см. рис. 6.17)

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

Л И Т Е Р А Т У Р А

1.

Ьу о п

ЛоЬп К- Ап

1п1гос1ис1юп 1о Оа1а Вазе

Оез^п. ТНе УШеу Соттиш^гарЬ

Зепез т

Визтезз

Эа1а Ргосеззт^, ЛоНп ДУПеу & Зопз, 1971.

2.

В а с Нт

а п

С. Ш. Оа1а 51гис1иге 01а§гатз.

Оа1а

Вазе,

Лоигпа1 о!

АСМ

5рес1а1

1п1егез1

Сгоир

ВгШзН Оа*а

Ргосеззтд,

Уо1.

1

N0. 2

(Зиттег ,1969).

3.

1МЗ/УЗ

5уз1ет/АррПсаИоп

Оез1§п

ОшЛе.

1ВМ СогрогаНоп,

Уогк.

4.

О 11е

\УППат Т. ТНе СоЛазу1

АрргоасН 1о

Эа1а Вазе Мапа^ешепН А ШПеу-

I п4 е г'з с 1 е п с е

Р и Ь П с а 11 о п,

Ло Ь п

\ УПе у

&

З о п з , 1978.

Р у с с к и й

пе

р е в о д : Ол л е

Т. В. Предложения

КОДАСИЛ по управлению базами данных. М.,

Финансы и

статистика, 1981.

Ч А С Т Ь 3

РЕАЛИЗАЦИЯ БАЗЫ ДАННЫХ

Г л а в а 7

МЕТОДЫ ХРАНЕНИЯ И ДОСТУПА К ДАННЫМ

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

7.1. ИНТЕРФЕЙСЫ МЕЖДУ ПОЛЬЗОВАТЕЛЕМ И БАЗОЙ ДАННЫХ

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

В процессе выполнения запроса пользователя система проходит несколько интерфейсов (рис. 7.1).

Интерфейс 1. При получении запроса СУБД «известно» описание представления пользователя и прикладной программы, а также условия безопасности и секретности. На основании представления пользователя определяется, к какой физической базе (базам) данных может осуществ­ ляться доступ. Кроме того, из описания физической базы (баз) данных известен используемый метод (методы) доступа внутренней модели. Раз­ ные реализации предоставляют различные возможности, однако в боль­ шинстве из них поддерживается несколько представлений пользователя о базе данных.

Интерфейс 2. В свою очередь СУБД использует методы доступа внут­ ренней модели, которые в разных системах реализованы по-разному: либо как специализированные методы доступа, предоставляемые СУБД, либо как сформированные из обобщенных методов доступа операционной системы. Примерами могут служить 15АМ (индексно-последовательный метод доступа) и ВЭАМ (базисный прямой метод доступа).

Рис. 7.1. Выполнение запроса пользователя обеспечивают СУБД, методы доступа внешней и внутренней моделей, а также методы доступа операционной системы

Интерфейс 3. Методы доступа внутренней модели совместно с метода­ ми доступа операционной системы осуществляют доступ к записи (запи­ сям) физической базы данных и создают основу для нахождения нужной записи (записей) методом (методами) доступа, описывающими логические взаимосвязи между различными частями записи базы данных.

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

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

Различают следующие методы доступа внутренней модели: физи­ ческий последовательный, индексно-последовательный, индексно-произ­ вольный, инвертированный и посредством хеширования (рис. 7.2, 7.3

и7.4). Для каждого из них зададим два критерия:

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

равна 0,5.

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

Физический последовательный

•	Значения	ключей физических записей находится в логической последовательности.
•	В основном применяется для «дампа» и «восстановления».
•	Может применяться как для хранения, так и для выборки данных.
•	Эффективность использования памяти близка к 100%.
Индексно-последовательный
•	Значения ключей физических записей находится в логической последовательности.
•	Может применяться как для хранения, так и для выборки данных.
•	В индекс	значений ключей заносятся статьи наибольших значений ключей в блоках.

•Наличие дубликатов значений ключей недопустимо.

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

•Эффективность хранения зависит от размера и изменяемости базы данных.

Рис. 7.2. Два метода доступа внутренней модели: физический последовательный

ииндексно-последовательный

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

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

Индексно-произвольный

•Значения ключей физических записей необязательно находятся в логической последова­ тельности.

•Хранение и доступ к индексу могут осуществляться с помощью индексно-последователь­ ного метода доступа.

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

•Может использоваться как для запоминания, так и для выборки данных.

Инвертированный

•Значения ключей физических записей необязательно находятся в логической последо­ вательности.

•Может использоваться только для выборки данных.

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

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

Рис. 7.3. Два метода доступа внутренней модели: индексно-произвольный и инвертированный

•При индексно-произвольном методе доступа записи хранятся в произвольном порядке. Создается отдельный файл из статей, содержащих значения действительного ключа

и физические адреса хранимых записей.

•Как правило, инвертированный метод доступа применяется только для выборки. Запоми­ нание осуществляется с помощью каких-либо других методов доступа.

Прямой метод доступа

•Не требуется упорядоченность значений ключей физических записей.

•Между ключом записи и ее физическим адресом существует взаимно однозначное

соответствие.

• Может применяться как для хранения, так и для поиска,

•Эффективность доступа всегда равна единице.

•Эффективность хранения зависит от плотности ключей.

•Наличие дубликатов ключей недопустимо.

Метод доступа посредством хеширования

•Не требуется логическая упорядоченность значений ключей физических записей.

•Значениям нескольких ключей может соответствовать один и тот же физический адрес (блок).

• Может применяться как Для хранения, так и для поиска.

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

•Эффективность хранения зависит от распределения ключей и алгоритма их преобра­ зования.

Рис. 7.4. Два метода доступа внутренней модели: прямой и посредством хеширования.

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

•Между этими двумя методами доступа существует сходство. При методе доступа посред­

ством хеширования адрес физической записи алгоритмически определяется из значения ключа записи.

Как правило, разработчику базы данных приходится находить приемлемое соотношение между эффективностью доступа и эффективностью хранения. Эффективность доступа приобретает первостепенное значение в оперативных системах. Некоторые СУБД сконструированы так, чтобы обновления (базы данных) в оперативном режиме выполнялись оптималь-, ным образом. Как будет показано в гл. 9, эффективность доступа косвенно зависит и от эффективности хранения.

На рис. 7.2, 7.3 и 7.4 приведены общие сведения о методах доступа внутренней модели.

7.2.1. Физический последовательный метод доступа

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

логическую последовательность, даже если они не передавались ей в этой последовательности.

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

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

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

7.2.2. Индексно-последовательный метод доступа

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

В индексно-последовательном методе доступа индексный файл всегда упорядочен по так называемому первичному ключу. Первичный клкЛ — главный атрибут физической записи. По его значению идентифицируется физическая запись. До тех пор, пока это возможно, записи хранятся в той же логической последовательности, что и индекс (отсюда и название «индексно-последовательный метод доступа»). Поэтому индекс должен содержать ссылки не на каждую запись базы данных по ключу, а на группу записей, хранимых в физическом блоке, по диапазону ключей. Например, если в блоке хранится 10 записей, то для него в индексном файле будет одна статья, а не десять, и размер индексного файла уменьшится в 10 раз.

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

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

Индексный файл

Файл данных

Рис. 7.5. Индексно-последовательный метод доступа. Индексный файл и файл данных' организованы последовательно. Индексный файл содержит только максимальные значения первичных ключей записей каждого блока

Наибольшее либо наименьшее значение ключа последней содержащейся в блоке записи (большинство поставляемых методов доступа обеспечива­ ют загрузку файла данных по возрастанию значения первичного ключа) заносится в индексный файл (рис. 7.5) *.

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

Возможны два пути решения этой проблемы:

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

2.При невозможности введения записи в блок он делится пополам. Пер­ вый из двух вновь созданных блоков содержит половину записей, содер­ жа щися в исходном блоке, а второй — другую половину. (Иногда разде­ ление блока производится таким образом, что первый блок содержит две трети записей исходного блока, а второй — оставшуюся одну треть.) Затем в индексном файле создается новая статья. По сравнению с орга­ низацией цепочек записей в области переполнения при использовании данного метода эффективность доступа в большинстве случаев выше. Однако при многократном расщеплении одних и тех же блоков следует разгрузить и реорганизовать файл, а также создать новый индексный файл. Примером такого подхода может служить метод доступа УЗАМ (виртуальный) фирмы 1ВМ.

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

* Здесь и далее в этой главе фамилии располагаются не в алфавитном порядке, а по возрастанию кодов букв.— Примеч. ред.

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

Чтобы достичь наивысшей производительности при работе с индексно­ последовательными файлами, нёобходимо учесть следующие факторы.

Индексный файл	Файл данных
блок 7	длок1

доступа

Эффективность доступа.

1. Размеры базы данных. По мере расширения базы данных индекс приоб­ ретает все большее число элементов. Вероятным результатом этого явля­ ется повышение уровня индексации. Но^наличие индексного файла боль­ шого размера или высокий уровень индексации снижают эффективность

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

2. Размер блока. Средний размер блока .и число блоков в базе данных — величины взаимно обратные. Чем больше размер блока, тем меньшее их число хранится в базе данных, и тем соответственно меньше элементов в индексе. Следует также принимать во внимание время передачи больших блоков по каналам. Необходимо определить оптимальный размер блока базы данных.

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

4. Индекс высшего уровня в памяти процессора. Выделение достаточного для размещения индекса высшего уровня памяти процессора повышает эффективность доступа.

Эффективность хранения.

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

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

В заключение следует отметить, что большинство коммерческих систем допускают только уникальные значения ключей индекса.

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

Тем не менее и индексно-произвольный метод доступа также базируется на использовании индекса.

7.2.3. Индексно-произвольный метод доступа

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

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