18227

Логічне проектування баз даних

Реферат

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

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

Украинкский

2013-07-07

106.5 KB

5 чел.

Логічне проектування баз даних.

Функціональна залежність.

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

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

Спочатку наведемо необхідні формальні означення.

Нехай задано відношення R D1D2 .

Кажуть, що набір атрибутів D1 функціонально визначає набір атрибутів D2, або набір атрибутів D2 функціонально залежить від набору атрибутів D1, якщо для  кожного кортежа d1D1 образ відношення R за цим кортежем   imR d1- 1 елемент.

Якщо R D1D2Dn, n2, R(α2): M1, M2  αR,  де М1, М2 – набори атрибутів,

то  структуру функціональних залежностей реляції можна описати як

(β(α2),R),

де β(α2)-булеан, а бінарне відношення R  визначається таким чином:

r1 R[M1],  r2 R[M2]    r1 R r2    rR ,   r1=r[M1]  r2=r[M2]

Функціональна залежність набору атрибутів M2  від набору атрибутів M1 позначається як

RM1RM2  (M1функціонально визначає M2).

RM1RM2  RM1  RM2  RM2  RM1 

Одним із базових понять є поняття ключа.

Ключі використовуються у файлових системах для доступу до даних на фізичних носіях.

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

Квазіключем (можливим ключем)   Кαк   деякої реляції R називається набір атрибутів,  для якого  виконуються умови :

1) МαR  R.KR.M ( Кожнен атрибут функціонально залежить від К).

2) К´К (власної підмножини)  М  αк: R.K´R.M  (З набору К не може бути видалений жоден атрибут, щоб не порушувалась умова 1).

Інколи приводять трохи інше визначення:

  замість умови 1) ставлять умову 1΄) R.KR.αк , а замість умови 2) ставлять умову

2΄)  ḱК,   k˝ K/ ḱ  R.k´R.k˝

Оскільки у відношенні може існувати більше ніж один ключ, то один з них називають первинним ключем (primary key). Будь-який з можливих ключів може бути первинним. Множина атрибутів, що містить можливий ключ, називається суперключем (superkey).

Атрибути, які входять в який-небудь можливий ключ відношення, називаються ключовими (key attributes),  атрибути, які належать первинному ключу, називаються первинними атрибутами (primary attributes). Решта атрибутів називаються непервинними або вторинними. 

Приклад.

Розглянемо реляційне відношення:   

А1

А2

А3

А4

А5

А6

А7

Тріска

08611

жива

200

400

140

60

Тріска

08611

заморожена

30

50

20

10

Тріска

08611

консерв.

100

75

25

75

Судак

08612

жива

100

150

34

66

Судак

08612

заморожена

150

200

75

75

Судак

08612

консерв.

100

40

35

65

А1 – назва продукції,

А2 – шифр,

А3 – стан,

А4 – факт одержання,

А5 – план,

А6 – одержання  1-го сорту,

А7 – одержання 2-го сорту.

В цій реляції присутні такі функціональні залежності:

R.A1 R.A2

R.(A6,A7)R.A4

R.(A4,A6)R.A7

R.(A4,A7)R.A6

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

По  А1 розмір поля змінюється в широкому діапазоні, по А2  розмір фіксований. А1 більш  інформативний, тобто його семантика вища, ніж на А2. Тому в квазіключ краще взяти А1.

Атрибути А1 і А3 не входять у структуру функціональної залежності. Вони повинні  обовязково входити у квазіключ. З А4, А6, А7 повинні ввійти у ключ А4 і один з А6 або А7. Отже, пропонується, щоб до квазіключа входили атрибути  А1, А3, А4, А5, А6.

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

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

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

Набір атрибутів М2 функціонально повно залежить від М1, якщо

  1.  R.M1  R.M2

2.АМ1 (власної підмножини М) ВМ2  RR

(M2 не залежить функціонально від жодного піднабору АМ1, що не містить M2)

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

Приклад:

Розглянемо схему реляції.

Т

КП

КД

місто

КПМ

Квазіключем є КП і КД, місто - непервинний атрибут, який залежить функціонально від підмножини квазіключа (КП). Розбили реляцію Т на Т1 і Т2. Реляція Т може бути відновлена з 2-х реляцій без втрати інформації.

Т1=Т[КП,М]

  Т2=Т[КД,КП]

Очевидно, що реляція в 2 НФ, якщо:

  1.  всі атрибути первинні або
  2.  кожен квазіключ має один атрибут.

Отже, реляції Т1=Т[КП,М]   та  Т2=Т[КД,КП] перебувають в другій нормальній формі.

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

Як приводити відношення до другої нормальної форми? Цього можна досягти тільки за допомогою розбиття відношення на (принаймні) два інших. При такому розбитті необхідно, щоб були виконані такі умови:

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

Теорема Heath I.Y. (Хіза)

Якщо список атрибутів М1 функціонально визначає список М2, то R можна розкласти на 2 реляції так, що природним зєднанням можна відновити попередню реляцію без втрат.

Природне зєднання відбувається по атрибутам М1.

R.M1  R.M2, тоді R=R[M1  M2] * R[αR\(M2\M1)]

                                                                 M1M2  , де  М2 = αR \ М2

Доведення

Беремо реляцію R [αR\(M2\M1)] і доповнюємо елементами М2, які однозначно визначаються за М1  отримуємо повну реляцію.

 

Користуючись цією теоремою рано чи пізно вийдемо на 2 НФ.

Отже, алгоритм приведення до 2NF наступний. Хай задане відношення R з множиною атрибутів αR. Якщо в R є неповна  функціональна залежність R.М1R.М2 неключового атрибута  М2 від можливого ключа М1, то відношення R розбивається на такі два відношення: R[М1, М2] і R[αR \(M2\M1)].  Якщо результуючі відношення все ще не є в другій нормальній формі, то до них знову застосовується цей алгоритм.

Процес приведення відношень до другої нормальної форми у ряді випадків не є однозначним.

2 НФП (посилена) – без непервинний:

Реляція знаходиться в 2-ій нормальній формі посиленій (2 НФП):

  1.  Знаходиться в 1 НФ
  2.  Кожен атрибут функціонально повно залежить від кожного квазіключа.

Нехай М1 і М2, М3αR, М1М2, М3М2 

М3 транзитивно залежить від М1, якщо R.M1  R.M2 &

                             R.M2  R.M3 &

                                                                               R.M2  R.M1

Зобразимо це графічно:

                                                             М1                                                                                               М3

                                                                                    М2

                                                                            

Реляція знаходиться в 3 НФП, якщо вона в 2 НФП і не має транзитивної залежності атрибутів відносно кожного квазіключа.

Приклад:

А5                А4                   А3

           А1 – шифр міністерства,

А2 – шифр головного управління,

А3 – шифр області,

                   А6 А2                                  А4 – шифр району,

                                                                                                             А5 – шифр підприємства,

                                                                                             А6 – шифр галузі.

                                     А1

 { А5А6А1}

                { А5А2А1} А5 є ключем ієрархічної структури.

                { А5А4А3}

Реляція в 3 НФП, якщо вона не має транзитивної залежності атрибутів відносно кожного квазіключа, а в даному випадку є транзитивні залежності        ця реляція не в 3 НФП.

Є транзитивна залежність А5А3.

Між атрибутами А5, А6, А2 також є транзитивна залежність ({ А5А6А2}, {А5А2А6}).

В { А261} нема транзитивної залежності, оскільки А6А2. Такі структури в логічному проектуванні називаються трикутником (кілька взаємо звязаних вершин).

Щоб привести цю реляцію до 3НФ, за теоремою  Хіза будемо «відсікати» транзитивні залежності, бажано діяти від листочків до кореня. Оптимальною є декомпозиція, у якій  менше реляцій.

Отже, виконуємо спочатку декомпозицію, що позбавляє нас транзитивної залежності А5А4А3:

 R1( А4, А3)  та  Ř1( А1, А2, А4, А56)

В реляції Ř1( А1, А2, А4, А56) залишається транзитивна залежність. Декомпозицію можна виконати двома способами. При проектуванні БД враховуються різні міркування і обирається варіант декомпозиції:

 R2( А2, А6, А1)  та  Ř2(А2, А4, А5).

При цьому ми позбавляємся транзитивної залежності, але втрачаємо функціональну залежність  А5А6, яку ми вважаємо менш важливою.

На практиці зустрічаються різні структури функціональних залежностей. Одна із таких структур – “сонечко”, реляція в 3 НФ:

 

  Непервинні атрибути


Багатозначна залежність.

КВП

Курс

Викладачі

Підручник

програмування

Іванчук

Pascal

програмування

Іванчук

C

програмування

Сидоренко

Pascal

програмування

Сидоренко

C

Функціональної залежності між окремими атрибутами немає, але це не означає, що залежності зовсім немає.

ВС

КЛ

КП

Рік

З/п

