Функциональная зависимость (программирование)

31.12.2020

Функциональная зависимость — бинарное отношение между множествами атрибутов данного отношения и является, по сути, связью типа «один ко многим». Её использование обусловлено тем, что она позволяет формально и строго решить многие проблемы.

Функциональная зависимость — концепция, лежащая в основе многих вопросов, связанных с реляционными базами данных, включая, в частности, их проектирование.

Определения

Функциональная зависимость

Пусть дано отношение r {displaystyle r} со схемой (заголовком) R {displaystyle R} , A {displaystyle A} и B {displaystyle B} — некоторые подмножества множества атрибутов отношения r {displaystyle r} . Множество B {displaystyle B} функционально зависит от A {displaystyle A} тогда и только тогда, когда каждое значение множества A {displaystyle A} связано в точности с одним значением множества B {displaystyle B} . Обозначается A → B {displaystyle A o B} .

Другими словами, если два кортежа совпадают по значениям в A {displaystyle A} , то они совпадают и по значениям в B {displaystyle B} .

r ( R ) ,   A ⊆ R ,   B ⊆ R {displaystyle rleft(R ight), Asubseteq R, Bsubseteq R} ( A → B ) ⇔ ( ( ∀ t 1 , t 2 ∈ r : t 1 ( A ) = t 2 ( A ) ) ⇒ ( t 1 ( B ) = t 2 ( B ) ) ) {displaystyle left(A o B ight)Leftrightarrow left(left(forall {{t}_{1}},{{t}_{2}}in r:{{t}_{1}}left(A ight)={{t}_{2}}left(A ight) ight)Rightarrow left({{t}_{1}}left(B ight)={{t}_{2}}left(B ight) ight) ight)}

В этом случае A {displaystyle A} — детерминант, B {displaystyle B} — зависимая часть.

Функциональная зависимость называется тривиальной, если зависимая часть является подмножеством детерминанта.

( B ⊆ A ) ⇒ ( A → B ) {displaystyle left(Bsubseteq A ight)Rightarrow left(A o B ight)}

Замыкание множества зависимостей

Одни функциональные зависимости могут подразумевать другие функциональные зависимости. Например, функциональная зависимость,

( A → B ) ∧ ( B → C ) ⇒ ( A → C ) {displaystyle left(A o B ight)wedge left(B o C ight)Rightarrow left(A o C ight)} .

Множество S + {displaystyle {{S}^{+}}} всех функциональных зависимостей, которые подразумеваются данным множеством функциональных зависимостей S {displaystyle S} называется замыканием множества S {displaystyle S} .

Замыкание множества атрибутов

Пусть Z {displaystyle Z} — некоторое множество атрибутов отношения r {displaystyle r} , а S {displaystyle S} — множество функциональных зависимостей этого отношения. Замыканием Z + {displaystyle {{Z}^{+}}} множества атрибутов Z {displaystyle Z} в пределах S {displaystyle S} называется такое множество всех атрибутов A i {displaystyle {{A}_{i}}} отношения r {displaystyle r} , что функциональная зависимость Z → A i {displaystyle Z o {{A}_{i}}} является членом замыкания S + {displaystyle {{S}^{+}}} .

r ( R ) ,   S ,   Z ⊆ R ,   A i ⊆ R ,   i = 1 , n ¯ {displaystyle rleft(R ight), S, Zsubseteq R, {{A}_{i}}subseteq R, i={overline {1,n}}} Z + = { A i : ( Z → A i ) ∈ S + } {displaystyle {{Z}^{+}}=left{{{A}_{i}}:left(Z o {{A}_{i}} ight)in {{S}^{+}} ight}}

Неприводимые множества зависимостей

Пусть S 1 {displaystyle {{S}_{1}}} и S 2 {displaystyle {{S}_{2}}} — некоторые множества функциональных зависимостей.

  • Если любая функциональная зависимость из S 1 {displaystyle {{S}_{1}}} входит и в S 2 + {displaystyle {{S}_{2}^{+}}} , то S 2 {displaystyle {{S}_{2}}} называют покрытием множества функциональных зависимостей S 1 {displaystyle {{S}_{1}}} .
  • Если S 2 {displaystyle {{S}_{2}}} — покрытие для S 1 {displaystyle {{S}_{1}}} , а S 1 {displaystyle {{S}_{1}}} — покрытие для S 2 {displaystyle {{S}_{2}}} (то есть S 1 + = S 2 + {displaystyle S_{1}^{+}=S_{2}^{+}} ), то такие множества называются эквивалентными.
  • Множество функциональных зависимостей S {displaystyle S} называется неприводимым тогда и только тогда, когда выполняются следующие условия:
    • В каждой функциональной зависимости зависимая часть содержит только один элемент;
    • Детерминант каждой функциональной зависимости является неприводимым (ни один атрибут не может быть удален из детерминанта без изменения замыкания S + {displaystyle {{S}^{+}}} );
    • Ни одну функциональную зависимость из S {displaystyle S} нельзя исключить без изменения замыкания S + {displaystyle {{S}^{+}}} .
  • Для любого множества функциональных зависимостей существует по крайней мере одно эквивалентное множество, которое является неприводимым. Такое эквивалентное множество называется неприводимым покрытием.

