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



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

Многозначна зависимост в една релация R наричаме твърдение от следния вид: ако в екземпляр на R, компонентите на кортежите, отговарящи на атрибутите A1, A2, …, An съвпадат, то компонентите на кортежите, съответни на атрибутите B1, B2, …, Bm са независими от стойностите на всички останали атрибути. Бележим многозначната зависимост по следния начин: A1 A2 …An  B1 B2 …Bm.

По-прецизно, казваме че многозначната зависимост

A1 A2 …An  B1 B2 …Bm е в сила за една релация R, ако за всяка двойка кортежи t, u в екземпляр на R, които се съгласуват по A1, A2, …, An съществува кортеж v, такъв че:


  • v се съгласува с t и u по A1, A2, …, An;

  • v се съгласува с t по B1, B2, …, Bm;

  • v се съгласува с u по всички останали атрибути на R.

Естествено, в това правило кортежите t и u могат да участват симетрично, така че съществува кортеж w, такъв че:

  • w се съгласува с t и u по A1, A2, …, An;

  • w се съгласува с u по B1, B2, …, Bm;

  • w се съгласува с t по всички останали атрибути на R.




A1, A2, …, An

B1, B2, …, Bm

други атрибути

t










u










v










w










Като следствие при фиксирани стойности на A1, A2, …, An съответните стойности на B1, B2, …, Bm и всички останали атрибути се комбинират по всевъзможни начини в различни кортежи на екземпляра на релацията R.


Както при функционалните зависимости можем да допускаме някои от атрибутите A1, A2, …, An да са сред B1, B2, …, Bm. Изрично ще отбележим, че за разлика от функционалните зависимости за многозначните зависимости не е в сила правилото за разделяне.

По-долу ще дадем пример, който показва това.

Може да се провери, че правилото за комбиниране е в сила за многозначните зависимости.
В примера от по-горе съществува следната многозначна зависимост:

name  street city. Действително, всевъзможните адреси на звездата Carrie Fisher се комбинират с всевъзможните филми, в които тя участва.


Правила за многозначните зависимости
Ще разгледаме някои правила за многозначните зависимости, които наподобяват правилата за функционалните зависимости, но има някои разлики.
Ако за една релация R е в сила многозначната зависимост

A1 A2 …An  B1 B2 …Bm, то за нея е в сила многозначната зависимост

A1 A2 …An  C1 C2 …Ck, където C1, C2, …, Ck съдържат B1, B2, …, Bm и някои от A1, A2, …, An. Също за R е в сила многозначната зависимост

A1 A2 …An  D1 D2 …Dr, където D1, D2, …, Dr са тези от B1, B2, …, Bm, които не с от A1, A2, …, An. Тези две правила наричаме правила за тривиалните зависимости.


Ако за една релация R са в сила многозначните зависимости

A1 A2 …An  B1 B2 …Bm и B1 B2 …Bm  C1 C2 …Ck, то за R е в сила многозначната зависимост A1 A2 …An  C1 C2 …Ck. Това правило наричаме транзитивно правило. Лесно се съобразява, че то е коректно чрез дефиницията за многозначна зависимост.


Ще покажем с пример, че за многозначните зависимости не е в сила правилото за разделяне. В релацията от по-горе е в сила многозначната зависимост name  street city, но не е в сила многозначната зависимост

name  street. Действително, да разгледаме следните два кортежа:



Carrie Fisher

123 Maple Str.

Hollywood

Star Wars

1977

Carrie Fisher

5 Locust Ln.

Malibu

Star Wars

1977

За тях по дефиниция трябва да съществува следния кортеж:

Carrie Fisher

123 Maple Str.

Маlibu

Star Wars

1977

Това, обаче, не е изпълнено.

За многозначни зависимости има две нови правила.


Aко функционалната зависимост A1 A2 …An  B1 B2 …Bm е в сила за една релация R, то за R е в сила многозначната зависимост

A1 A2 …An  B1 B2 …Bm. Действително, нека t и u са кортежи в екземпляр на R които се съгласуват по A1, A2, …An. Тогава кортежът v = u се съгласува с t по B1, B2, …, Bm, тъй като t и u се съгласуват по

B1, B2, …, Bm. Тук сме използвали, че за R е в сила

A1 A2 …An  B1 B2 …Bm. Също v се съгласува с u по всички останали атрибути, тъй като v = u. Аналогично, можем да изберем w = t.


За многозначните зависимости е в сила следното правило за допълнение, което не е в сила за функционалните зависимости:

ако за R е в сила многозначната зависимост A1 A2 …An  B1 B2 …Bm, то за R е в сила многозначната зависимост A1 A2 …An  C1 C2 …Ck, където

C1, C2, …, Ck са всички атрибути на R без A1, A2, …, An, B1, B2, …, Bm.

Това правило е коректно - разменяме ролите на v и w в дефиницията.

