Главная » SQL, Базы данных » ЗАМЫКАНИЕ МНОЖЕСТВА  ЗАВИСИМОСТЕЙ

0

Как упоминалось выше, из одних функциональных зависимостей могут  следовать другие функциональные зависимости. Например, рассмотрим  приведенную ниже зависимость.

{   S#,    Р#   }  → {   CITY,   QTY   }

Из нее следуют приведенные ниже функциональные зависимости.

{   S#,    Р#   }   →

CITY {   S#,    P#   }

→ QTY

В качестве более сложного примера можно привести переменную отношения R с атрибутами А, в и С, для которых выполняются функциональные зависимости А → в и В → С. Нетрудно заметить, что в этом случае также  выполняется функциональная зависимость А B и  C с, которая называется транзитивной функциональной зависимостью, т.е. с зависит от А транзитивно, или проходя через в.

Множество всех функциональных зависимостей, которые следуют из заданного множества функциональных зависимостей s, называется замыканием множества s и обозначается символом S+ (необходимо учитывать то, что оно не имеет ничего общего с понятием замыкания, которое рассматривается в реляционной алгебре). Из приведенного определения следует, что для решения сформулированной задачи необходимо найти алгоритм вычисления S+  на основе S. Первая попытка решить эту проблему была предпринята в статье Армстронга (Armstrong) [11.2], в которой автор предложил набор правил вывода новых функциональных зависимостей на основе заданных (эти правила также часто называют аксиомами  Армстронга). Эти правила вывода могут формулироваться разными способами, из которых самым простым является следующий. Пусть А, в и С — произвольные подмножества множества атрибутов заданной переменной отношения R. Условимся также, что символическая запись АВ означает объединение множеств А И В. Тогда правила вывода определяются следующим образом.

1.           Правило рефлексивности. Если множество в является подмножеством множества А,

ТО А  →   В.

2.           Правило дополнения. Если А → B, то АС → ВС.

3.           Правило транзитивности. Если А → B и B→C, то А → С.

Каждое из этих трех правил может быть непосредственно доказано на основе определения функциональной зависимости (безусловно, первое из них — это просто само определение тривиальной зависимости). Более того, эти правила являются полными в том смысле, что для заданного множества  функциональных  зависимостей s минимальный набор функциональных зависимостей, которые подразумевают все зависимости из множества S, может быть выведен из ФЗ множества s на основе только этих правил. Они являются также непротиворечивыми, поскольку с их помощью не могут быть выведены никакие дополнительные функциональные зависимости (т.е. зависимости,  которые не обусловлены функциональными зависимостями множества S). Иначе говоря, эти правила могут использоваться для получения замыкания S+.

В целях упрощения задачи практического вычисления замыкания S+, из трех приведенных выше правил можно вывести несколько дополнительных правил. (В дальнейшем предполагается, что D — это еще одно произвольное подмножество множества атрибутов R.)

4.           Правило самоопределения. А → А.

5.           Правило декомпозиции. Если А → ВС, то А → Bи A → C.

6.           Правило объединения. Если А → В И А → С, то А → ВС.

7.           Правило композиции.  Если А → B и С → D, то АС → BD.

Кроме того, Дарвен (Darwen) в своей работе [11.7] доказал следующее правило,  которое он назвал общей теоремой объединения.

8.          Если  А→  B  и C    →  D,  то  А   ∪   ( С В )   →  BD  (здесь   символ   " ∪ " обозначает                                                                                 операцию объединения множеств, а символ "-" — операцию разности множеств).

Название общая теорема объединения указывает на то, что некоторые из перечисленных выше правил могут быть выведены как частные случаи этой теоремы [11.7].

Пример. Пусть дана некоторая переменная отношения R с атрибутами А, В, С, D, E, F и следующими функциональными зависимостями.

А                                        →   ВС В     →   Е CD   

EF

Обратите внимание, что способ записи был немного дополнен (без ущерба для смысла); например,  символы  ВС  означают  множество,  состоящее  из  атрибутов  B  и   C,  хотя раньше они означали объединение B и  C, где B и  C были множествами атрибутов.

Примечание. Если необходимо, то этому примеру можно придать более  конкретный смысл, а именно: А— личный номер сотрудника, в — номер отдела, с — личный номер руководителя  (начальника)  данного  сотрудника,  D—  номер  проекта,  возглавляемого данным руководителем (уникальный для каждого  отдельно взятого руководителя), Е — название отдела, F — количество времени, уделяемое данным руководителем указанному проекту.

Теперь можно показать, что для переменной отношения R выполняется также функциональная зависимость AD → F, которая вследствие этого принадлежит к замыканию заданного множества функциональных зависимостей.

1.  А    → BC    (Дано).

2.  А→ C (Следует из п. 1 согласно правилу декомпозиции).

3. AD   → CD     (Следует из п. 2 согласно правилу дополнения).

4.  CD  → EF                                        (Дано).

5.  AD → EF     (Следует из пп. 3 и 4 согласно правилу транзитивности).

6.  AD → F                                          (Следует из п. 5 согласно правилу декомпозиции).

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии