Лекции по теории проектирования баз данных (БД) — страница 5

Для любого множества F-зависимостей G существует некоторое подмножество F, такое, что F является не избыточным покрытием G. Если G не избыточно, то F=G. Для определения не избыточного покрытия множества F- зависимостей G существует алгоритм NONREDUN, который имеет вид: Вход: множество F-зависимостей G. Выход: не избыточное покрытие G. NONREDUN(G) begin F=G for каждая зависимость X -> Y из G do if MEMBER(F-{X->Y],X->Y) then F=F-{X->Y} end return(F) end Пример: Пусть G= {A -> B, B ->

A, B -> C, A -> C}. Результатом работы алгоритма является множество: {A -> B, B -> A, A -> C}. Если бы G было представлено в порядке {A -> B, A -> C, B -> A , B -> C} , то результатом работы алгоритма было бы {A -> B, B -> A, B -> C}. Из примера видно, что множество F-зависимостей G может иметь более одного неизбыточного покрытия. Могут так же существовать неизбыточные покрытия G, не содержащиеся в G. В приведенном примере таким неизбыточным покрытием

будет множество F = {A -> B, B -> A, AB -> C}. Если F-неизбыточное множество F-зависимостей, то в нем нет “лишних” зависимостей в том смысле, что нельзя уменьшить F , удалив некоторые из них. Удаление любой F-зависимости из F приведет к множеству, не эквивалентному F. Однако размер можно уменьшить, удалив некоторые атрибуты F-зависимостей F. Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F-зависимость из F. Атрибут А из R

называется посторонним в X -> Y относительно F, если    и (F - {X -> Y}) {Z -> Y}    Y = AW, Y{X -> W} Иными словами, А - посторонний атрибут, если он может быть удален из правой или левой части X -> Y без изменения замыкания F. Пример. Пусть G = {A -> BC,B -> C,AB -> D}. Атрибут С является посторонним в правой части A -> BC, а атрибут B - в левой части AB -> D. Определение. Пусть F - множество F-зависимостей над R и X -> Y принадлежит F. F-зависимость X -> Y

называется редуцированной слева, если Х не содержит постороннего атрибута А и редуцированной справа, если Y не содержит атрибута А , постороннего для X -> y. Зависимость X -> Y называется редуцированной, если она редуцирована слева и справа и Y Определение. Множество F-зависимостей F называется редуцированным (слева, справа), если каждая F-зависимость из F редуцирована (соответственно слева, справа). Пример. Множество G = {A -> BC, B -> C,

AB -> D} не является редуцированным ни справа, ни слева. Множество G1 = {A -> BC, B -> C, A -> D} редуцировано слева, но не справа, а G2 = {A -> B, B -> C, AB -> D} редуцировано справа, но не слева. Множество G3 = {A -> B, B -> C, A -> D} редуцировано слева и справа, следовательно, поскольку правые части не пусты, редуцировано. Для нахождения редуцированных покрытий используется алгоритм: REDUCE Вход: множество F-зависимостей G. Выход: редуцированное покрытие