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

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

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

если атрибут обозначается произвольной латинской буквой, то знак объединения не ставится; запись 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. Ненормализованное отношение СПЧ

ПК	НП	СТС	ТР	ОС
п1	з1, з6		т1	10, 10
п2	з1		т1
п3	з2, з8, з9		т1	10, 5, 5
п4	з2		т2
п5	з3, з8		т2	10, 10

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

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

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

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

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

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

ПК	НП	СТС	ТР	ОС
п1	з1		т1
п1	з6		т1
п2	з1		т1
п3	з2		т1
п3	з8		т1
п3	з9		т1
п4	з2		т2
п5	з3		т2
п5	з8		т2

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

ПК	СТС	ТР		ПК	НП	ОС
п1	с1	т1		п1	з1
п2	с1	т1		п1	з6
п3	с2	т1		п2	з1
п4	с4	т2		п3	з2
п5	с4	т2		п3	з8
				п3	з9
				п4	з2
				п5	з3
				п5	з8

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

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

Ликвидация перечисленных недостатков достигается заменой отношения СПЧ отношениями С (табл. 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. Отношение КФ

ПК	СТС		СТС	ТР
п1	с1		с1	т1
п2	с1		с2	т1
п3	с2		с4	т2
п4	с4
п5	с4

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

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