Тема_5 (1122344), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

е.порождению множества FD, не эквивалентного S22.10.2009С.Д. Кузнецов. Базы данных.31 Проектирование РБДЭлементы теории функциональных зависимостей (21)Базовые определения и утверждения (22)Если считать, чтоединственнымвозможным ключомотношенияСЛУЖАЩИЕ_ПРОЕКТЫявляется атрибут СЛУ_НОМ,то множество FD{СЛУ_НОМ → СЛУ_ИМЯ, СЛУ_НОМ → СЛУ_ЗАРП, СЛУ_НОМ →ПРО_НОМ, ПРО_НОМ → ПРОЕКТ_РУК} будет минимальнымв правых частях FD этого множества находятся множества, состоящиеровно из одного атрибута;каждый из детерминантов тоже является множеством из одногоатрибута, удаление которого, очевидно, недопустимо;удаление каждой FD явно приводит к изменению замыканиямножества FD, поскольку утрачиваемая информация не выводится спомощью аксиом Армстронга22.10.2009С.Д.

Кузнецов. Базы данных.32 Проектирование РБДЭлементы теории функциональных зависимостей (22)Базовые определения и утверждения (21)С другой стороны, множества FD{СЛУ_НОМ → {СЛУ_ИМЯ, СЛУ_ЗАРП},СЛУ_НОМ → ПРО_НОМ,СЛУ_НОМ → ПРОЕКТ_РУК, ПРО_НОМ → ПРОЕКТ_РУК};{СЛУ_НОМ → СЛУ_ИМЯ,{СЛУ_НОМ, СЛУ_ИМЯ} → СЛУ_ЗАРП,СЛУ_НОМ → ПРО_НОМ,СЛУ_НОМ → ПРОЕКТ_РУК,ПРО_НОМ → ПРОЕКТ_РУК};{СЛУ_НОМ → СЛУ_НОМ,СЛУ_НОМ → СЛУ_ИМЯ,СЛУ_НОМ → СЛУ_ЗАРП,СЛУ_НОМ → ПРО_НОМ,СЛУ_НОМ → ПРОЕКТ_РУК, ПРО_НОМ → ПРОЕКТ_РУК}не являются минимальными22.10.2009С.Д. Кузнецов.

Базы данных.33 Проектирование РБДЭлементы теории функциональных зависимостей (23)Базовые определения и утверждения (22)Для первого множества в правой части первойFD присутствует множество из двух элементовДля второго множества удаление атрибутаСЛУ_ИМЯ из детерминанта FD {СЛУ_НОМ,СЛУ_ИМЯ} → СЛУ_ЗАРП не меняет замыканиемножества FDДля третьего множества удаление FDСЛУ_НОМ → СЛУ_НОМ не приводит кизменению замыканияЭти примеры показывают, что для определенияминимальности множества FD не всегдатребуется явное построение замыканияданного множества22.10.2009С.Д.

Кузнецов. Базы данных.34 Проектирование РБДЭлементы теории функциональных зависимостей (24)Базовые определения и утверждения (23)Для любого множества FD S существует (и даже может бытьпостроено) эквивалентное ему минимальное множество SПриведем общую схему построения S- по заданному множеству FD SИспользуя аксиому декомпозиции, мы можем привести множество S кэквивалентному множеству FD S1, правые части FD которого содержаттолько одноэлементные множества (простые атрибуты)Для каждой FD из S1, детерминант L {L1, L2, …, Ln} которой содержитболее одного атрибута, будем пытаться удалять атрибуты Li (i = 1, 2, …, n),получая множество FD S2Если после удаления атрибута Li множество S2 оказываетсяэквивалентным множеству S1, то этот атрибут удаляется, и пробуетсяследующий атрибутНазовем S3 множество FD, полученное путем допустимого удаленияатрибутов из всех детерминантов FD множества S1Для каждой FD f из множества S3 будем проверять эквивалентностьмножеств S3 и S3 MINUS {f}Если эти множества оказываются эквивалентными, удалим f из множестваS3, и в заключение получим множество S4, которое минимально и попостроению эквивалентно исходному множеству FD S22.10.2009С.Д.

