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

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

· средства поддержки набора данных и отношений между связанными данными;

· поддержка операций с данными;

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

· средства программирования высокого уровня, с помощью которых можно создавать свои собственные приложения – БД;

· набор средств администрирования, обеспечения секретности и безопасности информации.

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

· Добавление (вставка) данных;

· Удаление данных;

· Модификация (редактирование) данных.

Все эти операции зачастую заменяются одним термином – обновление данных. К операциям, изменяющим состояние базы данных, относятся:

1. Операции поиска и доступа к информации:

· Выборка (получение данных из БД и обеспечение пользователю доступности к выбранным данным);

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

· Сортировка;

· Фильтрация;

2. Операции поддержки функциональности;

3. Операции поддержки целостности и восстановления данных;

4. Операции контроля за доступом;

5. Операции поддержки обмена данными;

6. Администрирование.

А также сюда можно отнести так называемые низкоуровневые операции:

7. Управление данными во внешней памяти;

8. Управление буферами оперативной памяти;

9. Управление параллельностью и транзакциями;

10. Ведение журнала изменений в БД (имеется не во всех СУБД).

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

· язык описания данных (ЯОД) – это высокоуровневый непроцедурный язык декларативного типа, предназначенный для описания логической структуры данных. Он может дополнительно подразделяться на SDL – storage definition language и VDL – view definition language.

· язык манипулирования данными (ЯМД) – это совокупность инструкций, обеспечивающих выполнение основных операций по работе с данными: ввод, удаление, модификацию и выборку данных. Существует ЯМД высокого и низкого уровней. Первый используется для выборки набора данных, второй работает на уровне отдельных записей. Обычно такие языки указывают, какие данные необходимо извлечь, а не как они должны быть извлечены, и поэтому их называют декларативными.

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

 

Рис. 4.1 Структурная схема СУБД

 

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

Интерпретатор ЯОД обрабатывает инструкции определения/изменения структуры данных и сохраняет результаты в системном каталоге.

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

СУБД различаются по следующим признакам:

1. По типу поддерживаемой модели: реляционная, объектная, объектно-реляционная, иерархическая, сетевая, другие (многомерная, постреляционная).

2. По количеству поддерживаемых пользователей:

· однопользовательские,

· многопользовательские.

3. По количеству компьютеров, на которых располагается СУБД:

· централизованные (один компьютер),

· распределенные (distributed DBMS - DDBMS):

a) однородные

b) клиент-серверные

c) многоплатформенные (multi-tired)

4. По назначению:

· Специальные (обслуживание банков, продажи и резервирования билетов и т.д. Образуют категорию OLTP – on-line transaction processing systems),

· Общецелевые.

Индексация

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

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

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

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

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

Первичные индексы

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

Рис. 4.2 Структура первичного индекса

 

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

Вторичные индексы

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

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

Рис. 4.3. Структура вторичного индекса

Многоуровневые индексы

По способу своей организации индексы разделяются на одноуровневые и многоуровневые. Разбиение некоторого индекса на несколько уровней производится для дальнейшего увеличения скорости поиска записей при увеличении числа записей в индексируемой таблице. Число записей в самом индексе и, следовательно, размер индексного файла, может быть настолько большим, что операция открытия индекса и поиск в нем может занимать значительное время. Бинарный поиск требует приблизительно log₂b_i обращений к индексу, ссылающемуся на b_i блоков данных. Если разбить такой индекс на блоки записей одинаковой длины и включить в дополнительный уровень только значения первых записей полученных блоков и соответствующие указатели на эти блоки, то общее число обращений к индексу значительно сократиться. Количество обращений к индексу уже будет log_fs b_i, где fs это число записей в блоке индекса первого уровня. В такой схеме второй уровень будет являться первичным индексом для первого уровня, как представлено на рис. 4.4

Рис. 4.4. Структура многоуровневого индекса

Составные индексы

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

Ускорение поиска достигается опять возможностью применения быстрых алгоритмов поиска для всех полей составного индекса (вследствие их упорядоченности). В большинстве систем существует одно ограничение на использование составного индекса, а именно только последнее условие (т.е. сравнение с последним полем индекса) может быть неравенством. Например, Страна = ‘Беларусь’ And Город = ‘Минск’ And Предприятие <‘С’.

Хэширование данных

Хэширование – это метод прямого доступа к конкретной записи по значению её первичного ключа или некоторого поля.

Метод хэширования состоит в следующем:

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

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

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

Рассмотрим еще более простой пример использования подобной функции. Пусть имеются номера поставщиков S100, S200, S300, S400, S500 и для каждой записи поставщика отводится целая отдельная страница. Применяем следующую хэш-функцию:

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

