18231

Реляційна модель баз даних. Мови запитів

Лекция

Информатика, кибернетика и программирование

Реляційна модель баз даних. Мови запитів. Теоретичні основи реляційної моделі баз даних були закладені Е.Коддом на початку 70х років [1] і спочатку дійсно мали чисто теоретичний характер. На відміну від поширених на той час систем з ієрархічними чи мережаними типами стр

Украинкский

2013-07-07

119.5 KB

25 чел.

Реляційна модель баз даних. Мови запитів.

Теоретичні основи реляційної моделі баз даних були закладені Е.Коддом на початку 70-х років [1] і спочатку дійсно мали чисто теоретичний характер. На відміну від поширених на той час систем з ієрархічними чи мережаними типами структур даних реляційний підхід запропонував гранично спрощені структури даних – реляції чи таблиці, але значно употужнив мови маніпулювання даними та мови запитів. 

Введемо поняття реляції формально.

Нехай  V основний алфавіт, тобто деяка скінченна множина.  - деякий виділений елемент;   V. Забігаючи наперед, зазначимо, що буде означати невизначено.  

Позначимо через  D1, D2, … Dn   V* ;  де V* - множина всіх слів в алфавіті V.

Домени визначаються як Di = Di  {};

Множину імен атрибутів позначимо  . І введемо однозначне, але  не обовязково інєктивне відображення N:   {D1, D2, … Dn}, яке іменує домени. Кожен домен може мати кілька імен, позначимо  і = N-1(Dі) – множину всіх імен домена Dі. Очевидно, що ці множини мають такі властивості:

і  j  = ;      (i=1 n) і = ;

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

Атрибутом називається  (А,Dі) – де А  і , тобто атрибут визначається як іменований домен, причому у різних атрибутів домени можуть бути однакові, а імена відрізнятися.

Нехай       (Аі1,D1)і2,D2)ік,Dк) – відношення над декартовим добутком атрибутів. Введемо над множиною так визначених відношень розбиття на класи еквівалентності наступним чином: до одного класу віднесемо ті відношення, які відрізняються тільки порядком компонент у декартовому добутку. Представник такого  класу називається реляційною таблицею або реляцією R(і1,D1),(Аі2,D2),…,(Аік,Dк)).

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

Через aR будемо позначати множину імен атрибутів реляції R.

Розглянемо два приклади опису схем бази даних.

  1.  Перший приклад відноситься до предметної області, що повязана з постачальниками (П), деталями (Д), отримувачами (О) та поставками (ОПД).  Спочатку опишемо домени:

CREATE  DOMAIN  C   CHAR(3) DEFAULT ‘ ‘;

CREATE  DOMAIN  N   INTEGER DEFAULT  0;

     CREATE  DOMAIN  STR   CHAR(20) DEFAULT ‘ ‘;

CREATE  DOMAIN  COLOR   (черв,оранж,жовт,зел,блак,син,фіол);

У наведеному описі після ключових слів CREATE  DOMAIN задається власне ім’я домена, а далі – його тип.

    Тепер введемо реляції:

CREATE  TABLE П (кп  C,  прізв STR, статус N, місто STR,

 PRIMARY KEY(кп));

{кп – код постачальника}

CREATE  TABLE Д (кд  C,  назва STR, колір COLOR, вага REAL,

місто STR,  PRIMARY KEY(кд));

{кдкод деталі}

CREATE  TABLE O (кo  C,  прізв STR, місто STR,

PRIMARY KEY(кo));

{кокод отримувача}

CREATE  TABLE ОПД (кп  C, кд  C, ко С,  кільк N, ціна REAL,

 PRIMARY KEY(кп, кд, ко));

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

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

     Лектор(кл, прізв, орг, тел, наук_ступ);

{код_лектора,  місце основної роботи, телефон, науковий ступінь}

Предмет(кп, назва, тип, год, контр);

{код предмета, назва предмета, тип(лекції,практич,лаб...), кількість годин, контроль(іспит, залік, диф.залік, нічого)}

Група(кг, фак, каф, курс, к_чол);{студенти}

{код групи, факультет, кафедра, курс, кількість чоловік}

Розклад(кл, кп,кг, день, ауд, пара);

