Функциональные зависимости и их свойства

Для объединения множеств атрибутов употребляются следующие обозначения:

если наименование атрибута имеет смысл, то вместо знака объединения ставится один пробел;

если атрибут обозначается произвольной латинской буквой, то знак объединения не ставится; запись XY эквивалентна X Y.

Множество атрибутов Y функционально зависит от множества атрибутов X, где X, Y {A₁,А₂,...,A_n}, если значения атрибутов в X единственным образом определяют значения атрибутов Y. В этом случае говорят, что между множествами атрибутов X и Y существует функциональная зависимость (F-зависимость), или X определяет Y; обозначают F : X Y или просто X Y.

Пример 3.1. Рассмотрим отношение ПОСТАВКИ (ПОСТАВЩИК, ГОРОД, ТОВАР, КОЛИЧЕСТВО). На значения атрибутов этого отношения накладываются следующие ограничения:

1) Осуществлять поставку данного товара в данном количестве из определенного города может только один поставщик;

2) Некоторый поставщик из данного города и в данном количестве может осуществлять поставку только одного товара;

Перечисленные ограничения являются F-зависимостями и их можно записать так:

1) ТОВАР ГОРОД КОЛИЧЕСТВО ПОСТАВЩИК

2) ГОРОД ПОСТАВЩИК КОЛИЧЕСТВО ТОВАР

Пусть R(A₁,А₂,...,A_n) — схема отношения, X и Y — подмножества атрибутов. Будем говорить, что отношение R удовлетворяет F-зависимости X Y, если для любых кортежей t₁,t₂ R из t₁(X)=t₂(X) следует t₁(Y)= t₂(Y). В F-зависимости X Y подмножество X называется левой, а Y — правой частью.

Такая интерпретация F-зависимости является основой алгоритма ЗАВИСИМОСТЬ.

Вход. Отношение R и F-зависимость X Y.

Выход. Истина, если R удовлетворяет X Y, в противном случае — ложь.

Шаг 1. Сортировать отношение R по Х-столбцам так, чтобы собрать кортежи с равными X-значениями.

Шаг 2. Если каждая совокупность кортежей с равными X-значениями имеет также равные Y-значения, то на выходе получаем истину, в противном случае — ложь.

F-зависимостыо X Y на множестве атрибутов А можно считать упорядоченную пару (X,Y), где X,Y A. Тогда множеством всех функциональных зависимостей над А будет L={(X, Y)| X A, Y A}.

Если Y не зависит от X, то записывают X Y. Если X Y и Y X, то X и Y называют эквивалентными или говорят, что между X и Y существует биекция, т. е. X Y.

Пример 3.2. Пусть поставщик осуществляет поставки ТОВАРА, определенное КОЛИЧЕСТВО. Он находится в ГОРОДЕ и определенной СТРАНЕ. Можно сформировать следующие зависимости:

f1: ТОВАР КОЛИЧЕСТВО,

f2: ТОВАР ПОСТАВЩИК,

f3: ПОСТАВЩИК ГОРОД,

f4: ГОРОД СТРАНА,

f5: ТОВАР СТРАНА.

Аксиомы вывода

Для различных состояний отношения R(A) могут существовать разные совокупности F-зависимостей. Интерес представляет выявление множества F-зависимостей F, которым удовлетворяют все допустимые состояния R(A). Для этого нужно знать семантические связи между атрибутами отношения. Такое множество F-зависимостей можно считать заданным в схеме отношения R(A). В подобном случае любое отношение со схемой R(A) должно удовлетворять всем F-зависимостям из F. Данное множество F конечно, так как существует только конечное число подмножеств множества А. Одним из способов его нахождения является использование алгоритма ЗАВИСИМОСТЬ, что требует много времени. Другим способом являются аксиомы вывода — правила, позволяющие на основании данного множества F-зависимостей получить все F-зависимости, которым удовлетворяет отношение R(A). Рассмотрим эти аксиомы.

Пусть X, Y, Z, W — непустые подмножества множества A={A₁,А₂,...,A_n}. Тогда для любого отношения со схемой R(A) справедливы следующие аксиомы вывода.

F1. Рефлексивность: Х Х.

F2. Транзитивность: если X Y и Y Z, то X Z.

F3. Пополнение: если X Y, то XZ Y.

F4. Псевдотранзитивность: если X Y и YZ W, то XZ W.

F5. Аддитивность: если X Y и X Z, то X YZ.

