I. Основи на субд 2


III.Проектиране на БД 1.Функционални зависимости



Изтегляне 1.28 Mb.
страница10/14
Дата23.02.2017
Размер1.28 Mb.
#15584
1   ...   6   7   8   9   10   11   12   13   14

III.Проектиране на БД

1.Функционални зависимости

1.1.Основни понятия


Ще разгледаме концепцията за функционална зависимост.

Основно - ФЗ (FD) е едно много-към-едно отношение от едно множество от атрибути към друго множество от атрибути в една релация.

С други думи, ако знаем стойността на едно поле от определен запис, то можем да намерим стойностите на други полета от същия запис. Например, ако знаем стойността на първичен ключ (FACULTY_ID) от таблицата FACULTY, можем да получим името на факултета (FACULTY_NAME) и броя служители (EMPLOYEE_NUMBER). Казваме, че FACULTY_NAME и EMPLOYEE_NUMBER са функционално зависими от FACULTY_ID.

Ако знаем идентификатора на определен преподавател ще можем да научим и факултета, към който той работи.

Ако знаем ЕГН на определен човек, това значи, че можем да определим и името на този човек.

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

Функционалните зависимости се означават чрез следната нотация:

FACULTY_ID  FACULTY_NAME

FACULTY_ID  EMPLOYEE_NUMBER

LECTURER_ID  FACULTY_ID

ЕГН  име_човек

(студент, дисциплина)  оценка
Атрибутите от лявата страна се наричат детерминанти.

Накратко, функционалните зависимости са взаимоотношения между стойности на атрибути. Ако FACULTY_ID определя FACULTY_NAME, то на определена стойност на FACULTY_ID ще отговаря точно една стойност на FACULTY_NAME. На определен ЕГН ще съответства точно едно име на човек.

Обратното, обаче, не е вярно. На името Иван Иванов биха съответствали повече от един ЕГН. На FACULTY_ID биха съответствали повече от един преподаватели (LECTURER_ID) – в един факултет работят повече от един преподаватели. Следователно, можем да заключим, че взаимоотношенията на LECTURER_ID към FACULTY_ID са много към едно (n:1), т.е. много преподаватели могат да работят в един и същ факултет.

Обобщено, ако X(Y, Z), тогава XY и XZ. Но ако (X, Y)Z (случая с продадените артикули), то не можем да заключим, че XZ или YZ.



Дефиниция: нека R е релация и нека X и Y са произволни подмножества на множеството от атрибути на R. Y е функционално зависим от X (XY), ако и само ако на всяка X-стойност в R съответства точно една Y-стойност в R (в определен момент).

Ако Х е ПК (първичен ключ) на релацията R, тогава всички атрибути Y на релацията са функционално зависими от Х (следва от дефиницията на ключа-кандидат). В таблицата FACULTY:



{FACULTY_ID}  {FACULTY_ID, FACULTY_NAME, YEAR_ESTABLISHED, EMPLOYEE_NUMBER}

Трябва също така да отбележим, че в дефиницията на функционалната зависимост не се изисква X да бъде ключ-кандидат на R.

Ако релацията R удовлетворява ФЗ XY и X не е КК, тогава R ще включва някакво излишество.

1.2.Тривиални и нетривиални зависимости


Един очевиден начин да се редуцира обема на множеството на ФЗ е да елиминираме тривиалните зависимости.

Тривиална зависимост: зависимост, която не може да не бъде удовлетворена. ФЗ е тривиална, ако дясната страна е подмножество на лявата.

1.3.Затвореност на едно множество от зависимости


Някои ФЗ загатват за други. Например:

{FACULTY_ID}  {FACULTY_NAME, YEAR_ESTABLISHED}

загатва за двете зависимости



{FACULTY_ID}  {FACULTY_NAME }

{FACULTY_ID}  {YEAR_ESTABLISHED}

Затвореност: множеството на всички ФЗ, които следват от едно дадено множество S от ФЗ се нарича затвореност на S и се означава с S+.

Аксиоми на Армстронг (множество от правила за извод): нека A, B, C - произволни подмножества на множеството на атрибути на дадена релация R. Означаваме AB за A B. Тогава:

  • рефлексивност - ако B A, тогава AB;

  • разширяемост - ако AB, тогава ACBC;

  • транзитивност - ако AB и BC, тогава AC.

Всяко от тези правила следва директно от дефиницията на ФЗ. От тези правила могат да бъдат изведени други, които улесняват практическата дейност за получаване на S+.

  • самоопределение - AА;

  • декомпозиция - ако ABС, тогава AB и AC;

  • обединение - ако AB и АC, тогава ABC;

  • композиция - ако AB и CD, тогава ACBD.

  • general unification theorem - ако AB и CD, тогава A (C - B) BD.

Пример: нека е дадена релация R с атрибути A, B, C, D, E, F и ФЗ ABC, BE, CDEF.

Ще покажем, че ФЗ ADF е в сила в R и така тя е член на затвореността на даденото множество:


  1. ABC (дадено)

  2. AC (1, декомпозиция)

  3. ADCD (2, разширение)

  4. CDEF (дадено)

  5. ADEF (3 и 4, транзитивност)

  6. ADF (5, декомпозиция)

1.4.Затвореност на едно множество от атрибути


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

Дефиницията на суперключ може следователно да се изведе от тази на КК чрез премахване на изискването за несъкратимост.

Непосредствено следва, че суперключовете за една релация са тези подмножества K на множеството на атрибутите, така че ФЗ KA важи за всеки атрибут А.

Нека допуснем, че знаем ФЗ, които са в сила за дадена релация и искаме да определим КК-вете за тази релация. КК по дефиниция са тези суперключове, които са несъкратими. Така, определяйки дали едно множество от атрибути К е суперключ, е една голяма стъпка към определянето дали К е фактически един КК.

За да определим дали К е суперключ, ние трябва да определим дали множеството на всички атрибути, функционално зависещи от К, е фактически множеството на всички атрибути на релацията.

1.5.Несъкратими множества от зависимости


Обвивка: нека S1 и S2 са две множества от ФЗ. Ако всяка ФЗ, изведена от S1, се извежда от ФЗ в S2, т.е. ако S2+ S1+ тогава S2 е обвивка на S1.

Тава означава, че ако СУБД приложи ограниченията, представени чрез ФЗ в S2, тогава тя ще прилага автоматично и ФЗ в S1.



Еквивалентност: множествата от ФЗ S2 и S1 са еквивалентни ако S2 е обвивка на S1 и S1 е обвивка на S2.

Ако S2 и S1 са еквивалентни, тогава когато СУБД прилага ограниченията, представени чрез ФЗ в S2 , тогава тя ще прилага автоматично и ФЗ в S1 и обратно.



Несъкратимо множество от ФЗ: ако и само ако то удовлетворява следните три свойства:

  • дясната страна на всяка ФЗ в S включва точно един атрибут;

  • лявата страна на всяка ФЗ в S е несъкратима по ред - означава, че никой атрибут не може да бъде премахнат от нея без да промени затвореността й (т.е. без конвертиране S в някакво множество нееквивалентно на S). Така ФЗ е ляво-несъкратима;

  • никоя ФЗ в S не може да бъде отстранена от S без да промени затвореността й (т.е. без да трансформира S в някакво множество нееквивалентно на S).

Пример: да разгледаме релацията FACULTY. Следните ФЗ са в сила:

FACULTY_IDFACULTY_NAME

FACULTY_IDYEAR_ESTABLISHED

FACULTY_IDEMPLOYEE_NUMBER

Това множество на ФЗ е несъкратимо, защото:



  • за всичките случаи дясната страна е единичен атрибут;

  • лявата страна очевидно е несъкратима;

  • никоя ФЗ не може да се премахне без да промени затвореността (т.е. без загуба на информация).

Следните множества от ФЗ обаче, не са несъкратими:

FACULTY_ID(FACULTY_NAME, EMPLOYEE_NUMBER) - дясната страна не е един атрибут

FACULTY_IDYEAR_ESTABLISHED
(FACULTY_ID, FACULTY_NAME)YEAR_ESTABLISHED - тази ФЗ може да бъде опростена чрез премахване на FACULTY_NAME от лявата страна без промяна на затвореността, т.е. тя не е ляво-несъкратима

FACULTY_IDEMPLOYEE_NUMBER

FACULTY_IDFACULTY_ID - тази ФЗ не може да бъде премахната без промяна на затвореността

FACULTY_IDFACULTY_NAME

FACULTY_IDYEAR_ESTABLISHED

FACULTY_IDEMPLOYEE_NUMBER
За всяко множество от ФЗ съществува по едно еквивалентно множество, което е несъкратимо.

Нека оригиналното множество от ФЗ е S.



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

  • за всички ФЗ f в S ние разглеждаме всеки атрибут A от лявата страна на f - ако S и множеството от ФЗ, получено чрез елиминиране на A от лявата страна на f са еквивалентни, ние изтриваме A от лявата страна на f. Т.е. за всички f в S, ако S≡(S - f), изтриваме f от S. Окончателното множество S е несъкратимо и еквивалентно на оригиналното.

Пример: да разгледаме релацията R с атрибути A, B, C, D. Следните ФЗ са в сила:



ABC

BC

AB

ABC

ACD


  1. Единична дясна страна.

AB

AC

BC

AB

ABC

ACD

ФЗ AB се появява два пъти - едната може да се задраска.




  1. Атрибутът C може да се елиминира от лявата страна на ACD, понеже имаме AC, тогава AAC (чрез разширение) и дадена ACD.

Така AD (чрез транзитивност). Следователно C в лявата страна на ACD е излишно.

AB

AC

BC

ABC

ACD

AD


  1. ФЗ ABC може да бъде елиминирана, защото отново имаме AC, тогава ABCB (чрез разширение) и така ABC (чрез декомпозиция).

AB

AC

BC

ABC

AD


  1. ФЗ AC е изведена чрез ФЗ AB и BC, така че тя също може да се елиминира. Така остават:

AB

BC

AD

Това множество е несъкратимо.

Едно множество M от ФЗ, което е несъкратимо и е еквивалентно на някое друго множество S от ФЗ се нарича несъкратима обвивка на S.

Следователно, за дадено множество S от ФЗ, което трябва да се приложи, е важно за системата да намери и приложи една несъкратима обвивка M, вместо него.


1.6.Типове зависимости


Ще разгледаме четири вида функционални зависимости – функционални, транзитивни, мулти-стойностни и JOIN зависимости.

1.6.1.Функционални зависимости


Функционална зависимост (ФЗ) съществува между две полета A и B, когато единична стойност на А е директно свързана с единична стойност на B. Това означава, че по дадена стойност на А за определен запис в таблица винаги може да бъде извлечена стойността на B в този запис.

Функционалната зависимост се бележи така:



AB

като елемента отляво на стрелката наричаме детерминант, а този отдясно - зависим.

Казваме, че стойността на А определя стойността на B

или


стойността на B е функционално зависима от стойността на А.

Коректно проектираните таблици винаги съдържат добре дефинирани функционални зависимости. За пример може да послужи първичният ключ, който функционално определя всички неключови полета в таблицата – по зададена стойност на първичния ключ за определен запис можем да извлечем стойностите на всички неключови полета от записа. Фигура 11-1 илюстрира това добре. В посочената таблица полето CustomerId определя всички останали полета в таблицата.



1.6.2.Транзитивни зависимости


Нека имаме три полета A, B и C, между които съществуват следните функционални зависимости:

АB

BC

Транзитивна зависимост (ТЗ) съществува между А и С, защото конкретна стойност на А е индиректно асоциирана с конкретна стойност на C посредством B. Логиката е следната:



А определя стойността на B

B определя стойността на С

Следователно А транзитивно определя стойността на С.

Транзитивната зависимост се бележи така:

АС

Казваме, че стойността на А транзитивно определя стойността на С (чрез В)

или

стойността на С е транзитивно зависима от стойността на А (чрез В).



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

Фигура 11-2 представя таблица с транзитивна зависимост между полето EmpID и полетата за отдела. Логиката е следната:



  • EmpID определя DepartmentID

  • DepartmentID определя Department

По този начин EmpID транзитивно определя Department.

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


1.6.3.Мулти-стойностни (multi-valued) зависимости


Мулти-стойностна зависимост (МСЗ) е налице между две полета A и B, когато единична (конкретна) стойност на А е директно асоциирана с две или повече стойности на В.

Мулти-стойностна зависимост се бележи така:



AB

Казваме, че конкретна стойност на А определя множество стойности на В

или

множество стойности на В са функционално зависими от стойност на А.



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

МСЗ са подобни на транзитивните зависимости в смисъл, че тяхното наличие означава, че таблицата представя два или повече обекта. Такава таблица, естествено, е некоректно проектирана и е субект на аномалиите на промените.

Фигура 11-3 представя таблица с МСЗ на ниво поле. Тази таблица съдържа служители и комисии, в които те участват. МСЗ е налице между полетата EmpID и Committees – една стойност на EmpID е асоциирана с една или много стойности на Committees. Въпреки че не е съвсем очевидно, тази таблица представя поне два обекта – служители и комисии, съставени от служители.

Фигура 11-4 представя същата таблица с МСЗ, но на ниво запис. Зависимостта е отново между полетата EmpID и Committees. В този случай, обаче, данните за служителя се повтарят за всяка комисия, в която той участва. Тази таблица отново представя двата обекта – служители и комисии, съставени от служители.



Фигура 11-5 представя таблица с две независими МСЗ – едната е между полетата EmpID и Language, другата е между EmpID и Certificate. Лесно се забелязва се повторението на данните за всеки служител, когато трябва да се регистрира факта, че той владее език или има сертификат.

Тези две зависимости казваме, че са независими една от друга, защото владеенето на английски не е задължително условие, за да бъде служителят разработчик на системи с MS SQL Server 2000. От друга страна сертификатът за Visual Basic 6 не е задължително условие за владеенето на немски език.

Тъй като тази таблица притежава две МСЗ, то лесно се забелязва, че тя представя 3 обекта – служители, езици, които служителите владеят, и сертификати на служителите.

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


1.6.4.JOIN зависимости


JOIN зависимост (JD) съществува в една таблица А, ако всеки запис в таблицата може да бъде реконструиран от SQL JOIN операция, която съединява отново всички таблици, създадени при нейната декомпозиция. Това твърдение трябва да е истина за всички съществуващи записи в А към момента на нейната декомпозиция и за всеки валиден запис, който би могъл да бъде въведен преди декомпозицията й. Записи, добавени в декомпозираните таблици, трябва да могат да формират валиден запис за А, когато те бъдат обединени чрез JOIN. Освен това, никакви записи не трябва да бъдат изгубени и никакви фалшиви да бъдат добавени при тази декомпозиция.

Можем да кажем, че таблицата на фигура 11-6 има JOIN зависимост, защото тя може да бъде декомпозирана на по-малки таблици (това не означава, че задължително трябва да бъде декомпозирана) – една за статуса на продавачите (фиг. 11-7) и една за данните на самите продавачи (фиг. 11-8).





Поради наличието на JD трябва да можем да изпълним следната заявка (фиг. 11-9), която да създаде наново оригиналната таблица Vendor, като при този процес не трябва да има загуба на данни нито поява на фалшиви записи.



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



Каталог: sites -> default -> files
files -> Образец №3 справка-декларация
files -> Р е п у б л и к а б ъ л г а р и я
files -> Отчет за разкопките на праисторическото селище в района на вуз до Стара Загора. Аор през 1981 г. ХХVІІ нац конф по археология в Михайловград, 1982
files -> Медии и преход възникване и развитие на централните всекидневници в българия след 1989 година
files -> Окръжен съд – смолян помагало на съдебния заседател
files -> Семинар на тема „Техники за управление на делата" 18 19 юни 2010 г. Хисар, Хотел „Аугуста спа" Приложение
files -> Чинция Бруно Елица Ненчева Директор Изпълнителен директор иче софия бкдмп приложения: програма
files -> 1. По пътя към паметник „1300 години България

Изтегляне 1.28 Mb.

Сподели с приятели:
1   ...   6   7   8   9   10   11   12   13   14



©obuch.info 2024
отнасят до администрацията
    Начална страница
Автореферат
Анализ
Бизнес-план
Биография
Глава
Диплом
Доклад
Задача
Закон
Занятие
Заседание