Лекция №11
Название лекции: Зависимости и Правила Армстронга.
План:
1. Функциональные зависимости и целостность БД.
2. Тривиальные и нетривиальные зависимости.
3. Замыкание множества зависимостей.
4. Правила АРМСТРОНГА.
1. Функциональные зависимости и целостность БД.
Очевидно, что ФЗ по второму типу существенно меньше, чем по первому. ФЗ фактически является условиями ограничения целостности. Т.о. их необходимо проверять при обновлении данных в СУБД. Пусть множество таких ФЗ обозначается S. Если таких зависимостей много, то их сложно проверить. Т.о. возникает задача получить такое множество Т, которое было бы гораздо меньшего размера, чем исходное множество S. Причём каждая ФЗ из S могла бы быть заменена условиями из Т. Поиск такого множества ФЗ представляет большой практический интерес.
2. Тривиальные и нетривиальные зависимости.
ФЗ тривиальна тогда и только тогда, когда правая часть символической записи данной зависимости является подмножеством левой части. Исключения тривиальных зависимостей сокращает множество ФЗ.
3. Замыкание множества зависимостей.
Из некоторых ФЗ могут быть получены другие ФЗ.
Пример: (A, B)®(C, D) Þ (A, B)®C, (A, B)®D.
Пусть дано некоторое множество функциональных зависимостей S.
Определение: Множество всех ФЗ, которые могут быть получены из данного множества S, называют замыканием множества зависимостей (S+). Чтобы получить множество S+ используют правила вывода функциональных зависимостей (правила АМСТРОНГА).
Пусть А,В,С,D – произвольные подмножества некоторого множества реквизитов отношения R. Запись АВ означает АÈВ (для краткости).
4. Правила Армстронга.
1) Рефлексивность ВÎА=>А→В.
2) Дополнение (А→В)=>АС→ВС.
3) Транзитивность (А→В)Ù(В→С)=>(А→С).
4) Самоопределение (А→А).
5) Декомпозиция (А→ВС)=>(А→В)Ù(А→С).
6) Объединение (А→В)Ù(А→С)=>А→ВС.
7) Композиция (А→В)Ù(С→D)=>(АС→ВD)
Доказательство правил выполняется на основании определения функциональной зависимости. Правила 1..3 называются основными правилами. Они являются необходимыми и достаточными для получения из множества S замыкание множества S+. Для удобства используют правила 4..7, которые называются вспомогательными.
Пример: Пусть R={a,b,c,d,e,f}, где а – номер сотрудника, b – номер отдела, c – номер руководителя, d – номер проекта, e – название отдела, f – доля времени, уделяемая руководителем данному проекту.
S={{a}→{b,c}, {b}→{e}, {c,d}→{e,f}}
Доказать: {a,d}→{f}
Доказательство:
{a}→{b,c}=>{a}→{b}٨{a}→{c}=>{a}→{c}=>{a,d}→{c,d}٨{c,d}→{e,f}=>{a,d}→{e,f}=>{a,d}→{e}٨{a,d}→{f}=>{a,d}→{f}, что и требовалось доказать.
Замечание: Правила Армстронга позволяют получить замыкание множества ФЗ, но не дают алгоритм как это сделать.