Точная оптимизация для подмножества реляционных запросов.

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

Конъюнктивным называется запрос, который может быть выражен в РИ с переменными на доменах следующим образом:

где переменные на доменах или константа;

переменные на доменах;

константы;

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

Тот факт, что есть конъюнкция термов, дает название запросу.

Пример: найти читателей, которые берут книги, опубликованные в городе, где они живут:

Ранее ввели понятие эквивалентных выражений. Аналогично можно говорить об эквивалентных запросах, т.к. любое выражение описывает запрос: ( Два запроса и эквивалентны т. и т.т., когда ).

Можно также ввести понятия:

Запрос содержится в : если для каждого отношения имеем .

Конъюнктивные запросы можно проверить на эквивалентность, проверив: .

Проверка справедливости отношения «содержится» для конъюнктивных запросов и основывается на существовании определенного вида отображений символов, используемых в , в символы, используемые в .

Пусть

Свёрткой в называется отображение символов в символы , такое, что:

1. ;

2. константы неизменны, и, следовательно, должна быть при некотором ;

3. является каким-либо из ;

4. Если – какой-либо терм , то некоторый терм , где , примененное к кортежу , определяется равенством .

Пример:

Теорема: Запрос , если и только если найдется некоторая свертка в Два запроса эквивалентны , если и только если найдется свертка в и в

Минимизация конъюнктивных запросов.

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

Свёртка как отображение термов.

Термы запроса Термы запроса

f

g f

f – min-й запрос

g

f

g

Композиция двух свёрток также является свёрткой.

Теорема: Для каждого конъюнктивного запроса найдется эквивалентный ему конъюнктивный запрос с наименьшим возможным числом термов.

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

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

Пример: . После удаления получаем min эквивалент :

Проверка того, что этот запрос минимален, трудная (NP-полная) задача, т.к. любое выражение РА, включающее , может быть представлено в виде конъюнктивного запроса, то рассмотренный класс содержит многие из наиболее часто встречающихся запросов, в частности, главную конструкцию РА «селекция – проекция – соединение».

Эта задача может быть решена при небольшом числе атомов.

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

• БД с распределенной обработкой. Файлы БД находятся на сервере, а программы обработки на рабочих станциях.

• Распределенные БД, если файлы БД произвольно распределены на компьютерном NBC.

Задача оптимизации запросов является NP-полной, она разрешима для подкласса табло запросов, состоящих из простых табло запросов.

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

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

Назовём ограниченным алгебраическим выражением алгебраическое выражение, построенное из отношений с использованием операций:

• селекции

• проекции

• естественного соединения.

Табло похоже на отношения, но вместо значений атрибутов содержит переменные из некоторого множества . Оно является объединением двух множеств и , где – множество выделенных переменных (состоит из букв с индексами); – множество невыделенных переменных, обозначенных буквами с индексами.

Табло записывается в виде таблицы:

Множество атрибутов, именующих столбцы табло, образуют схему табло. Кортежами отношения являются строки табло.

Ограничения:

1. каждая переменная в табло принадлежит только одному столбцу;

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

Если имеем ( – можно поставить в соответствие).

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

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

строка в

В табло запросов, так же как и в табло переменные делятся на выделенные и невыделенные, кроме них в ТЗ встречаются константы и пробелы. Выделенные переменные, невыделенные, константы будем называть собирательно символом. Табло запросов содержит также резюме – выделенную строку. Резюме запроса записывается над строками ТЗ и будет выделяться линиями сверху и снизу.