Тема 3.1. Реляційна структура даних.

У науковій літературі, присвяченій реляційним базам даних, на означення того, що було названо вище реляцією або таблицею, часто за­стосовується термін відношення. Кожен із цих термінів має свої переваги й недоліки. Терміном «відношення» у математичній теорії відношень позначається дещо ін­ше поняття і тому тлумачення цього терміну в контексті теорії баз даних є неод­нозначним. Недолік терміну «реляція» полягає в його недавньому іншомовному походженні. Слово «таблиця» часто вживається в різних значеннях і має більш прикладний наголос. Тому для теоретичних розглядів будемо вживати термін «ре­ляційне відношення», а в прикладах — «відношення» або «таблиця».

Розглянемо приклад. Таблиця розкладу руху потягів чи літаків, умовно кажучи, складається з двох частин: наповнення та опису структури таблиці. Наповнення — це ті номери рейсів потягів чи літаків та час їхнього відправлення, що занесені у відповідні клітинки таблиці й періодично змінюються, а структура таблиці опи­сується заголовками стовпців. Згідно з термінологією баз даних і реляційного підходу, наповнення таблиць називають даними. Інколи буває так, що таблиця розкладу містить лише порожні стовпці. Такий об'єкт фахівець з баз даних міг би назвати схемою.

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

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

Схема реляційного відношення має такі властивості:

♦ реляційне відношення має ім'я;

♦ імена атрибутів у межах схеми одного реляційного відношення мають бути унікальними;

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

Приклад схеми реляційного відношення: ВИКЛАДАЧ(#Ід, ПІБ. Адреса). Тут ВИКЛА­ДАЧ - це ім'я реляційного відношення, а #Ід, ПІБ, Адреса - імена його атрибутів.

Екземпляр реляційного відношення — це його наповнення. Точніше, екземпляр є множиною кортежів, а кортеж — це множина значень Екземпляр відношення має такі властивості:

♦ порядок кортежів довільний;

♦ кортежі, як елементи множини, мають бути унікальними в межах реляційного відношення.

Реляційне відношення може бути зображене у вигляді таблиці.

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

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

 

Таблиця 3.1. Відповідність термінів, що вживаються під час розгляду реляційних відношень та їхніх табличних зображень
Формальний термін	Неформальний еквівалент
Відношення	Таблиця
Кортеж	Рядок, запис
Кардинальність	Кількість рядків
Атрибут	Стовпець, поле
Степінь	Кількість стовпців
Первинний ключ	Ідентифікатор
Домен	Область допустимих значень

Поняття ключа

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

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

Ключ називається простим, якщо складається з од­ного атрибута (#Ід), і складеним — якщо з кількох атрибутів, наприклад (ПІБ, Ад­реса). Ключ називають надлишковим, якщо певна його підмножина також є клю­чем. Наприклад, ключ (#Ід, ПІБ, Адреса) є надлишковим тому, що містить атри­бут #Ід, який також є ключем. Ключ, що не є надлишковим, називають мінімаль­ним. Іноді надлишковий ключ називають суперключем, а мінімальний — можли­вим ключем. Реляційне відношення може мати багато можливих ключів, але тіль­ки один із них є первинним.

Первинний ключ має такі властивості:

♦ кожне реляційне відношення має один і лише один первинний ключ;

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

♦ значення первинного ключа не можуть повторюватися, але допускаються по­вторення значень частини складеного первинного ключа;

♦ апріорі значення первинного ключа не впливають на порядок кортежів у таб­личному зображенні реляційного відношення, хоча інколи таблиці впорядко­вують за ключем;

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

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

Зовнішні ключі мають такі властивості:

♦ значення зовнішнього ключа завжди посилається на певне значення відповід­ного первинного ключа, тобто будь-яке значення зовнішнього ключа має бути значенням первинного ключа іншого відношення;

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

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

Типи зв’язків між таблицями

Існує три типи зв’язків між таблицями.

· Зв’язок «один-до-багатьох»

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

Щоб представити зв’язок «один-до-багатьох» у структурі власної бази даних, візьміть первинний ключ на стороні зв’язку «один» і вставте його як додаткове поле або поля в таблицю на стороні зв’язку «багато». У цьому разі, наприклад, нове поле — поле ідентифікатора з таблиці «Клієнти» — потрібно додати до таблиці «Замовлення» та назвати його «Ідентифікатор клієнта». Потім Access зможе використати номер із поля «Ідентифікатор клієнта» в таблиці «Замовлення» для пошуку користувачів, які відповідають певним замовленням.

· Зв’язок «багато-до-багатьох»

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

Для представлення зв’язку «багато-до-багатьох» потрібно створити третю таблицю, яку часто називають розподільною, щоб розділити зв’язок «багато-до-багатьох» на два зв’язки «один-до-багатьох». Первинний ключ із кожної з двох таблиць потрібно вставити в третю таблицю. У результаті в третій таблиці буде записано усі випадки, або екземпляри, зв’язків. Наприклад, таблиці «Замовлення» та «Товари» пов’язані зв’язком «багато-до-багатьох», який визначатиметься через створення двох зв’язків «один-до-багатьох» із таблицею «Відомості про замовлення». В одному замовленні може зустрічатися багато товарів, і кожний товар може зустрічатися в багатьох замовленнях.

· Зв’язок «один-до-одного»

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

Тема 3.2. Реляційна алгебра

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

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

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

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

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

Реляційні відношення. називаються сумісними, якщо:

1) у них однакова кількість атрибутів, тобто k = п;

2) можна встановити взаємно однозначну відповідність між доменами атри­бутів першої та другої реляцій, тобто існує таке об’єктивне відображення