{день заняття,аудиторія, пара(1,2,3,4,5..)}

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


ІІ.1.1. Реляційна алгебра Кодда.

Алгебраїчна пара : основна множина і сигнатура. Елементи і результати операцій належать основній множині.

Реляційна алгебра – алгебра в строгому розумінні. Елементи основної множини – реляції.

Сигнатура складається з 8-ми операцій.

Теоретико-множинні операції Ç,È,\ – частково визначені (визначені тільки для сумісних реляцій з однаковою структурою).

Реляції R1(A1, … , An) і R2(B1, … , Bk) називаються сумісними, якщо:

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

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

S:{1, … , k} ® {1, … , k}, що

N(Ai) = N(BS(i)),    i = l k.

Об’єднання.

R1ÈR2: в результуючу реляцію попадають всі кортежі першої і другої реляції без дублів.

Перетин.

R1ÇR2: в результуючу реляцію попадають кортежі, присутні і в першій, і в другій реляції.

Різниця.

R1\R2: в результуючу реляцію попадають кортежі з R1, яких немає в R2.

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

  1.  Деякі домени можуть бути нескінченними, в результаті операції доповнення можна отримати або нескінченну реляцію, або реляцію з дуже великою кількістю кортежів. Тому у реляційній алгебрі на відміну від алгебри множин використовується операція різниці, а не доповнення.
  2.  Часткова визначеність введених операцій теж зумовлена прагматичним аспектом. Без обмеження сумісності результатом операції обєднання могли б бути різноструктурні кортежі, а не таблиця.

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

R1ÄR2 – визначається для будь-яких реляцій.

R1ÄR2 = {(r1, … , rk, rk+1, … , rk+n) | (r1, … , rk) Î R1, (rk+1, … , rk+n) Î R2}.

Ця операція може різко збільшити об’єм результату.

Проекція.

Реляція S(B1, … , Bn) узгоджена з R(A1, … , Ak), якщо

$ f : aS ® aR, N(f(Bi)) = N(Ai), i = 1 n.

Відображення f однозначне, але, взагалі кажучи, не взаємно однозначне.

Проекцією реляції R на схему S відносно узгодження f будемо називати реляцію

T = R[S] таку, що

T = {(r[Ai1], r[Ai2], … , r[Ain])}

T = R[Ai1, Ai2, … , Ain,]

Реляція R несе і схему, і дані, а реляція S – тільки схему.

Атрибути реляції S повинні бути підмножиною множини атрибутів реляції R.

Примітка.

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

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

Посилаючись на реляцію П (постачальник), запит “знайти прізвища всіх постачальників” може бути виражений так: П[прізв].

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

Операція q - з’єднання (q - join).

Введемо поняття q - порівнюваності для кортежів.

На двох реляціях R(A1, … , Ak) і S(B1, … , Bn) візьмемо відповідно два підкортежі:

r1 = (d1, d2, … , dm),  r2 = (d1|, d2|, … , dm|);

Нехай  q = {=, ¹, <, £, >, ³, …}; наповнення цієї множини залежить від того, які бінарні предикати задані на відповідних доменах.

Два кортежі r1 і r2 q - порівнювані:

r1q r2  Û  di q di|,  i = 1,m; (m £ k, m £ n);

Нехай в реляції R виділений список атрибутів M1 = {A1, … , Am}, а в реляції S список атрибутів M2 = {B1, … , Bm}, причому відповідні атрибути співпадають по доменам, тобто

N(Ai) = N(Bi),   i = 1,m;

Операція q - з’єднання реляції R з реляцією S по спискам M1 і M2 :

R[M1 q M2]S = {t Î R Ä S | t[M1] q t[M2]}.

Операція q - з’єднання по порівнянню ‘=’ називається еквіз’єднанням.

Приклад.

R

A1

A2

A3

S

B1

B2

 

A

1

1

 

2

U

 

A

2

1

 

3

V

 

B

1

2

 

4

U

 

B

2

5

 

C

3

3

R1¬R[A3 = B1]S

R1

A1

A2

A3

B1

B2

 

B

1

2

2

U

 

C

3

3

3

V


R2¬R[A2 > B1]S

R2

A1

A2

A3

B1

B2

 

C

3

3

