Стадія 2. Виконання операцій UNION, EXCEPT, INTERSECT

Якщо в операторі SELECT були присутні ключові слова UNION, EXCEPT і INTERSECT, то таблиці, одержані в результаті виконання 1-й стадії, об'єднуються, віднімаються або перетинаються.

Стадія 3. Впорядкування результату

Якщо в операторі SELECT присутній розділ ORDER, то рядки одержаної на попередніх кроках таблиці упорядковуються відповідно до списку впорядкування, приведеному в розділі ORDER.

Як насправді виконується оператор SELECT

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

Насправді в РСУБД є оптимізатор, функцією якого є знаходження такого оптимального алгоритму виконання запиту, який гарантує отримання правильного результату.

Схемно роботу оптимізатора можна представити у вигляді послідовності декількох кроків:

Крок 1 (Синтаксичний аналіз). Запит, що поступив, піддається синтаксичному аналізу. На цьому кроці визначається, чи правильно взагалі (з погляду синтаксису SQL) сформульований запит. В ході синтаксичного аналізу виробляється деяке внутрішньо представлення запиту, що використовується на подальших кроках.

Крок 2 (Перетворення в канонічну форму). Запит у внутрішньому уявленні піддається перетворенню в деяку канонічну форму. При перетворенні до канонічної форми використовуються як синтаксичні, так і семантичні перетворення. Синтаксичні перетворення (наприклад, приведення логічних виразів до кон’юнктивної або диз'юнктивної нормальної форми, заміна виразів "x AND NOT x" на "FALSE", і т.п.) дозволяють одержати нове внутрішньо представлення запиту, синтаксично еквівалентне початковому, але стандартне в деякому розумінні. Семантичні перетворення використовують додаткові знання, якими володіє система, наприклад, обмеження цілісності. В результаті семантичних перетворень виходить запит, синтаксично не еквівалентний початковому, але даючий той же самий результат.

Крок 3 (Генерація планів виконання запиту і вибір оптимального плану). На цьому кроці оптимізатор генерує безліч можливих планів виконання запиту. Кожний план будується як комбінація низькорівневих процедур доступу до даних з таблиць, методів з'єднання таблиць. Зі всіх планів, що згенерували, вибирається план, що володіє мінімальною вартістю. При цьому аналізуються дані про наявність індексів біля таблиць, статистичних даних про розподіл значень в таблицях, і т.п. Вартість плану це, як правило, сума вартостей виконання окремих низькорівневих процедур, які використовуються для його виконання. У вартість виконання окремої процедури можуть входити оцінки кількості звернень до дисків, ступінь завантаженості процесора і інші параметри.

Крок 4. (Виконання плану запиту). На цьому кроці план, вибраний на попередньому кроці, передається на реальне виконання.

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

Реалізація реляційної алгебри засобами оператора SELECT (Реляційна повнота SQL)

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

Оператор декартового добутку

Реляційна алгебра:

Оператор SQL:

SELECT A.Поле1, A.Поле2 ., B.Поле1, B.Поле2 .

FROM А, B;

або

SELECT A.Поле1, A.Поле2 ., B.Поле1, B.Поле2 .

FROM А CROSS JOIN B;

Оператор проекції

Реляційна алгебра:

Оператор SQL:

SELECT DISTINCT X, Y, _, Z

FROM А;

Оператор вибірки

Реляційна алгебра: ,

Оператор SQL:

SELECT *

FROM А

WHERE з;

Оператор об'єднання

Реляційна алгебра:

Оператор SQL:

SELECT *

FROM А

UNION

SELECT *

FROM B;

Оператор віднімання

Реляційна алгебра:

Оператор SQL:

SELECT *

FROM А

EXCEPT

SELECT *

FROM B

Реляційний оператор перейменування RENAME виражається за допомогою ключового слова AS в списку відбираних полів оператора SELECT. Таким чином, мова SQL є реляційно повною.

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

Оператор з'єднання

Реляційна алгебра:

Оператор SQL:

SELECT A.Поле1, A.Поле2 ., B.Поле1, B.Поле2 .

FROM А, B

WHERE c;

або

SELECT A.Поле1, A.Поле2 ., B.Поле1, B.Поле2 .

FROM А CROSS JOIN B

WHERE c;

Оператор перетину

Реляційна алгебра:

Оператор SQL:

SELECT *

FROM А

INTERSECT

SELECT *

FROM B;

Оператор поділу

Реляційна алгебра:

Оператор SQL:

SELECT DISTINCT A.X

FROM А

WHERE NOT EXIST

(SELECT *

FROM B

WHERE NOT EXIST

(SELECT *

FROM А A1

WHERE

A1.X = A.X AND

A1.Y = B.Y));

Зауваження. Оператор SQL, що реалізовує розподіл відносин важко запам'ятати, тому дамо приклад еквівалентного перетворення виразів, що представляють суть запиту.

Хай відношення А містить дані про поставки деталей, відношення B містить список всіх деталей, які можуть поставлятися. Атрибут X є номером постачальника, атрибут Біля є номером деталі.

Розділити відношення А на відношення B означає в даному прикладі "відібрати номери постачальників, які поставляють всі деталі".

Перетворюваний текст виразу:

"Відібрати номери постачальників, які поставляють всі деталі" еквівалентно

"Відібрати ті номери постачальників з таблиці А, для яких не існує деталей, що не поставляються, в таблиці B" еквівалентно

"Відібрати ті номери постачальників з таблиці А, для яких не існує тих номерів деталей з таблиці B, які не поставляються цим постачальником" еквівалентно

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

Останній вираз дослівно перекладається на мову SQL. При