Кузнецов. Базы данных.35 Проектирование РБДЭлементы теории функциональных зависимостей (25)Базовые определения и утверждения (24)Пусть, например, имеется переменная отношения r с заголовком {A,B, C, D}, и задано множество FDS = {A → B, A → BC, AB → C, AC → D, B → C}По аксиоме декомпозиции S эквивалентно множеству{A → B, A → C, AB → C, AC → D, B → C}В детерминанте FD AC → D можно удалить атрибут C, посколькуFD AB → C может быть удалена, поскольку может быть выведена изFD A → Cпо аксиоме пополнения из наличия FD A → C следует наличие FD A → AC;по аксиоме транзитивности выводится FD A → D, и поэтомуатрибут C в детерминанте FD AC → D является избыточнымпо аксиоме пополнения из этой FD выводится FD AB → BC,а по аксиоме декомпозиции далее выводится AB → CНаконец, FD A → C тоже выводится по аксиоме транзитивности изFD A → B и B → CТаким образом, мы получаем множество FD {A → B, A → D, B → C},которое является минимальным и эквивалентно S по построению22.10.2009С.Д.

Кузнецов. Базы данных.36 Проектирование РБДЭлементы теории функциональных зависимостей (26)Базовые определения и утверждения (25)Определение 5.9. Минимальное покрытиемножества FDМинимальным покрытием множества FD Sназывается любое минимальное множество FD S1,эквивалентное SПоскольку для каждого множества FD существуетэквивалентное минимальное множество FD,у каждого множества FD имеется хотя бы одноминимальное покрытие,причем для его нахождения не обязательно находитьзамыкание исходного множества22.10.2009С.Д. Кузнецов. Базы данных.37 Проектирование РБДЭлементы теории функциональных зависимостей (27)Декомпозиция без потерь и функциональные зависимости (1)Далее мы будем обсуждать подход кпроектированию реляционных баз данных наоснове нормализации,Считаются правильными такие декомпозицииотношения, которые являются обратимыми,т.

е. декомпозиции (разбиения путем проецирования)отношения, находящегося в предыдущей нормальнойформе, на два или более отношений, удовлетворяющихтребованиям следующей нормальной формыт. е. имеется возможность собрать исходное отношение издекомпозированных отношений без потери информацииТакие декомпозиции называются декомпозициямибез потерь22.10.2009С.Д. Кузнецов. Базы данных.38 Проектирование РБДЭлементы теории функциональных зависимостей (28)Декомпозиция без потерь и функциональные зависимости (2)Две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ22.10.2009С.Д.

Кузнецов. Базы данных.39 Проектирование РБДЭлементы теории функциональных зависимостей (29)Декомпозиция без потерь и функциональные зависимости (3)В случае декомпозиции (1) мы не потерялиинформацию о служащихВторая декомпозиция не дает возможностиполучить данные о проекте служащего, посколькуИванов и Иваненко получают одинаковую зарплатупро каждого из них можно узнать имя, размер зарплаты,номер выполняемого проекта и имя руководителя проектаследовательно, эта декомпозиция приводит к потереинформацииЧто же привело к тому, что одна декомпозицияявляется декомпозицией без потерь, а вторая –нет?22.10.2009С.Д. Кузнецов. Базы данных.40 Проектирование РБДЭлементы теории функциональных зависимостей (30)Декомпозиция без потерь и функциональные зависимости (4)При выполнении декомпозиции мы использовалиоперацию взятия проекцииВ случае декомпозиции (1) отсутствие потериинформации означает, что в результате естественногосоединения значений отношений СЛУЖ и СЛУ_ПРОбудет гарантированно получено значение отношения,Каждое из значений отношений СЛУЖ, СЛУ_ПРО иЗАРП_ПРО является проекцией исходного значенияотношения СЛУЖАЩИЕ_ПРОЕКТЫзаголовок и тело которого совпадают с заголовком и теломзначения отношения СЛУЖАЩИЕ_ПРОЕКТЫЭто произойдет для любых допустимых (исогласованных) значений переменных отношенийСЛУЖАЩИЕ_ПРОЕКТЫ, СЛУЖ и СЛУ_ПРО, поскольку увсех этих переменных атрибут СЛУ_НОМ являетсявозможным ключом22.10.2009С.Д.

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