Като пример, тъй като за горната релация е в сила многозначната зависимост name  street city, то за нея е в сила многозначната зависимост name  title year.
Четвърта нормална форма
Излишеството, което се поражда от многозначните зависимости може да се избегне чрез подходяща декомпозиция, подобно на декомпозицията при BCNF. В резултат на тази декомпозиция се елиминират излишествата, породени както от многозначните, така и от функционалните зависимости.
Казваме, че многозначната зависимост A1 A2 …An  B1 B2 …Bm е нетривиална, ако:


  1. { B1, B2, …, Bm }  { A1, A2, …, An } = .

  2. A1, A2, …, An, B1, B2, …, Bm не изчепват всички атрибути на R.

Казваме, че една релация R е в четвърта нормална форма (4NF), ако във всяка нетривиална многозначна зависимост A1 A2 …An  B1 B2 …Bm

{ A1, A2, …, An} е суперключ.

Това означава, че всяка нетривиална многозначна зависимост всъщност е функционална и в лявата и част има суперключ.


Примерната релация по-горе не е в четвърта нормална форма.

Действително, за нея е в сила нетривиалната многозначна зависимост

name  street city и name не е суперключ - единственият ключ (суперключ) на тази релация е множеството от всички атрибути.

Естествено, всяка релация, която се намира в четвърта нормална форма се намира и в трета нормална форма, т.е. 4NF  BCNF. Това следва от факта, че всяка функционална зависимост е многозначна.

Обратното не е вярно, както показва разгледания пример.
Всяка релация с два атрибута се намира в четвърта нормална форма, тъй като в нея не може да има нетривиални многозначни зависимости.
Декомпозиция в 4NF
Алгоритъмът за декомпозиране в 4NF е аналогичен на този за BCNF.

Нека A1 A2 …An  B1 B2 …Bm e нетривиална многозначна зависимост, която нарушава 4NF. Тогава разбиваме релацията R на две релации със следните схеми:



  • първата съдържа атрибутите A1, A2, …, An, B1, B2, …, Bm;

  • втората съдържа атрибутите A1, A2, …, An и всички останали атрибути, които не участват в многозначната зависимост.

Ако новополучените релации не са в 4NF, то към тях прилагаме същата процедура. Този процес ще е краен, тъй като винаги получаваме релации с по-малко атрибути, а всяка релация с два атрибута е в 4NF.

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

Причината е, че декомпозицията не е безпринципна, а се извършва на базата на многозначните зависимости.
Както вече споменахме, 4NF влече BCNF, която от своя страна

влече 3NF. Свойствата на декомпозицията при трите нормални форми могат да се обобщят в следната таблица:



свойство

3NF

BCNF

4NF

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

в повечето случаи

да

да

отстранява излишества, породени от многозначни зависимости

не

не

да

запазва функционалните зависимости

да

в някои случаи

в някои случаи

запазва многозначните зависимости

в някои случаи

в някои случаи

в някои случаи


Релационна алгебра
Релационната алгебра е нотация за описване на заявки към релации. Множеството от операциите, които осигурява релационната алгебра не е пълно по Тюринг, в смисъл че съществуват операции, които не могат да се опишат със средствата на релационната алгебра, но могат да се опишат например на C++ или на кой да е от обикновените езици за програмиране. Предимството е, че това дава възможност за по-ефективно оптимизиране на заявките.

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


Примерна схема на база от данни
По-долу в някои примери ще използваме базата от данни, която има следната схема:

Movie (title : string,



year : integer,

length : integer,

inColor : boolean,

studioName : string,

producerC# : integer)

StarsIn (movietitle : string,



movieyear : integer,

starname : string)

MovieStar (name : string,

address : string,

gender : char,

birthdate : date)

MovieExec (name : string,

address : string,

cert# : integer,

netWorth : integer)

Studio (name : string,

address : string,

presC# : integer)
Схемата се състои от пет релации. Посочили сме атрибутите на всяка от релациите, заедно с техните области от стойности. Ключовите атрибути във всяка релация са подчертани.

Новите елементи, които не сме разглеждали са следните:



  • добавени са продуценти на филми, които се идентифицират чрез техния сертификационен номер; в релацията Movie атрибутът producerC# е номерът на продуцента на филма;

  • добавен е атрибут пол за звездите от тип символ - ‘F’ за жена или ‘M’ за мъж;

  • атрибутът inColor приема стойност true, ако филмът е цветен и стойност false, ако е черно-бял;

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


Основи на релационната алгебра
В релационната алгебра операндите, които използваме са конкретни релации или променливи, които означават релации. В класическата релационна алгебра, както споменахме, релациите са множества от кортежи. Традиционните операции в релационната алгебра делим на четири групи:

  • обикновените операции с множества - обединение, сечение, разлика, приложени към релации;

  • операции, които премахват части от релация – селекция, която премахва кортежи (редове) и проекция, която премахва атрибути (колони);

  • операции, които комбинират кортежите на две релации - декартово произведение, което съединява кортежите на две релации по всички възможни начини и различни други операции за съединение, които съединяват само част от тези кортежи;

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

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


Операции с множества върху релации
Когато прилагаме операция с множества към две релации R и S, то трябва да са изпълнени следните условия:

  • R и S трябва да имат едни и същи схема с идентични множества от атрибути, както и области от стойности за тези атрибути;

  • преди да се изпълни операцията колоните на R и S трябва да се подредят по един и същи начин.

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

Обединението бележим по следния начин: R  S.

Сечението бележим по следния начин: R  S.

Разликата бележим по следния начин: R - S.

Да отбележим, че разликата не е комутативна операция, т.е. релациите

R - S и S - R в общия случай са различни.

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

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

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


name

address

gender

birthdate

Carrie Fisher

123 Maple St., Hollywood

F

9/9/99

Mark Hamill

456 Oak Rd., Brentwood

M

8/8/88

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



name

address

gender

birthdate

Carrie Fisher

123 Maple St., Hollywood

F

9/9/99

Harrison Ford

789 Palm Dr., Beverly Hills

M

7/7/77

Обединението R  S е следната релация:



name

address

gender

birthdate

Carrie Fisher

123 Maple St., Hollywood

F

9/9/99

Mark Hamill

456 Oak Rd., Brentwood

M

8/8/88

Harrison Ford

789 Palm Dr., Beverly Hills

M

7/7/77

Сечението R  S е следната релация:



name

address

gender

birthdate

Carrie Fisher

123 Maple St., Hollywood

F

9/9/99

Разликата R - S е следната релация:



name

address

gender

birthdate

Mark Hamill

456 Oak Rd., Brentwood

M

8/8/88

Разликата S - R е следната релация:



name

address

gender

birthdate

Harrison Ford

789 Palm Dr., Beverly Hills

M

7/7/77


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

колоните на R. Бележим , естествено A1, A2, …, An са част от атрибутите на R. Схемата на новата релация се състои само от атрибутите A1, A2, …, An. Естествено, кортежите на новата релация са проекции на кортежите на R върху атрибутите A1, A2, …, An. Ако някои кортежи от R имат еднакви стойности за A1, A2, …, An, то в релацията



включваме само една от съответните проекции - в релационната алгебра, базирана на множества не допускаме дублиране на кортежите. Като пример, ако R е релацията от по-горе, то релацията name, birthdate (R) има следния вид:

name

birthdate

Carrie Fisher

9/9/99

Mark Hamill

8/8/88

Селекция
Резултатът от селекцията, приложена върху релация R е друга релация с множество кортежи, което е подмножество на кортежите на R. Кортежите, които се включват в резултата са точно онези кортежи от R, които удоволетворяват някакво условие C за стойностите на атрибутите.

Резултатът от селекцията бележим по следния начин: C (R).

Схемата на релацията C (R) съвпада със схемата на R.

C е условен израз, в който като операнди участват константи или имена на атрибути на R. В C могат да се използват различните операции за сравнение - =, <, >, , <=, >=, както и логическите съюзи and, not, or.

Условието C се прилага към всеки кортеж t на релацията R, като името на всеки атрибут в условието C се замества със съответната му стойност от кортежа t. Ако условието се оцени като истина, то кортежът t се включва в релацията C (R), в противен случай не се включва.

Ще разгледаме пример. Нека R е следната релация:



title

year

length

inColor

studioName

producerC#

Star Wars

1977

124

true

Fox

12345

Mighty Ducks

1991

104

true

Disney

67890

Wayne’s World

1992

95

true

Paramount

99999

Тогава релацията length >= 100 (R) има следния вид:

title

year

length

inColor

studioName

producerC#

Star Wars

1977

124

true

Fox

12345

Mighty Ducks

1991

104

true

Disney

67890

Действително, за първия кортеж след заместването условието C приема вида 124 >= 100 и се оценява с истина, за втория кортеж условието C приема вида 104 >= 100 и се оценява с истина, а за третия кортеж C приема вида 95 >= 100 и се оценява с лъжа.
Релацията length>=100 AND studioName =’ Fox (R) има следния вид:

title

year

length

inColor

studioName

producerC#

Star Wars

1977

124

true

Fox

12345

Действително, за първия кортеж след заместването условието C приема вида 124 >= 100 AND ‘Fox’ = ‘Fox’ и се оценява с истина, тъй като и двете части на конюнкцията се оценяват с истина, за втория кортеж условието C приема вида 104 >= 100 AND ‘Disney’ = ‘Fox’ и се оценява с лъжа, тъй като втората част на конюнкцията се оценява с лъжа, а за третия кортеж C приема вида 95 >= 100 AND ‘Paramount’ = ‘Fox’ и се оценява с лъжа, тъй като и двете части на конюнкцията се оценяват с лъжа.
Каталог: 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
отнасят до администрацията

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