Лекции по бази данни



страница6/10
Дата16.12.2016
Размер1.96 Mb.
#11293
ТипЛекции
1   2   3   4   5   6   7   8   9   10

Декартово произведение
Декартово произведение на релациите R и S е нова релация, която бележим с R x S и която има за кортежи всевъзможните съединения на кортеж от R с кортеж от S. Схемата на R x S е обединение на схемите на R и S с тази особеност, че ако R и S имат атрибути с еднакви имена предварително трябва да се извърши преименуване на дублиращите се атрибути. Изполваме така наречената точкова нотация - за да различаваме атрибутът A на релациите R и S записваме R.A за атрибута от R и S.A за атрибута от A. Ще считаме, че атрибутите на R предшестват атрибутите на S в схемата на R x S.

Ще разгледаме пример.



Нека R е следната релация:

A

B

1

2

3

4

Нека S е следната релация:

B

C

D

2

5

6

4

7

8

9

10

11

Тогава R x S е следната релация:

A

R.B

S.B

C

D

1

2

2

5

6

1

2

4

7

8

1

2

9

10

11

3

4

2

5

6

3

4

4

7

8

3

4

9

10

11

Тъй като B е атрибут и на двете релации сме използвали R.B и S.B в схемата за R x S. За останалите атрибути не е нужно да се извършва преименуване, тъй като те не се дублират. В релацията R x S всеки от кортежите на R е съединен с всеки от кортежите на S.
Естествено съединение
Много често се налага при образуване на декартово произведение на релации да не се извършват всевъзможни съединения на кортежи.

Естествено съединение на две релации R и S е нова релация, която означаваме с R ⋈ S. Нейните кортежи са всевъзможни съединения на кортеж от R с кортеж от S, които се съгласуват по общите атрибути на релациите R и S. По-прецизно, нека A1, A2, …, An са общите атрибути в схемите на релациите R и S. Тогава схемата на R ⋈ S е теоретико-множествено обединение на схемите на R и S, т.е. не се извършва преименуване и атрибутите A1, A2, …, An участват само по веднъж в схемата на R ⋈ S. Два кортежа r и s се съединяват успешно, ако те се съгласуват по стойностите на A1, A2, …, An. Toгава съответният кортеж на R ⋈ S се съгласува по всички атрибути на R с кортежа r и по всички атрибути на S с кортежа s. Това естествено е възможно точно когато двата кортежа r и s са успешно съединени.

Ще отбележим, че тази операция за естествено съединение е същата, която използвахме при възстановяване на информацията след декомпозиция в нормална форма на Boyce-Codd.

Ще разгледаме примери.

За релациите от по-горе R и S релацията R ⋈ S има следния вид:



A

B

C

D

1

2

5

6

3

4

7

8

Единственият общ атрибут на R и S е B. Така кортеж от R се съгласува с кортеж от S точно когато стойностите им за B съвпадат. Резултатните кортежи в R ⋈ S включват компоненти за следните атрибути:

A (от R), B (от R или S), C (от S) и D (от S). Както се вижда, третият кортеж на S не се съгласува с никой от кортежите на R. Такъв кортеж се нарича висящ кортеж.

Нека U е следната релация:


A

B

C

1

2

3

6

7

8

9

7

8

Нека V е следната релация:

B

C

D

2

3

4

2

3

5

7

8

10

Тогава релацията ⋈ има следния вид:

A

B

C

D

1

2

3

4

1

2

3

5

6

7

8

10

9

7

8

10

Общите атрибути на U и V са B и C. Така кортеж от U се съгласува с кортеж от V точно когато стойностите им за B и C съвпадат.

В този пример първият кортеж на U се съгласува с първите два кортежа на V, а вторият и третият кортеж на U се съгласуват с третия

кортеж на V. При това естествено съединение няма висящи кортежи.
Тита-съединение
При естественото съединение кортежите на релациите се комбинират по точно едно условие - съвпадение на общите атрибути. Понякога се налага кортежи да се съединяват и по други условия.

Тита-съединение на релациите R и S е нова релация, която означаваме по следния начин: R ⋈C S. Нейната схема е обединение на схемите

на R и S, при това се извършва преименуване на атрибутите, които се дублират. C е условен израз, подобен на условния израз от селекцията, но в него могат да участват имена на атрибути и на R и на S.

Кортежите на R ⋈C S получаваме по следния начин:


  • образуваме релацията R x S;

  • избираме онези кортежи на R x S, които удоволетворяват условието C (след заместване на имената на атрибутите със съответните стойности).

Да отбележим, че при тита-съединението, за разлика от естественото съединение в резултатната схема общите атрибути не се сливат в едно копие. Причината е, че при естественото съединение това има смисъл, тъй като условието за съединение е съвпадащи атрибути. При

тита-съединението условието може да е произволно.

Ще разгледаме примери.

За релациите U и V от по-горе релацията U ⋈A < D S изглежда така:



A

U.B

U.C

V.B

V.C

D

1

2

3

2

3

4

1

2

3

2

3

5

1

2

3

7

8

10

6

7

8

7

8

10

