Еквівалентні вирази і оптимізація запитів.

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

Перейменування атрибутів.

Як ми бачили, у процесі конструювання запитів дуже часто виникає потреба у явному задані імен відношень і їх атрибутів. Для перейменування відношення R використовується оператор ρS(A1, A2,…An)(R). Оператор переіменовуе відношення R у відношення S, а його атрибути отримують імена A1, A2,….,An у порядку зліва направо. Якщо треба змінити тільки назву відношення, застосовується скорочений запис оператора ρS(R).

Приклад 5.5.

Розрахувати декартовий добуток відношень R і S (рис.5.10) з попереднім перейменуванням атрибута В відношення S на ім’я Х.

Результат виконання операції перейменування ρS(X,C,D)(S) – це відношення, назване S,. яке виглядає майже як відношення S на рис.5.6, за виключенням того, що його перший атрибут позначен як Х замість В.

 

А	В		Х	С	В

Відношення R Відношення S після операції перейменування атрибута В

 

A	B	Х	C	D

 

Відношення R×ρ_S(X,C,D)(S)

 

Рис. 5.10. Розрахунок декартового добутку відношень R і S з попереднім перейменуванням атрибута В відношення S на ім’я Х.

 

Залежні і незалежні операції.

Шість операцій – об’єднання, різниці, вибору, проекції, декартового добутку і перейменування – являються незалежними, і кожну із них неможна виразити у термінах решти операцій. До залежних відносяться операції пересічення, натурального з’єднання, тета - з’єднання. Вони можуть бути виражені у термінах других операцій реляційної алгебри. Так операція пересічення може бути замінена двома операціями різниці

 

R∩S = R – (R – S)

 

Операцію тета - з’єднання можна представити у вигляді сполучення операцій декартового добутку і вибору.

 

R S = σ_С(R´S)

^С

 

Операцію натурального з’єднання відношень R і S можна почати із розрахунку їх декартового добутку, R´S, а потім застосувати до останнього оператор вибору за умовою С виду

 

R.A₁ = S.A₁ AND R.A₂ = S.A₂ AND ××××AND R.A_n = S.A_n,

 

де A1, A2, ××××An – це атрибути, що одночасно присутні у схемах R і S. На завершення треба виконати операцію проекції, щоб обрати по одній копії із кожної пари співпадаючих атрибутів. Нехай L представляє собою список атрибутів схеми R, за якими слідують атрибути S, які відсутні в R. Тоді повний вираз буде мати вигляд:

 

R S = π_L(σ_C(R ´ S))

 

Алгебраїчні вирази у лінійному представленні.

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

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

2. оператора присвоювання:=;

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

Приклад 5.6.

Представити дерево часткових виразів на рис.5.9 у вигляді послідовності виразів присвоювання. Один із варіантів послідовності виразів присвоювання такий:

 

R(t, y, l, i, s, p):= σ _length≧100 (Movie);

S(t, y, l, i, s, p):= σ _{studioName = “Fox”} (Movie);

T(t, y, l, i, s, p):= R ∩ S;

Answer (title, year):=π_{t, y}(T)

 

Першим кроком є отримання відношення, що відповідає проміжній вершині дерева, позначеної як σ _length>=100. Слід звернути увагу, що у лівій частині оператора присвоювання приводиться надане ім’я проміжного відношення і надані імена його атрибутів. Дозволяється надавати любі імена. Ліві частини інших проміжних вершин створені аналогічно.