Вычисление замыканий

Правила вывода Армстронга

В 1974 году Вильям Армстронг предложил набор правил вывода новых функциональных зависимостей на основе данных.

Пусть у нас есть отношение r ( R ) {displaystyle rleft(R ight)} и множества атрибутов A , B , C , D ⊆ R {displaystyle A,B,C,Dsubseteq R} . Для сокращения записи вместо X ∪ Y {displaystyle Xcup Y} будем писать просто X Y {displaystyle XY} .

  • Рефлексивность: ( B ⊆ A ) ⇒ ( A → B ) {displaystyle left(Bsubseteq A ight)Rightarrow left(A o B ight)}
  • Пополнение: ( A → B ) ⇒ ( A C → B C ) {displaystyle left(A o B ight)Rightarrow left(AC o BC ight)}
  • Транзитивность: ( A → B ) ∧ ( B → C ) ⇒ ( A → C ) {displaystyle left(A o B ight)wedge left(B o C ight)Rightarrow left(A o C ight)}

Правила вывода Армстронга полны (используя их, можно вывести все остальные функциональные зависимости, подразумеваемые данным множеством) и надежны («лишних» функциональных зависимостей вывести нельзя: выведенная функциональная зависимость справедлива везде, где справедливы исходные функциональные зависимости (из которого она была выведена)).

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

  • Самоопределение: A → A {displaystyle A o A}
  • Декомпозиция: ( A → B C ) ⇒ ( A → B ) ∧ ( A → C ) {displaystyle left(A o BC ight)Rightarrow left(A o B ight)wedge left(A o C ight)}
  • Объединение: ( A → B ) ∧ ( A → C ) ⇒ ( A → B C ) {displaystyle left(A o B ight)wedge left(A o C ight)Rightarrow left(A o BC ight)}
  • Композиция: ( A → B ) ∧ ( C → D ) ⇒ ( A C → B D ) {displaystyle left(A o B ight)wedge left(C o D ight)Rightarrow left(AC o BD ight)}
  • Теорема всеобщего объединения Дарвена: ( A → B ) ∧ ( C → D ) ⇒ ( A ∪ ( C − B ) → B D ) {displaystyle left(A o B ight)wedge left(C o D ight)Rightarrow left(Acup left(C-B ight) o BD ight)}

Теорема: Функциональная зависимость A → B {displaystyle A o B} выводима из данного множества функциональных зависимостей S {displaystyle S} по правилам вывода Армстронга тогда и только тогда, когда B ⊆ A + {displaystyle Bsubseteq {{A}^{+}}} .

Замыкание множества атрибутов

Если применять правила из предыдущего раздела до тех пор, пока создание новых функциональных зависимостей не прекратится само собой, то мы получим замыкание для заданного множества функциональных зависимостей. На практике редко требуется вычислять это замыкание само по себе, чаще всего нам гораздо интереснее узнать, будет ли та или иная функциональная зависимость входить в замыкание. Для этого нам достаточно вычислить замыкание детерминанта. Для этого существует довольно простой алгоритм.

  • Пусть X {displaystyle X} — множество атрибутов, которое в конечном счете станет замыканием.
  • Осуществляем поиск функциональных зависимостей вида B 1 B 2 … B m → C {displaystyle {{B}_{1}}{{B}_{2}}ldots {{B}_{m}} o C} , где B 1 B 2 … B m ⊆ X {displaystyle {{B}_{1}}{{B}_{2}}ldots {{B}_{m}}subseteq X} , а C ⊄ X {displaystyle C ot subset X} . Зависимую часть каждой найденной зависимости добавляем в X {displaystyle X} .
  • Повторяем пункт 2, пока ко множеству X {displaystyle X} будет невозможно добавить атрибуты.
  • Множество X {displaystyle X} , к которому невозможно добавить атрибуты и будет замыканием.
  • Применение

    Проектирование БД

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

    Если I {displaystyle I} является неприводимым покрытием исходного множества функциональных зависимостей S {displaystyle S} , то проверка выполнения функциональных зависимостей из I {displaystyle I} автоматически гарантирует выполнение всех функциональных зависимостей из S {displaystyle S} . Таким образом, задача поиска минимально необходимого набора сводится к отысканию неприводимого покрытия множества функциональных зависимостей, которое и будет использоваться вместо исходного множества.



    Имя:*
    E-Mail:
    Комментарий: