Использование БД

Запросы, как показано ранее, могут быть описаны на языках реляционной алгебры и реляционного исчисления.

С помощью реляционной алгебры может быть построено дерево запроса. Более того, запрос может быть оптимизирован |4, 9, 12, 13]. Оптимизация может выполняться с учетом следующих правил.

1. Выполнение селекции как можно раньше.

2. Сортировка файлов или создание индексов путем соединения декартова произведения с последующей селекцией.

3. Предварительное вычисление общих выражений.

4. Выполнение селекции и проекции за один просмотр.

5. Комбинирование проекции с предшествующими или последующими операциями.

6. Объединение селекции с предшествующим декартовым произведением.

Алгоритмически это может быть представлено в таком виде.

Шаг 1. Селекцию (Е) представить как каскад селекций – закон 1.4 (см. § 4.1).

Шаг 2. Переместить любую селекцию в дереве как можно ниже – законы 1.4, IV.1, IV.3, IV.5.

Шаг 3. Переместить любую проекцию в низ дерева – законы 1.2, 1V.5, IV.6.

Шаг 4. Скомбинировать любой каскад селекций (проекций) в одиночную селекцию (проекцию) – законы 1.1, 1.2, 1.5, – или селекцию с последующей проекцией.

Шаг 5. Разбить внутренние узлы дерева на группы: объединить двухместные операции с предшествующими или последующими узлу унарными операциями S и Р.

Шаг 6. Перейти к более высокому уровню иерархии.

Пример оптимизации. Пусть дана [4] база данных "Библиотека":

КН[ИГИ](Название[_книги], Автор, Название-издательства, N_бк),

ИЗД[АТЕЛИ](Название_издательства, Место, Адрес_издательства),

ЧИТ[АТЕЛИ](Фамилия, Адрес, Город, N_форм[уляра]),

ВЫД[АЧИ](М_форм[уляра], Ν_бк, Дата),

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

Запрос: найти, у кого находятся книги, выданные до 01.01.1997. Ему соответствует на языке АЛЬФА запрос (рис. 4.8, а)

где F = ЧИТ.Ν_форм = ВЫД.N_форм Ç ΚΗ.Ν_бк = ВЫД.N_бк, S = Название_книги, Автор, Название издательства, Ν_бк, Фамилия, Адрес, Город, Ν_форм, Дата).

На рис. 4.8, а разделяют две селекции и перемещают как можно ниже в дереве. Селекция

(4.2)

ниже проекции и двух селекций по законам 1.1, 1.5.

Селекция (4.2) применяется к произведению (ВЫД × ЧИТ) × КН. Дата – единственный атрибут отношения ВЫД, потому

на

и

Селекцию можно переместить вниз по дереву. Селекция с условием ΚΗ.Ν_бк = ВЫД.N_бк не может быть перемещена ниже любого декартова произведения, поскольку имеет атрибуты как отношения КН, так и других отношений.

может быть перемещена ниже и применена к произведению

ВЫД.N_форм есть имя атрибута отношения, полученного в σДАТА≤1.1.1997(ВЫД), ибо это атрибут отношения ВЫД.

Рис. 4.8. Дерево запроса

По заколу 1.2 две проекции комбинируются в одну pНАЗВАНИЕ и результат отражается на рис. 4.8, б.

По закону 1.4 pНАЗВЛНИЕ и σкн.Ν_бк=выд.N_бк заменим на каскад

(4.3)

По закону IV.6 выражение (4.3) заменяется на pНАЗВАНИЕ, кн.Ν_бк, примененного к отношению КН и

(4.4)

примененного к левому оператору декартова произведения более высокого уровня (рис. 4.8, 6).

Последняя проекция (4.4) взаимодействует с нижней селекцией по закону 1.4 и получается каскад:

(4.5)

Проекция (4.5) "просеивается" через декартово произведение по закону IV.6 и частично – через σДАТА≤1.1.1997(ВЫД) по закону 1.4. Кроме того, проекция π выд.Ν_бк,выд.Ν_форм.дата – излишняя (это все атрибуты ВЫД) и исключается. Тогда окончательный результат принимает вид, приведенный на рис. 4.9, на котором группы операторов обведены пунктирными линиями. Любое из декартовых произведений является фактически эквисоединением, если его скомбинировать с селекцией, находящейся в дереве выше. Иными словами, селекция для ВЫД и проекция для ЧИТ могут быть скомбинированы в группы I и II, при этом сначала выполняются операции группы I, а затем – группы II.

Рис. 4.9. Преобразованное дерево запроса

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

Процедура оптимизации выполнения запроса реализована в ряде СУБД. Так, в СУБД Access [29] она выполняется через последовательное обращение к элементам меню СервисАнализБыстродействие. Далее необходимо ввести индексы для всех полей составного первичного ключа, указать все поля с критериями выбора или сортировки, связей между таблицами.