ПТ

геометрія

1979

180

ПТ

алгебра

1979

180

ПТ

геометрія

1980

200

ПТ

алгебра

1980

200

СД

математика1

1979

250

СД

математика2

1979

250

СД

математика1

1980

270

СД

математика2

1980

270

Це і є багатозначні залежності, яким потім дали форму 4 НФ.

Нехай Х і У списки атрибутів реляції R, визначимо узагальнене поняття образу

Х,У  αR:   

imR(X,Y)={y | zR  &  z[X]=x  &  z[Y]=y}

Визначимо z = αR \ (XY). Набір атрибутів У багатозначно залежить від набора атрибутів Х  (ХУ), якщо  

(x,z)  XZ,  imR(XZ, Y)  =  imR(X, Y).

За визначенням X   для будь-якої сукупності атрибутів X з R. Більш того, завжди має місце X  Y, якщо R визначено тільки на множині атрибутів  XY. Ці два види багатозначної залежності називаються тривіальними, оскільки вони присутні в будь-яких відношеннях. В інших випадках  багатозначна залежність називається нетривіальною.

 

Очевидно, що будь-яка функціональна залежність є багатозначною, але не навпаки. Проте, функціональна і багатозначна залежність істотно відрізняються. Функціональна залежність X  Y визначається тільки через X і Y, існування ж багатозначної залежності X  Y є властивістю всієї сукупності атрибутів R. 

Легко показати, що в загальному випадку у відношенні R (X, Y, Z) існує багатозначна залежність ХУ в тому і тільки в тому випадку, коли існує багатозначна залежність ХZ. 

У наведеному вище прикладі:

Х – КЛ

У – КП

Z – (рік, з/п)

Образ {ПТ, 1979, 180} є {геометрія, алгебра}

Образ {ПТ} це { геометрія, алгебра}.

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

Реляція знаходиться в 4 НФ, якщо вона знаходиться в 3 НФ і не має нетривіальної багатозначної залежності.

Або:

                R  A B , якщо  A αR +3 НФ  (А - ключ)

Або:

Відношення R знаходиться в четвертій нормальній формі4NF (forth normal form), якщо з існування в ньому нетривіальної багатозначної залежності АВ (В – не порожнє і не є підмножиною А і АС складається не зі всіх атрибутів R ) витікає, що А є ключем відношення.

Теорема Фейджина. Нехай відношення R складається з атрибутів (або множині атрибутів) А, В, С. Залежність А  В має місце в R тоді і лише тоді, коли

R = R[А, B] * R[А, С].

Реляцію можна розбити на підреляції в 4 НФ (кожну нетривіальну на тривіальні).

Наприкінці ці залежності важко знаходити.

Визначення. Відношення R має залежність по з'єднанню (join dependency) щодо множин атрибутів М1, М2,…, Мn,, що позначається як *(М1, М2,…, Мn), якщо воно дорівнює природному зєднанню його проекцій за М1, М2,…, Мn, тобто::

   R = R[М1] * R[М2]*…*R[Мп]

Реляція знаходиться в 5 НФ, якщо вона знаходиться в 4 НФ і не має нетривіальних  залежностей, який дозволяє декомпонувати      , які дозволяють виконувати зєднання без втрат. 

Визначення. Відношення з схемою R знаходиться в п'ятій нормальній формі (fifth normal form – 5NF) тоді і лише тоді, коли  в кожній його нетривіальній залежності за  з'єднанням *(М1, М2,…, Мn )  будь-яка множина Мi – можливий ключ.

Функціональна залежність багатозначна залежність залежність типу 5 НФ.


 

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

37887. ИСПЫТАНИЕ ВЫТЯЖНОЙ ВЕНТИЛЯЦИОННОЙ 223.16 KB
  атериальное обеспечение. Вытяжной вентиляционный шкаф с воздуховодом, оборудованный шторкой для изменения площади рабочего проёма; анемометр крыльчатый АСО-3, секундомер; комбинированный приёмник воздушного давления, микроманометр многопредельный с наклонной трубкой ММН-240(5)-1,0, шумомер ШУМ-1М.
37888. ЛАБОРАТОРНАЯ РАБОТА № 110. 297.5 KB
  4 ИССЛЕДОВАНИЕ МАГНИТНОГО ПОЛЯ НА ОСИ КОЛЬЦЕВОЙ КАТУШКИ Методическое указание к выполнению лабораторной работы по курсу общей физики для студентов инженерно технических специальностей Калининград 2006 1. Цель работы: Исследование магнитного поля на оси катушки: измерить магнитную индукцию в различных точках на оси кольцевой катушки; построить график изменения магнитной индукции вдоль оси катушки; проверить результаты измерения расчётом. Для кольцевой катушки содержащей витков:...
