Замыкание множества функциональных зависимостей. Аксиомы Армстронга (с доказательством). Расширенный набор правил вывода Дейта (с выводом)

Замыканием множества FD S является множество FD S+, включающее все FD, логически выводимые из FD множества S. Пример: (CN) -> (CName, CZarplata) => CN->CName и CN->CZarplata

Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг. Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD).

· если B содержится в A, то A –> B (рефлексивность);

· если A–> B, то AC –> BC (пополнение);

· если A –> B и B –> C, то A –> C (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при B содержится в A FD A->B является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD AC->BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a), но t1 {BC} <> t2 {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}. Поскольку имеется FD A->B, должно соблюдаться равенство t1 {B} = t2 {B}. Тогда из неравенства (b) следует, что t1 {C} <> t2 {C}, что противоречит наличию тривиальной FD AC->C. Следовательно, предположение об отсутствии FD ACBC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD A->C не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} <> t2 {C}. Но из наличия FD AB следует, что t1 {B} = t2 {B}, а потому из наличия FD B->C следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD A->C не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее, Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

· A –> A (самодетерминированность) – прямо следует из правила (1);

· если A –> BC, то A –> B и A –> C (декомпозиция) – из правила (1) следует, что BC –> B; по правилу (3) A –> B; аналогично, из BC –> С и правила (3) следует A –> C;

· если A –> B и A –> C, то A –> BC (объединение) – из правила (2) следует, что A –> AB и AB –> BC; из правила (3) следует, что A –> BC;

· если A –> B и C –> D, то AC –> BD (композиция) – из правила (2) следует, что AС –> BС и BC –> BD; из правила (3) следует, что AC –> BD;

· если A –> BC и B –> D, то A –> BCD (накопление) – из правила (2) следует, что BС –> BCD; из правила (3) следует, что A –> BCD.

Поиск по сайту: