Карпова Т.С. Базы данных: модели, разработка, реализация

Подождите немного. Документ загружается.

Понятие

представления операции создания представлений

161

Ограничение стандарта

SQL1

на

обновление

представлений

Несмотря

на

то,

что для

пользователей

представления выглядят

как

реальные

отношения,

существует

ряд

ограничений

на

операции

модификации

данных,

свя-

занные

представлениями.

СУБД

может

обновлять

данные

через

представления

только

в том

случае,

если

она

может однозначно сопоставить каждой

строке

представления

строку

из ре-

альной

таблицы базы данных,

а для

каждого обновляемого столбца представле-

ния

однозначно

определить

исходный

столбец

исходной

таблицы

базы

данных.

Далеко

не для

всех

запросов

это

возможно

сделать. Действительно, запросы

группировкой, сложные запросы

подзапросами возвращают результат, кото-

рый

СУБД

не

сможет

однозначно

интерпретировать

терминах

реальных

таб-

лиц

БД.

Согласно

стандарту,

представление можно обновлять только

в том

случае,

когда

его

запрос

соответствует

следующим требованиям;

запросе должен отсутствовать предикат

DISTINCT,

то

есть повторяющиеся

строки

не

должны исключаться

из

таблицы

результатов

запроса.

предложении

FROM

должна быть

задана

только

одна

таблица, которую мож-

но

обновлять,

то

есть

представления

должна

быть только

одна

исходная

таблица

(это

горизонтальное

или

вертикальное

представление),

пользова-

тель

должен иметь соответствующие права доступа

ней.

Если

таблица сама

является

представлением,

то она

тоже

должна

удовлетворять данным усло-

виям.

Каждое

имя в

списке возвращаемых столбцов должно быть ссылкой

на

простой

столбец:

списке

не

должны

содержаться

выражения,

вычисляемые

столбцы

или

агрегатные

функции.

Q В

предложении

WHERE

не

должен стоять вложенный запрос;

в нем

могут при-

сутствовать только простые условия поиска.

Q В

запросе

не

должно

присутствовать выражение группировки

GROUP

BY или

HAVING.

Однако

ряде коммерческих СУБД

оти

требования

смягчены

операции

Модификации

разрешены

для

более широкого класса

представлений.

ГЛАВА

Физические

модели

баз

данных

Физические

модели

баз

данных

определяют способы

размещения

данных

сре-

де

хранения

способы

доступа

этим

данным,

которые

поддерживаются

па фи-

зическом

уровне.

Исторически

первыми

системами

храпения

доступа

были

файловые

структуры

системы

управления

файлами

(СУФ),

которые фактиче-

ски

являлись

частью

операционных

систем.

СУБД

создавала

над

этими

файло-

выми

моделями

свою

надстройку,

которая позволяла

организовать

всю

совокуп-

ность

файлов

таким

образом, чтобы

она

работала

как

единое целое

получала

централизованное

управление

от

СУБД.

Однако

непосредственный

доступ

осу-

ществлялся

па

уровне файловых

команд,

которые

СУБД

использовала

при ма-

нипулировании

всеми

файлами,

составляющими

хранимые

данные

одной

пли

нескольких

баз

данных,

Однако

механизмы

буферизации

управления

файловыми

структурами

не

при-

способлены

для

решения

задач

собственно

СУБД,

эти

механизмы

разрабатыва-

лись

просто

для

традиционной

обработки

файлов,

и с

ростом

объемов

храни-

мых

данных

они

стали

неэффективны

ми

для

использования

СУБД.

Тогда

посте-

пенно

произошел

переход

от

базовых файловых структур

непосредственному

управлению

размещением

данных

на

внешних

носителях

самой СУБД.

про-

странство

внешней

памяти

уже

выходило

лз-под

владения

СУФ л

управлялось

непосредственно

СУБД.

При

этом

механизмы,

применяемые

файловых систе-

мах,

перешли

во

многом

и в

новые

системы

организации

данных

во

внешней

па-

мяти,

называемые чаще

страничными

системами

хранения

информации. Поэто-

му

наш

раздел,

посвященный

физическим

моделям

данных,

мы

начнем

обзора

файлов

файловых

структур, используемых

для

организации

физических

мо-

делей,

применяемых

базах

данных,

а в

конце

ознакомимся

механизмами

