Системы управления базами данных

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

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

Двунаправленный список удобен при удалении записи. Для корректности удаления подчиненной записи нужно, чтобы предыдущая запись содержала ссылку на последующую запись (по отношению к удаленной). Например, при удалении записи В2 (рис. 5.3,в) запись В1 должна ссылаться на запись В3. Имея ссылку на предыдущую запись, можно сразу выполнить шаг назад и изменить значение ссылки у записи В1, не проходя заново по всему списку.



Рис. 5.3. Реализация групповых отношений (а): б) замкнутый цепной список; в) двунаправленный цепной список

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

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

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

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

5.1 Способы доступа к записям

Рассмотрим основные способы доступа к данным.

· Последовательная обработка области БД. Областью БД может быть файл или другое множество страниц. Последовательная обработка предполагает, что система последовательно просматривает страницы, пропускает пустые участки и выдаёт записи в физической последовательности их хранения.

· Доступ по ключу базы данных (КБД). КБД определяет местоположение записи в памяти ЭВМ. Зная его, система может извлечь нужную запись за одно обращение к памяти.

· Доступ по структуре. Эта разновидность доступа применяется для групповых отношений и позволяет перейти к предыдущему или следующему экземпляру группового отношения, к экземпляру-владельцу группового отношения или к списку подчинённых экземпляров.

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

5.2 Индексирование данных

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

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

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

Обращение к записи через индексы осуществляется в два этапа: сначала в индексной структуре находится требуемое значение атрибута и соответствующий адрес записи, затем по этому адресу происходит обращение к внешнему запоминающему устройству (ВЗУ). Индекс загружается в ОП целиком (или хранится в ней постоянно во время работы с БД).

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

Различают одиночные индексы и составные. Составной индекс включает два или более столбца одной таблицы (рис. 6.2). Последовательность вхождения столбцов в индекс определяется при создании индекса.

Таблица

ID	DATA	SHIFR	FIRM	PRICE
100	01.12.95	А4	Комус	312.0
200	01.12.95	А4	Партия	321.5
100	02.12.95	А2	ОАО "Заря"	110.6
110	10.12.95	А4	Фирма "Б+"	314.0
200	01.12.95	А2	Партия	114.0
200	02.12.95	А1	Amos ltd.	52.8

Индекс

ID	DATA	SHIFR
100	01.12.95	А4
100	02.12.95	А2
110	10.12.95	А4
200	01.12.95	А2
200	01.12.95	А4
200	02.12.95	А1

Рис. 6.2. Пример составного индекса

5.2.1 Способы организации индексов

Существует множество способов организации индексов:

1. В плотных индексах для каждого значения ключа имеется отдельная статья индекса, указывающая место размещения конкретной записи. Неплотные индексы строятся в предположении, что на каждой странице памяти (или в блоке) хранятся записи, отсортированные по значениям ключа индексирования. Тогда для каждой страницы индекс задаёт диапазон значений ключей хранимых в ней записей, и поиск записи осуществляется среди записей на указанной странице.

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

3. Одноуровневый индекс представляет собой линейную совокупность значений одного или нескольких полей записи. На практике он используется только в простейших случаях, когда количество индексируемых записей невелико. В более сложных случаях индекс занимает много памяти (иногда - несколько страниц), и возникает задача минимизации доступа к нему. Тогда индекс разбивается на несколько иерархических уровней, что позволяет ускорить поиск требуемого значения. Особенно эффективной является организация многоуровневых индексов в виде сбалансированных деревьев (balance trees, B-деревьев), в которых все пути от корня к листьям имеют одинаковую длину.

5.2.2 Многоуровневые индексы на основе В-дерева

B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок - это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня. Каждое B-дерево должно удовлетворять следующим условиям:

1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо - к вершине с большими ключами.

2. Любая неконечная вершина имеет не менее n/2 подчинённых вершин.

3. Если неконечная вершина содержит k (k? n) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии.

