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

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

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

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

f

gf

f – min-й запрос

g

f

g

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

- селекции

- проекции

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

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

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

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

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

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

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

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

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

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

строка в

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

 

Правила построения табло запросов:

1) Столбцы снабжены метками .

2) Каждая выделенная переменная может встретиться лишь в одном столбце.

3) Если в столбце стоит выделенная переменная, то она должна встречаться и в резюме этого запроса.

4) В строках должны стоять только символы (а не пробелы).

5) В резюме должны стоять только выделенные переменные, константы и пробелы.

6) Если в столбце с меткой стоит константа C, то эта константа принадлежит домену .

Резюме будем обозначать , а строки .

Пример:

 

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

1. ;

2. ;

3. строка , .

 

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

		…	…

– уже не является простым.

Простые ТЗ эффективно минимизируются и эквивалентность минимальных ТЗ легко проверить.

Теорема: Для простого ТЗ существует подтабло , которое является минимальным, эквивалентным ТЗ .