С.Д. Кузнецов - Основы баз данных (1121716), страница 25
Текст из файла (страница 25)
Если эти множества эквивалентны, удалим г из множества ЗЗ, и в заключение получим множество Я4, которое минимально и эквивалентно исходному множеству ГР З. Пусть, например, имеется отношение г (А, В, с, Р) и задано множествоГОз = (л 8, л вс, лв О, лс )з, в с).Поправилудекомпозиции з эквивалентно множеству з2 (л в, л О, лв О, лс (з, (з с). В детерминанте ГР лс () можно удалить атрибут с, поскольку по правилу дополнения из ГР л с следует л лс; по правилу транзитивности выводится ГО л о, поэтому атрибут с в детерминанте ГО лс о является избыточным. ГР лв с может быть удалена, поскольку может быть выведена из ГР л О (по правилу пополнения из этой ГР выводится лв-дО, а по правилу декомпозиции далее выводится лВ О).
Наконец, ГО л с тоже выводится по правилу транзитивности из ГО л в и в с. Таким образом, мы получаем множество зависимостей (л в, л )з, в-й, которое является минимальным и эквивалентно Я по построению. Определение 6.9. Минимальное покрытие множества ГО Минимальным покрытием множества ГО З называется любое минимальное множество ГР ЗЗ, эквивалентное З.
Конец определения. Поскольку для каждого множества ГО существует эквивалентное минимальное множество ГО, у каждого множества ГО имеется хотя бы одно минимальное покрытие, причем для его нахождения не обязательно находить замыкание исходного множества. Декомпозиция без потерь и функциональные зависимости Как уже отмечалось, в следующей лекции мы будем обсуждать подход к проектированию реляционных баз данных на основе нормализации, т. е. декомпозиции (разбиения путем проецирования) отношения, находящегося в предыдущей нормальной форме, на два или более отношений, удовлетворяющих требованиям следующей нормальной формы.
118 Ф нкционапьные зависимости и декомпозиция без потерь Лекция Б Считаются правильными такие декомпозиции отношения, которые обратимы, т, е, имеется возможность собрать исходное отношение из деком- позированных отношений без потери информации. Такие декомпозиции называются декомпозициями без потерь. Корректные и некорректные декомпозиции отношений. Теорема Хита На рис. б.З приведены две возможные декомпозиции отношения служАЩИЕ ПРОЕктЫ (для экономии места мы сократили и слегка изменили тело отношения из рис. 6.1). сдуадщиа пвоекты Декомпозиция (1).
Отношения спУЩ и сдУ пво Декомпозиция (2). Отношения стплж и здвп пво Рис. б.З. Две возможные декомпозиции отношения СЛУЖАЩИЕ ПРОЕКТЫ 119 Основы баз данных К рс Анализ рис. 6.3 показывает, что в случае декомпозиции (!) мы не потеряли информацию о служащих — про каждого из них можно узнать имя, размер зарплаты, номер выполняемого проекта и имя руководителя проекта. Вторая декомпозиция не дает возможности получить данные о проекте служащего, поскольку Иванов и Иваненко получают одинаковую зарплату; следовательно, эта декомпозиция приводит к потере информации.
Что же привело к тому, что одна декомпозиция является декомпозицией без потерь, а вторая — нет? Заметим, что при проведении декомпозиции мы использовали операцию взятия проекции. Каждое из отношений служ, СПУ пРо и зАРп пРо является проекцией исхолного о~ношения СЛУЖАЩИЕ ПРОЕКТЫ.
В случае декомпозиции (!) отсутствие потери информации означает, что в результате естественного соединения отношений СЛУЖ и СЛУ ПРО мы гарантированно получим отношение, заголовок и тело которого совпадают с заголовком н телом отношения слУжАЩие пРОекты. Следует отметить, что это произойлет для любых допустимых (и согласованных) значений переменных отношений СЛУЖАЩИе пРОЕКтЫ, СЛУЖ и СЛУ ПРО, поскольку у всех этих переменных атрибут слУ ном является возможным ключом. Однако если выполни~ь естественное соединение отношений СЛУ и ЗАРП ПРО, то будет получено отношение, показанное на рис. 6.4. Схема этого отношения, естественно (поскольку соединение — естественное), совпадает со схемой отношения СЛУЖАЩИЕ ПРОЕКТЫ, но в теле появились лишние кортежи, наличие которых и приводит к утрате исходной информации.
Интуитивно понятно, что это происходит потому, что в отношении зАРП пРО отсутствуют функциональные зависимости СЛУ ЗАРП-ПРО гЮМ и СЛУ ЗАРП ПРОЕКТ РУк, но точнее причину потери информации в данном случае мы объясним несколько позже. Корректность же декомпозиции ! следует из теоремы Хита: Теорема Хита. Пусть задано отношение т (А, в, с) (А, в и с, в общем случае, являются составными атрибутами) и выполняется Г!) А-В. Рис. 6.4. Результат естественного соединения отношений СЛУЖ и ЗАРП ПГ'О !го Лекция б Функциональные зависимости и декомпозиция без потерь Тогда » = (» РЕОзест (А, В)) НАТОЕАВ ВОТН (» РЕОтеСТ (А, С)).
Доказательство. Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через »Т) содержатся все кортежи тела отношения». Действительно, пусть кортеж (а, Ь, с) Р». Тогда по определениюоперации взятия проекции (а, Ь) Р (» РРОаеСт (А, В) ) и (а, с) Р (» РЕОдЕСТ (А, С) ). Следовательно, (а, ь, с) Р д Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т. е. что сели кортеж (а, Ь, с) Р »Т„то (а, Ь, с) Р».
Если (а, Ь, с) Р»), то существуют (а, Ь] Р (» РРОдест (А, В)) и (а, с) Р (» РРОдест (А, с)). Последнее условие может выполняться в том и только в том случае, когла существует кортеж (а, )т*, с) Р». Но поскольку выполняется ГП А В, то Ь = Ь* и„следовательно, (а, Ь, с) = (а, Ь*, с). Коиецдоказательства. Для иллюстрации общего случая применения теоремы Хита рассмотрим отношение СЛУжлщИЕ Отделы ЛРОЕКТЫ (Слу ном, слу Отд, ПРО НОН) (рис.6.5).Атрибутслу Отдсодержитномераотделов,вкоторых работают служащие, а пРО ном — номера проектов, в которых служащие Рис. 6.5.
Декомпозиция без потерь по теореме Хита 121 Основы баз данных Курс принимают участие. Каждый служащий работает только в одном отделе, т. е. имеется ГР спу ном слу отд, но один служащий может участвовать в нескольких проектах. В отношении служлщие отделы пРоекты атрибут слУ ном не является возможным ключом, но, как показано на рис. 6.5, наличия ГР спу ном слу отд оказывается достаточно для декомпозиции этого отношения без потерь. Для дальнейшего изложения нам потребуется ввести еще одно определение и сделать пару замечаний. Определение 6.10. Минимально зависимые атрибуты Атрибут в минимально зависит от атрибута А, если выполняется минимальная слева ГР л в. Конец определения.
Например, в отношении служлщие ПРОЕКТЫ выполняются ГР СЛУ НОМ СЛУ ЗЛРП и (СЛУ НОМ, СЛУ ИМЯ)-СЛУ ЗЛРП. Первая ГР является минимальной слева, а вторая — нет. Поэтому слУ злвп минимально зависитотспу ном,адля (слу ном, слу имя) свойствоминимальнойзависимости не выполняется. Диаграммы функциональных зависимостей Далее, для иллюстраций в следующей лекции нам пригодятся диаграммы РР, с помощью которых можно наглядно представлять минимальные множества РР. Например, на рис. 6.6 приведена диаграмма минимального множества ГР отношения СЛУЖАЩИЕ ПРОЕКТЫ.
В левой части диаграммы все стрелки начинаются с атрибута спу ном, который является единственным возможным (и, следовательно, первичным) ключом отношения спужлщие проекты. Обратите внимание на отсутствие стрелки от слу ном к пнзект РУк. Конечно, поскольку слу ном является возможным ключом, должна выполняться и РР СЛУ НОМ ПРОЕКТ РУК. Но эта ГР является транзитивной (через пРО НОМ) Рис.
6.6. Диаграмма минимального множества РР отношения СЛУЖАЩИЕ ПРОЕКТЫ 1гг Функциональные зависимости и декомпозиция без потерь Лекция б и поэтому не входит в минимальное множество ГО. Заметим, что в процессе нормализации, к рассмотрению которого мы приступим в следующей лекции, из диаграмм множества ГР удаляются стрелки, начинающиеся не от возможных ключей. Заключение В этой лекции было введено понятие функциональной зависимости и исследовались важные свойства функциональных зависимостей. Одна из целей состояла в том, чтобы на основе некоторого множества функциональных зависимостей суметь построить минимальное эквивалентное множество функциональных зависимостей. Мы начали обсуждение с понятия замыканий множества функциональных зависимостей и аксиом Амстронга, теоретически позволяющих построить такое замыкание.
Замыкание множества функциональных зависимостей содержит все функциональные зависимости, выводимые из функциональных зависимостей заданного множества. Рассмотренный далее алгоритм построения замыкания множества атрибутов над заданным множеством функциональных зависимостей упрощает задачу, позволяя определить принадлежность заданной функциональной зависимости к замыканию заданного множества функциональных зависимостей без потребности в реальном построении замыкания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