37889. ИССЛЕДОВАНИЕ ЭЛЕКТРИЧЕСКОГО ПОЛЯ ДИПОЛЬНОЙ МОДЕЛИ СЕРДЦА 73 KB
  2 ЛАБОРАТОРНАЯ РАБОТА ИССЛЕДОВАНИЕ ЭЛЕКТРИЧЕСКОГО ПОЛЯ ДИПОЛЬНОЙ МОДЕЛИ СЕРДЦА ЛИТЕРАТУРА: Ремизов А. построение кардиограммы дипольной модели сердца. Будем считать что плечо диполя сердца через равные промежутки времени t в условных единицах последовательно принимает значения l приведенные в таблице. Эти графики будут соответствовать кардиограммам I II III отведений на треугольнике Эйнтховена нашей дипольной модели сердца.
37890. Включение фотоэлектрок Олориметра и порядок работы 225.5 KB
  Поставить выключатель гальванометра в положение. Оптическим клином грубой наводки поставить стрелку гальванометра на “0â€. Оптическим клином грубой и точной наводки установить стрелку гальванометра на “0†точно.
37891. Определение отношения теплоемкостей газа при постоянном давлении и объеме 1.41 MB
  11 Лабораторная работа № 116 Определение отношения теплоемкостей газа при постоянном давлении и объеме Цель работы Изучение закономерностей изменения параметров состояния газа в различных процессах и определение отношения теплоемкостей воздуха при постоянном давлении и объеме. Удельная и молярная теплоемкости газов зависят как от природы газа так и от условий его нагревания.3 Изменение внутренней энергии идеального газа однозначно определяется его начальным и конечным состояниями тогда как совершаемая газом работа зависит от характера...
37892. Определение отношения теплоемкостей газа при постоянном давлении и постоянном объеме резонансным методом 1.34 MB
  12 Лабораторная работа № 119 Определение отношения теплоемкостей газа при постоянном давлении и постоянном объеме резонансным методом 1. Теплоемкость и коэффициент Пуассона газа Для характеристики тепловых свойств вещества наряду с другими величинами используют молярную и удельную теплоемкости. Теплоемкость газа зависит от природы его молекул и от того как происходит его нагревание.1 Внутренняя энергия идеального газа это энергия теплового движения его молекул и атомов в молекулах.
37893. ОПРЕДЕЛЕНИЕ ТЕПЛОТЫ ПАРООБРАЗОВАНИЯ ВОДЫ 115 KB
  12 ЛАБОРАТОРНАЯ РАБОТА № 122 ОПРЕДЕЛЕНИЕ ТЕПЛОТЫ ПАРООБРАЗОВАНИЯ ВОДЫ Цель работы Определение удельной и молярной теплоты парообразования воды при фазовом переходе первого рода по экспериментально полученной зависимости давления насыщенных паров от температуры.11 Полученная формула устанавливает связь между молярной теплотой парообразования воды давлением и температурой водяного пара. Изменяя температуру пара T необходимо построить график зависимости по угловому коэффициенту которого можно определить молярную теплоту парообразования...
37894. ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ ВОЗДУХА КАПИЛЛЯРНЫМ МЕТОДОМ 2.7 MB
  Изучение внутреннего трения воздуха как одного из явлений переноса в газах. При протекании жидкости или газа в узкой прямолинейной цилиндрической трубе капилляре при малых скоростях потока течение является ламинарным т. поток газа движется отдельными слоями которые не смешиваются между собой. Для идеального газа  υТ  2.
37895. ОПРЕДЕЛЕНИЕ МОЛЯРНОЙ МАССЫ И ПЛОТНОСТИ ГАЗА МЕТОДОМ ОТКАЧКИ 140 KB
  10 ЛАБОРАТОРНАЯ РАБОТА № 124 ОПРЕДЕЛЕНИЕ МОЛЯРНОЙ МАССЫ И ПЛОТНОСТИ ГАЗА МЕТОДОМ ОТКАЧКИ 1. Цель работы Ознакомление с одним из методов определения молярной массы и плотности газа. Теоретическая часть Состояние некоторой массы газа определяется значениями трёх параметров: давлением P под которым находится газ его температурой T и объёмом V.1 представляет собой уравнение состояния данной массы газа.