2

U

Операція еквіз’єднання називається природним з’єднанням(natural join), якщо в результат проходить лише один стовпчик з двох (в обох стовпчиках у кожному рядочку значення повинні співпадати за визначенням операції еквіз’єднання).

Наприклад: R1¬R[A3  B1]S – в результуючій таблиці не було б атрибута B1.

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

В літературі іноді цю операцію називають селекцією або фільтрацією.

Ця операція задається над однією реляцією з двома списками атрибутів; використовується також поняття q - порівнюваності.

Нехай задана реляція R(aR), де aR - множина імен атрибутів;

M1 = {A1, … , Am} Í aR; і

M2 = {B1, … , Bm} Í aR - списки атрибутів з властивістю

N(Ai) = N(Bi); i = 1,m;

q - обмеження реляції R по спискам M1 і M2 :

R[M1 q M2] = {r | (r R) &(r[M1] q r[M2])}.

R3¬R[A2 = A3]

R3

A1

A2

A3

 

A

1

1

 

C

3

3

Операція ділення.

Спочатку введемо одне допоміжне поняття.

Нехай задана реляція R(A1, … , Ak) і два взаємнодоповнюючі списки атрибутів

M1 = {A1, … , An}; M2 = {An+1, … , Ak}

Нехай є С1 = D1´´Dn; С2 = Dn+1´´Dk; де Di = N(Ai), i = 1,k;

Якщо візьмемо деякий елемент x Î С1, то образом x по реляції R буде називатись множина підкортежів :

imRx = {y Î С2 | (x, y) Î R}

Розглянемо реляції R(aR), S(aS) і списки атрибутів

{A1, … , An}aR ; {B1, … , Bn}aS;

Необхідно, щоб реляції R[A1, … , An] і S[B1, … , Bn] були сумісними, тоді операція R[A ¸ B]S називається діленням R на S по спискам {A1, … , An} і {B1, … , Bn}

Результатом є множина підкортежів по атрибутам, що доповнюють список {A1, … , An}.

R[A ¸ B]S = {r[An+1, … , Ak] | (r Î R) & (S[B1, … , Bn] Í imR(r[An+1, … , Ak]))}

Приклад використання операції ділення.

Нехай задана таблиця R з двома атрибутами (мова програмування і прізвище програміста, який цією мовою володіє) 

Знайти прізвища програмістів, які знають мови А і Ф одночасно. Для виконання такого запиту утворимо допоміжну реляцію S з одним атрибутом і двома кортежами з відповідними значеннями кодів мов програмування {А,Ф}.

R[мова ¸ мв]S

R

Мова

прізв

S

мв

 

А

І

 

А

А

П

 

Ф

ПЛ

С

Ф

Ф

Ф

І

Ф

С

ПЛ

П

П

Ф

П

І

Образом І буде {А, Ф, П}, що є надмножиною відносно{А, Ф}, тому І проходить у результуючу таблицю; а П, С, Ф – не проходять у результуючу таблицю, бо їх образи не накривають {А, Ф}. Це означає, що програміст І знає мови {А, Ф}(можливо ще щось), а інші не знають цих мов одночасно.

Приклади використання операцій реляційної алгебри у запитах на основі бази даних про поставки.

Знайти прізвища постачальників, що живуть в Одесі.

(П[місто = ‘Одеса’])[прізв] ® П1.

Зауважимо, що використання константи ‘Одеса’ у наведеному прикладі операції -обмеження є відступом від теоретичної “чистоти” реляційної моделі, але розробники мов на основі реляційної алгебри йшли на подібні відступи задля зручності користувача  та практичної ефективності. Ми і надалі будемо використовувати такі відступи. Наведемо також теоретично “чистий” варіант вищезгаданого запиту. Для цього введемо допоміжну реляцію ДОП(місто) з єдиним кортежем ‘Одеса’.

(П[місто = місто]ДОП)[прізв] ® П1.

Знайти ціни поставок деталей з кодом Д1, що виконують постачальники з кодом S1.

(ОПД[КП = ‘S1’ & КД = ‘Д1’])[ціна] ® ОП2.