F6. Проективность: если X FZ, то X Y или Х Z.

Рассмотрим сформулированные аксиомы на примере отношения R, включающего атрибуты: X — ТОВАР, У — ПОСТАВЩИК, Z — ГОРОД, W — СТРАНА.

F1. Рефлексивность. Отношение π_X( _X=x(R)) всегда имеет не более одного кортежа. Следовательно, Х Х всегда истинно в R. Например, ТОВАР ТОВАР.

F2. Транзитивность. Пусть t₁ и t₂ — кортежи в R. Если t₁(X) = t₂(X), то t₁(Y) = t₂(Y), а из t₁(Y) = t₂(Y) вытекает t₁(Z) = t₂(Z). Таким образом, если

t₁(X) = t₂(X), то t₁(Z) = t₂(Z), т. е. R удовлетворяет X Z. Например, если ТОВАР ПОСТАВЩИК и ПОСТАВЩИК ГОРОД, то ТОВАР ГОРОД.

F3. Пополнение. Эта аксиома позволяет расширить левую часть F-зависимости. Если R удовлетворяет X Y, то π_Y( _X=x(R)) имеет не более одного кортежа для любого х Х. Если L R, то _XZ=xz(R) _X=x(R) и, следовательно, π_Y( _XZ=xz(R)) π_Y( _X=x(R)). Таким образом, π_Y( _XZ=xz(R)) имеет максимум один кортеж и R должно удовлетворять F-зависимости XZ Y. Например, если ТОВАР ПОСТАВЩИК, то ТОВАР ГОРОД ПОСТАВЩИК.

F4. Псевдотранзитивность. Пусть t₁ и t₂ — кортежи в R. По условию если t₁(X) = t₂(X), то t₁(Y) = t₂(Y), и аналогично, если t₁(YZ) = t₂(YZ), то t₁(W) = t₂(W). Из t₁(XZ) = t₂(XZ) получаем, что t₁(X) = t₂(X). Значит, t₁(Y) = t₂(Y) и, кроме того, t₁(YZ) = t₂(YZ), откуда следует, что t₁(W) = t₂(W). Таким образом, R удовлетворяет XZ W. Например, если ТОВАР ПОСТАВЩИК и ПОСТАВЩИК ГОРОД СТРАНА, то ТОВАР ГОРОД СТРАНА.

F5. Аддитивность. Эта аксиома позволяет объединить две F-зависимости с одинаковыми левыми частями. Из X Y и X Z следует, что π_Y( _X=x(R)) и π_Z( _X=x(R)) имеют не более одного кортежа для любого х Х. Если бы отношение π_YZ( _X=x(R)) имело более одного кортежа, то по крайней мере одно из отношений π_Y( _X=x(R)) или π_Z( _X=x(R)) имело бы более одного кортежа. Таким образом, R удовлетворяет F-зависимости X YZ. Например, если ТОВАР ПОСТАВЩИК и ТОВАР ГОРОД, то ТОВАР ПОСТАВЩИК ГОРОД.

F6. Проективность. Эта аксиома в некоторой степени обратна аксиоме аддитивности. Если R удовлетворяет Х YZ, то π_YZ( _X=x(R)) имеет не более одного кортежа для любого х Х. Так как π_Y(π_YZ( _X=x(R))) = π_Y( _X=x(R)), то π_Y( _X=x(R)) также может иметь не более одного кортежа. Следовательно, R удовлетворяет Х У. Например, если ТОВАР ПОСТАВЩИК ГОРОД, то ТОВАР ПОСТАВЩИК или ТОВАР ГОРОД.

Некоторые аксиомы вывода могут быть получены из других аксиом. Например, транзитивность F2 является частным случаем псевдотранзитивности F4 при Z = . Аксиома F4 выводится из F1...F3 и F5; если X Y и YZ W, то, как следствие, F1, Z Z. Согласно F3 имеем XZ Y и XZ Z. Используя F5, получаем XZ YZ. Наконец, применяя F2, имеем XZ W.

С помощью аксиом F1, F3 и F4 можно вывести аксиомы F2, F5 и F6. Как было сказано, F2 является частным случаем F4. Если X Y и X Z, то из F1 получаем YZ YZ и, дважды применяя F4, сначала получаем XZ YZ, а затем X YZ. Поэтому F5 следует из F1, F3 и F4. Для доказательства F6 предположим, что X YZ. Из F1 имеем Y Y, а из F3 получаем YZ Y. Применение F4 дает X Y.

