Інформаційні технології та інформаційні системи

Аксіоми Армстронга

Функціональна залежність: RÌD1´D2, d1ÎD1, imRd1 –1 елемент.

Якщо реляція бінарна, то функціональна залежність має таке визначення: довільне значення першого атрибуту (його образ) складається з одного елементу.

Узагальнене поняття ФЗ на випадок n-арної реляції:

Нехай RÌD1´...´Dn, n³2, R(AR), M1, M2 ÍAR, тоді "r1ÎR[M1], "r2ÎR[M2] r1tRr2Û$rÎR1, r1 = r[M1] Ù r2=r[M2].

R.M1®R.M2 – означає, що атрибути списку М1 функціонально визначають список М2

R.M1«R.M2 - взаємооднозначність.

Тепер реляції можна розглядати у вигляді (b(AR), f R), де b(AR) - булеан всіх імен атрибутів, f R – структура функціональних залежностей.

Нехай R – система властивостей функціональних залежностей реляції.

Перша система аксіом (випливає з визначення ФЗ).

· R1.”Проективність”. М1, М2 – множини атрибутів деяких реляцій. М1 Ê М2=> М1®М2

· R2. Транзитивність. М1®М2 & М2®М3 => М1®М3

· R3. Монотонність. М1®М2 => (М1ÈМ3)®(М2ÈМ3)

Будемо казати, що пара множин М1, М2 більша або рівна парі множин М3, М4, якщо

(М1, М2) ³ (М3, М4) <=> M1ÍM3 & M2ÊM4 " MÎb(R).

Аксіоми Армстронга.

· Р1. Рефлексивність. М1®М2

· Р2. Транзитивність (Р2º R3). М1®М2 & М2®М3 => М1®М3

· Р3. М1®М2 & (М1,М2) ³ (М3,М4) => М3®М4

· Р4. Щось на зразок монотонності (псевдомонотонність). М1®М2 & М3®М4 => М1ÈМ2®М2ÈМ4

Теорема: Р еквівалентна R.

Інформаційні технології та інформаційні системи