Знову зауваження відносно теоретичної “чистоти”. “Чистий” варіант для такого  запиту передбачає введення допоміжної реляції ДОП1(КП1,КД1) з єдиним кортежем <‘S1’,‘Д1’>.

(ОПД[КП,КД = КП1,КД1]ДОП1)[ціна] ® ОП2.

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

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

(Д[колір = черв])[КД] ® Д3

{знайдено коди деталей червоного кольору}

(ОПД[КД = КД]Д3)[КП] ® П4

{знайдено коди постачальників, що постачають деталі з Д3} 

(П[КП = КП]П4)[прізв] ® Res

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

((ОПД[КП, КД])[КП ° КП]П4)[КД] ® Д4

((ОПД[КП, КД])[КД ° КД]Д4) ® П5

(П5[КП ° КП]П)[прізв] ® Res1

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

 

Знайти прізвища постачальників, що постачають всі деталі.

(ОПД[КП, КД])[КД ¸ КД]( Д[КД] ) ® R1

(R1[КП ° КП]П)[прізв] ® Res

Зауважимо, що природні мови, зокрема українська, на відміну від формальних мов мають неоднозначності, які необхідно уточнювати. У наведеному запиті словосполучення “всі деталі” може означати всі існуючі деталі (таблиця Д), чи всі деталі, що постачаються (таблиця ОПД). Запис засобами операцій реляційної алгебри орієнтується на таблицю Д, для іншого варіанту виділений курсивом текст Д[КД] потрібно було б замінити на ОПД[КД].

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

((П[прізв = ‘Іванов’])[КП ° КП](ОПД[КП,КД]))[КД] ® R1

{знайдено коди деталей, які постачає Іванов}

((ОПД[КП,КД])[КД ° КД]R1)[КП] ® R2

(П[КП ° КП]R2)[прізв] ® Res

6. Знайти прізвища постачальників, які постачають всі ті деталі, які постачає Іванов.

((П[прізв = ‘Іванов’])[КП ° КП]ОПД[КП,КД])[КД] ® R1

(ОПД[КП, КД])[КД ¸ КД]R1 ® R2

(П[КП ° КП]R2)[прізвище] ® Res

7. Знайти прізвища постачальників, які постачають точно ті деталі, які постачає Іванов.

{реляцію R1 взято з попереднього прикладу}

(ОПД[КП, КД])[КД ¸ КД]R1 ® R2

{знайдено коди постачальників, що постачають принаймні всі деталі з R1}

((ОПД[КП, КД])[КД ¹ КД]R1)[КП] ® R3

{знайдено коди постачальників, що постачають хоча б одну деталь не з R1}

R2\R3 ® R4

8. Знайти номери одержувачів, які не одержують жодної червоної деталі від постачальників з міста N.

Задача розв’язується від супротивного, розбивається на підзадачі. Спочатку знаходимо коди одержувачів, які одержують хоча б одну червону деталь, а потім від всіх кодів одержувачів віднімаємо R3.

(П[місто = ‘N’])[КП] ® R1

(Д[колір = черв])[КД] ® R2

(((R1[КП ° КП]ОПД)[КД, КО])[КД ° КД]R2)[КО] ® R3

(О[КО]\R3) ® R4

  1.  Знайти прізвища постачальників, які постачають принаймні всі червоні та всі зелені деталі.

(Д[колір = черв Ú колір = зел])[КД] ® R1

(ОПД[КП, КД])[КД ¸ КД]R1 ® R2

(R2[КП ° КП]П)[прізв] ® R3

10. Знайти прізвища постачальників, які постачають принаймні одну червону та одну зелену деталь.

(Д[колір = черв])[КД] ® Д1

(Д[колір = зел])[КД] ® Д2

((ОПД[КП, КД])[КД ° КД]Д1)[КП] ® П1

((ОПД[КП, КД])[КД ° КД]Д2)[КП] ® П2

П1 Ç П2 ® П3

  1.  Знайти прізвища постачальників, які постачають одну і ту ж саму деталь всім одержувачам.

((ОПД[КП, КД, КО])[КО ¸ КО](О[КО]))[КП] ® R1

(R1[КП ° КП]П)[прізв] ® R2

Зауважимо, що у цьому записі дуже важливою є роль атрибута КД (виділено курсивом). У ході виконання операції ділення образ КО формується для підкортежа <КП, КД>, отже створюється ефект “однієї і тієї ж деталі”.

