Оптимізація обчислення виразів реляційної алгебри

Date: 2015-10-07; view: 635.

Описані вище властивості операцій реляційної алгебри дають змогу вирішувати завдання логічної оптимізації алгебраїчних виразів. Піл терміном логічна оптимі-зація ми маємо на увазі оптимізацію, що дає можливість прискорити обчислення реляційних виразів незалежно від способів реалізації реляційних відношень. На відміну від алгебри числових виразів, складність виконання формул реляційної алгебри залежить не лише від кількості операцій, але й від розміру операндів. Розглянемо приклад оптимізаційних перетворень реляційного виразу. Нехай задано вираз:

.

Можливі шляхи послідовних еквівалентних перетворень, що оптимізують об­числення цього виразу, наведені на рис. 3.4. Оптимізаційні перетворення здій­снюються згідно з властивостями, описаними в підрозділі 3.2.3.

Наведемо тепер основні правила оптимізації виразів реляційної алгебри.

1. Кожна селекція згідно з властивістю 4 подається у вигляді послі­-
довності селекцій .

2. Кожна селекція переміщується деревом виразу вниз наскільки це можливо
(властивості 3е, 5, 7, 8). У такий спосіб зменшується кардинальність відношень.

3. Розташовані поруч селекції і декартові добутки замінюються з'єднаннями, як­
що це допускається властивістю 6.

4. Кожна проекція переміщується деревом виразу вниз наскільки це можливо
(властивості 2, 3). У такий спосіб зменшується степінь відношень.

5. Кожен каскад селекцій і проекцій перетворюється на одиничну селекцію, оди­
ничну проекцію чи селекцію з наступною проекцією (властивості 2, Зе, 4). Пе­
ретворення може суперечити евристиці «роби проекцію якомога раніше», од­
нак ефективніше виконати всі можливі операції селекції і проекції за один
перегляд відношення, ніж здійснювати кілька переглядів.

R(A, В) S(C, D) R(A, В) 5(С, D) R(A, В)

б

Рис. 3.4.Приклад еквівалентних перетворень, що оптимізують вирази реляційної алгебри:

а — вихідний вираз обчислюється так, як він записаний; б — селекція поділяється на каскад

селекцій відповідно до властивості 4; β — одна з отриманих селекцій опускається нижче

декартового добутку відповідно до властивості 5а; г — декартів добуток і селекція

замінюються на з'єднання згідно з властивістю 6.