що

тобто домени зіставлених атрибутів однакові.

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

Дамо також означення кількох властивостей бінарних операцій:

♦ операція ф є комутативною, якщо і

♦ операція ф є асоціативною, якщо

♦ операція ф є дистрибутивною з операцією 0, якщо

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

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

Під час розгляду операцій реляційної алгебри атрибути позначатимемо вели­кими літерами з початку латинського алфавіту: А, В,..., а множини атрибутів — великими літерами з середини латинського алфавіту: L, М,....

Отже, розглянемо операції реляційної алгебри.

Об'єднання

Нехай L — певна множина атрибутів. Об'єднанням сумісних реляційних відно­шень R1 і R₂ зі схемами R1(L) і R2(L) (позначається як R1 ﮞ R₂) називається таке реляційне відношення R зі схемою R(L), що містить кортежі обох поєднуваних відношень, але без повторень:

Операція комутативна, асоціативна й дистрибутивна щодо перетину.

Приклад __________________________________________________

Перетин

Припустимо, що L — певна множина атрибутів. Перетином сумісних реляційних відношень R1 і R₂ зі схемами R1(L) і R₂(L) (позначається як R1∩ R₂) називається таке реляційне відношення R зі схемою R(L), яке містить кортежі, що входять до складу обох операндів:

Операція комутативна, асоціативна й дистрибутивна щодо об'єднання.

Приклад __________________________________________________

Різниця

Нехай L — певна множина атрибутів. Різницею сумісних реляційних відношень R1(L) і R₂(L) зі схемами R1(L) і R₂(L) (позначається як R1 - R₂) називається реляційне відношення R зі схемою R(L), що містить ті кортежі з першого операнда R1 яких немає у другому операнді R₂:

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

Приклад _________________________________________________

Зауважимо, що

Зазначимо деякі особливості теоретико-множинних операцій.

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

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

Розглянемо операції, які визначені лише в реляційній алгебрі.

Проекція