В результате вычислений получали для наших пяти поставщиков соответствующие значения: 9, 5, 1, 10, 6. То есть записи поставщика с номером S100 назначается страниц с номером 9, а с номером S500 – страница с номером 6.

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

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

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

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

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

Этот метод требует соблюдения следующего условия: поле записи должно содержать уникальные значения, т. е. по сути быть первичным ключом. Заметим, что это не сильное требование.

Рассмотрим кратко расширяемый метод хэширования.

1. Пусть h(k) – хэш-функция от некоторого значения k, первичного ключа записи r. В результате использования этой функции мы получаем хэш-значение s=h(k), называемое псевдоключом записи r. Псевдоключи применяются для косвенного поиска адресов хранения, как описано ниже.

2. Файл имеет связанный с ним каталог, который также хранится на диске. Каталог включает 2 ^d указателей, где d – глубина (заголовок) каталога. Указатели указывают на страницы с записями, т. е. имеется 2 ^d страниц.

3. Ведущие d битов псевдоключа можно рассматривать как двоичное число σ, тогда указатель в каталоге (1 ≤ i ≤ 2 ^d) указывает на страницу, содержащую все записи с σ = i – 1. Чтобы найти запись с первичным ключом k, необходимо хэшировать k для определения псевдоключа s и взять первые d битов этого псевдоключа; если первые биты этого псевдоключа имеют значение i-1, осуществляется переход к i -му указателю в каталоге (первое обращение к диску) и далее переход по этому указателю к странице с требуемой записью (второе обращение к диску). Каталог обычно делают небольшим для того, чтобы он хранился в оперативной памяти. Поэтому требуется лишь одно обращение к диску для получения записи.

4. Каждая страница с данными также имеет заголовок с указанием локальной глубины p этой страницы (p≤d). Предположим d=3 и первый указатель в каталоге (000) указывает на страницу с глубиной p=2. Локальная глубина 2 означает, что эта страница содержит все записи с псевдоключами, начинающиеся с 00 (а именно, с 000 и с 001).

5. Предположим, что на страница с данными 000 заполнена нужно вставить новую запись, псевдоключ который начинается с 000 (или 001). В этом случае указанная страница разделяется на две: из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется так, чтобы он указывал на новую страницу (указатель 000 указывает на струю страницу). Теперь локальная глубина для этих двух страниц будет равна 3, а не 2.

6. Теперь допустим, что страница с начальной строкой битов 000 снова заполнена и должна быть опять разделена. Существующий каталог не позволяет такого разделения, так как p=d=3. Поэтому размера каталога удваивается, т. е. значение d увеличивается на единицу и каждый указатель заменяется парой смежных указателей. Теперь страница разделяется на две: записи 0000 остаются на строй странице, а записи 0001 перемещаются на новую страницу (первый указатель в каталоге остается неизменным и указывает на струю страницу, а второй указатель корректируется таким образом, чтобы он указывал на новую страницу). Операция удваивания размера каталога не требует больших затрат времени.

 

Упражнения

1. Дайте определение СУБД.

2. Перечислите основные операции CУБД.

3. Перечислите три основные операции СУБД, отвечающие за поиск данных.

4. Зарисуйте структурную схему СУБД и поясните назначение каждого блока.

5. Дайте классификацию СУБД.

6. Перечислите признаки, по которым можно различать СУБД.

7. Сформулируйте назначение индексов в БД.

8. Представьте схематично структуру первичного индекса.

9. Представьте схематично структуру вторичного индекса.

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

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

12. Чем отличается составной индекс от простого.

 

ГЛАВА 5. ЯЗЫК ЗАПРОСОВ SQL

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

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

Операторы языка SQL можно условно разделить на два подъязыка: язык определения данных и язык манипулирования данными. Основные операторы языка SQL представлены в таблице:

Операторы языка SQL

Вид	Название	Назначение
ЯОД	CREATE TABLE	создание таблицы
DROP TABLE	удаление таблицы
ALTER TABLE	изменение структуры таблицы
CREATE INDEX	создание индекса
DROP INDEX	удаление индекса
CREATE VIEW	создание представления
DROP VIEW	удаление представления
CREATE DOMAIN	создание домена
ALTER DOMAIN	изменение домена
DROP DOMAIN	удаление домена
GRAND	назначение привилегий
REVOKE	удаление привилегий
ЯМД	SELECT	выборка записей
UPDATE	изменение записей
INSERT	вставка новых записей
DELETE	удаление записей
TRANSFORM	создание перекрестного запроса
UNION	создание запроса на объединение

 

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

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