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

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

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

Існує багато підходів до визначення реляційної алгебри, які розрізняються набором операцій і способами їх інтерпретації, але в принципі, більш-менш рівносильні. Ми опишемо трохи розширений початковий варіант алгебри, який був запропонований Коддом. У цьому варіанті набір основних алгебраїчних операцій складається з восьми операцій, які діляться на два класи -- теоретико-множинні операції та спеціальні реляційні операції. До складу теоретико-множинних операцій входять операції: об'єднання відносин; перетину відносин; взяття різниці відносин; прямого твори відносин.

Спеціальні реляційні операції включають: обмеження відносини; проекцію відносини; з'єднання відносин; поділ відносин.

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

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

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

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

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

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

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

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

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

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

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

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

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

Інші проблеми пов'язані з операцією взяття прямого твори двох відносин. У теорії множин пряме твір може бути отримано для будь-яких двох множин, та елементами результуючого безлічі є пари, складені з елементів першого і другого множин. Оскільки відносини є множинами, то і для будь-яких двох відносин можливе отримання прямого твори. Але результат не буде відношенням! Елементами результату будуть не кортежі, а пари кортежів.

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

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

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

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

З приводу теоретико-множинних операцій реляційної алгебри слід ще зауважити, що всі чотири операції є асоціативними. Тобто, якщо позначити через OP будь-яку з чотирьох операцій, то (A OP B) OP C = A (B OP C), і отже, без введення двозначності можна писати A OP B OP C (A, B і C - Відносини, що володіють властивостями, необхідними для коректного виконання відповідної операції). Всі операції, крім взяття різниці, є комутативність, тобто A OP B = B OP A. 5.1.4. Спеціальні реляційні операції

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

Операція обмеження

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

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

Нехай UNION позначає операцію об'єднання, INTERSECT - операцію перетину, а MINUS - операцію взяття різниці. Для позначення операції обмеження будемо використовувати конструкцію A WHERE comp, де A - обмежувати відносини, а comp - Просте умова порівняння. Нехай comp1 і comp2 - два прості умови обмеження. Тоді за визначенням: A WHERE comp1 AND comp2 позначає те ж саме, що й (A WHERE comp1) INTERSECT (A WHERE comp2) A WHERE comp1 OR comp2 позначає те ж саме, що й (A WHERE comp1) UNION (A WHERE comp2) A WHERE NOT comp1 позначає те ж саме, що й A MINUS (A WHERE comp1)

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

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

Операція взяття проекції

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

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

Операція з'єднання відносин

Загальна операція з'єднання (що також називається з'єднанням за умовою) вимагає наявності двох операндів - з'єднуються відносин і третій операнда - простого умови. Нехай з'єднуються відносини A і B. Як і у випадку операції обмеження, умова з'єднання comp має вигляд або (a comp-op b), або (a comp-op const), де a і b - імена атрибутів відносин A і B, const - літерально задана константа, а comp-op - допустима в даному контексті операція порівняння.

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

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

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

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

Операція природного з'єднання застосовується до пари відносин A і B, що володіють (можливо складовим) загальним атрибутом c (тобто атрибутом з одним і тим же ім'ям і певним на одному і тому ж домені). Нехай ab позначає об'єднання заголовків відносин A і B. Тоді природне з'єднання A і B - це спроектований на ab результат еквісоедіненія A і B за A/c і BBC. Якщо згадати введене нами наприкінці попереднього глави визначення зовнішнього ключа відносини, то має стати зрозуміло, що основний зміст операції природного з'єднання - можливість відновлення складної суті, декомпозірованной через вимоги першої нормальної форми. Операція природного з'єднання не включається прямо до складу набору операцій реляційної алгебри, але вона має дуже важливе практичне значення.

Операція поділу відносин

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

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

Припустимо, що в базі даних співробітників підтримуються два відносини: СПІВРОБІТНИКИ (ІМ'Я, ОТД_НОМЕР) і ІМЕНА (ІМ'Я), причому Унарне ставлення ІМЕНА містить усі прізвища, якими володіють співробітники організації. Тоді після виконання операції реляційного поділу відносини СПІВРОБІТНИКИ на ставлення ІМЕНА буде отримано Унарне відношення, що містить номери відділів, співробітники яких володіють усіма можливими в цій організації іменами. Реляційне числення

Припустимо, що ми працюємо з базою даних, що володіє схемою СПІВРОБІТНИКИ (СОТР_НОМ, СОТР_ІМЯ, СОТР_ЗАРП, ОТД_НОМ) і ВІДДІЛИ (ОТД_НОМ, ОТД_КОЛ, ОТД_НАЧ), і хочемо дізнатися імена та номери співробітників, які є начальниками відділів з кількістю співробітників більше 50.

Якби для формулювання такого запиту використовувалася реляційна алгебра, то ми отримали б алгебраїчне вираз, що читалося б, наприклад, наступним чином: виконати підключення відносин СПІВРОБІТНИКИ і ВІДДІЛИ за умовою СОТР_НОМ = ОТД_НАЧ; обмежити отримане відношення за умовою ОТД_КОЛ> 50; спроектувати результат попередньої операції на атрибут СОТР_ІМЯ, СОТР_НОМ.

Ми чітко сформулювали послідовність кроків виконання запиту, кожен з яких відповідає одній реляційної операції. Якщо ж сформулювати той самий запит з використанням реляційного обчислення, якому присвячується цей розділ, то ми отримали б формулу, яку можна було б прочитати, наприклад, наступним чином: Видати СОТР_ІМЯ і СОТР_НОМ для співробітників таких, що існує відділ з таким же значенням ОТД_НАЧ і значенням ОТД_КОЛ великим 50.

У другій формулюванні ми вказали лише характеристики результуючого відносини, але нічого не сказали про спосіб його формування. У цьому випадку система має сама вирішити, які операції і в якому порядку потрібно виконати над відносинами СПІВРОБІТНИКИ і ВІДДІЛИ. Зазвичай кажуть, що алгебраїчна формулювання є процедурної, тобто задає правила виконання запиту, а логічна -- описової (або декларативною), оскільки вона всього лише описує властивості бажаного результату. Як ми вказували на початку лекції, насправді ці дві механізму еквівалентні і існують не дуже складні правила перетворення одного формалізму в іншій. 5.2.1. Кортежние змінні та правильно побудовані формули

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

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

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

Для визначення кортежной змінної використовується оператор RANGE. Наприклад, для того, щоб визначити змінну СПІВРОБІТНИК, областю визначення якої є ставлення СПІВРОБІТНИКИ, потрібно вжити конструкцію RANGE СПІВРОБІТНИК IS СПІВРОБІТНИКИ

Як ми вже говорили, з цього визначення випливає, що в будь-який момент часу мінлива СПІВРОБІТНИК представляє деякий кортеж відносини СПІВРОБІТНИКИ. При використанні кортежних змінних у формулах можна посилатися на значення атрибута змінної (це аналогічно тому, як, наприклад, при програмуванні на мові Сі можна послатися на значення поля структурної змінної). Наприклад, для того, щоб послатися на значення атрибуту СОТР_ІМЯ змінної СПІВРОБІТНИК, потрібно вжити конструкцію СОТРУДНІК.СОТР_ІМЯ.

Правильно побудовані формули (WFF - Well-Formed Formula) служать для вираження умов, накладених на кортежние змінні. Основою WFF є прості порівняння (comparison), що являють собою операції порівняння скалярних значень (значень атрибутів змінних або літерально заданих констант). Наприклад, конструкція "СОТРУДНІК.СОТР_НОМ = 140" є простим порівнянням. За визначенням, просте порівняння є WFF, а WFF, укладена в круглі дужки, є простим порівнянням.

Більш складні варіанти WFF будуються за допомогою логічних зв'язок NOT, AND, OR і IF ... THEN. Так, якщо form - WFF, а comp - просте порівняння, то NOT form, comp AND form, comp OR form і IF comp THEN form є WFF.

Нарешті, допускається побудова WFF за допомогою кванторів. Якщо form - це WFF, в якій бере участь мінлива var, то конструкції EXISTS var (form) і FORALL var (form) представляють wff.

Змінні, що входять до WFF, можуть бути вільними або зв'язаними. Всі змінні, що входять в WFF, при побудові якої не використовувалися квантори, є вільними. Фактично, це означає, що якщо для якогось набору значень вільних кортежних змінних при обчисленні WFF отримано значення true, то ці значення кортежних змінних можуть входити в результуюче ставлення. Якщо ж ім'я змінної використано відразу після квантора при побудові WFF виду EXISTS var (form) або FORALL var (form), то в цій WFF і у всіх WFF, побудованих з її участю, var - зв'язана змінна. Це означає, що така змінна не видно за межами мінімальної WFF, що зв'язала цю змінну. При обчисленні значення такої WFF використовується не одне значення пов'язаної змінної, а вся її область визначення.

Нехай СОТР1 і СОТР2 - два кортежние змінні, визначені на ставленні СПІВРОБІТНИКИ. Тоді, WFF EXISTS СОТР2 (СОТР1.СОТР_ЗАРП> СОТР2.СОТР_ЗАРП) для поточного кортежу змінної СОТР1 приймає значення true в тому і тільки в тому випадку, якщо в усьому стосовно СПІВРОБІТНИКИ знайдеться кортеж (пов'язаний зі змінною СОТР2) такою, що значення його атрибуту СОТР_ЗАРП задовольняє внутрішнього умові порівняння. WFF FORALL СОТР2 (СОТР1.СОТР_ЗАРП> СОТР2.СОТР_ЗАРП) для поточного кортежу змінної СОТР1 приймає значення true в тому і тільки в тому випадку, якщо для всіх кортежів відносини СПІВРОБІТНИКИ (пов'язаних зі змінною СОТР2) значення ознаки СОТР_ЗАРП задовольняють умові порівняння.

Насправді, правильніше говорити не про вільні і пов'язаних змінних, а про вільних і пов'язаних входження змінних. Легко бачити, що якщо мінлива var є пов'язаною в WFF form, то у всіх WFF, що включають дану, може використовуватися ім'я змінної var, яка може бути вільною або пов'язаної, але в будь-якому випадку не має ніякого відношення до входження змінної var в WFF form. Ось приклад: EXISTS СОТР2 (СОТР1.СОТР_ОТД_НОМ = СОТР2.СОТР_ОТД_НОМ) AND FORALL СОТР2 (СОТР1.СОТР_ЗАРП> СОТР2.СОТР_ЗАРП)

Тут ми маємо два пов'язаних входження змінної СОТР2 із зовсім різним змістом. 5.2.2. Цільові списки та вирази реляційного обчислення

Отже, WFF забезпечують кошти формулювання умови вибірки з відносин БД. Щоб можна було використовувати для обчислення реальної роботи з БД, потрібно ще один компонент, який визначає набір і імена стовпців результуючого відносини. Цей компонент називається цільовим списком (target_list).

Цільовий список будується з цільових елементів, кожен з яких може мати наступний вигляд: var.attr, де var - ім'я вільної змінної відповідної WFF, а attr - ім'я атрибута відносини, на якому визначена мінлива var; var, що еквівалентно наявності підсписки var.attr1, var.attr2, ..., var.attrn, де attr1, attr2, ..., attrn включає імена всіх атрибутів визначає відносини; new_name = var.attr; new_name - нове ім'я відповідного атрибута результуючого відносини.

Останній варіант потрібно в тих випадках, коли в WFF використовуються декілька вільних змінних з однаковою областю визначення.

Виразом реляційного обчислення кортежів називається конструкція виду target_list WHERE wff. Значним вираження є ставлення, тіло якого визначається WFF, а набір атрибутів і їх імена - цільовим списком. 5.2.3. Реляційне числення доменів

У численні доменів областю визначення змінних є не відносини, а домени. Стосовно до бази даних СПІВРОБІТНИКИ-ВІДДІЛИ можна говорити, наприклад, про доменні змінних ІМ'Я (значення - допустимі імена) або НОСОТР (значення -- допустимі номери співробітників).

Основним формальним відзнакою обчислення доменів від обчислення кортежів є наявність додаткового набору предикатів, що дозволяють висловлювати так звані умови членства. Якщо R - це n-арное відношення з атрибутами a1, a2, ..., An, то умова членства має вигляд R (ai1: vi1, ai2: vi2, ..., aim: vim) (m СОТР_ЗАРП1)

Реляційне числення доменів є основою більшості мов запитів, заснованих на використанні форм. Зокрема, на цьому численні базувався відомий мову Query-by-Example, який був перший (і найбільш цікавим) мовою в сімействі мов, заснованих на табличних формах.