Средства ускорения доступа к данным

 

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

В современных СУБД используются два основных метода ускорения доступа к данным: индексирование и хеширование. Эти методы обеспечивают лучшее по сравнению с остальными время поиска и модификации таблиц БД.

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

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

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

Еще один интересный подход, применяемый для повышения эффективности доступа к данным, - хеширование (hashing). Для метода хеширования, к сожалению, нет житейского аналога, поэтому объяснить его «на пальцах» вряд ли получится. Основная идея хеширования - организация ассоциативной памяти для хранения строк таблицы с определением места строки в таблице по значениям одного или нескольких ее ключевых атрибутов. Место строки вычисляется хэш-функцией, аргументы которой - значения атрибутов, а результат - целое число в диапазоне номеров строк таблицы. Идеальная хэш-функция должна давать разные значения номеров строк для разных ключевых атрибутов. Однако построить такую хэш-функцию - дело трудоемкое и не всегда возможное.

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

f(k) = k mod p,

где f - хэш-функция, k - целочисленный атрибут, а р - простое число.

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

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

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

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

 

Язык запросов

 

База данных бесполезна, если отсутствуют средства доступа к информации в ней. Для получения информации из БД пользователи направляют СУБД запросы. СУБД обрабатывает их и отправляет результаты обработки пользователям. Запросы формулируются на специальном «языке запросов». Фактическим стандартом такого языка для современных реляционных СУБД стал SQL (Structured Query Language - структурный язык запросов).

Этот язык имеет официальный стандарт, последняя версия которого была принята ANSI и ISO в 1992 году. Большинство разработчиков СУБД придерживаются этого стандарта. Тем не менее они часто расширяют его для реализации специальных возможностей обработки данных. SQL - это не язык программирования в традиционном смысле. Это язык запросов к базе данных. С его помощью можно сформулировать, какие данные требуется получить, но невозможно определить, как это следует сделать. На SQL не пишутся программы - в нем отсутствуют многие операторы процедурных языков программирования, например, операторы проверки условия (if...then...else), операторы циклов и др. Для того чтобы использовать SQL в приложениях, работающих с БД, необходимо использовать библиотеки подпрограмм, позволяющие встраивать запросы на SQL в текст на С или Pascal. В современных СУБД имеются свои средства, позволяющие разрабатывать прикладные программы с применением SQL и средств управления интерфейсом с пользователем.

Запросы на языке SQL строятся с использованием одного или нескольких операторов. Операторы разделяются символом перевода строки или точкой с запятой. В таблице 8.1 перечислены некоторые операторы, входящие в текущий стандарт языка SQL.

Стандарт языка SQL определяет также типы данных, которые можно использовать при создании БД и работе с ней. В таблице 8.2 перечислены основные типы данных, используемые в SQL, а также указаны соответствующие им типы языка С.

 

Таблица 8.1.

Оператор	Назначение
SELECT	Выбрать данные из БД
INSERT	Добавить данные в БД
UPDATE	Обновить данные в БД
DELETE	Удалить данные из БД
GRANT	Предоставить привилегии пользователю
REVOKE	Отменить привилегии пользователя
COMMIT	Зафиксировать текущую транзакцию
ROLLBACK	Прервать текущую транзакцию

 

Таблица 8.2.

Тип данных SQL/92	Описание	Тип языка С
CHARACTER	Стока символов фиксированной длины	char[]
INTEGER	Целое число	long
SMALLINT	Целое число	short
REAL	Число с плавающей запятой	float
DOUBLE PRECISION	Число с плавающей запятой двойной точности	double

 

В стандарте SQL определяются также некоторые специальные типы:

1) денежные единицы (MONEY);

2) дата (DATE) и время (TIME);

3) числовые типы, для которых задается масштаб и точность (FLOAT, NUMERIC, DECIMAL).

С использованием SQL можно определить отношения, содержащие данные любого из перечисленных типов, однако для использования этих данных в приложениях, написанных на стандартных языках программирования (С, Pascal), требуются специальные средства – в этих языках нет многих типов данных SQL.

 

Контрольные вопросы:

1. Дайте определение документальной информационной системы.

2. Дайте определение фактографической информационной системы.

3. Дайте определение термину «база данных».

4. Перечислите основные модели данных. Приведите примеры.

5. Перечислите и опишите основные операции реляционной алгебры, реализуемые в СУБД.

6. Опишите метод нормализации отношений, применяемый при проектировании баз данных.

7. Перечислите и опишите основные методы ускорения доступа к данным.

8. Что такое запросы и для чего они служат?