Базы данных.42 Проектирование РБДЭлементы теории функциональных зависимостей (32)Декомпозиция без потерь и функциональные зависимости (6)Теорема ХитаПусть задана переменная отношения r с заголовком {A, B, C}(A, B и C, в общем случае, являются составными атрибутами),и выполняется FD A → BТогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C})ДоказательствоПусть R – некоторое произвольное значение переменной rОбозначим результат операции R PROJECT {A, B} через R1,результат операции R PROJECT {A, C} через R2,а результат R1 NATURAL JOIN R2 через R3Докажем, что в BR3 содержатся все кортежи, содержащиеся в BRДействительно, пусть кортеж {<A, vA>, <B, vB>, <C, vC>} ∈ BRТогда по определению операции взятия проекции {<A, vA>, <B, vB>} ∈ BR1и {<A, vA>, <C, vC>} ∈ BR2Следовательно, {<A, vA>, <B, vB>, <C, vC>} ∈ BR322.10.2009С.Д.

Кузнецов. Базы данных.43 Проектирование РБДЭлементы теории функциональных зависимостей (33)Декомпозиция без потерь и функциональные зависимости (7)Теперь докажем, что в теле результата естественногосоединения нет лишних кортежей, т. е.

чтоесли кортеж {{<A, vA>, <B, vB>, <C, vC>} ∈ BR3,то {<A, vA>, <B, vB>, <C, vC>} ∈ BRДействительно, если {{<A, vA>, <B, vB>, <C, vC>} ∈ BR3, тосуществуют кортежи {<A, vA>, <B, vB>} ∈ BR1 и{<A, vA>, <C, vC>} ∈ BR2Последнее условие может выполняться в том и только в томслучае, когда существует кортеж {<A, vA>, <B, vB*>, <C, vC>} ∈ BRНо поскольку выполняется FD A → B, то vB = vB*и, следовательно, {<A, vA>, <B, vB>, <C, vC>} = {<A, vA>, <B, vB*>,<C, vC>}22.10.2009С.Д. Кузнецов. Базы данных.44 Проектирование РБДЭлементы теории функциональных зависимостей(34)Декомпозиция без потерь и функциональные зависимости (8) Иллюстрация общего случаяприменения теоремы Хита Атрибут СЛУ_ОТД содержит номераотделов, в которых работают служащие,а ПРО_НОМ – номера проектов, вкоторых служащие принимают участие Каждый служащий работает только водном отделе, т.

е. имеется FDСЛУ_НОМ → СЛУ_ОТД, но одинслужащий может участвовать внескольких проектах Атрибут СЛУ_НОМ не являетсявозможным ключом, но наличия FDСЛУ_НОМ_СЛУ_ОТД оказываетсядостаточно для декомпозиции этогоотношения без потерь22.10.2009С.Д. Кузнецов. Базы данных.45 Проектирование РБДЭлементы теории функциональных зависимостей(35)Декомпозиция без потерь и функциональные зависимости (9)Определение 5.10. Минимально зависимые атрибутыАтрибут B минимально зависит от атрибута A, если выполняетсяминимальная слева FD A → BНапример, в отношенииСЛУЖАЩИЕ_ПРОЕКТЫвыполняютсяFD СЛУ_НОМ → СЛУ_ЗАРПи {СЛУ_НОМ, СЛУ_ИМЯ} →СЛУ_ЗАРППервая FD являетсяминимальной слева, а вторая – нетПоэтому СЛУ_ЗАРП минимально зависит от СЛУ_НОМ, а для{СЛУ_НОМ, СЛУ_ИМЯ} свойство минимальной зависимости невыполняется22.10.2009С.Д. Кузнецов.

Базы данных.46 Проектирование РБДЭлементы теории функциональных зависимостей(36)Декомпозиция без потерь и функциональные зависимости (10)Диаграмма минимальногомножества FD отношенияСЛУЖАЩИЕ_ПРОЕКТЫВ левой части диаграммывсе стрелки начинаются сатрибута СЛУ_НОМ,который являетсяединственным возможным(и, следовательно, первичным) ключом отношенияСЛУЖАЩИЕ_ПРОЕКТЫОтсутствует стрелка от СЛУ_НОМ к ПРОЕКТ_РУККонечно, поскольку СЛУ_НОМ является возможным ключом,должна выполняться и FD СЛУ_НОМ → ПРОЕКТ_РУКНо эта FD является транзитивной (через ПРО_НОМ) ипоэтому не входит в минимальное множество FD22.10.2009С.Д.

Характеристики

Список файлов лекций