4. Все конечные вершины расположены на одном уровне.

Алгоритм формирования B-дерева порядка n предполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании каждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент B-дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно - осуществляется перестройка дерева. Пример построения B-дерева порядка 3 приведён на рис. 6.3.

Рис. 6.3. Пример построения B-дерева порядка 3

Индексирование в виде B-дерева используется, например, в СУБД Oracle (рис. 6.4).

Рис. 6.4. Пример индексного блока СУБД Oracle

Организация индексов в СУБД Oracle несколько отличается от рассмотренной выше классической организации B-дерева, но принцип остаётся тот же: одинаковое количество уровней на любом пути и автоматическая сбалансированность. Верхние блоки содержат данные индекса, которые ссылаются на блоки индекса нижних уровней. Самый нижний n-й уровень содержит блоки индекса (блоки-листья), которые содержат непосредственно данные индекса (ключи) и соответствующие идентификаторы строк ROWID (row identification, КБД), используемые для нахождения самих строк. Блоки-листья связаны между собой указателями.

Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (по левому указателю), иначе - к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X₀ и конечное значения X_к ключа, а также три указателя. Если значение искомого ключа больше, чем X₀, то происходит обращение по левому указателю; если оно меньше, чем X_к, то происходит обращение по правому указателю; если оно попадает в диапазон X_0?X_к - по среднему указателю.

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

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

Индекс в виде B-дерева автоматически поддерживается в сбалансированном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического перемещения записей данных). Например, если при добавлении новой записи с ключом "Горин" возникает переполнение соответствующего блока индекса (рис. 6.4), система может перераспределить значения ключей так, как показано на рис. 6.5.

Если все блоки-листья индекса заполнены приблизительно на три четверти, то при добавлении новой записи осуществляется полная перестройка B-дерева путём введения дополнительного уровня. Всё это скрыто от пользователя и происходит автоматически.



Рис. 6.5. Пример перераспределения данных индексного блока СУБД Oracle

Структура B-дерева имеет следующие преимущества:

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

· B-дерево автоматически поддерживается в сбалансированном виде.

· B-деревья обеспечивают хорошую производительность для широкого спектра запросов, включая поиск по конкретному значению и в заданном интервале.

· Добавление, обновление и удаление строк выполняется достаточно эффективно.

· Производительность B-дерева одинаково хороша для маленьких и больших таблиц, и не меняется существенно при росте таблицы.

5.2.3 Использование индексов

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

Система может воспользоваться индексом по определённому полю, если в запросе на значение этого поля накладывается условие, например:

SELECT * FROM emp WHERE name = 'Даль';

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

Обращение к составному индексу возможно только в том случае, если в условиях выбора участвуют столбцы, представляющие собой лидирующую часть составного индекса. Например, если индекс строится по столбцам (X, Y, Z), то обращение к индексу будет происходить в тех случаях, когда в условии запроса участвуют столбцы XYZ, XY или X.

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

Выбор индексируемых столбцов определяется следующими соображениями:

· В первую очередь выбираются столбцы, которые часто встречаются в критериях поиска.

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

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

· Не индексируются столбцы, которые часто обновляются, т.к. команды обновления ведут к потере времени на обновление индекса.

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

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

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

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

Примечание: многие СУБД (в том числе, Oracle) автоматически строят индекс по первичному ключу и по уникальным столбцам.

5.3 Хеширование

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

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

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

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

5.3.1 Методы хеширования

Многочисленные эксперименты с реальными файлами выявили удовлетворительную работу двух основных типов хеш-функций. Один из них основан на делении, другой - на умножении. Все рассуждения ведутся в предположении, что хеш-функция h(K): 0? h(K)? N для всех ключей K, где N - размер памяти (количество ячеек).

Метод деления использует остаток от деления на М:

h(K)= К mod M.

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

М ?r^k ±a

