Базисные кошти маніпулювання реляционными данными

Базисные кошти маніпулювання реляционными данными.

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

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

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

об'єднання відносин; перетину відносин; взяття різниці відносин; прямого твори відносин.

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

обмеження відносини; проекцію відносини; з'єднання відносин; розподіл відносин.

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

5.1.1. Загальна інтерпретація реляционных операцій

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

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

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

5.1.2. Замкненість реляційної алгебри і операція перейменування

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

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

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

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

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

5.1.3. Особливості теоретико-множинних операцій реляційної алгебри

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

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

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

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

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

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

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

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

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

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

По приводу теоретико-множинних операцій реляційної алгебри треба ще помітити, що чотири операції є асоціативними. Т. е., якщо позначити через OP будь-яку з чотирьох операцій, то (A OP B) OP З = A (B OP З), і отже, без запровадження двозначності можна писати A OP B OP З (A, B і З — відносини, які мають властивості, необхідними для коректного виконання відповідної операції). Усі операції, окрім узяття різниці, є коммутативными, тобто. 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, які мають (можливо складовим) загальним атрибутом з (тобто. атрибутом з однією і тим самим ім'ям й певним однією й тому самому домені). Нехай 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, який був охарактеризований першим (і найцікавішим) мовою у сімействі мов, заснованих на виключно табличных формах.