Проекцією реляційного відношення R зі схемою R(A{,..., А^) за атрибутами Ац,...,

що позначається Р.[Ац,..., А_іп], називається таке відношення S зі схемою S(A_ib..., А_іп), кортежі якого отримані з кортежів відношення R шляхом видалення значень, що не належать атрибутам, за якими виконується проекція. При цьому в кінцевому відношенні повторні екземпляри кортежів ви­даляються.

Якщо S кортежем відношення R, то записом r[L], де L — підмножина атрибу­тів відношення R, позначимо множину тих елементів кортежу г, що відповідають значенням атрибутів з L. Тоді наведене вище визначення проекції може бути за­писане у такий спосіб:

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

Такі ж самі проблеми мають місце в усіх операціях, де операндами є списки атрибутів.

Приклад _________________________________________________

Обмеження (селекція)

Спочатку дамо означення 9-порівнянності атрибутів. Нехай 0 є одним з операто­рів порівняння: =, Ф, <, <, >, > (набір операторів можна розширити). Атрибути А і В одного й того самого чи різних відношень називаються 0 -порівнянними, якщо для будь-яких значень а є Aib є В результат операції а 0 Ь є визначеним (істин­ним або хибним). Інакше кажучи, ця операція визначена на відповідних атрибу­тах. Набори атрибутів L = (A_h..., А^) та М= (В\,..., В_п) називаються 0-порівнянни-ми, якщо k - п і Aj 0-порівняннез Bj (і = 1, 2,..., k).

Тепер дамо означення операції обмеження.

Нехай L і М — набори 0-порівнянних атрибутів схеми відношення R. Тоді обме­женням реляційного відношення R за умовою L 9 М, що позначається R[L 8 М], називається реляційне відношення, кортежі якого відповідають умові L 0 М:

Множина М може складатися як з атрибутів, так і з констант.

Приклад __________________________________________________

Декартів добуток

Декартовом добутком реляційних відношень R і S зі схемами R(A_h Л₂,..., А_п) та S(B_b 5₂,..., В_т) відповідно, що позначається R x S, називається відношення Q зі схемою Q(A_b А₂,..., А_п, В\, В₂,..., В_т), яке містить усі можливі з'єднання корте­жів відношення R з кортежами відношення S:

Операція комутативна й асоціативна.

Приклад __________________________________________________

З'єднання

Припустимо, що відношення R має схему R(L, М), а відношення S - схему S(N, P). Нехай множини атрибутів М і N — 9-порівнянні. Тоді з'єднанням, або 0-з'єд- нанням, відношень R і S за умовою М 0 iV, що позначається як Д[М 0 N]S, назива­ється відношення Q зі схемою Q(L, М, N, Р), кортежі якого можна отримати з'єд­нанням тих кортежів відношень R і S, на яких виконується умова М 0 N:

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

Іноді операція з'єднання позначається як R й S, де F — умова з'єднання.

З'єднання за умовою рівності називається еквіз'єднанням. З'єднання за умо­вою рівності, коли один з порівнюваних атрибутів (чи група порівнюваних атри­бутів) видаляється з кінцевого відношення, називається природним з'єднанням; на його позначення використовується символ «*». Наприклад, якщо задані відно­шення R(A, В, С, D) і S(C, D, Е), то в результаті виконання операції Q=R* S отри­маємо реляційне відношення Q(A, В, С, D, Е),

Серед операцій 0-з'єднання виділяють операцію напівз'єднання, за якої з результату видаляються всі атрибути одного з відношень, що з'єднуються. Вона записується як R[M 0 N)S і формально визначається так:

Операція напівз'єднання не розширює можливостей реляційної алгебри, ос­кільки вона виражається через з'єднання і проекцію в такий спосіб:

Приклад

Ділення

Нехай задано відношення зі схемою R(M, N). Образом реляційного відношення R за кортежем t\ є R[M] називається така множина кортежів t₂ є R[N], для яких зчеплення (t\, t-i) належить відношенню R. Образ R за кортежем t\ позначається /д(£і) і формально визначається у такий спосіб:

Приклад __________________________________________________

Нехай задано відношення R і S зі схемами R(M, N) та S(K, І), для яких про­екції R[N] та S[K] є сумісними. Діленням відношення R на відношення S за набо­рами атрибутів N і К (позначається R[N+K\S) називається операція, результатом якої є відношення Q зі схемою Q(M), що складається з таких кортежів t є R[M], образи I_R(t) яких містять усі кортежі проекції S[K], тобто:

Можна показати, що операція ділення виражається через інші операції алгеб­ри в такий спосіб:

Операція не комутативнай не асоціативна.