ответы к зачёту по Базам Данных (2009), страница 6

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD A->C не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} <> t2 {C}. Но из наличия FD AB следует, что t1 {B} = t2 {B}, а потому из наличия FD B->C следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD A->C не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее, Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

• A –> A (самодетерминированность) – прямо следует из правила (1);

• если A –> BC, то A –> B и A –> C (декомпозиция) – из правила (1) следует, что BC –> B; по правилу (3) A –> B; аналогично, из BC –> С и правила (3) следует A –> C;

• если A –> B и A –> C, то A –> BC (объединение) – из правила (2) следует, что A –> AB и AB –> BC; из правила (3) следует, что A –> BC;

• если A –> B и C –> D, то AC –> BD (композиция) – из правила (2) следует, что AС –> BС и BC –> BD; из правила (3) следует, что AC –> BD;

• если A –> BC и B –> D, то A –> BCD (накопление) – из правила (2) следует, что BС –> BCD; из правила (3) следует, что A –> BCD.

1. Замыкание множества атрибутов на множестве FD. Алгоритм построения. Пример. Польза. Суперключ отношения, его связь с замыканием и FD.

Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Z+ таких атрибутов Y отношения R, что FD Z –> Y входит в S+.

Алгоритм вычисления Z+

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством

FD S = {A –> D, AB –> E, BF –> E, CD –> F, E –> C}. Пусть требуется найти {AE}+ над S.

На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD A –> D и E –> C, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CD –> F, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.

Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Z –> B в замыкание S+. Очевидно, что необходимым и достаточным условием для этого является вхождение составного атрибута B в замыкание Z.

Суперключом отношения R называется любое подмножество K заголовка R, включающее, по меньшей мере, хотя бы один возможный ключ R.

Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD K –> A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K+ совпадает с заголовком R.

1. Покрытие множества FD. Эквивалентные покрытия. Минимальное множество FD. Примеры. Алгоритм построения минимального эквивалентного множества. Минимальное покрытие множества функциональных зависимостей.

Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.

Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+ принадлежит S2+.

Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1+ = S2+.

Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

• правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);

• детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т. е. порождению множества FD, не эквивалентного S;

• удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.

Пример:

Рассмотрим отношение СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК}. Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ->СЛУ_ИМЯ,

СЛУ_НОМ->СЛУ_ЗАРП,

СЛУ_НОМ->ПРО_НОМ,

СЛУ_НОМ->ПРОЕКТ_РУК} будет минимальным.

С другой стороны, множество FD

{СЛУ_НОМ->(СЛУ_ИМЯ, СЛУ_ЗАРП),

СЛУ_НОМ->СЛУ_ИМЯ,

СЛУ_НОМ->СЛУ_ЗАРП,

СЛУ_НОМ->ПРО_НОМ,

СЛУ_НОМ->ПРОЕКТ_РУК} не является минимальными.

Для любого множества FD S существует (и даже может быть построено) эквивалентное ему минимальное множество S.

Алгоритм построения минимального эквивалентного подмножества:

Приведем общую схему построения S- по заданному множеству FD S:

1. Декомпозиция: если А-> ВС, то A->B и A->C , получили новое множество S1.

2. Удаление атрибутов из левой части без изменения замыкания: для каждой FD из S1, детерминант D {D1, D2, …, Dn} которой содержит более одного атрибута, будем пытаться удалять атрибуты Di, получая множество FD S2. Если после удаления атрибута Di S2 эквивалентно S1, то этот атрибут удаляется, и пробуется следующий атрибут. Получили S3.

3. Удаление FD не меняющих S. Для каждой FD f из множества S3 будем проверять эквивалентность множеств S3 и S3 MINUS {f}. Если эти множества эквивалентны, удалим f из множества S3, и в заключение получим множество S4, которое минимально и эквивалентно исходному множеству FD S.

Минимальным покрытием множества FD S называется любое минимальное множество FD S1, эквивалентное S.

1. Корректные и некорректные декомпозиции отношений. Теорема Хита (с доказательством). Минимально зависимые атрибуты.

Считаются правильными такие декомпозиции отношения, которые обратимы, т. е. имеется возможность собрать исходное отношение из декомпозированных отношений без потери информации. Такие декомпозиции называются декомпозициями без потерь.

Рис. 7.3 Две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ

Анализ рис. 7.3 показывает, что в случае декомпозиции (1) мы не потеряли информацию о служащих. Вторая декомпозиция не дает возможности получить данные о проекте служащего, поскольку Иванов и Иваненко получают одинаковую зарплату, следовательно, эта декомпозиция приводит к потере информации. Что же привело к тому, что одна декомпозиция является декомпозицией без потерь, а вторая – нет?

Схема этого отношения, естественно (поскольку соединение – естественное), совпадает со схемой отношения СЛУЖАЩИЕ_ПРОЕКТЫ, но в теле появились лишние кортежи, наличие которых и приводит к утрате исходной информации. Интуитивно понятно, что это происходит потому, что в отношении ЗАРП_ПРО отсутствуют функциональные зависимости СЛУ_ЗАРП->ПРО_НОМ и СЛУ_ЗАРП->ПРОЕКТ_РУК, но точнее причину потери информации в данном случае мы объясним несколько позже. Корректность же декомпозиции 1 следует из теоремы Хита:

Теорема Хита. Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD AB. Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}).

Рис. 7.4. Результат естественного соединения отношений СЛУЖ и ЗАРП_ПРО

Доказательство.

Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через r1) содержатся все кортежи тела отношения r. Действительно, пусть кортеж {a, b, c} принадлежит r. Тогда по определению операции взятия проекции {a, b} принадлежит (r PROJECT {A, B}) и {a, с} принадлежит (r PROJECT {A, С}). Следовательно, {a, b, c} принадлежит r1. Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т. е. что если кортеж {a, b, c} принадлежит r1, то {a, b, c} принадлежит r. Если {a, b, c}- принадлежит r1, то существуют {a, b}, принадлежащее (r PROJECT {A, B}), и {a, с} , принадлежащее (r PROJECT {A, С}). Последнее условие может выполняться в том и только в том случае, когда существует кортеж {a, b*, c}= r. Но поскольку выполняется FD AB, то b = b* и, следовательно, {a, b, c} = {a, b*, c}. Конец доказательства.

Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD AB.

1. Минимальные функциональные зависимости. Аномалии, возникающие из-за наличия неминимальных FD. Пример декомпозиции, решающий проблему. 2НФ.

Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD AB.

Аномалии обновления, возникающие из-за наличия неминимальных FD

Во множество FD отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ входит много FD, в которых детерминантом является не возможный ключ отношения (соответствующие стрелки в диаграмме начинаются не с {СЛУ_НОМ, ПРО_НОМ}, т. е. некоторые функциональные зависимости атрибутов от возможного ключа не являются минимальными). Это приводит к так называемым аномалиям обновления. Под аномалиями обновления понимаются трудности, с которыми приходится сталкиваться при выполнении операций добавления кортежей в отношение (INSERT), удаления кортежей (DELETE) и модификации кортежей (UPDATE). Обсудим сначала аномалии обновления, вызываемые наличием FD

СЛУ_НОМ->СЛУ_УРОВ (эти аномалии связаны с избыточностью хранения значений атрибутов СЛУ_УРОВ и СЛУ_ЗАРП в каждом кортеже, описывающем задание служащего в некотором проекте).

1. Добавление кортежей. Мы не можем дополнить отношение СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ данными о служащем, который в данное время еще не участвует ни в одном проекте (ПРО_НОМ является частью первичного ключа и не может содержать неопределенных значений). Между тем часто бывает, что сначала служащего принимают на работу, устанавливают его разряд и размер зарплаты, а лишь потом назначают для него проект.

2. Удаление кортежей. Мы не можем сохранить в отношении СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ данные о служащем, завершившем участие в своем последнем проекте (по той причине, что значение атрибута ПРО_НОМ для этого служащего становится неопределенным). Между тем характерна ситуация, когда между проектами возникают перерывы, не приводящие к увольнению служащих.

3. Модификация кортежей. Чтобы изменить разряд служащего, мы будем вынуждены модифицировать все кортежи с соответствующим значением атрибута СЛУ_НОМ. В противном случае будет нарушена естественная FD СЛУ_НОМ->СЛУ_УРОВ (у одного служащего имеется только один разряд).

Возможная декомпозиция

Для преодоления этих трудностей можно произвести декомпозицию переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ на две переменных отношений – СЛУЖ {СЛУ_НОМ, СЛУ_УРОВ, СЛУ_ЗАРП} и СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}. На основании теоремы Хита эта декомпозиция является декомпозицией без потерь, поскольку в исходном отношении имелась FD {СЛУ_НОМ, ПРО_НОМ}->СЛУ_ЗАДАН.