где k и a - небольшие числа, а r - "основание системы счисления" для большинства используемых литер (как правило, 64, 256 или 100), т.к. остаток от деления на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетворительные результаты даёт М = 1009.

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

где w - размер машинного слова (обычно, 2³¹), А - целое число простое по отношению к w, а M - некоторая степень основания системы счисления ЭВМ (2^m). Таким образом, в качестве значения функции берутся m правых значащих цифр дробной части произведения значения ключа и числа A/w. Вычисление произведения обычно выполняется быстрее, чем деление. Число А выбирают так, чтобы значение Q каждого из его байтов лежало в "хорошем" диапазоне (6.1) и не было слишком близким к значениям других байтов или их дополнениям.

(6.1)

При использовании любых методов хеширования для размещения записей должен быть выделен участок памяти размером N. Для того чтобы полученное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так:

А(К) = h(K) mod N.

5.3.1 Разрешение коллизий

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

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

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

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

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

Примечание: существуют и более сложные стратегии рехеширования; но их рассмотрение выходит за рамки данного пособия.

5.3.2 Использование хеширования

Хеширование таблицы полезно в следующих случаях:

· Большинство запросов обращаются по значению уникального ключа, например:

SELECT … WHERE unique_key = …;

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

· Таблица практически статична (редко обновляется). Число строк и требуемое физическое пространство можно определить заранее и зафиксировать. Если впоследствии таблица вырастет и придётся отводить ей дополнительные блоки, это может сильно ухудшить производительность.

Хеширование не рекомендуется в следующих случаях:

· Большинство запросов выбирают строки в некотором интервале. Хеширование не даёт здесь преимуществ, т.к. строки не упорядочены (в отличие от индексирования).

· Таблица быстро меняется и постоянно растёт.

· Большинство запросов просматривают таблицу целиком.

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

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

5.4 Кластеризация данных

5.4.1 Принцип организации кластеров

Кластеризация является методом совместного хранения родственных данных (таблиц). Кластер - это структура памяти, в которой хранится набор таблиц (в одних и тех же блоках данных). Эти таблицы должны иметь общие столбцы, используемые для соединения (например, первичный ключ таблицы ТОВАРЫ и внешний ключ таблицы ПОСТАВКИ, рис. 6.6,б).

Рис. 6.6. Некластеризованные (а) и кластеризованные (б) данные

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

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

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

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

Два основных преимущества кластеров:

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

· Значение кластерного ключа хранится только один раз для кластера вне зависимости от того, сколько строк различных таблиц имеют это значение кластерного ключа, за счёт чего достигается экономия памяти.

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

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

Кластеры обычно строятся для таблиц, часто используемых в соединении друг с другом, например, связанных отношением "один-ко-многим". Не стоит создавать кластер:

· если данные в кластерном ключе этих таблиц часто обновляются;

· если часто требуется полный просмотр отдельной таблицы.

· если суммарные данные таблиц с одним и тем же значением кластерного ключа занимают больше одного блока данных.

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

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

Часто для окончательного определения целесообразности создания кластера в конкретной ситуации ставят эксперименты и измеряют производительность БД.

6. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ДОСТУПА К ДАННЫМ

Параллельный доступ к данным подразумевает одновременное выполнение двух и более запросов к одним и тем же объектам данных (таблицам, блокам и т.п.). Для организации одновременного доступа не обязательно наличие многопроцессорной системы. На однопроцессорной ЭВМ запросы выполняются не одновременно, а параллельно. Обычно для каждого запроса выделяется некоторое количество процессорного времени (квант времени), по истечении которого выполнение запроса приостанавливается, он ставится в очередь запросов, а на выполнение запускается следующий (по очереди) запрос. Таким образом, процессорное время делится между запросами, и создаётся иллюзия, что запросы выполняются одновременно.

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

6.1 Механизм транзакций

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

Транзакция обладает следующими свойствами:

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

