Функціональні залежності та їх властивості

Нехай R = (U) – схема відносини, U = {A₁, A₂,..., А_т} – безліч атрибутов, X, Y ⊆ U. Кажуть, що Х функціонально визначає Y або що Y функціонально залежить від X і позначають це Х → Y, якщо в будь-якому відношенні R, що є поточним значенням схеми R, не можуть міститися два кортежу, компоненти яких збігаються по всім атрибутам, що належить безлічі X, але не збігаються хоча по одному атрибуту, що належить безлічі Y.

Функціональні залежності виникають різним чином, наприклад, якщо R містить опис набору об'єктів і A₁, A₂,..., А_т – атрибути цього типу об'єктів, а Х – множина атрибутів, що утворюють його ключ, то можна стверджувати, що Х → Y для будь-якого Y ⊆ { A₁, A₂,..., А_т}. Це випливає з того, що кортежі R представляють об'єкти, а об'єкти однозначно ідентифікуються значеннями атрибутів ключа, отже, два кортежу, що збігаються за атрибутами, що належить X, повинні представляти один і той же об'єкт, і тому є одним і тим же кортежем.

Слід зазначити, що функціональні залежності є твердженнями про всі відношення, які можуть бути значеннями схеми R, тобто функціональна залежність – це властивість схеми, а не конкретного екземпляра відношення. Отже, неможливо, аналізуючи конкретний поточне значення схеми R, визначити, які залежно мають місце для R, в кращому випадку можна стверджувати про деякі залежностях, що вони не мають місця у схемою R. Єдиний спосіб визначення функціональних залежностей для схеми відношення полягає в тому, щоб проаналізувати семантику атрибутів. У цьому сенсі залежності є фактично висловлюваннями про предметної області, вони не можуть бути доведені формальними засобами проектування схем баз даних, хоча, як буде показано нижче, можна виводити нові (не задані явно при описі схеми) залежно з вже заданих.

Нехай задано безліч атрибутів U = { A₁, A₂,..., А_n} і деякий безліч функціональних залежностей F, записаних у вигляді пар підмножин (X, Y), X, Y ⊆ U, таких, що X → Y; відповідну схему відношення будемо записувати у вигляді R = (U, F). Кажуть, що залежність A → B логічно випливає з F, якщо для кожного екземпляра відношення R зі схемою R, що задовольняє залежностей F, виконується також залежність A → B. Наприклад, легко показати, що якщо X → Y і Y → Z, то X → Z.

Нехай F⁺ означає замикання F, тобто множина всіх функціональних залежностей, які логічно випливають з F (включаючи, звичайно, саме F); F при цьому називають системою утворюючих структури функціональних залежностей. Якщо F⁺ = F, то F називають замкнутим безліччю залежностей. Тепер розглянемо задачу пошуку залежностей, які логічно випливають із заданого набору F.

Як показав Армстронг, сукупність всіх пар (X, Y), таких, що X, Y ⊆ U і X → Y, утворює структуру функціональних залежностей відношення R, яка характеризується наступним набором аксіом, які називаються аксіомами Армстронга:

1) якщо X ⊇ Y, то X → Y (рефлексивність);

2) якщо X → Y і W ⊇ Z, то X ∪ W → Y ∪ Z (продовження);

3) якщо X → Y і Y → Z, то X → Z (транзитивність).

Легко бачити, що аксіоми 2) і 3) можуть бути об'єднані в одну аксіому:

4) якщо X → Y і Y ∪ W → Z, то X ∪ W → Z (псевдотранзитивность).

Корисні також такі властивості, що випливають із 1)-3):

5) якщо X → Y і X → Z, то X → Y ∪ Z (адитивність);

6) якщо X → Y і Z ⊆ Y, то X → Z (декомпозиція).

Аксіоми Армстронга можна розглядати як правила виводу, які дозволяють виводити функціональні залежності, які логічно випливають із заданого набору залежностей.

Аксіоми Армстронга є надійними і повними, іншими словами, якщо залежність X → Y виведена з F з цим аксіомам, то вона виконується в будь-якому відношенні, в якому виконуються всі залежності F, і навпаки, якщо деяка залежність X → Y не виводиться з F з аксіомам Армстронга, то можна побудувати примірник відносини, для якого виконуються всі залежності F і не виконується залежність X → Y.

Нехай задана схема відношення R = (U, F), X ⊆ U, замиканням множини атрибутів Х щодо набору залежностей F називається множина всіх таких атрибутів A_і ∈ U, що залежність X → A_і виводиться з F з аксіомам Армстронга; замикання Х позначають Х⁺.

Таким чином, Х ⁺– максимальне по включенню підмножина множини U, функціонально залежна від Х при заданому наборі функцій F. Ясно, що залежність (X → Y) ∈ F тоді і тільки тоді, коли Х⁺⊇ Y.

Відзначимо наступні властивості замикань:

1) X⁺ ⊇ X;

2) X ⊇ Y ⇒ X⁺ ⊇ Y⁺;

3) (X⁺)⁺ = X⁺.

Аналогічні властивості мають і замикання наборів функцій.

Обчислення F⁺– досить трудомістка задача, оскільки F+ може бути досить великим, навіть якщо F мало, і може містити порядку 2ⁿ елементів, де n – кількість атрибутів у відношенні. Фактично обчислення F⁺ зводиться до обчислення замикань підмножин атрибутів.

Аксіоми Армстронга не є досить зручними для безпосереднього застосування при обчисленні замикань підмножин атрибутів, і зазвичай використовується описаний нижче алгоритм, його правильність легко обґрунтовується тими ж аксіомами Армстронга. Цей алгоритм вимагає часу пропорційно довжині всіх виписаних залежностей з набору F.

Нехай задана схема R = (U, F) і X ⊂ U, потрібно обчислити Х⁺.

Крок 1: покласти Х⁽⁰⁾: = Х, i: = 0;

Крок 2: знайти ∆ Х^(s+1) – множина всіх таких атрибутів у ∈ U \ X⁽ⁱ⁾, що існує деяка залежність V → W ∈ F, така що Х⁽ⁱ⁾ ⊇ V і y ∈ W;

Крок 3: якщо ∆ Х⁽ⁱ⁺¹⁾= ∅, то Х⁽ⁱ⁾ = Х⁺ і кінець роботи, інакше X: = Х^(і+1) ∪ ∆ X^(і+1), i: = i + l і перейти до кроку 2.

Оскільки безліч атрибутів U звичайно, то алгоритм завжди закінчує роботу за кінцеве число ітерацій.

ПРИКЛАД

Нехай R = (U, F) – схема відношення, де U = {A₁, A₂,..., А₇},

F = {А₁, А₄ → А₂; А₂ → A₃; А₃ → А₄; А₄, А₇ → А₅; А₅ → А₆; А₆ → А₇},

множина Х = {А₃, А₅}.

Потрібно обчислити Х⁺.

Випишемо послідовність дій для кожного етапу.

Х⁽⁰⁾ = (А₃, А₅);

∆ X⁽¹⁾ = {А₄, А₆}, Х⁽¹⁾= {А₃, А₄, А₅, А₆};

∆ Х⁽²⁾ ={А₇}, Х⁽²⁾={А₃, А₄, A₅, А₆, А₇};

∆ X⁽³⁾= ∅, отже, Х⁺ = Х⁽²⁾ = {А₃, А₄, А₅, А₆, А₇}.