Гринберг А.С., Иванюкович В.А., Новыш Б.В., Шешолко В.К. Ситуационный анализ и моделирование на основе информационных технологий баз данных

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

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

страницы и последовательности страниц внутри набора страниц (обычно это

порядок возрастания идентификационных номеров записей). Такая

последовательность называется физической, хотя она не обязательно

соответствует физическому расположению данных на диске.

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

Основное назначение индексов состоит в обеспечении эффективного

прямого доступа к кортежу отношения по ключу.

Рассмотрим в качестве примера таблицу с данными о поставщиках (рис.3.5.3)

и запрос типа "Найти всех поставщиков из города С". На основании этой

таблицы может быть создан файл с данными о городах. Файл городов может

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

полю ГОРОД, с указателями на соответствующие записи в файле поставщиков.

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

городов

Индексированный файл поставщиков

Город Ук П№ Имя_П Статус Гор

Брест



П1 Волк 20 Брест

Брест



П2 Заяц 10 Минск

Гродно



П3 Лев 30 Гродно

Минск



П4 Лиса 20 Минск

Минск



П5 Бык 30 Брест

Рис. 3.6.2. Индексирование файла Поставщики по полю Город файла

городов

Поиск всех поставщиков из Минска, например, можно выполнить двумя

способами:

1. Найти весь файл поставщиков, найти все записи, для которых названием

города является строка Минск;

2. Найти файл городов, найти в нем строку Минск, а затем согласно

указателям извлечь все соответствующие записи из файла поставщиков.

Если доля всех поставщиков из Минска по отношению к общему

количеству поставщиков достаточно мала, то второй способ будет гораздо

эффективнее первого. СУБД известна физическая последовательность записей

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

для такого поиска потребуется гораздо меньше операций ввода-вывода,

поскольку физический размер файла городов меньше, чем размер файла

поставщиков из-за меньшего размера записей.

В рассматриваемом примере файл городов называется индексным файлом

или индексом по отношению к файлу поставщиков, а файл поставщиков

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

Индексный файл – это хранимый файл особого типа, в котором каждая запись

состоит из двух значений, а именно данных и RID-указателя, необходимого для

связывания с соответствующей записью индексированного файла.

Если индексирование организовано на основе ключевого поля, например

на основе поля П№ файла поставщиков, то индекс называется первичным (или

уникальным), а если индекс организован на основе другого поля, например

поля ГОРОД, как в рассматриваемом примере, то он называется вторичным.

Значительное ускорение процесса выборки или извлечения данных

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

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

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

добавить новый индекс в индексный файл. Поэтому при выборе некоторого

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

СУБД: скорость извлечения данных или скорость обновления?

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

использовать для последовательного доступа к индексированному файлу, где

последовательность задается значениями индексного поля. Например, индекс

по полю ГОРОД из рассматриваемого примера будет определять доступ к

записям файла поставщиков согласно алфавитному перечню городов (найти

поставщиков из городов, начинающихся на буквы К-М). Во-вторых, индексы

могут использоваться для прямого доступа к отдельным записям

индексированного файла на основе заданного значения индексного поля.

Пример запроса "Найти поставщиков из Минска" является типичным примером

такого использования индексов.

Хранимый файл может иметь несколько индексов. Например, хранимый

файл поставщиков может иметь индекс ГОРОД и индекс СТАТУС. Они могут

как раздельно, так и совместно использоваться для более эффективного доступа

к записям о поставщиках. Для иллюстрации "совместного" использования

индексов рассмотрим запрос "Найти поставщиков из Бреста со статусом 20".

Если согласно индексу ГОРОД для поставщиков из Бреста найдены записи с

RID-указателями r2 и r3, а согласно индексу СТАТУС – записи с RID-

указателями r3 и r5, то условиям запроса удовлетворяет только запись с

данными о поставщике c указателем r3. Только после этого в СУБД будет

организован доступ к файлу поставщиков и будет извлечена данная запись.

Индексы часто называют инвертированными списками, а файл с

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

Индекс можно также создать на основе комбинации двух или более полей.

Например, если проиндексировать файл поставщиков на основе комбинации

полей ГОРОД и СТАТУС, то запрос типа "Найти поставщиков из Бреста со

статусом 30" можно выполнить на основе однократного просмотра с помощью