Система гарантирует невозможность фиксации части изменений, произведённых транзакцией. До тех пор, пока транзакция не зафиксирована, её можно "откатить", т.е. отменить все сделанные операторами из транзакции изменения в БД. Успешное выполнение транзакции означает, что все операторы транзакции проанализированы, интерпретированы как правильные и безошибочно исполнены.

2. Согласованность: транзакция начинается на согласованном множестве данных и после её завершения множество данных также согласовано.

3. Изолированность, т.е. отсутствие влияния транзакций друг на друга. (На самом деле это влияние существует и регламентируется стандартом: см. раздел 7.2. "Взаимовлияние транзакций").

4. Продолжительность: результаты зафиксированной транзакции не могут быть потеряны. Возврат БД в предыдущее состояние может быть достигнут только путём запуска компенсирующей транзакции.

Для управлением транзакциями в системах, поддерживающих механизм транзакций и язык SQL, используются следующие операторы:

- фиксация транзакции: COMMIT [WORK];

- откат транзакции: ROLLBACK [WORK];

- точка сохранения: SAVEPOINT <имя_точки_сохранения>;

(Ключевое слово WORK необязательно). Предложение SAVEPOINT запоминает промежуточную "текущую копию" состояния базы данных для того, чтобы впоследствии, при необходимости, можно было вернуться к состоянию БД в точке сохранения: откатить работу от текущего момента до точки сохранения (rollback to <имя_точки>) или зафиксировать работу от начала транзакции до точки сохранения (commit to <имя_точки>).

Начало транзакции соответствует появлению первого исполняемого SQL-оператора. Транзакция завершается при наступлении одного из следующих событий:

· Поступила команда COMMIT или ROLLBACK (результаты транзакции соответственно зафиксируются или откатываются).

· Выдана и успешно проанализирована одна из команд языка описания данных (DDL, Data Definition Language), таких как CREATE, DROP или ALTER. При этом фиксируется предыдущая транзакция.

· Завершилась команда DDL. Таким образом, транзакция, содержащая оператор языка описания данных фиксируется автоматически.

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

· Процесс пользователя аварийно завершен (последняя транзакция автоматически откатывается).

Фиксация транзакции заключается в следующем:

1. Изменения, внесённые транзакцией, делаются постоянными.

2. Уничтожаются все точки сохранения для данной транзакции.

3. Завершается транзакция (уничтожаются системные записи о транзакции в оперативной памяти).

4. Если выполнение транзакций осуществляется с помощью блокировок, то освобождаются объекты, заблокированные транзакцией.

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

6.2 Взаимовлияние транзакций

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

Взаимовлияние транзакций может проявляться в виде:

· потери изменений;

· чернового чтения;

· неповторяемого чтения;

· фантомов.

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

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

транзакция 1 - UPDATE СОТРУДНИКИ SET Оклад = 9200

WHERE Номер = 1123

транзакция 2 - UPDATE СОТРУДНИКИ

SET Должность = "старший экономист", ЕТС = 14

WHERE Номер = 1123

Обе транзакции считали одну и ту же запись (1123, "Рудин В.П.", "экономист", 12, 8300) и внесли каждая свои изменения: в бухгалтерии изменили оклад (транзакция 1), в отделе кадров - должность и ставку по ЕТС (транзакция 2). Результаты транзакции 1 будут потеряны (рис. 7.1).

Рис. 7.1. Взаимовлияние транзакций: потеря изменений

СУБД не допускает такого взаимовлияния транзакций, при котором возможна потеря изменений.

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

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

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

6.3 Уровни изоляции транзакций

С целью обеспечения предсказуемости работы приложений для многопользовательских БД стандарт ANSI/ISO для SQL устанавливает различные уровни изоляции для операций, выполняемых над базами данных. Уровень изоляции определяет, может ли транзакция "видеть" результаты работы других одновременно выполняемых завершённых и/или незавершённых транзакций (табл. 7.1).

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

Таблица 7.1. Уровни изоляции по стандарту ANSI / ISO

