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

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

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

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

1. Кожна селекція у F₁\&...&F_n(E) згідно з властивістю 4 подається у вигляді послі­довності селекцій у_F1 (...(у_Fп(Е)...)).

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

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

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

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

 

Тема 3.3. Нормалізація відносин

Завдяки теорії нормалізації схем відношень у реляційній моделі даних встанов­люється, в який спосіб схема реляційних відношень може бути перетворена на ін­шу схему, що еквівалентна в певному розумінні початковій і в певному розумінні є кращою за неї. В межах цієї теорії формулюються критерії еквівалентності й оцінювання якості схем реляційних відношень, а також описуються механізми еквівалентних перетворень названих схем, які надають можливість підвищити їхню якість.

У цьому розділі наводяться базові означення й розглядаються властивості функціональної та багатозначної залежностей, означуються нормальні форми ре­ляційних відношень і формулюється основне завдання проектування схем реля­ційної моделі даних.

Функціональні залежності

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

Основні поняття

Нехай задано відношення R, яке містить набори атрибутів А і В. У відношенні R набір атрибутів В функціонально залежить від А і А функціонально визначає В тоді й лише тоді, коли кожному значенню проекції R[A] у будь-який момент часу відповідає точно одне значення проекції R[B].

Означена вище функціональна залежність позначається як R.A -> R.B. Якщо належність А і В відношенню R відома апріорі, то пишеться А -> В. Формально функціональна залежність означується так:

Поняття функціональної залежності може бути звужене на той випадок, коли А і В є окремими атрибутами.

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

Набір К атрибутів відношення R називається можливим ключем, або квазіключем відношення R, якщо:

а) кожний атрибут відношення R функціонально залежить від К;

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

У формульному вигляді це означення записується так. Нехай М — повний на­бір атрибутів відношення R. Підмножина атрибутів К відношення R є можливим ключем, якщо:

Символ -** вказує на те, що функціональна залежність відсутня.

У будь-якому відношенні існує принаймні один можливий ключ, оскільки на­бір усіх атрибутів відношення задовольняє властивість (а), а потім цей набір можна «стиснути» так (відкидаючи надлишкові атрибути), щоб він задовольняв властивість (б).

Оскільки у відношенні може існувати більше одного ключа, то один із них на­зивається первинним. Будь-який із можливих ключів може бути первинним.

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