Аксіоми Армстронга — множина аксіом (або, точніше, правил висновування), що використовуються для висновування всіх функціональних залежностей у реляційній базі даних. Їх розробив у своїй газетній статті 1974 року. Аксіоми правильні в генеруванні тільки функціональних залежностей у замиканні множини функціональних залежностей (позначеному ), коли застосовані до цієї множини (позначеній ). Також вони повні в тому, що повторне застосування цих правил генеруватиме всі функціональні залежності в замиканні .
Формальніше, нехай позначає реляційну схему над множиною атрибутів зі множиною функціональних залежностей . Скажемо, що функціональна залежність логічно слідує з , і позначимо це , якщо й тільки якщо для кожного примірника із , що задовольняє функціональні залежності в , також задовольняє . Позначимо множину всіх функціональних залежностей, які логічно слідують із .
Більше того, з повагою до множини правил висновування , скажемо, що функціональна залежність є похідною з функціональних залежностей у за множиною правил висновування , і позначимо це , якщо й тільки якщо можна отримати шляхом повторного застосування правил висновування в до функціональних залежностей у . Позначимо множину всіх функціональних залежностей, які є похідними від за правилами висновування в .
Тоді множина правил висновування правильна, якщо й тільки якщо має місце наступне:
інакше кажучи, ми не можемо вивести за допомогою функціональні залежності, які логічно не слідують з . Множину правил висновування називають повною, якщо має місце наступне:
простіше кажучи, ми здатні вивести за всі функціональні залежності, які логічно слідують із .
Аксіоми (первинні правила) Нехай — схема відношення над множиною атрибутів . Надалі позначатимемо літерами , , будь-яку підмножину , а, для стислості, об'єднання двох множин атрибутів та як замість звичайного ; ця нотація є достатньо стандартною в при роботі зі множинами атрибутів.
Аксіома рефлексивності Якщо — множина атрибутів, а — підмножина , то вміщує . Тоді вміщує [] означає, що функціонально визначає .
Якщо , то .
Аксіома доповнення Якщо вміщує , а — множина атрибутів, то вміщує . Це означає, що атрибут у залежностях не змінює основних залежностей.
Якщо , то для будь-якого .
Аксіома транзитивності Якщо вміщує , а вміщує , то вміщує .
Якщо та , то .
Додаткові (другорядні) правила Ці правила можуть виводитися від вищенаведених аксіом.
Декомпозиція Якщо , то та .
Доведення 1. (Дано) 2. (Рефлексивність) 3. (Транзитивність 1 і 2)
Композиція Якщо та , то .
Доведення 1. (Дано) 2. (Дано) 3. (Доповнення 1 і A) 4. (Декомпозиція 3) 5. (Доповнення 2 і X) 6. (Декомпозиція 5) 7. (Об'єднання 4 і 6)
Об'єднання (нотація) Якщо та , то .
Псевдо-транзитивність Якщо та , то .
Доведення 1. (Дано) 2. (Дано) 3. (Доповнення 1 і Z) 4. (Транзитивність 3 і 2)
Самовизначення для будь-якої . Це слідує прямо з аксіоми рефлексивності.
Екстенсивність Наступна властивість є особливим випадком доповнення, коли .
Якщо , то .
Екстенсивність може замінити доповнення як аксіому в сенсі, що доповнення може бути доведене з екстенсивності разом з іншими аксіомами.
Доведення 1. (Рефлексивність) 2. (Дано) 3. (Транзитивність 1 і 2) 4. (Екстенсивність 3) 5. (Рефлексивність) 6. (Транзитивність 4 і 5)
Відношення Армстронга Дано множину функціональних залежностей , відношення Армстронга — відношення, яке задовольняє всім функціональним залежностям у замиканні й тільки цим залежностям. На жаль, мінімальний розмір відношення Армстронга для даної множини залежностей може бути експоненційною функцією від кількості атрибутів у залежностях, які розглядаються.
Примітки
Посилання