Уровень изоляции	Черновое чтение	Неповторяемое чтение	Фантомы
Read Uncommited - чтение незавершённых транзакций	да	да	да
Read Commited - чтение завершённых транзакций	нет	да	да
Repeatable Read - повторяемое чтение	нет	нет	да
Serializable - последовательное чтение	нет	нет	нет

По умолчанию обычно используется уровень Read Commited.

Наиболее распространённый механизм разграничения транзакций - использование блокировок.

6.4 Блокировки

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

Различают следующие типы блокировок:

· по степени доступности данных: разделяемые и исключающие;

· по множеству блокируемых данных: строчные, страничные, табличные;

· по способу установки: автоматические и явные.

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

Разделяемая блокировка, установленная на определённый ресурс, предоставляет транзакциям право коллективного доступа к этому ресурсу. Обычно этот вид блокировок используется для того, чтобы запретить другим транзакциям производить необратимые изменения. Например, если на таблицу целиком наложена разделяемая блокировка, то ни одна транзакция не сможет удалить эту таблицу или изменить её структуру до тех пор, пока эта блокировка не будет снята. (При выполнении запросов на чтение обычно накладывается разделяемая блокировка на таблицу.)

Исключающая блокировка предоставляет право на монопольный доступ к ресурсу. Такие блокировки накладываются, обычно, на отдельные записи (блоки), которые подвергаются модификации в процессе выполнения транзакции. Но в том случае, если модификация затрагивает большую часть записей таблицы (более 1000 записей или более 20% от объёма таблицы), целесообразнее заблокировать всё отношение, а не тратить время на построчную блокировку таблицы, при которой увеличивается количество требуемых системных ресурсов и время выполнения. Кроме того, при большом количестве построчных блокировок транзакция может не завершиться (из-за истечения тайм-аута, например), и тогда все сделанные изменения придётся откатить, что снизит производительность системы.

Блокировка может быть автоматической и явной. Если запускается новая транзакция, СУБД сначала проверяет, не заблокирована ли другой транзакцией строка, требуемая этой транзакции: если нет, то строка автоматически блокируется и выполняется операция над данными; если строка заблокирована, транзакция ожидает снятия блокировки. Явная блокировка, накладываемая командой LOCK (SQL), обычно используется тогда, когда транзакция затрагивает существенную часть отношения.

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

Тупиковые ситуации (deadlocks) возникают при взаимных блокировках транзакций, выполняющихся на пересекающихся множествах данных. На рис. 7.2 приведён пример взаимной блокировки трех транзакций T_i на отношениях R_j.

Рис. 7.2. Взаимная блокировка трех транзакций

Транзакция T₁ заблокировала данные B₁ в отношении R₁ и ждёт освобождения данных B₂ в отношении R₂, которые заблокированы транзакцией T₂, ожидающей освобождения данных B₃ в отношении R₃, заблокированных транзакцией T₃, которая не может продолжить выполнение из-за транзакции T₁.

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

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

2. СУБД отслеживает возникающие тупики и отменяет одну из транзакций. Этот метод требует дополнительных накладных расходов.

3. Вводится таймаут (time-out) - максимальное время, в течение которого транзакция может находиться в состоянии ожидания. Если транзакция находится в состоянии ожидания дольше таймаута, считается, что она находится в состоянии тупика, и СУБД инициирует её откат с последующим рестартом через случайный промежуток времени.

7. СПЕЦИАЛЬНАЯ ОБРАБОТКА БАЗЫ ДАННЫХ

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

7.1 Обеспечение целостности данных

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

Рассмотрим различные типы ограничений целостности:

1. Уникальность значения первичного ключа (PRIMARY KEY).

2. Уникальность значения комбинации ключевых полей:

UNIQUE(A),

где A - атрибут или комбинация атрибутов.

(1,2 - структурные ограничения.)

3. Задание диапазона значений атрибута:

BETWEEN min_value AND max_value

