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 НФ.


 

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

19094. Принципы линейной обработки дискретных сигналов. 258.5 KB
  Лекция № 7. Принципы линейной обработки дискретных сигналов. Линейная обработка дискретных сигналов цифровая обработка цифровая фильтрация – произвольная линейная операция над входными дискретными данными. Дискретный фильтр цифровой фильтр – дискретная сис
19095. Характеристики дискретных (цифровых) фильтров 176 KB
  Лекция № 8. Характеристики дискретных цифровых фильтров. Основными характеристиками стационарных линейных дискретных фильтров являются следующие: импульсная характеристика ; комплексная частотная характеристика ; амплитудночастотная и фазочастот...
19096. Z-преобразование 233 KB
  Лекция № 9. Zпреобразование. Удобным способом анализа дискретных последовательностей является Zпреобразование. При Zпреобразовании разностные уравнения описывающие работу дискретной системы преобразуются в алгебраические уравнения с которыми проще производит
19097. Связь системной функции с частотная характеристикой. Обратное Z-преобразование 214.5 KB
  Лекция № 10. Связь системной функции с частотная характеристикой. Обратное Zпреобразование. Структурную схему дискретной системы можно составить либо по разностному уравнению либо с помощью системной передаточной функции. Применяя Zпреобразование к обеим частям ...
19098. Цифровая обработка сигналов в частотной области. Дискретное преобразование Фурье 198 KB
  Лекция № 11. Цифровая обработка сигналов в частотной области. Дискретное преобразование Фурье. Дискретное преобразование Фурье ДПФ относится к классу основных преобразований при цифровой обработке сигналов. Дискретное преобразование Фурье по возможности вычисляе
19099. Цифровая обработка сигналов в частотной области. Быстрое преобразование Фурье 316.5 KB
  Лекция № 12. Цифровая обработка сигналов в частотной области. Быстрое преобразование Фурье. Нахождение спектральных составляющих дискретного комплексного сигнала непосредственно по формуле ДПФ требует комплексных умножений и комплексных сложений. Так как колич...
19100. Некоторые специальные возможност и Excel 467.55 KB
  После этого появится новое окно, где нужно ввести значения для указанных ячеек. Описанную операцию нужно повторить несколько раз для создания нескольких. Для того, чтобы заполнить ячейки значениями из конкретного сценария
19101. Устойчивость дискретных систем 199 KB
  Лекция № 13. Устойчивость дискретных систем. Линейная дискретная система с постоянными параметрами стационарный фильтр называется устойчивой если при любых начальных условиях и любом ограниченном входном сигнале выходной сигнал также остается ограниченным то е...
19102. Реализация алгоритмов цифровой фильтрации 281 KB
  Лекция № 14. Реализация алгоритмов цифровой фильтрации. Графическим представлением алгоритмов цифровой фильтрации являются структурные схемы. Структурную схему дискретной системы можно составить либо по разностному уравнению либо с помощью системной передаточн...