12. До реляції Д внести новий кортеж

Д È {<‘Д7’, ‘чайка’, ‘сірий’, 20, ‘Одеса’>} Д

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

13. З реляції П вилучити кортеж

П È {<‘S3’, ‘Сидоров’, 7, ‘Донецьк’>} П

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

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

Примітка.

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

II.1.2. Реляційна алгебра вибору (Дрібаса).

Реляційна алгебра вибору була запропонована пізніше реляційної алгебри Кодда і еквівалентна останній з точки зору виразових можливостей. Головною перевагою реляційної алгебри вибору є її орієнтація на прагматичні аспекти.

Основною множиною цієї алгебри, як і раніше, є множина реляцій. До складу множини операцій входять теоретико – множинні операції: È, Ç, \ , Ä, операція проекції і

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

 

Операції фільтрації.

Попереднє зауваження: умова (фільтр) має структуру подібну до виразів у квадратних дужках операцій з’єднання та обмеження (розширений варіант).

Fβ(R, β) – проста фільтрація; R – реляція, а  β - фільтр.

В результуючу реляцію проходять тільки ті кортежі з R, які задовольняють умові β.

2.1) F$(R1, R2, β) – фільтрація по існуванню; R1,R2 – реляції, а  β - фільтр.

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

  1.  F"(R1, R2, β) – фільтрація по узагальненню; R1,R2 – реляції, а  β - фільтр.

Результат містить тільки ті кортежі з R1, для яких умова β виконується для всіх кортежів з реляції R2. Перевірка входження кортежа в  результат виконується до першого випадку невиконання β.

3) FS(R1, R2, A, Ba q C) – фільтрація з множинним порівнянням.

R1,R2 – реляції

A, Ba – списки атрибутів з R1

C – список атрибутів з R2

q – бінарний предикат множинного порівняння: Í, Ì, Ê, É, =, ¹.

Семантику цієї фільтрації опишемо алгоритмічно:

кортежі реляції R1 групуються по значенням атрибутів списку A; {R1a}aÎA

R2 проектується по C

з груп {R1a} вибираються ті кортежі, для яких виконується умова R1[B] q R2[C]

в результуючу реляцію вибрані кортежі.

Як уже відзначалося, алгебра вибору має переваги прагматичного аспекту:

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

 


 

А также другие работы, которые могут Вас заинтересовать

65758. Стратегия экономического роста России под воздействием инфляционных процессов 1.3 MB
  Проблема инфляции занимает важное место в экономической науке, поскольку ее показатели и социально-экономические последствия играют серьезную роль в оценке экономической безопасности страны. Данная проблема в настоящее время широко обсуждается различными авторами...
65761. Пути совершенствования механизма разработки и реализации кадровой политики ГУП “Роскоммунпромкомплект” 410.5 KB
  Кадровая политика признается одной из наиболее важных сфер жизни предприятия способного многократно повысить ее эффективность а само понятие управление персоналом рассматривается в достаточно широком диапазоне: от экономико-статистического до философско-психологического.
65763. Организация стратегического управления в ТОО «Омега» 508 KB
  При осуществлении в нашей стране реформы возникает проблема выработки такой хозяйственной политики и стратегии которые позволяют организации поддерживать конкурентоспособность в обозримой перспективе. Действия организации и их руководителей не могут сводиться к простому реагированию на происходящие перемены.
65765. Творчество П. Рубенса 18.87 KB
  Антверпен плодовитый южно-нидерландский фламандский живописец как никто другой воплотивший подвижность безудержную жизненность и чувственность европейской живописи эпохи барокко. Творчество Рубенса органичный сплав традиций брейгелевского реализма с достижениями венецианской школы.
65766. Філософія Стародавнього Китаю (філософські погляди Лао-Цзи, школа «Фацзя». Філософія Конфуція) 40 KB
  Загальновідомим є те, що Конфуцій не звертав уваги на вивчення та розробку загальнотеоретичних проблем, він не створив філософської системи крайнього спрямування. Всю свою увагу він зосередив на питаннях етики, бо цього вимагали історичні умови того часу, соціальний інтерес.