ПОРІВНЯЛЬНИЙ АНАЛІЗ реляційного числення І реляційної алгебри

На початку цієї глави стверджувалося, що реляційна алгебра і реляційне числення в своїй основі еквівалентні Обговоримо це твердження більш докладно Спочатку Кодд в [71] показав, що алгебра є, щонайменше, настільки ж потужною, як і літочислення Для цієї мети він запропонував алгоритм, що отримав назву алгоритму редукції Кодда, за допомогою якого будь-який вираз обчислення можна перетворити в семантично еквівалентну вираз алгебри Ми не станемо наводити тут цей алгоритм повністю, а обмежимося досить складним прикладом, иллюстрирующим в загальних рисах, як він функціонірует3

В якості основи для нашого прикладу використовується не звична база даних постачальників і деталей, а її розширена версія, згадувана у вправах глави 4 і в інших розділах Для зручності на рис 81 наведено приклад можливих значень для цієї бази даних (це – копія рис 45 з глави 4)

3 Насправді алгоритм, представлений в [71], містить невелику помилку [82] Більш того, певна в цій статті версія реляційного числення не включає аналог оператора обєднання, отже, обчислення Кодда є строго менш потужним, ніж його алгебра Як би там не було, але твердження про те, що алгебра та обчислення, що включає аналог операції обєднання, еквівалентні, є істинним, і це доведено багатьма авторами (див, наприклад, [711])

Рис 81 База даних постачальників, деталей та проектів (значення дані для прикладу)

Розглянемо тепер наступний запит: Отримати імена постачальників і назви міст, в яких знаходяться постачальники деталей, що поставляють деталі принаймні для одного проекту в Афінах (Athens) в кількості не менше 50 деталей кожного типу . Вираз реляційного числення для цього запиту наведено нижче

{ SXSNAME, SXCITY } WHERE EXISTS JX FORALL PX EXISTS SPJX ( JXCITY = Athens

AND JXJ# = SPJXJ#

AND PXP# = SPJXP#

AND SXS# = SPJXS#

AND SPJXQTY &gt QTY (

50 ) )

Тут SX, PX, JX і SPJX – змінні області значень, що приймають значення, відповідно, з змінних відносини s, P, J і SPJ Тепер покажемо, як можна обчислити цей вираз, щоб досягти необхідного результату

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

SX Всі кортежі відносини s – 5 кортежів

РХ Всі кортежі відносини р – 6 кортежів

JX Кортежі відношення J, в яких CITY = Athens-2 кортежу

■ SPJX Кортежі відносини SPJ, в яких QTY ≥ QTY (50) – 24 кортежу

Етап 2 Будуємо декартовій твір діапазонів, обраних на першому етапі Результат представлений нижче

(І тд) Все твір містить 5 * 6 * 2 * 24 = 1440 кортежів

Примітка Для економії місця тут це відношення повністю не наводиться Ми також не перейменовували атрибути (хоча це слід було б зробити, щоб уникнути двозначності), а просто розташували їх у такому порядку, щоб було видно, який атрибут s # відноситься, наприклад, до відношення S, а який – до відношення SPJ Це також зроблено для скорочення викладу

Етап3  Застосовуємо операцію скорочення до сформованого на етапі 2 добутку відповідно до частиною конструкції WHERE, що відноситься до зєднання. У нашому прикладі ця частина виглядає таким чином

JXJ# = SPJXJ# AND PXP# = SPJXP# AND SXS# = SPJXS#

Тому з твору виключаються кортежі, для яких значення атрибута s # з відношення постачальників не дорівнює значенню атрибута s # з відношення поставок, або значення атрибута Р # з відношення деталей не дорівнює значенню атрибута Р # з відношення поставок, або значення атрибута J # з відношення проектів не дорівнює значенню атрибута J # з відношення поставок Потім отримуємо підмножина декартова твори, що складається (як виявилося) тільки з десяти кортежів

(Це відношення являє собою наочний приклад зєднання по еквівалентності)

Етап 4 Застосовуємо квантори в порядку справа наліво наступним чином

■ Для квантора EXISTS V (де v – мінлива області значень, приймає зна чення з деякого відносини r) формуємо проекцію поточного промежуточ ного результату, щоб виключити всі атрибути відносини r

■ Для квантора FORALL V ділимо поточний проміжний результат на ставлення з областю значень, отриманої за допомогою операції скорочення, відпо вующее відношенню V, яке було отримано вище При виконанні цієї опе рації також будуть виключені всі атрибути відносини rj

Примітка Під діленням тут мається на увазі оригінальна операція

ділення

Кодда (див анотацію до [74])

У нашому прикладі маємо наступні квантори

EXISTS JX FORALL PX EXISTS SPJX

Таким чином, потім виконуються наступні операції

■ EXISTS SPJX Виняток за допомогою операції проекції атрибутів змін ної відносини SPJ (SPJS #, SPJP #, SPJ J # і SPJQTY) В результаті получа ем наступне,

■ FORALL PX Розподіл отриманого результату на ставлення Р В результаті маємо наступне

■ EXISTS JX Виняток за допомогою операції проекції атрибутів відносини J (J J #, J JNAME і J CITY) В результаті отримуємо наступне

Етап 5 Отримання проекції результату етапу 4 у відповідності зі специфікаціями в кортежі-прототипі У нашому прикладі кортеж-прототип має наступний вигляд

(SXSNAME,   SXCITY)

Значить, кінцевий результат обчислень буде такий

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

Цим ми завершуємо обговорення даного прикладу Звичайно, можна набагато поліпшити використовуваний алгоритм (див главу 18, зокрема, анотацію до [184]) І хоча багато подробиці в поясненнях були опущені, цей приклад цілком адекватно відображає загальну ідею роботи алгоритму редукції

До речі, тепер можна пояснити одну (не єдину) з причин того, чому Кодд визначив рівно вісім алгебраїчних операторів Ці вісім операторів утворюють зручний цільової мову, який може служити засобом можливої ​​реалізації реляційного числення Іншими словами, для заданого мови, побудованого на основі реляційного числення (подібно до мови QUEL), один з можливих підходів до реалізації полягає в тому, що організується отримання запиту в тому вигляді, в якому він наданий користувачем По суті, він буде просто вираженням реляційного числення, до якого потім можна буде застосувати певний алгоритм редукції, щоб отримати еквівалентну алгебраїчне вираз Це вираження алгебри, зрозуміло, буде включати набір алгебраїчних операцій, які, безумовно, будуть реалізованими за визначенням (Наступний етап полягає в оптимізації отриманого алгебраїчного виразу, про що йтиметься у розділі 18)

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

Насамперед, відзначимо, що деякий мову прийнято називати реляційно повним,

якщо він за своїми можливостями, принаймні, не поступається реляційному обчисленню Інакше кажучи, для цього необхідно, щоб будь-яке відношення, яке можна визначити за допомогою реляційного числення, можна було визначити і за допомогою деякого виразу аналізованого мови [71] (У розділі 7 зазначалося, що реляційно повний означає не поступається за можливостями реляційної алгебрі , а не обчисленню, але, як читач незабаром переконається, це одне і те ж По суті, з самого існування алгоритму редукції Кодда негайно випливає, що реляційна

алгебра володіє реляційної повнотою)

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

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

Далі, оскільки алгебра володіє реляційної повнотою, для доказу того,

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

показати, що в ньому є аналоги пяти примітивних операцій) і що операнди будь-якої операції мови L можуть бути представлені виразами мови L (відповідного типу) Мова SQL – це приклад мови, реляционную повноту якого можна довести описаним способом (упр 89) Мова QUEL – ще один приклад подібного мови Насправді на практиці часто простіше показати те, що в мові

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

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

Обчислювальна повнота – це один з факторів, що спонукали ввести в реляційну алгебру операції EXTEND І SUMMARIZE (обговорювалися в главі 7) У наступному розділі описано, як можна розширити реляционное числення, щоб забезпечити в ньому наявність аналогів цих операцій

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

[813] Звідси випливає, що реляційна алгебра і реляційне числення логічно

еквівалентні

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*