Відкрити головне меню

Семантична оптимізація запитів СУБД - процес валідації та перетворення синтаксичного дерева запиту в форму, яка придатна для подальших кроків оптимізації.

На цій стадії виконується:

  1. Перетворення запитів у канонічну форму;
    1. Розкриття уявлень;
    2. Перетворення підзапитів у сполуки;
    3. Спуск предикатів;
  2. Спрощення умов і розподіл предикатів;
  3. Перетворення дерева умов до шляхів вибірки. 

Перетворення запитів до канонічної формиРедагувати

Запити зводяться до канонічної форми, тобто переписуються так, щоб вони містили мінімальну кількість операторів SELECT (з'єднання-фільтрація-проекція). Скрізь, де можливо, запит повинен бути зведений до форми єдиного оператора SELECT. Це може дозволити наступним фазам оптимізації згенерувати значно ефективніший (на 2-3 порядки) план виконання для складних запитів.

Розкриття уявленьРедагувати

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

Початковий запит Результат
( T where cond1 ) where cond2 T where ( cond1 and cond2)

Перетворення підзапитів у сполукиРедагувати

Перетворення підзапитів у сполуки є необхідним для застосування конвеєрної обробки даних та мінімізації обсягу результатів підзапитів, акумульованих у тимчасовій дисковій чи оперативній пам'яті.

Початковий запит Результат
select distinct T.a from T

where T.b in ( select T1.b from T1 where T1.c < T.c)

select distinct T.a

from T,T1 where T.b = T1.b and T1.c < T.c

Спуск предикатівРедагувати

Початковий запит Результат
( A join B) where condA and condB (A where condA) join (B where condB)

Спрощення умов та розподіл предикатівРедагувати

Спрощення умовРедагувати

Виконується шляхом перетворення дерева логічних операцій у КНФ та спрощення отриманої логічної функції.

Перетворення дерева логічних операцій у КНФ виконується наступним чином:

  1. 1. Для всіх диз'юнкцій, які входять у прямому вигляді, застосовується розподільний закон:
P OR (Q AND R) = (P OR Q) AND (P OR R)
(P AND Q) OR R = (P OR R) AND (Q OR R)
  1. Для всіх диз'юнкцій, що входять у інверсному вигляді, застосовується правило де Моргана
NOT (P OR Q) = NOT P AND NOT Q

Перетворення триває рекурсивно до тих пір, поки дерево не буде складатися із кон'юнкцій конституент 0.

Отримана логічна функція знаходиться у кон’юнктивній нормальній формі, проте вона надлишкова. Для спрощення застосовують методи оптимізації логічних функцій, такі як Еспрессо (Логіка) або Куайна-Мак-Класкі.

Розподіл предикатівРедагувати

Розподіл предикатів виконується

  • Для всіх предикатів виду:

A.B pred C

Для яких існує предикат

A.B = D.E

Як результат - отримаємо предикат

D.B pred C

де C - константа; A, D - відношення; B, E - порівнювані атрибути. Це спрощення виконується на основі припущення, що початковий предикат A.B pred C може бути ефективнішим для відношення D.

  • Для кожної умови об'єднання виду:

A.B pred D.E

генерується обернена умова

D.E inversed pred A.B

для можливості виконати з'єднання в оберненому порядку.

Перетворення дерева умов у шляху вибіркиРедагувати

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

ЛітератураРедагувати

  • Дейт К. Дж. Введение в системы баз данных. 2001. Из-во: Вильямс. ISBN 5-8459-0138-3
  • Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. Из-во: Вильямс (М., 2003) ISBN 5-8459-0527-3
  • Кимельман Михаил Леонидович. Исследование и разработка языковой подсистемы SQL сервера. Диссертация на соискание ученой степени кандидата физико-математических наук. Москва 1996

Див. такожРедагувати