одного индекса. Причем, комбинированный индекс ГОРОД/СТАТУС может

также служить индексом по одному полю ГОРОД, поскольку все записи в

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

До сих пор предполагалось, что для ускорения процесса извлечения

данных используются указатели записей (RID-указатели). Но иногда для этого

достаточно использовать указатели страниц (т.е. номеров страниц). Конечно,

для последующего поиска записи внутри данной страницы придется

осуществить еще одну операцию извлечения записи. Однако теперь она будет

выполняться в оперативной памяти и для этого не придется увеличивать число

дисковых операций ввода-вывода. Если в таблице ПОСТАВЩИКИ выполнена

кластеризация по полю П№ и по этому же полю осуществляется

индексирование, то нет необходимости хранить в индексном файле указатели

для каждой записи индексируемого файла (в данном случае для файла

поставщиков). Достаточно иметь указатель для каждой страницы, состоящий из

максимального номера поставщика для данной страницы и соответствующего

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

поставщика будет состоять из помещения в оперативную память

соответствующей страницы и очень быстрого поиска нужной хранимой записи.

Такой индекс называется неплотным. Все описанные ранее индексы,

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

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

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

3.6.3. Структуры типа Б-дерева

Наиболее популярным подходом к организации индексов в базах данных

является использование структур типа Б-дерева (B-tree, или индексов

бинарного типа). Благодаря тому, что бинарные индексы обладают в

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

использование предусмотрено почти во всех СУБД, а некоторые СУБД

работают только на основе такого индекса.

Структуры типа Б-дерева позволяют избежать просмотра всего содержимого

индексированного файла согласно его физической последовательности. Если

индексированный файл имеет большой размер, то и его индекс также очень

велик. Поэтому последовательный просмотр даже одного только индекса

требует больших затрат времени. Для разрешения такой проблемы можно

рассмотреть индексный файл как обычный хранимый файл и создать для него

еще один индекс. Эту операцию можно осуществлять повторно нужное

количество раз (обычно она применяется трижды, поскольку создание

большого количества иерархических уровней индексирования требуется для

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

неплотным по отношению к нижнему индексируемому уровню.

Структура индекса типа Б-дерева является частным случаем индекса

древовидного дерева, который состоит из двух частей: набора

последовательностей и набора индексов.

Набор последовательностей включает одноуровневый индекс для реальных

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

в индексированном файле проведена кластеризация на основе индекса). Записи

внутри индекса сгруппированы по страницам, а страницы связаны в цепочку

таким образом, чтобы логическое упорядочение на основе индекса

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

последовательности записей внутри второй страницы этой последовательной

цепочки и т.д. Таким образом, с помощью набора последовательностей можно

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

Набор индексов, в свою очередь, обеспечивает быстрый непосредственный

доступ к набору последовательностей (а значит, и к данным). По сути, набор

индексов является древовидным индексным файлом для набора

последовательностей или индексом со структурой Б-дерева. Комбинация

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

Б-плюс-дерева (В-plus tree или B+-tree). На самом верхнем уровне такого

индекса находится только один элемент структуры (страница, содержащая

множество записей), который называется корневым (root).

3.6.4. Хеширование

Альтернативным и все более популярным подходом к организации индексов

является использование техники хеширования. Хешированием, хеш-адресацией

или хеш-индексированием называется технология быстрого прямого доступа к

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

обязательно, чтобы поле было ключевым. Ниже перечислены основные черты

этой технологии.

Каждая хранимая запись базы данных размещается по адресу (RID-указателю

или номеру страницы), который вычисляется с помощью специальной хеш-

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

полем.

Для сохранения записи в СУБД сначала вычисляется хеш-адрес новой

записи, а затем диспетчер файлов помещает эту запись по вычисленному

адресу.

Для извлечения нужной записи по заданному значению хеш-поля в СУБД

сначала вычисляется хеш-адрес, а затем диспетчеру файлов посылается запрос

для извлечения записи по вычисленному адресу.

В качестве иллюстрации предположим, что у нас есть записи с данными о

поставщиках с номерами 100, 200, 300, 400 и 500 (вместо П1, П2, ПЗ, П4, П5),

для хранения каждой из них предназначается отдельная страница, а в качестве

хеш-функции используется следующая:

хеш-адрес (т.е. номер страницы) = остаток от деления на 13 числа,