Таким образом, аксиомы F1, F3 и F4 составляют полное подмножество для F1...F6 и являются независимыми в том смысле, что ни одна из аксиом не может быть получена из двух других. Аксиомы F1, F3 и F4 иногда называют аксиомами Армстронга.

Система аксиом F1...F6 является полной, т.е. путем одно- или многократного применения к F этих аксиом можно получить любую F-зависимость, которая следует из множества F.

Множество функциональных зависимостей F={f₁,f₂,...,f_m}, находится в приведенной канонической форме, если F-зависимости не имеют одинаковых левых частей. Для таких функциональных зависимостей если X_i Y_i и X_i Y_j, то X_i Y_i Y_j. Например, приведенной канонической формой для F={f₁,f₂, f₃} из примера 3.2 будет:

ТОВАР КОЛИЧЕСТВО ПОСТАВЩИК СТРАНА.

Замыкания

Пусть F= {X_i Y_i}, 1≤ i ≤n, — множество функциональных зависимостей. Замыканием множества F называют множество F⁺, содержащее все те зависимости, которые могут быть получены применением к F аксиом Армстронга. Замыкание множества функциональных зависимостей используется для определения биекций и ликвидации избыточности множества функциональных зависимостей.

Пример 3.3. Пусть F = {АВ С, С В} — множество F-зависимостей на R(A, В, С). Тогда F⁺ = {А А, AB А, АС A, АВС А, В В, АВ B, ВС В, ABC В, С С, АС С, ВС С, ABC С, АВ АВ, ABC АВ, АС AC, ABC АС, ВС ВС, ABC ВС, ABC ABC, АВ С, АВ АС, АВ ВС, AВ ABC, С В, С ВС, АС В, АС АВ}.

Вычисление F⁺ для множества зависимостей F является весьма трудоемкой задачей, так как множество зависимостей F⁺ может быть большим, даже если само F мало. Рассмотрим множество F = {A B₁, A B₂,..., A B_n}. Тогда F⁺ включает все зависимости A Y, где Y — подмножество множества {B₁,B₂,...,B_n}. Так как существует 2ⁿ таких подмножеств Y, то даже при небольших n их нелегко перечислить.

Более простым является вычисление замыкания атрибутов множества А относительно множества функциональных зависимостей F. Пусть F — множество функциональных зависимостей на множестве атрибутов U, а X — некоторое подмножество U. Тогда Х⁺ — замыкание X относительно F — есть множество атрибутов А таких, что зависимость Х A может быть выведена из F по аксиомам Армстронга. Замыкание X⁺ позволяет сразу определить, выводится ли зависимость X Y из F по аксиомам Армстронга. Существует следующая лемма.

Утверждение. Функциональная зависимость X Y выводится из аксиом Армстронга тогда и только тогда, когда Y Х⁺.

Рассмотрим алгоритм вычисления замыкания множества атрибутов U относительно множества функциональных зависимостей F.

Вход. Конечные множества: атрибутов U, зависимостей F и атрибутов X U.

Выход. Замыкание Х⁺ множества атрибутов X относительно F.

Вычисляем последовательность множеств атрибутов Х⁽⁰⁾, Х⁽¹⁾,... по следующим правилам.

Шаг 1. Х⁽⁰⁾ есть X.

Шаг 2. Хⁱ⁺¹ есть Xⁱ плюс множество атрибутов А таких, что в F существует некоторая зависимость Y Z, А принадлежит Z и Y X⁽ⁱ⁾ Поскольку Х = Х⁽⁰⁾ Х⁽¹⁾ ... U и U конечно, в итоге достигнем такого i, что X⁽ⁱ⁾ = X⁽ⁱ⁺¹⁾. Отсюда X⁽ⁱ⁾ = X⁽ⁱ⁺¹⁾ =X⁽ⁱ⁺²⁾ =... и поэтому процесс вычисления Х⁺ прекращается, если X⁽ⁱ⁾ = X⁽ⁱ⁺¹⁾.

Пример 3.4. Пусть F состоит из следующих зависимостей:

АВ С, AE G,

ВС D, D EC,

В АЕ, EG K,

