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


 

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

33391. СУ класса PCNC MSH-PС104. Назначение, состав, структура 31.5 KB
  Конструктивно состоит из двух блоков: управления и пультового. Пульт управления имеет цветной плоскопанельный с активной TFT матрицей дисплей 121 мембранную клавиатуру и Flsh память емкостью 32 64 128 Mb. УЧПУ обеспечивает следующие технологические функции: – токарная фрезерная версия ПО â€œMSHKCNCâ€; – G M T коды параметрическое программирование подпрограммы циклы; – графический интерактивный режим разработки УП; – графический модуль отображения траектории движения инструмента; – измерительные циклы; – компенсация люфтов...
33392. СУ класса PCNC MSH-TURBO-M. Назначение, состав, структура 34 KB
  Основные принципы менеджмента включают в себя: принцип научности важно понимать причины несовпадения целей и результатов видеть противоречия между теорией и практикой знать свойства больших систем и методы работы в них; принцип системности и комплексности важно видеть наиболее значимый комплекс взаимосвязанных и взаимообусловленных подсистем входящих в организацию например как в Японии: подсистема пожизненного найма подсистема подготовки на рабочем месте подсистема ротации кадров подсистема репутаций подсистема...
33393. СУ класса PCNC NC-110. Назначение, состав, структура 32 KB
  УЧПУ является многофункциональной СУ и способна управлять станками всех основных типов: токарными фрезерными расточными копировальными шлифовальными а также кузнечнопрессовым оборудованием системами термической лазерной и гидравлической резки деревообрабатывающим оборудованием. УЧПУ NC110 выполнено на базе промышленного компьютера имеющего набор периферийных модулей для управления оборудованием. Для подготовки УЧПУ к управлению оборудованием необходимо выполнить установку параметров и характеристик аппаратных и программных модулей...
33394. СУ класса PCNC «Микрос-12Т». Назначение, состав, структура 31 KB
  УЧПУ Микрос12Т предназначено для модернизации и комплектации токарных станков. УЧПУ построено по архитектуре промышленного компьютера с использованием собственной операционной системы жесткого реального времени. Конструктивно УЧПУ состоит из двух блоков: управления рис. Блочная конструкция УЧПУ позволяет расположить компактный пульт управления близко к зоне обработки детали.
33395. АЛУ ОМК КР1816ВЕ51 30.5 KB
  АЛУ состоит из регистра аккумулятора двух программнонедоступных регистров Т1 и Т2 предназначенных для временного хранения операндов сумматора дополнительного регистра В регистра слова состояния программы ССП схемы десятичной коррекции и схемы формирования признаков. Важной особенностью АЛУ является его способность оперировать не только байтами но и битами. Таким образом АЛУ может оперировать четырьмя типами информационных объектов: булевскими 1 бит цифровыми 4 бита байтными 8 бит и адресными 16 бит.
33396. Признаки регистра ССП КР1816ВЕ51 38.5 KB
  В таблице приводится перечень флагов ССП даются их символические имена и описываются условия их формирования. Формат регистра слова состояния программы ССП Символ Позиция Наименование и назначение флага C PSW.7 Флаг переноса.6 Флаг вспомогательного переноса.
33397. Граф возможных вариантов пересылки … КР1816ВЕ51 31 KB
  Возможны следующие виды пересылки: пересылка в аккумулятор из регистра и пересылка в регистр из аккумулятор; пересылка в аккумулятор прямоадресуемого байта и пересылка по прямому адресу аккумулятора; пересылка в аккумулятор байта из РДП и пересылка в РДП из аккумулятора; пересылка в регистр прямоадресуемого байта и пересылка по прямому адресу регистра; пересылка прямоадресуемого байта по прямому адресу; пересылка в аккумулятор байта из ВПД и пересылка в ВПД из аккумулятора; пересылка в аккумулятор байта из расширенной ВПД и пересылка в...
33398. Структура РПП и ВПП КР1816ВЕ51 28.5 KB
  Организация памяти в микроконтроллере иллюстрируется рисунке Память программ имеет 16битовую адресную шину ее элементы адресуются с использованием счетчика команд PC или инструкций которые вырабатывают 16разрядные адреса. Память программ доступна только по чтению. ОМЭВМ не имеют команд и управляющих сигналов предназначенных для записи в память программ.
33399. Структура РПД и ВПД КР1816ВЕ51 27.5 KB
  Организация памяти в микроконтроллере иллюстрируется рисунке Память данных делится на внешнюю и внутреннюю каждая из них имеет свое пространство адресов. В архитектуре MК51 пространство адресов внутренней памяти данных объединяет все внутренние программно доступные ресурсы. Это пространство размером 256 байт в свою очередь делится на пространство адресов внутреннего ОЗУ резидентная память данных РПД размером 128 байт и пространство адресов регистров специальных функций.