3.5 Базисні засоби маніпулювання реляційними даними

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

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

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

Відомо (і ми не будемо це доводити), що механізми реляційної алгебри і реляційного числення еквівалентні, тобто для будь-якого допустимого виразу реляційної алгебри можна побудувати еквівалентну (тобто що проводить такий же результат) формулу реляційного числення і навпаки. Чому ж в реляційній моделі даних присутні обидва ці механізми?

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

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

Відмітимо, що украй рідко алгебра або числення приймаються як повна основа якої-небудь мови БД. Звичайно (як, наприклад, у разі мови SQL) мова грунтується на деякій суміші алгебраїчних і логічних конструкцій. Проте, знання алгебраїчної і логічної основ мов баз даних, часто корисне на практиці.

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

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

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

• об'єднання відношень;

• перетину відношень;

• узяття різниці відношень;

• прямого добутку відношень.

Спеціальні реляційні операції включають:

• обмеження відношення;

• проекцію відношення;

• з'єднання відношень;

• ділення відношень.

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

Теоретіко - множинні операції.

Всі операції володіють очевидною і простою інтерпретацією. Хай задані два відношення R1={ r1 }, R2={r2}, де r1 і r2 - відповідно кортежі відносин R1 і R2.

При виконанні операції об'єднання двох відношень проводиться відношення, що включає всі кортежі, що входять хоч би в одне з відношень - операндів.

R1  R2 = { r | r  R1  r  R2}

Операція перетину двох відносин проводить відношення, що включає всі кортежі, що входять в обидва відношення-операнд.

R1  R2 = { r | r  R1  r  R2}

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

R1\R2 = {r| r R1  rR2}

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

R1R2 = { (r1,r2) | r1R1  r2R2}

Приклад. Дані три відношення з еквівалентними схемами:

R1 = { ПІБ, Паспорт, Школа} - містить список абітурієнтів, що складали репетиційні іспити.

R2 = { ПІБ, Паспорт, Школа} - містить список абітурієнтів, що складали іспити на загальних умовах.

R3 = { ПІБ, Паспорт, Школа} - містить список абітурієнтів, прийнятих в інститут.

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

Відповімо на наступні питання:

1. Список абітурієнтів, які поступали двічі і не поступили у ВНЗ.

R = (R1  R2) \ R3

2. Список абітурієнтів, які поступили у ВНЗ з першого разу.

R = ((R1 \R2)  R3 )  (( R2\R1)  R3)

3. Список абітурієнтів, які поступили у ВНЗ тільки з другого разу.

R = R1  R2  R3

4. Список абітурієнтів, які поступали тільки один раз і не поступили.

R = ((R1 \R2)  (R2\R1)) \ R3

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

Спеціальні операції реляційної алгебри

Результатом обмеження відношення по деякій умові є відношення, що включає кортежі відношення-операнда, що задовольняє цій умові.

Операція обмеження вимагає наявність двох операндів: обмежуваного відношення і простої умови обмеження. Проста умова обмеження може мати або вигляд (а comp b), де а і b - імена атрибутів обмежуваного відношення, для яких осмислена операція порівняння comp, або вигляд (а comp const), де а - ім'я атрибуту обмежуваного відношення, а const - літерально задана константа.

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

Для позначення операції обмеження використовуватимемо конструкцію R WHERE comp, де R - обмежуване відношення, а comp - проста умова порівняння.

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

На інтуїтивному рівні операцію обмеження краще всього представляти як узяття деякої "горизонтальної" вирізки з відношення-операнда.

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

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

Результатом проекції відношення R за списком атрибутів a₁, a2, ..., an є відношення, із заголовком, визначуваною безліччю атрибутів a1, a2, ..., an, і з тілом, що складається з кортежів вигляду <a1:v1, a2:v2, ... an:vn> таких, що відносно R є кортеж, атрибут a1 якого має значення v1, атрибут a2 має значення v2, ..., атрибут an має значення vn. Тим самим, при виконанні операції проекції виділяється "вертикальна" вирізка відношення-операнда з природним знищенням потенційно виникаючих кортежів-дублікатів.

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

Загальна операція з'єднання (звана також з'єднанням по умові) вимагає наявність двох операндів - відносин, що сполучаються, і третього операнда - простої умови. Хай з'єднуються відносини R1 і R2. Як і у разі операції обмеження, умова з'єднання comp має вигляд або (а comp b), або (а comp const), де а і b - імена атрибутів відносин R1 і R2, const - літерально задана константа, а comp - допустима в даному контексті операція порівняння. Тоді за визначенням результатом операції порівняння є відношення, що одержується шляхом виконання операції обмеження по умові comp прямого твору відносин R1 і R2.

Якщо уважно осмислити це визначення, то стане ясно, що в загальному випадку застосування умови з'єднання істотно зменшить потужність результату проміжного прямого твору відношень-операндів тільки у тому випадку, коли умова з'єднання має вигляд (а comp b), де а і b - імена атрибутів різних відношень-операндів. Тому на практиці звичайно вважають реальними операціями з'єднання саме ті операції, які грунтуються на умові з'єднання приведеного вигляду.

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

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

Операція природного з'єднання застосовується до пари відносин R1 і R2, що володіють (можливо складеним) загальним атрибутом з (тобто атрибутом з одним і тим же ім'ям і визначеним на одному і тому ж домені). Якщо пригадати введене нами визначення зовнішнього ключа відношення, то повинно стати зрозуміло, що основний сенс операції природного з'єднання - можливість відновлення складної суті, декомпозіваної унаслідок вимоги першої нормальної форми. Операція природного з'єднання не включається прямо до складу набору операцій реляційної алгебри, але вона має дуже важливе практичне значення.

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

Ця операція найменше очевидна зі всіх операцій реляційної алгебри і тому потребує докладнішого пояснення. Хай задані два відношення - A із заголовком {a1, a2, ..., an b1, b2, ..., bm} і B із заголовком {b1, b2, ..., bm}. Вважатимемо, що атрибут bi відношення A і атрибут bi відношення B не тільки володіють одним і тим же ім'ям, але і визначені на одному і тому ж домені. Назвемо безліч атрибутів {aj} складеним атрибутом а, а безліч атрибутів {bj} - складеним атрибутом b. Після цього говоритимемо про реляційне ділення бінарного відношення A(а,b) на унарне відношення B(b).

Результатом ділення A на B є унарне відношення C(a), що складається з кортежів v таких, що відносно A є кортежі <v, w> такі, що безліч значень {w} включає безліч значень атрибуту b відносно B.

Операція перейменування проводить відношення, тіло якого співпадає з тілом операнда, але імена атрибутів змінені.

Операція присвоювання дозволяє зберегти результат обчислення реляційного виразу в існуючому відношенні БД.

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