ор-

ганизации

данных

во

внешней

памяти,

использующими

страничный

принцип

организации.

файловые

структуры,

используемые

для

хранения

информации

базах данных

163

Файловые

структуры,

используемые

для

хранения

информации

базах данных

каждой

СУБД

по-разному

организованы

храните

доступ

данным,

однако

существуют

некоторые

файловые

структуры, которые имеют

общепринятые

спо-

собы

организации

широко

применяются

практически

во

всех

СУБД,

системах

баз

данных

файлы

файловые

структуры,

которые

используются

для

хранения

информации

по

внешней

памяти,

можно

классифицировать

сле-

дующим

образом

(см.

рпс.

9.1).

Рис.

9.1.

Классификация

файлов,

используемых

системах

баз

данных

точки

зрения

пользователя,

файлом

называется

поименованная

линейная

по-

следовательность

записей,

расположенных

на

внешних

носителях.

На

рис.

9.2

представлена

такая

условная

последовательность

записей.

Так

как

файл

— это

линейная

последовательность

записей,

то

всегда

файле

можно

определить

текущую

запись,

предшествующую

ей

следующую

за

ней.

Всегда

существует

понятие

первой

последней

записи

файла.

Не

будем

вда-

ваться

особенности

физической

организации

внешней

памяти,

выделим

в пей

те

черты, которые

существенны

для

рассмотрения

нашей

темы.

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

методами

управления

доступом

различают

устройства

внешней

памяти

производыюй

адресацией

(магнитные

оптические

диски)

устройст-

ва

последовательной

адресацией

(магнитофоны,

стримеры).

На

устройствах

произвольно]:

адресацией

теоретически

возможна

установка

головок

чтения-записи

произвольное

место

мгновенно,

Практически

сущест-

вует

время

позиционирования

головки,

которое весьма мало

по

сравнению

со

временем,

считывания-записи.

устройствах

последовательным

доступом

для

получения

доступа

некото-

рому

элементу

требуется

«перемотать

(пройти)»

все

предшествующие

ему

эле-

менты

информации.

На

устройствах

последовательным

доступом

вся

память

рассматривается

как

линейная

последовательность

информационных

элементов

(см.

рис. 9.3).

164

Глава

Физические

модели

баз

данных

Рис. 9.3,

Модель

хранения информации

на

устройстве

последовательного

доступа

Файлы

постоянной

длиной

записи,

расположенные

на

устройствах

прямого

доступа

(УПД),

являются файлами

пряного

доступа,

этих файлах физический адрес

расположения

нужной

записи

может быть

вы-

числен

по

номеру записи (NZ).

Каждая файловая

система

СУФ

—

система

управления файлами поддерживает

некоторую

иерархическую файловую

структуру,

включающую чаще всего

не-

ограниченное

количество уровней иерархии

представлении

внешней

памяти

(см. рис. 9.4).

Для

каждого файла

системе хранится следующая информация:

имя

файла;

тип

файла (например, расширение

или

другие характеристики);

размер записи;

количество-

занятых

физических

блоков;

базовый

начальный

адрес;

Файловые

структуры,

используемые

для

хранения

информации

базах

данных

165

Рис. 9.4.

Иерархическая

организация

файловой

структуры

хранения

Для

файлов

постоянной

длиной

записи адрес

размещения

записи

номером

может

быть

вычислен

по

формуле:

ВА

+ (К - 1) * LZ + 1,

где

ВЛ —

базовый

адрес,

длина

записи.

И как мы уже

говорили ранее, если можно всегда определить адрес,

па

кото-

рый

необходимо

позиционировать

механизм

считывания-записи,

то

устройства

прямого доступа

делают

это

практически

мгновенно,

поэтому

для

таких

файлов

чтение

произвольной

записи

практически

не

зависит

от

ее

номера.

Файлы

пря-

мого

доступа обеспечивают

наиболее

быстрый доступ

произвольным записям,

их

использование

считается наиболее

перспективным

системах

баз

данных.

На

устройствах последовательного доступа могут быть

организованы

файлы

толь-

ко

последовательного доступа.

Файлы

переменной

длиной

записи

всегда являются

файлами

последователь-

ного

доступа.

Они

могут

быть

организованы

двумя

способами;

Конец

записи

отличается

специальным

маркером.

166

Глава