9

7

8

7

8

10

Релацията U ⋈A < D AND U.B V.B S изглежда така:

A

U.B

U.C

V.B

V.C

D

1

2

3

7

8

10


Комбиниране на операциите
За конструиране на по-сложни заявки трябва да комбинираме сравнително простите операции, които въведохме. С други думи, като операнди можем да използваме както дадените релации, така и резултатните релации от вече извършени операции.

По този начин можем да получаваме произволно сложни заявки.


Сложните заявки ще записваме с изрази, като всеки израз се получава чрез прилагане на операция към негови подизрази. За еднозначно прочитане на подизразите ще използваме скоби. Възможно е за представяне на изразите да използваме обичайната дървовидна структура.
Ще разгледаме примери с нормализираните релации

Movie1 (title, year, length, type, studioName),

Movie2 (title, year, starName).

Да предположим, че имаме следната заявка: “Да се намерят заглавията и годините на филмите, произведени от Fox и дълги поне 100 минути.”

Едно решение е следното:


  1. Намираме всички филми, дълги поне 100 минути.

  2. Намираме всички филми, произведени от Fox.

  3. Намираме сечението на 1. и 2.

  4. Намираме проекцията на 3. по заглавие и година.

Съответният израз от релационната алгебра се представя

чрез следното дърво:



Във вътрешните възли на дървото стоят операциите. Тъй като използваме и унарни операции, то някои възли имат само един наследник. В листата на дървото са дадените релации.

Съвременните СУБД получават заявките, представени именно по този начин. Оптимизацията и изпълнението на заявките се извършват въз основа на това дърво.
Друг начин да запишем заявката е чрез обичайната за записване на израз с поставяне на скоби по следния начин:

title, year (length>=100 (Movie1)  studioName=’Fox’ (Movie1)).


Много често е възможно различни изрази от релационната алгебра да водят до едно и също изчисление. Например, дадената заявка

може да се представи и чрез следния израз:

title, year (length>=100 AND studioName=’Fox’ (Movie1)).
По-общо в сила са следните закони:

C (R)  D (R) = C AND D (R)

C (R)  D (R) = C OR D (R)

C (R) - D (R) = C AND NOT D (R)


Като друг пример да разгледаме следната заявка: “Да се намерят звездите, които участват във филми, дълги поне 100 минути.”

Естествено, тук трябва да използваме естествено съединение за да възстановим информацията от декомпозираните релации.

Съответният израз от релационната алгебра е следния:

starName (length>=100 (Movie1 ⋈ Movie2)).


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

Резултатът от преименуването на релация R бележим по следния начин:



(R). Изискването е n да съвпада с броя на атрибутите на R.

Резултатната релация има име S и схема S (A1, A2, …, An). Кортежите на S съвпадат с кортежите на R. Възможно е да променяме само името на релацията R, без да променяме имената на атрибутите като използваме операцията в следната форма: (R). Схемата и екземплярът на R се запазват при тази операция, а името се променя на S.


Ще разгледаме пример.

Нека R е следната релация:



A

B

1

2

3

4

Нека S е следната релация:

B

C

D

2

5

6

4

7

8

9

10

11

При образуване на декартово произведение на R и S можем да не искаме да използваме точковата нотация. В такъв случай явно трябва да преименуваме съвпадащите атрибути.

Например, релацията R x S (X,C,D) (S) изглежда така:



A

B

X

C

D

1

2

2

5

6

1

2

4

7

8

1

2

9

10

11

3

4

2

5

6

3

4

4

7

8

3

4

9

10

11

Друг начин е да извършим декартовото произведение и след това да преименуваме. Изразът RS (A,B,X,C,D) (R x S) се изчислява до същата релация, с тази разлика че в този случай тя има име - RS.
Зависими и независими операции
Някои от операциите на релационната алгебра могат да бъдат изразени с помощта на други операции.

Например, сечението R  S може да се изрази чрез обединение и разлика по следния начин: R  S = R - (R - S).

Естественото съединение и тита-съединението могат да се изразят чрез декартово произведение, проекция и селекция по следния начин:

R ⋈C S = C (R x S), R ⋈ S = L (C (R x S)). Тук условието C има вида:

R.A1 = S.A1 AND R.A2 = S.A2 AND …AND R.An = S.An, където A1, A2, …, An са общите атрибути на R и S. Списъкът от атрибути L започва с атрибутите на R, последвани от тези атрибути на S, които не са атрибути на R.

Шестте останали операции - обединение, разлика, декартово произведение, селекция, проекция и преименуване образуват независимо множество, т.е. никоя от тях не може да се изрази чрез останалите.




Линейна нотация
Ще разгледаме още едно представяне на сложните заявки с повече от една операция, което наричаме линейна нотация. При него на междинните релации, които отговарят на вътрешните възли на дървото се поставят имена. Самата сложна заявка се представя като последователност от присвоявания. Те трябва да са разположени в такъв ред, че за всеки връх на дървото N преди да изчисляваме релация, отговаряща на N трябва да сме изчислили всички релации, отговарящи на децата на N. Ще използваме следната нотация за присвояванията:

R (A1, A2, …, An) := израз_от_релационната_алгебра.

В лявата страна стои името и схемата на междинната релация, в дясната страна стои израз от релационната алгебра, при това операндите в него са или дадени релации или получени релации в

по-горни присвоявания. В релацията с име Answer получаваме резултатът - тя отговаря на корена на дървото.

Обикновено в изразите в дясна част се използва само една операция, т.е. за всеки междинен връх на дървото има отделно присвояване.

Възможно е, обаче, в изразите в дясна част да се комбинират няколко операции - например с цел повишаване на ефективността.

Като пример ще опишем първата заявка от по-горе в линейна нотация:

R (t, y, l, t, s) := length>=100 (Movie1)

S (t, y, l, t, s) := studioName=’Fox (Movie1)

T (t, y, l, t, s) := R  S

Answer (title, year) := t, y (T)

Възможно е последните две присвоявания да се комбинират в едно:

R (t, y, l, t, s) := length>=100 (Movie1)

S (t, y, l, t, s) := studioName=’Fox’ (Movie1)

Answer (title, year) := t, y (R  S)
Първите СУБД са били реализирани чрез линейна нотация.
Операции върху мултимножества
В съвременните СУБД екземплярите на релациите са мултимножества от кортежи, а не множества от кортежи, както е в класическата релационна алгебра. С други думи, допуска се в една релация да се дублират кортежи. Причината е, че много от операциите се реализират по-ефективно, когато се прилагат към мултимножества.

Например, при обединение на релации R, S с екземпляри мултимножества кортежите на S просто се добавят към кортежите на R без да се премахват дубликатите. Също, при проекция на една релация R може два различни кортежа да се проектират в еднакви кортежи.

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


Обединение, сечение и разлика на мултимножества
Нека R и S са релации с екземпляри мултимножества.

Обедининието R  S се образува по следния начин:

всеки кортеж, който присъства n пъти в R и m пъти в S присъства

m+n пъти в R  S.

Сечението R  S се образува по следния начин:

всеки кортеж, който присъства n пъти в R и m пъти в S присъства

min (m, n) пъти в R  S.

Разликата R - S се образува по следния начин:

всеки кортеж, който присъства n пъти в R и m пъти в S присъства

mаx (0, n-m) пъти в R - S. С други думи, всяко едно срещане на кортежа в S елиминира едно срещане на кортежа в R.

Ще разгледаме някои примери.

Нека R е следната релация:



A

B

1

2

3

4

1

2

1

2

Нека S е следната релация:

A

B

1

2

3

4

3

4

5

6

Тогава R  S е следната релация:

A

B

1

2

3

4

1

2

1

2

1

2

3

4

3

4

5

6

Релацията R  S изглежда по следния начин:

A

B

1

2

3

4

Релацията R - S изглежда по следния начин:

A

B

1

2

1

2

Релацията S - R изглежда по следния начин:

A

B

3

4

5

6

Всяко множество естествено може да се разглежда като мултимножество. Лесно се съобразява, че операциите сечение и разлика на мултимножества, приложени върху множества са идентични на операциите сечение и разлика на множества. Това, обаче, не е в сила за операцията обединение. Например, ако R и S са релации с екземпляри множества от кортежи и един кортеж t се съдържа както в R, така и в S, то чрез обединението на мултимножества получаваме релация, в която кортежът t се среща поне два пъти, т.е. дори не получаваме множество.
Изрично ще отбележим, че някои от обичайните закони за операциите с множества престават да бъдат в сила за съответните операции с мултимножества. Например, законът (R  S) - T = (R - T)  (S - T), който е в сила за множества не е в сила за мултимножества.

Действително, нека един кортеж t се среща точно по веднъж в R, S и Т.

Тогава t се среща точно веднъж в (R  S) - T, но не се среща в

(R - T)  (S - T). Други закони, обаче, остават в сила. Например,

R  S = S  R, R  S = S  R, (R  S)  T = R  (S  T),

(R  S)  T = R  (S  T).


Каталог: materials
materials -> Исторически преглед на възникването и развитието на ес
materials -> Съюз на математиците в българия-секция русе коледно математическо състезание – 12. 2006 г. 4 клас
materials -> Великденско математическо състезание 12. 04. 2008 г. 2 клас Времето за решаване е 120 минути
materials -> Съюз на математиците в българия-секция русе коледно математическо състезание – 09. 12. 2006г
materials -> Съюз на математиците в българия-секция русе коледно математическо състезание – 12. 2006 г. 8 клас
materials -> Великденско математическо състезание 12. 04. 2008г. 3 клас
materials -> К а т е д р а " информатика"
materials -> Зад. 2 Отг.: 5- 3т Зад. 3 Отг.: (=,-);(+,=);(+,=) по 1т., общо 3т. За
materials -> Іv клас От 1 до 5 зад по 3 точки, от 6 до 10 – по 5 и от 11 до 15 – по 7


Сподели с приятели:
1   2   3   4   5   6   7   8   9   10




©obuch.info 2024
отнасят до администрацията

    Начална страница