Алгоритм оптимизации выражений РА.

Исходные данные – дерево разбора, представляющее выражения РА. Выходные – тоже дерево, но оптимизированное (программа, для вычисления выражения).

Метод:

1. Каждую селекцию представляем в виде каскада по правилу 4): ;

2. Перемещаем каждую селекцию насколько это возможно вниз по дереву, используя правила 5)-8);

3. Перемещаем каждую проекцию в дереве вниз настолько, насколько это возможно, используя правило 3), которое приводит к исчезновению некоторых проекций, следствие из 5), которое расщепляет на несколько, и правила 9) и 10);

4. Комбинируем каждый каскад селекций и проекций в одиночную селекцию, одиночную проекцию, или селекцию с последующей проекцией, используя правила 3) – 5);

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

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

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

Шаги алгоритмов могут быть:

1. выполнение одиночной селекции или проекции;

2. выполнение декартового произведения, объединения, либо разности множеств, которые, возможно, предшествуют или за которыми следуют селекция или проекция, применяемая к одному или обоим операндам.

Пример:

Рассмотрим БД «библиотека», состоящую из отношений:

Книги (название; автор; издательство; инв. №)

Издатель (издательство; город; адрес)

Читатели (ФИО; город; адрес; № читательского билета)

Выдача (инв. №; № читательского билета; дата)

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

(1)

F=(R₃.№_читательского_билета=R₄.№_читательского_билета) Ù (R₁.инвентарный_№=R₄.инвентарный_№)=F₁ÙF₂

X= название; автор; издательство; инв. №; ФИО читателя; город; адрес; № читательского билета; дата.

Опишем запрос: перечислить книги, которые были выданы до 01.01.2000.

После подстановки S в (1) получаем следующее дерево разбора:

1-й шаг: расщепление селекции на две: .

2-й шаг: перемещаем каждую из 3-х селекций как можно ниже в дереве. Селекцию перемещаем ниже проекции и двух селекций по правилам 4) и 5).

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

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

3-й шаг: можно скомбинировать две проекции в одну по правилу 3):

4-й шаг: по обобщенному правилу 5) делаем замену:

5-й шаг: применим правило 9) с целью замены последней проекции на , применим к и , применим к левому операнду декартова произведения более высокого уровня (см. последний рисунок).

Последняя проекция взаимодействует с помещенной ниже селекцией по обобщенному правилу 5). В результате получаем каскад:

6-й шаг: последнюю проекцию можно записать в виде (она просеивается через декартово произведение по правилу 9) и частично через селекцию по правилу 5)):

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

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

- - - – группы операторов.

 

 

 

 

|

´

 

|

´