Интернет магазин китайских планшетных компьютеров

Компьютеры - Семантическая оптимизация запросов СУБД - Упрощение условий и распределение предикатов

Упрощение условий

Выполняется путем преобразования дерева логических операций в КНФ и упрощения полученной логической функции.

Преобразования дерева логических операций в КНФ выполняется следующим образом:

1. Для всех дизъюнкций, входящих в прямом виде, примененяется распределительный закон:

P OR = AND
 OR R = AND

1. Для всех дизъюнкций, входящих в инверсном виде, примененяется правило де Моргана:

NOT = NOT P AND NOT Q

Преобразование продолжается рекурсивно до тех пор, пока дерево не будет состоять из конъюнкций конституэнт 0.

Полученная логическая функция находится в конъюнктивной нормальной форме, но избыточна. Для упрощения применяют методы оптимизации логических функций, такие как Эспрессо или Куайна-Мак-Класки.

Распределение предикатов

Распределение предикатов выполняется

1. для всех предикатов вида:

A.B pred C

для которых существует предикат

A.B = D.E

В результате получаем предикат

D.B pred C

где C — константа; A,D — отношения; B,E — сравниваемые атрибуты. Данное упрощение выполняется на основе предположения, что исходный предикат A.B pred C может быть эффективней для отношения D.

1. для каждого условия объединения вида:

A.B pred D.E

генерируется обратное условие

D.E inversed pred A.B

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

Преобразование дерева условий в пути выборки

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