Реляционная целостность данных

Реляционная целостность данных рассматривается в двух аспектах ключи отношения и реляционные ограничения целостности.

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

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

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

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

Обычно ключи используют для:

l исключения дублирования значений в ключевых атрибутах (другие атрибуты в расчет не принимаются);

l упорядочения кортежей. Возможно упорядочение по воз­растанию или убыванию значений всех ключевых атрибу­тов, а также смешанное упорядочение (по одним атрибу­там возрастание, по другим — убывание);

l ускорения работы с кортежами отношения;

l организации связывания таблиц.

Если в отношении R1 имеется не ключевой атрибут A, значения которого являются значениями ключевого атрибута B другого отношения R2, то атрибут A отношения R1является внешним ключом.

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

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

Кроме этого, для БД задаются два правила целостности, которые называются реляционными ограничениями целостности — ограничениями для всех допустимых состояний БД:

l правила целостности сущностей (отношений);

l правила ссылочной целостности.

Определитель NULL указывает на то, что значение атрибута в данный момент неизвестно или неприемлемо для данного кортежа, NULL не входит в область определения некоторого кортежа либо никакое значение еще не задано. Ключевое сло­во NULL представляет собой способ обработки неполных или необычных данных, NULL ни в коем случае нельзя отождеств­лять как нулевое численное значение или заполненную про­белами текстовую строку (нули и пробелы — это некоторые значения; NULL — это отсутствие значения).

Целостность отношений — в базовом (основном) отношении ни один атрибут первичного ключа не может содержать отсутствующих значений, т. е. NULL значений.

Ссылочная целостность — значение внешнего ключа отношения должно либо соответствовать значению первичного ключа базового отношения, либо задаваться определителем NULL.

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

Индексирование

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

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

Решение проблемы организации физического доступа к ин­формации зависит в основном от следующих факторов:

l вида содержимого в поле ключа записей индексного файла;

l типа используемых ссылок (указателей) на запись основ­ной таблицы;

l метода поиска нужных записей.

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

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

Рис. 2 Одноуровневая схема индексации

В каждом блоке записи располагаются в порядке возрастания значения ключа (или свертки). Старшим ключом каждого блока является ключ его последней записи. Если в индексном файле хранятся хеш-коды ключевых полей индексированной таблицы, то алгоритм поиска нужной запи­си включает три этапа.

1 Образование свертки значения ключевого поля искомой записи.

2 Поиск в индексном файле записи о блоке, значение первого поля которого больше полученной свертки (это гарантирует нахождение искомой свертки в данном блоке).

3 Последовательный просмотр записей блока до совпадения сверток искомой записи и записи блока файла. В случае коллизий сверток(нескольким разным ключам может соответствовать одно значение хеш-функции, т. е. один адрес) ищется запись, значение ключа которой совпадает со значением ключа искомой записи.

Недостаток одноуровневой схемы — ключи (свертки) записей хранятся вместе с записями, что приводит к увеличению вре­мени поиска записей из-за большой длины просмотра (значения данных в записях приходится пропускать). В двухуровневой схеме ключи (свертки) записей отделены от содержимого записей (рис. 3).

В данном случае индекс основной таблицы распределен по совокупности файлов: одному файлу главного индекса и множеству файлов с блоками ключей.

На практике при создании индекса для некоторой таблицы базы данных указывают поле таблицы, которое требует ин­дексации. Ключевые поля таблицы во многих СУБД индекси­руются автоматически. Индексные файлы, создаваемые по ключевым полям таблицы, называются файлами первичных индексов.

Индексы, создаваемые не для ключевых полей, называются вторичными (пользовательскими) индексами. Введение этих индексов не изменяет физического расположения записей таблицы, но влияет на последовательность просмотра запи­сей. Индексные файлы, создаваемые для поддержания вто­ричных индексов таблицы, называются файлами вторичных индексов. Блок ключей-1

Рис.3 Двухуровневая схема индексации

Некоторые СУБД поддерживают кластеризацию и класте­ризованные хешированные индексы.

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

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

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

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

Используемая литература

1. Мейер М / / Теория реляционных баз данных //М.: Мир, 1987

2. Копейкин М.В., Спиридонов В.В., Шумова Е.О // Базы данных. Объектно-реляционный подход: Учеб. Пособие // СПб.: СЗПИ, 1998

3. Дрибас В.П// Реляционные модели баз данных //Минск: БГУ, БССР, 1982

4. Дейт К.Дж// Введение в системы баз данных// Пер. с англ. 6-е изд. К.: Диалектика, 1998

Вопрос 18

Хеширование

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

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

NZ =F(К),

где NZ — номер записи, К — значение ключа, F () — функция.

Функция F () при этом должна быть линейной, чтобы обеспечивать однозначное соответствие (см. рис. 4).

Рис. 4 Пример линейной функции пересчета значения ключа в номер записи

Однако далеко не всегда удается построить взаимно-однозначное соответствие между значениями ключа и номерами записей.

Часто бывает, что значения ключей разбросаны по нескольким диапазонам. В этом случае не удается построить взаимно-однозначную функцию, либо эта функция будет иметь множество незадействованных значений, которые соотвествуют недопустимым значениям ключа. В подобных случаях применяют различные методы хэширования (рандомизации) и создают специальные хэш-функции. Суть методов хэширования состоит в том, что мы берем значения ключа (или некоторые его характеристики) и используем его для начала поиска, то есть мы вычисляем некоторую хэш-функшпо h(k) и полученное значение берем в качестве адреса начала поиска. То есть мы не требуем полного взаимно-однозначногосоответствия, но, с другой стороны, для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного поучения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш-функцин (то есть один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами. Поэтому при использовании хэширования как метода доступа необходимо принять два независимых решения:

l выбрать хэш-функцню;

l выбрать метод разрешения коллизий.

Существует множество различных стратегий разрешения коллизий, но мы для примера рассмотрим две достаточно распространенные,