содержащегося в поле П№

Это простейший пример общего класса хеш-функций типа деление/остаток (в

качестве делителя следует выбирать простое натуральное число). В этом

примере номерами страниц для заданных записей будут 9, 5, 1, 10 и 6

соответственно.

Теоретически для определения адреса вместо хеш-функции можно было бы

использовать непосредственно значение ключевого поля (если это поле имеет

числовой тип). Однако практически такой способ неприемлем, поскольку

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

диапазона имеющихся адресов. В нашем примере номера записей с данными о

поставщиках находятся в диапазоне 000 – 500, т.е. их может быть около 500,

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

Таким образом, во избежание неэффективного использования дискового

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

диапазон 000 – 500, например, до 0 – 9. Для того чтобы зарезервировать

дополнительное пространство (размером 20% от исходной величины), диапазон

0 – 9 в данном примере расширен до 0 – 12 за счет делителя 13.

В этом примере также наглядно проявляется недостаток хеширования.

Физическая последовательность записей внутри хранимого файла почти всегда

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

логически заданной последовательности. К тому же, между последовательно

размещенными записями могут быть промежутки неопределенной

протяженности. Практически всегда физическая последовательность записей в

хранимом хешированном файле не имеет ничего общего с заданной в нем

логической последовательностью.

Еще одним недостатком хеширования является возможность возникновения

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

одинаковые адреса. Допустим, что файл поставщиков из предыдущего примера

(с поставщиками 100, 200 и т.д.) содержит также поставщика с номером 1400.

При использовании хеш-функции типа "остаток от деления на 13" возникнет

коллизия (по адресу 9) с записью 100. Ясно, что такая хеш-функция

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

Наиболее часто на практике для разрешения коллизий используется значение

хеш-функции в качестве адреса не какой-либо записи с данными, а точки

привязки. Точка привязки – это начальный адрес цепочки указателей (цепочки

коллизий), связывающей вместе все записи или все страницы с записями,

которые имеют одинаковый хеш-адрес. Внутри цепочки коллизий записи также

могут быть упорядочены согласно хеш-полю для упрощения последующего

поиска.

Еще один недостаток описанного выше способа хеширования – возрастание

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

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

поскольку все больше и больше времени придется тратить на поиск записей в

наборах конфликтующих записей. Однако этот недостаток можно устранить,

если реорганизовать файл, т.е. выгрузить данный файл и загрузить его вновь,

используя новую хеш-функцию. Для этого используют метод расширяемого

хеширования, основанный на технологии B-деревьев с расщеплениями и

слияниями, благодаря которой потребуется не более двух доступов к диску для

поиска заданной записи (т.е., записи, имеющей заданное значение ключевого

поля), а в некоторых случаях будет достаточно даже одного доступа

независимо от размера файла.

4 . Р Е Л Я Ц И О Н Н А Я А Л Г Е Б Р А

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

реляционной алгебре. Операторы в реляционной алгебре используют

отношения в качестве операндов и возвращают отношения в качестве

результата. Это реляционное свойство называется свойством замкнутости.

Благодаря этому свойству результат одной операции может использоваться в

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

формировать вложенные выражения, т.е., выражения, в которых операнды

сами представлены выражениями. Это же свойство обусловливает

необходимость принятия правил наследования имен атрибутов для того, чтобы

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

реляционной операции. Задав такие правила для всех операций, можно

гарантировать, что для выражения любой сложности будет вычисляться

результат, имеющий вполне определенный набор атрибутов. Более того,

поскольку каждое отношение имеет множество потенциальных ключей, то

могут быть ситуации, когда должны быть известны потенциальные ключи для

каждого результирующего отношения, т.е., должны быть приняты правила

наследования потенциальных ключей.

По определению Е.jКодда, основу реляционной алгебры составляют

восемь операторов. Причем, некоторые из них могут выполняться при

определенных условиях. Например, в математике объединение двух множеств

является множеством всех элементов, принадлежащих или обоим, или одному

из исходных множеств. Объединение множества кортежей поставщиков в

отношении ПОСТАВЩИКИ и множества кортежей деталей в отношении ДЕТАЛИ

является множеством, но не являются отношением – отношения не могут

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

объединения требуется, чтобы два исходных отношения имели одну и туже

форму, т.е., были совместимы по типу. Два отношения совместимы по типу,

если

1. каждое из них имеет одно и то же множество имен атрибутов (и поэтому они

имеют одну и ту же степень);

2. соответствующие атрибуты определены на одном и том же домене.

4.1. Традиционные реляционные операции

К традиционным операциям над множествами относятся операторы

объединения, пересечения, вычитания и произведения.

Объединением двух совместимых по типу отношений А и В (A UNION B)

называется отношение с тем же заголовком, как и в отношениях А и В, и с

телом, состоящим из множества всех кортежей t, принадлежащих А или В или

обоим отношениям. При этом совпадающие кортежи записываются один раз.

Пересечением двух совместимых по типу отношений А и В (A INTERSECT B)

называется отношение с тем же заголовком, как и в отношениях А и В, и с

телом, состоящим из множества всех кортежей t, которые принадлежат

одновременно обоим отношениям А и В.

Вычитанием двух совместимых по типу отношений А и В (A MINUS B)

называется отношение с тем же заголовком, как и в отношениях А и В, и с

телом, состоящим из множества всех кортежей t, принадлежащих отношению А

и не принадлежащих отношению В.

Произведение. Декартово произведение двух

отношений А и В (A TIMES B), где А и В не имеют

общих имен атрибутов, определяется как отношение

с заголовком, который представляет собой сцепление

двух заголовков исходных отношений А и В, и

телом, состоящим из множества всех кортежей t таких, что t представляет

собой сцепление кортежа a, принадлежащего отношению А, и кортежа b,

принадлежащего отношению В. Кардинальное число результата равняется

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

сумме их степеней.

4.2. Специальные реляционные операции

К специальным реляционным операциям относятся выборка, проекция,

соединение и деление.

Выборка – это сокращенное название -выборки, где  обозначает любой

скалярный оператор сравнения (=, , , > и т.д.). -выборкой из отношения А

по атрибутам X и Y (A WHERE X  Y) (порядок учитывается!) называется

отношение, имеющее тот же заголовок, что и отношение А, и тело, содержащее

множество всех кортежей t отношения А, для которых проверка условия «X  Y»

дает значение истина. Атрибуты X и Y должны быть определены на одном и

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

домена. Пример выборки показан на рис. 2.7.4.

Проекцией отношения А по атрибутам X, Y, …, Z, где каждый из

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

{X,Y,…,Z} и телом, содержащим множество кортежей с атрибутами,

совпадающими с соответствующими атрибутами отношения А.

TIMES

X = A X

В Y A Y

С B X

B Y

C X

C Y

Рис.4.1.1

Т.е., с помощью операции проекции получается вертикальное

подмножество исходного отношения – подмножество, получаемое

исключением всех атрибутов, не указанных в списке атрибутов, и

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

Пример проекции показан на рис. 2.7.5.

Соединением (или естественным соединением) отношений А и В (A JOIN B)

с заголовками X,Y и Y,Z соответственно и с атрибутами Y, определенными на

одном и том же домене, называется отношение с заголовком {X,Y,Z} и телом,

содержащим множество кортежей с атрибутами, совпадающими с

соответствующими атрибутами отношений А и В.

Соединение обладает свойствами ассоциативности и коммутативности.

Если отношения А и В не имеют общих имен атрибутов, то естественное

соединение превращается в декартово произведение. Пример операции

соединения показан на рис.2.7.6.

Делением двух отношений,

бинарного и унарного, является

отношение, содержащее все значения

одного атрибута бинарного отношения,

которые соответствуют (в другом

атрибуте) всем значениям в унарном

отношении.

На рис.4.2.1 показаны два примера

деления отношений.

Следует быть осторожным при использовании этой операции (например,

при наличии пустых отношений).

4.3. Дополнительные реляционные операции

Описанные выше элементы реляционной алгебры не содержат средств для

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

операция расширения EXTEND. С помощью этой операции создается новое

отношение, похожее на исходное, но содержащее дополнительный атрибут,

значения которого получены посредством некоторых скалярных вычислений:

П№ Д№ Д№ П№

П1 Д1 DIVIDEDBY Д2 = П1

П1 Д2 Д4 П4

П1 Д4

П2 Д1

П2 Д2

П3 Д2 DIVIDEDBY Д1 = П1

П4 Д1 П2

П4 Д2 П4

П4 Д4

ПДПр