а Х=АВ. Используя алгоритм, получаем Х⁽⁰⁾=Х=АВ. Для вычисления Х⁽¹⁾ находим зависимости, которые имеют в левой части А, В или АВ. Во множестве F существуют две зависимости: АВ С и В АЕ. Поэтому присоединяем С и E к Х⁽⁰⁾ получаем Х⁽¹⁾ =АВСЕ. Затем вычисляем Х⁽²⁾ путем поиска левых частей зависимостей F, содержащихся в Х⁽¹⁾. Находим BC D и AE G. Таким образом, Х⁽²⁾=ABCDEG. Далее находим EG K, D G и, наконец, Х⁽³⁾=ABCDEGK — множество всех атрибутов. Следовательно, Х⁽³⁾= Х⁽⁴⁾= ... . Итак, получаем (AB)⁺=ABCDEGK.

Пусть задано отношение R на множестве атрибутов {A₁,А₂,...,A_n}, Множество атрибутов К называется ключом отношения R (первичным ключом), если каждый атрибут A_i {A₁,А₂,...,A_n},, который не входит в К, функционально зависит от К, т. е. К A_i; и никакое подмножество К не удовлетворяет этому свойству. В дальнейшем ключевые атрибуты в схемах отношений будут подчеркиваться.

Пример 3.5. В функциональной зависимости ТОВАР ДАТА КОЛИЧЕСТВО ГОРОД ПОСТАВЩИК ключом является (ТОВАР ДАТА КОЛИЧЕСТВО).

Два множества F-зависимостей F и G над схемой отношения R эквивалентны, F ≡G, если F⁺ = G⁺. Если F ≡G, то F есть покрытие для G.

Пример 3.6. Множества F={A BC, A D, CD E} и G={А ВСЕ, A ABD, CD E} эквивалентны. Множество F не эквивалентно множеству G'={A BCDE}, поскольку зависимость CD E не выводится в G'.

Множество F-зависимостей F неизбыточно, если у него нет такого собственного подмножества F' что F'≡F. Если такое подмножество F' существует, то F избыточно.

Пример 3.7. Множество F={АВ С, А ВС, А В, В С} избыточно, так как есть подмножество F'={A B, B C}, которое эквивалентно F.

Пусть имеется множество функциональных зависимостей F={X_i Y_i}, i = . Множество атрибутов Z_i X_i называют посторонним в X_i, если X_i Z_i Y_i может быть получено в замыкании F⁺.

Пример 3.8. В примере 3.2 комбинация атрибутов ТОВАР и ПОСТАВЩИК определяет атрибут ГОРОД, т. е. f₃ может заменить зависимость

ТОВАР ПОСТАВЩИК ГОРОД.

Из f₂ видно, что атрибут ПОСТАВЩИК с левой стороны является посторонним.

Множество F-зависимостей F называют минимальным, если оно содержит не больше F-зависимостей, чем любое эквивалентное множество F-зависимостей.

Минимальное множество F-зависимостей не может содержать избыточных зависимостей. Таким образом, оно одновременно и неизбыточно.

Пример 3.9. Множество G={A BC, B A, AD E, BD L} неизбыточно, но не минимально, поскольку существует множество F={A BC, B A, AD EL}, которое эквивалентно G и содержит меньшее число F-зависимостей. Множество F является минимальным покрытием G.

При проектировании схем БД для минимального покрытия множества F-зависимостей полезно использовать следующие ограничения:

1) правая часть каждой F-зависимости содержит единственный атрибут;

2) ни для какой F-зависимости Х А в F множество F—(Х А) не эквивалентно F;

3) ни для какой F-зависимости Х А в F и собственного подмножества Z X множества F—(X A) (Z A) и F не эквивалентны.

Пример 3.10. Пусть F состоит из таких F-зависимостей:

AB C, ACD B, CG BD,

C A, D EG, CE AG,

BC D, BE C,

Используя условие 1), получаем

АВ C, D Е, CG B,

С A, D G, CG D,

ВС D, BE C, СЕ A,

ACD В, СЕ G.

Здесь F-зависимость СЕ А избыточна, поскольку она следует из зависимости С А. Подобным образом избыточна F-зависимость CG B, так как из CG D, С А и ACD B получаем CG B. Никакие другие F-зависимости не являются избыточными. Однако ACD B может быть замещена зависимостью CD B, поскольку С А. Таким образом, минимальное покрытие включает следующие F-зависимости:

AB C, CD B, BE C,

C A, D E, CG D,

BC D, D G, CE G.

Другое минимальное покрытие, построенное из F исключением СЕ А, CG D и АСD B, имеет вид

AB C, D E, CG B,

C A, D G, CE G.

B CD, BE C,

Отметим, что эти два минимальных покрытия имеют разное число зависимостей.

Более короткое представление множества F является предпочтительным: во-первых, потому, что от мощности F зависит временная сложность алгоритмов для обработки этого множества; во-вторых, объем используемой памяти и число операций при модификации БД также определяются числом F-зависимостей.

Нормализация отношений

Одной из важных и сложных проблем процесса проектирования реляционных схем БД является выбор оптимальной структуры кортежа отношения. Из множества группировок атрибутов необходимо выбрать наиболее рациональную структуру кортежа, устойчивую при изменении как данных, так и связей между ними.

Процесс нормализации отношений заключается в представлении любых зависимостей между данными в виде отношения в первой — четвертой нормальных формах.

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

Рассмотрим процесс нормализации отношений на примере связей поставщиков и произведенных ими поставок, используя следующие функциональные зависимости:

f₁ : ПК ФС ГРД СТС ТР

f₂ : НП КО ОС

f₃ : ПК НП ОС

f₄ : ТР СТС

В этих зависимостях ПК и ФС — соответственно поставщик и форма собственности; ГРД — город, где располагается головной офис; ТР и СТС — соответственно товар, получаемый от поставщика и статус; НП, КО и СЕ — соответственно номер поставки, количество и стоимость единицы товара; ОС — общая стоимость поставки.

На основании подобных зависимостей можно составить такие схемы отношений:

С(ПК, ФС, ГРД, СТС, ТР),

П(НП, КО, СЕ),

СП (ПК, НП, ОС).

Рассмотрим схему отношения

СПЧ (ПК, НП, СТС, ТР, ОС)

и соответствующее отношение (табл. 3.1). Его первичным ключом является ПК НП, при этом атрибут СТС зависит от атрибута ТР. Отношение СПЧ можно представить в виде схемы (рис. 3.1), где атрибуты СТС и ТР функционально не полностью зависят от первичного ключа и не являются взаимно независимыми.

Таблица 3.1. Ненормализованное отношение СПЧ

Первая нормальная форма

Отношение R находится в первой нормальной форме (1НФ), если все входящие в него атрибуты имеют атомарные (неделимые) значения. Другими словами, значения в доменах отношения не являются ни списками, ни множествами простых

Отношение СПЧ (табл. 3.1) не удовлетворяет этому требованию, и его нужно нормализовать так, чтобы каждый элемент табл. 3.1 был единственным значением. В результате получаем табл. 3.2. При использовании операций запоминания (ВКЛЮЧИТЬ, УДАЛИТЬ, ОБНОВИТЬ) отношение СПЧ (табл. 3.2) имеет следующие недостатки.

ВКЛЮЧИТЬ. Невозможно ввести информацию о поставщике, статусе и товаре, который он поставляет, пока за поставщиком не будет закреплены данные о произведенных поставках. Это связано с тем, что каждый компонент первичного ключа должен иметь значение. В данном случае первичный ключ составляют атрибуты ПК, НП.

Рис. 3.1. Функциональная зависимость в отношении СПЧ

Таблица 3.2. Нормализованное отношение СПЧ

Таблица 3.3. Отношение СТаблица 3.4. Отношение СП

УДАЛИТЬ. При удалении информации об общей стоимости произведенных поставок удаляется и остальная информация, находящаяся в кортеже.

ОБНОВИТЬ. Предположим, схема отношения содержит атрибут ГРД , в котором располагается поставщик. При переезде поставщика в другой город и необходимости изменить значение атрибута ГРД требуется просмотр всего отношения, а не отдельного кортежа, так как для одного поставщика может существовать множество кортежей.

Ликвидация перечисленных недостатков достигается заменой отношения СПЧ отношениями С (табл. 3.3) и СП (табл. 3.4) со схемами С (ПК, СТС, ТР) и СП (ПК, НП, ОС) (рис. 3.2).

Рис. 3.2. Функциональные зависимости в отношениях С (а)и СП (б) связанные с операциями запоминания

ВКЛЮЧИТЬ. Можно ввести в отношение С информацию о поставщике, даже если за ним не закреплены данные о поставках.

УДАЛИТЬ. Можно из отношения СП исключить кортеж, содержащий информацию об общей стоимости произведенных поставок, не удаляя информации о самом поставщике.

ОБНОВИТЬ. Значение атрибута ГРД для данного поставщика будет встречаться лишь в отдельном кортеже отношения С и поэтому требуется лишь одно обновление.

Вторая нормальная форма

Перед тем как ввести эту форму, приведем определения.