Физические модели

баз

данных

Файлы

прямым доступом

обеспечивают

наиболее быстрый способ доступа.

Мы

не

всегда

можем хранить

информацию

виде

файлов

прямого доступа,

по

главное

— это то, что

доступ

по

номеру

записи

базах

данных

весьма неэффек-

тивен.

Чаще всего

базах

данных

необходим

поиск

по

первичному

или

возмож-

ному ключам,

иногда

необходима

выборка

по

внешним

ключам,

но во

всех

этих

случаях

мы

знаем

значение

ключа,

но не

знаем

номера

записи,

который

соответ-

ствует

этому ключу.

При

организации

файлов прямого

доступа

некоторых

очень

редких случаях

возможно

построение

функции,

которая

по

значению

ключа

однозначно

вычис-

ляет адрес

(номер

записи

файла).

F(K),

где

NZ —

номер записи,

К —

значение ключа,

F( ) —

функция.

Функция

при

этом должна

быть

линейной,

чтобы обеспечивать

однозначное

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

(см. рис. 9.5).

Рис.

9.5, Пример линейной функции пересчета значения ключа

номер

записи

Однако далеко

не

всегда

удается

построить

взаимно-однозначное

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

между

значениями

ключа

номерами записей.

Часто

бывает,

что

значения

ключей разбросаны

по

нескольким

диапазонам

(см.

рис.

9.6).

этом случае

не

удается построить

взаимно-однозначную

функцию,

либо

эта

функция

будет

иметь

множество

незадейстиованиых

значении,

которые

соответ-

Файловые

структуры

(

используемые

для

хранения

информации

базах данных

167

ствуют

недопустимым

значениям

ключа.

подобных случаях

применяют

различ-

ные

методы хэширования

(рандомизации)

создают

специальные

хэш-

функции.

Суть методов

хэширования

состоит

том,

что мы

берем

значения

ключа

(

или

некоторые

его

характеристики)

используем

его для

начала

поиска,

то

есть

мы

вычисляем

некоторую

хэш-функцпю

h(k)

полученное

значение

берем

каче-

стве адреса начала

поиска.

То

есть

мы не

требуем

полного

взаимно-однозначно-

го

соответствия,

но,

другой

стороны,

для

повышения

скорости

мы

ограничива-

ем

время

этого

поиска

(количество

дополнительных шагов)

для

окончательного

получения

адреса.

Таким

образом',

мы

допускаем,

что

нескольким разным

клю-

чам

может

соответствовать

одно

значение

хэш-функции

(то

есть

один

адрес).

Подобные

ситуации

называются

коллизиями.

Значения

ключей,

которые

имеют

одно

то же

значение

хэш-фупкшш,

называются

синонимами.

Поэтому

при

использовании

хэширования

как

метода

доступа

необходимо

при-

нять

два

независимых

решения:

выбрать

хэщ-фупкцшо;

выбрать метод

разрешения

коллизий.

Существует

множество

различных

стратегий

разрешения

коллизий,

но мы для

примера

рассмотрим

две

достаточно

распространенные.

Стратегия

разрешения коллизий

областью переполнения

Первая

стратегия

условно

может

быть

названа

стратегии"!

областью

переполнения.

При

выборе этой

стратегии

область

храпения

разбивается

на 2

части:

основную

область;

область

переполнения.

Для

каждой

повои

записи

вычисляется

значение

хэш-фуикщш,

которое

опреде-

ляет

адрес

ее

расположения,

запись

заносится

основную

область

соответст-

вии

полученным

значением

хош-фупкцпп.

Основная

область:

168

Глава

Физические

модели

баз

данных

Если вновь заносимая запись имеет

значение

функции

хэширования

такое

же,

которое использовала

другая

запись,

уже

имеющаяся

в БД, то

новая запись

за-

носится

область переполнения

на

первое свободное

место,

а в

записи

гсинони-

ме,

которая

находится

основной

области, делается ссылка

на

адрес вновь раз-

мещенной

записи

области

переполнения,

Если

же уже

существует

ссылка

записи-синониме, которая расположена

основной

области,

то

тогда новая

запись

получает

дополнительную

информацию

виде

ссылки

и уже в

таком

виде заносится

область переполнения.

При

этом цепочка синонимов

не

разрывается,

но мы не

просматриваем

ее до

конца,

чтобы расположить новую запись

конце цепочки

синонимов,

распола-

гаем

всегда

новую

запись

на

второе

место

цепочке синонимов,

что

существен-

но

сокращает время размещения

новой

записи.

При

таком алгоритме время раз-

мещения

любой

новой записи

составляет

не

более

двух

обращений

диску,

уче-

том

того,

что

номер первой свободной записи

области переполнения хранится

виде системной переменной.

Рассмотрим теперь механизмы поиска произвольной записи

удаления записи

для

этой стратегии хэширования.

При

поиске

записи также сначала вычисляется

значение

ее

хэш-фупкции

счи-

тывается

первая

запись

цепочке синонимов, которая расположена

основной

области.

Если

искомая запись

не

соответствует первой

цепочке синонимов,

то

далее поиск

происходит

перемещением

по

цепочке синонимов, пока

не

будет

обнаружена требуемая запись. Скорость поиска зависит

от

длины

цепочки

си-

нонимов,

поэтому качество

хэш-функции

определяется

максимальной

длиной

цепочки,

синонимов. Хорошим результатом может считаться наличие

не

более

синонимов

цепочке.

При

удалении произвольной записи сначала

определяется

ее

место расположе-

ния.

Если удаляемой является первая запись

цепочке синонимов,

то

после

удаления

на ее

место

основной области

заносится

вторая

(следующая)

запись

цепочке

синонимов,

при

этом

все

указатели (ссылки

на

синонимы)

сохраня-

ются.

Если

же

удаляемая запись

находится

середине

цепочки

синонимов,

то

необхо-

димо провести корректировку

указателей;

записи,

предшествующей

удаляе-

мой,

цепочке ставится указатель

из

удаляемой

записи.

Если

это

последняя

за-

пись

цепочке,

то все

равно

механизм

изменения

указателей

такой

же, то

есть

предшествующую

запись заносится

признак

отсутствия следующей записи

цепочке,

который ранее хранился

последней записи.

Организация

стратегии

свободного

замещения

При

этрй

стратегия

файловое пространство

не

разделяется

на

области,

по для

каждой

записи добавляется

указателя: указатель

на

предыдущую запись

в це-

почке

синонимов

указатель

на

следующую запись

цепочке

синонимов.

От-

сутствие

соответствующей

ссылки

обозначается

специальным символом, напри-

мер

нулем.

Для

каждой повой записи

вычисляется

значение

хэш-функции,

если

данный

адрес

свободен,

то

запись

попадает

на

заданное место

становится пер-

вой

цепочке

синонимов,

Если адрес, соответствующий

полученному

значению

Индексные

файлы

169

хэш-функции,

занят,

то по

наличию

ссылок определяется, является

ли

запись,

расположенная

по

указанному адресу, первой

цепочке

синонимов.

Если

да, то

новая запись

располагается

на

первом свободном месте

и для нее

устанавлива-

ются соответствующие ссылки:

она

становится

второй

цепочке синонимов,

на

нее

ссылается

первая

запись,

а она

ссылается

на

следующую,

если таковая

есть.

Если

запись,

которая занимает требуемое место,

не

является первой записью

цепочке

синонимов,

значит,

она

занимает данное место

«незаконно*-

и при по-

явлении

-«законного

владельца» должна быть

«выселена»,

есть перемещена

на

новое место. Механизм

перемещения

аналогичен

занесению

новой записи,

которая

уже

имеет

синоним,

занесенный

файл,

Для

этой записи ищется пер-

вое

свободное место

корректируются

соответствующие ссылки;

•

записи,

ко-

торая

является

предыдущей

цепочке синонимов

для

перемещаемой записи,

заносится

указатель

на

новое

место перемещаемой записи,

указателе

же в

самой

перемещаемой записи остаются

прежние.

После перемещения «незаконной» записи вновь вносимая запись занимает

свое

законное

место

становится первой записью

новой цепочке

синонимов.

Механизмы удаления записей

во

многом

аналогичны

механизмам удаления

стратегии

областью переполнения.

Однако

еще раз

кратко опишем

их.

Если удаляемая запись является первой

записью

цепочке

синонимов,

то

после

удаления

на ее

место перемещается следующая

(вторая)

запись

из

цепочки

си-

нонимов

проводится соответствующая корректировка указателя третьей запи-

си в

цепочке синонимов, если таковая

существует,-

Если

же

удаляется

запись,

которая

находится

середине

цепочки синонимов,

то

производится только корректировка указателей:

предшествующей записи ука-

затель

на

удаляемую запись заменяется указателем

па

следующую

аа

удаляемой

запись,

а в

записи, следующей

за

удаляемой, указатель

на

предыдущую

запись

заменяется

на

указатель

на

запись,

предшествующую

удаляемо]!,

Вопросы

для

самостоятельной

работы

Сравнить

обе

стратегии

определить, какая

из

них

будет

наиболее

перспек-

тивной

и в

каких

случаях.

Разработать алгоритмы удаления

записей

для

первой

второй

стратегий.

По-

казать,

как

определяются ссылки.

Индексные

файлы

Несмотря

на

высокую

эффективность

хэш-адресации,

файловых

структурах

далеко

не

всегда

удается

найти

соответствующую

функцию,

поэтому

при

орга-

низации

доступа

по

первичному

ключу

широко

используются индексные

файлы.

некоторых

коммерческих

системах

индексными

файлами

называются

также

файлы,

организованные

виде

инвертированных

списков, которые

используют-

ся

для

доступа

по

вторичному ключу.

Мы

будем

придерживаться

классической

интерпретации

индексных

файлов

надеемся,

что

если

вы

столкнетесь

иной

170

ГлаваЭ.

Физические

модели

баз

данных

интерпретацией»

то

сумеете

разобраться

сути, несмотря

на

некоторую

путани-

цу

терминологии.

Наверное,

это

отчасти

связано

тем,

что

область

баз

данных

является

достаточно

молодой

областью

знаний,

несмотря

на то, что

здесь

уже

выработалась

определенная

терминология,

многие

поставщики

коммерческих

СУБД предпочитают свой упрощенный сленг

при

описании

собственных

про-

дуктов. Иногда

это

связано

тем,

что в

целях

рекламы

они не

хотят

ссылаться

на

старые, хорошо известные

модели

методы

организации

информации

сис-

теме,

изобретают

новые

названия

при

описании

своих

моделей,

тем

самым

пытаясь

разрекламировать эффективность своих

продуктов.

Хорошее

знание

принципов

организации

данных

поможет

вам

объективно

оценивать

решения,

предлагаемые

поставщиками

современных

СУБД,

и не

попадаться

на

реклам-

ные

крючки.

Индексные

файлы можно

представить

как

файлы,

состоящие

из

двух частей.

Это

не

обязательно

физическое

совмещение

этих

двух

частей

одном

файле,

большинстве

случаев

индексная

область образует

отдельный

индексный

файл,

основная область образует файл,

для

которого создается индекс.

Но

нам

удоб-

нее

рассматривать

эти

две

части

совместно,

так как

именно

взаимодействие

этих

частей

определяет использование

механизма

индексации

для

ускорения

до-

ступа

записям.

Мы

предполагаем,

что

сначала

идет

индексная

область, которая занимает

неко-

торое

целое число блоков,

затем

идет

основная

область,

которой последова-

тельно

расположены

все

записи

файла,

зависимости

от

организации

индексной

основной

областей

различают

типа

файлов:

плотным

индексом

и с

неплотным

индексом.

Эти

файлы

имеют

еще

дополнительные названия, которые

напрямую

связаны

методами

доступа

произвольной

записи,

которые

поддерживаются

данными

файловыми

структу-

рами.

Файлы

плотным

индексом

называются также

иидексио-прлмымн

файлами,

файлы

неплотным

индексом

называются

также

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

файлами.

Смысл этих

названий

нам

будет

ясен

после

того,

как мы

более под-

робно

рассмотрим

механизмы

организации

данных

файлов.

Файлы

плотным

индексом,

или

индексно-

прямые

файлы

Рассмотрим

файлы

плотным

индексом.

этих

файлах

основная

область содер-

жит

последовательность

записей

одинаковой

длины,

расположенных

в^

произ-

вольном

порядке,

структура

индексной

записи

них

имеет

вид:

Здесь

значение

ключа

— это

значение

первичного

ключа,

помер

записи

это

порядковый номер

записи

основной

области,

которая

имеет

данное

значение

первичного

ключа.

Значсшю

ключа

Номер

записи