4. Задание взаимоотношений между значениями атрибутов:

A @ B,

где @ - оператор отношения (например, знак ">").

5. Задание списка возможных значений:

IN (value1, value2,… valueN)

6. Определение формата атрибута (например, даты или числа).

7. Определение домена атрибута на основе значений другого атрибута: множество значений некоторого атрибута отношения является подмножеством значений другого атрибута этого или другого отношения.

3.-7. - ограничения на значения данных.

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

9. Ограничения на параллельное выполнение операций (механизм транзакций) и проверка ограничений целостности после окончания внесения взаимосвязанных изменений.

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

7.2 Обеспечение защиты данных

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

7.2.1 Безопасность данных (обеспечение физической защиты)

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

Наиболее типичными сбоями являются следующие:

1. Пользовательские ошибки.

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

2. Сбой предложения.

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

3. Сбой процесса.

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

4. Сбой экземпляра базы данных (сервера).

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

5. Сбой носителя (диска).

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

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

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

Резервное копирование означает периодическое сохранение на ВЗУ файлов БД в момент, когда их состояние является непротиворечивым. Резервная копия не должна создаваться на том же диске, на котором находится сама БД, т.к. при аварии диска базу невозможно будет восстановить. Периодичность резервного копирования определяется администратором системы и зависит от многих факторов: объём БД, интенсивность запросов к БД, интенсивность обновления данных и др. В случае сбоя (или аварии диска) БД восстанавливается на основе последней копии. Все изменения, произведённые в данных после последнего копирования, утрачиваются; но при наличии журнала транзакций их можно выполнить ещё раз, обеспечив полное восстановление БД.

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

Полная резервная копия включает всю базу данных (все файлы БД, в том числе, вспомогательные, состав которых зависит от СУБД). Частичная резервная копия включает часть БД, определённую пользователем. В резервную копию входят только те блоки памяти, которые реально содержат данные (т.е. пустые блоки, выделенные под объекты БД, в резервную копию не входят).

Резервное копирование может быть полным и инкрементным. Полная копия (level 0 backup) включает все блоки данных БД или табличной области. Инкрементная копия состоит только из тех блоков, которые изменились со времени последнего резервного копирования. Создание инкрементной копии происходит быстрее, чем полной, но возможно только после проведения полного резервного копирования.

Обычно технология проведения резервного копирования такова:

· раз в неделю (день, месяц) осуществляется полное копирование;

· раз в день (час, неделю) проводится обновление копии (инкрементное копирование).

Журнал транзакций - это служебный файл (или группа файлов), в котором хранятся записи обо всех завершённых транзакциях с привязкой по времени (системному или относительному). Рассмотрим структуру журнала транзакций на примере СУБД Oracle8 (рис.8.1).

Рис. 8.1. Структура журнала транзакций СУБД Oracle8

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

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

· Блоки, содержащие подтверждённые модификации, не были записаны в файлы данных, так что эти изменения отражены лишь в журнале транзакций. Следовательно, журнал транзакций содержит подтверждённые данные, которые должны быть переписаны в файлы данных.

· Журнал транзакций и блоки данных, возможно, содержат изменения, которые не были подтверждены. Изменения неподтверждённых транзакций во время восстановления должны быть удалены из файлов данных.

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

1. Прокрутка вперед.

Это первый этап восстановления. Он заключается в применении к файлам данных всех изменений, зарегистрированных в журнале транзакций. Прокрутка вперед обрабатывает столько файлов журнала транзакций, сколько необходимо, чтобы привести БД в состояние на требуемый момент времени. Если вся необходимая информация повторения находится в активном журнале транзакций, СУБД выполняет этот шаг восстановления автоматически при запуске базы данных. После прокрутки вперед файлы данных содержат все как подтверждённые, так и неподтверждённые изменения, которые были зарегистрированы в журнале транзакций.

2. Прокрутка назад.

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

7.2.2 Защита от несанкционированного доступа

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