Пусть R — схема отношения (с несколькими ключами). Атрибут А, принадлежащий некоторому ключу из R, называют ключевым (главным) в R, в противном случае А — неключевой атрибут. Например, в отношении С ключевой атрибут — ПК, а СТС и ТР — неключевые атрибуты.

Пусть Х А — F-зависимость. Атрибут А частично зависит от X, если А функционально зависит от некоторого подмножества У Х, т. е. У А: Атрибут А полностью зависит от X, если он не зависит от любого подмножества X.

Отношение R находится во второй нормальной форме (2НФ), если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от первичного ключа. Отношения С и СП представлены в 2НФ. Их первичными ключами являются соответственно ПК и ПКНП. Отношение СПЧ не находится в 2НФ.

Сравнение рис. 3.1 и 3.2 показывает, что результатом проведенного преобразования является устранение неполной функциональной зависимости, что и ликвидирует все недостатки. В отношении СПЧ зависимые атрибуты СТС и ТР не определяют общей стоимости всех произведенных поставок. Смешением двух типов информации в одном отношении и объясняются перечисленные выше недостатки.

Отношение, находящееся в 1НФ и не представленное в 2НФ, всегда можно преобразовать в эквивалентную совокупность отношений, представленных в 2НФ. Преобразование заключается в замене отношения совокупностью его проекций, естественное соединение которых дает исходное отношение. При таком преобразовании информация не теряется и процесс является обратимым. Отношение в нашем примере, представленное в 1НФ, а не в 2НФ, имеет составной первичный ключ; любую информацию из исходного отношения можно получить и из преобразованного отношения. Более того, новая структура может содержать данные, которые нельзя представить в исходном отношении (например, информацию о поставщике, не имеюшем совершенных поставок).

Заметим, однако, что отношению, представленному в 2НФ, а не в третьей и четвертой нормальных формах (как отношение СП), присущи недостатки. Так, в отношении С имеется зависимость между атрибутами СТС и ТР, т.е. каждое значение ПК определяет значение СТС, которое в свою очередь определяет значение ТР. Другими словами, существует транзитивная зависимость между атрибутами ПК, СТС и ТР, а это опять приводит к трудностям в выполнении операций запоминания. Рассмотрим недостатки, встречающиеся при выполнении названных операций.

ВКЛЮЧИТЬ. Невозможно указать в отношении С, что некоторое значение ТР определяет значение СТС, если отсутствует значение ПК (т.е. первичный ключ), от которого зависит значение ТР.

УДАЛИТЬ. Удаление кортежа с некоторым значением СТС влечет за собой не только исключение значения ПК, но и того факта, что значение ТР определяет значение СТС.

ОБНОВИТЬ. Имеется множество значений ТР в отношении С и при изменении зависимости между значениями СТС и ТР требуется просмотр всех кортежей этого отношения.

Третья нормальная форма

Ликвидировать перечисленные недостатки, как и ранее, можно, заменив исходное отношение С отношениями СК (табл. 3.5) и КФ (табл. 3.6) со схемами СК(ПК, СТС) и КФ(СТС, ТР) (рис. 3.3). Естественным соединением данных отношений можно получить исходное. В результате преобразования исчезает транзитивная зависимость атрибутов СТС и ТР.

Отношение R находится в третьей нормальной форме (3НФ), если оно представлено в 2НФ и каждый неключевой атрибут нетранзитивно зависит от первичного ключа. Отношения СК и КФ представлены в 3НФ, а отношение С — нет. Отношение в 2НФ всегда можно преобразовать в эквивалентную совокупность отношений в 3НФ.

Из сказанного ранее известно, что этот процесс обратим и, следовательно, никакая информация в процессе преобразования не теряется. Однако отношение в 3НФ может содержать информацию, которую нельзя представить в отношении, находящемся в 2НФ. Например, отношение КФ может содержать кортеж <ВМ ФПМ>, в то время как в исходном отношении информация о зависимости значений ВМ и ФПМ отсутствует, если нет значений ПК, определяющих значение ВМ.

Таблица 3.5. Отношение СК Таблица 3.6. Отношение КФ

Заметим, что если неключевой атрибут частично зависит от ключа, то имеет место и транзитивная зависимость этого атрибута от ключа. Следовательно, схема отношений в 3НФ принадлежит и 2НФ.

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

• ⇐ Назад
• 5
• 6
• 7
• 8
• 9
• 10
• 111213
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• Далее ⇒