С.Д. Кузнецов - Основы баз данных (1121716), страница 30
Текст из файла (страница 30)
Первая МЧ0 означает, что каждому значению атрибута слУ ном соответствует определяемое только этим значением множество значений атрибута про нон. Другими словами, в результате вычисления алгебраического выражения (СПУЖ ПРО НОМ У(НЕВЕ (СПУ НОМ = сн АНВ СПУ ЗАДАН = сз) ) РЕОбЕСТ (ПРО НОМ) для фиксированного допустимого значения сии любого лопустнмого значения сз мы всегда получим одно и то же множество значений атрибута ПРО НОМ.
Аналогично трактуется вторая МЧ0. Определение 8.1. Мпогозпачпая зависимость В переменной отношения т с атрибутами А, в, с (в общем случае, составными) имеется многозначиая зависимость В от А (А В) в том и только в том случае, когда множество значений атрибута В, соответствующее паре значений атрибутов А и С, зависит от значения А и не зависит от значения с. Конец определения. Многозначные зависимости обладают интересным свойством «двойственности», которое демонстрирует следующая лемма.
Лемма Фейджппа В отношении г (А, В, С) выполняется МЧ0 А В в том и только в том случае, когда выполняется МЧ0 А--С. Доказательство достаточности условия леммы. Пусть выполняется МЧ0 А В. Пусть имеется некоторое удовлетворяющее этой зависимоспл значение у„переменной отношения г, а обозначает значение атрибута А в некотором кортеже тела У„, а ()з) — множество значений атрибута в, взятых из всех кортежей тела ("о в которых значением атрибута А является а. Предположим, что для этого значения а МЧ0 А с не выполняется. Это означает, что существуют такое допустимое значение с атрибута С и такое значение (зб ()з), что кортеж <а, Ь, с>~У,.
Но это противоречит наличию МЧ0 А в. Следовательно, если выполняется МЧ0 А В, то выполняется и МЧ0 А С Аналогично можно доказать нсобходимосп условия леммы. Конец доказательства. Таким образом, МЧ0 А- -в и А с всегда составляют пару. Поэтомуобычноихпредставляютвместе вформеА в ( с. г0 является частным случаем МЧ0, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется г0 А В, то выполняется и МЧ0 А в.
' Мы видим, что отношения служ про ном и служ злдлние не содер- "Упражнение по колу лекции. Пусть имеется отношение т с атрибутами л, в, с(в общем случае, составными), в котором сушествует Е(у л в. Что в этом случае можно сказать про зависимость атрибутов л и с") Основы баз данных Курс жат МУО, отличных от ГП, н именно в этом выигрываег декомпозиция из рис. 8.2. Правомочность этой декомпозиции доказывается приведенной ниже теоремой Фейджина, которая является уточнением и обобщением теоремы Хита.
Теорема Фейджииа ПуетЬ ИМЕЕтСя ПЕрЕМЕННая ОтНОШЕНИя с С атрИбутаМИ Л, В, С (В ОбщЕМ случае, составными). Отношение с декомпозируется без потерь на проекции (л, в] и (л, с) тогда н только тогда, когда для него выполня- етсяМУОЛ В ~ С. Долам<ем достаточность условия теоремы. Пусть у, является некоторым допустимым значением переменной отношений г. Пусть а есть значение атрибута л в некотором кортеже тела Р„(ь) — множество значений атрибута в, взятых из всех кортежей тела ~;, в которых значением атрибута л является а, и ( с) — множество значений атрибута С, взятых из всех кортежей тела ('„в которых значением атрибута л является а.
Тогда очевидно, что в тело значения переменной отношения с РВО,УКСТ (Л, В) будут входить все кортежи вида (а, Ь,), где Ь,Е(Ь), и если некоторый кортеж ( а, Ьх ) входит в тело значения переменной отношения г РВОткст (л, в], то Ь,.а(Ь). Аналогичные рассуждения применимы к с РВОвеСт (Л, С). Очевидно, что из этого следует, что при наличии многозначной зависимостил — в ~ Свпеременной отношения с(л, в, С] декомпозиция сна проекции г РВО,)кст (л, в] и г РВОвкст (л, с) является декомпозицией без потерь. Для доказательства необходимости условия теоремы предположим, что декомпозиция переменной отношения с (Л, В, С) на проекции с Рвовкст (л, в] не РВОвкст (л, с) являетсядекомпозициейбезпотерь лля любого допустимого значения Р переменной отношения ж Мы должны показать, что в теле в, значения-отношения ~'„поддерживается ограничение ?Р (<а, Ь„с> ВВ, АНР <а, Ь, с,> <В,-) Тих (<а, Ь,, с,> < В АИР <а, Ь„с,> 6 Вх) Действительно, пусть в в, входят кортежи < а, Ь„с, > и < а, Ь„с,>.
Предположим, что <а, Ь„с,> ~ в, ОВ <а, Ь„с,> е во Но втелозначения переменной отношения с РВОВЕСТ (Л, В) входят кортежи <а, Ь,> и <а, Ь,>, а в тело значения переменной отношения г РВООКСТ (Л, С] — <а, с,> и <а, с,>. Очевидно, что в тело значения естественного соединения г РВОТЕСТ (Л, В) ИАТРВАЬ аО?Н с РВООЕСТ (Л, С) войдугкортежи <а, Ь„с,> и <а, Ь„с,>, и наше предположение об отсутствии по крайней мере одного из этих кортежей в В„противоречит исходному предположению о том, что декомпозиция сна проекции г РВОвкст (л, в] и с РВОТКСТ (Л, С) яапястея дЕКОМПОЗИцИЕй бсэ ПОтЕрЬ.
ТЕМ СаМЫМ, тЕО- рема Фейджина полностью доказана. Конец доказательства. л ц е Дальнейшая нормализация Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей «аномальныеь многозначные зависимости, с приведением отношений в четвертую нормальную форму. Определение 8.2. Четвертая нормальная форма Переменная отношения г находится в четвертой нормальной форме (4ХГ) в том и только в том случае, когда она находится в ВС)ч)Г и все МЛ) г являются ГР с детерминантами — возможными ключами отношения г. Конец определения, В сущности, 4)чГ является ВСХГ в которой многозначные зависимости вырождаются в функциональные (позволим себе на один момент отказаться от сокрашений).
Понятно, что отношение Олуд пвз Зйдлн не находится в 4ХГ, поскольку детерминант МЛ) слу ном- -про нОМ и слу нОм- слу злдлн не является возможным ключом, и эти МЛ) неявляются функциональными. С другой стороны, отношения спуд прО ном и Олух злдлнив находятся в ВСХГ и не содержат МЪ'О, отличных от ГР с детерминантом — возможным ключом. Поэтому они находятся в 4)ч) Г Зависимости проекции/соединения и пятая нормальная форма Приведение отношения к 4ХГ предполагает его декомпозицию без потерь на две проекции (как и в случае 2ХГ ЗХГ и ВСХГ).
Однако бывают (хотя и нечасто) случаи, когда декомпозиция без потерь на две проекции невозможна, но можно произвести декомпозицию без потерь на большее число проекций. Будем называть л-декомпозируемым отношением отношение, которое может быть декомпозировано без потерь на л проекций. До сих пор мы имели дело с 2-декомпозируемыми отношениями. и-декомпозируемме отношения Начнем с еще одного определения. Определение 8.3.
Тривиальная многозначная зависимость В переменной отношения г с атрибутами (возможно, составными) л и в МЛЭ я- в называется тривиальной, если либо 4~В, либо л пнгОн в совпадает с заголовком отношения г. Конец определения. Тривиальная МЛ) всегда удовлетворяется.
При Аыв она вырождается в тривиальную ГР. В случае Л ~йаов В = Нг требования многозначной зависимости соблюдаются очевидным образом. Для примера л-декомпозируемого отношения при л > 2 рассмотрим пятый вариант переменной отношения Олуж пРО золян, в которой имеется единственно возможный ключ (Олу нОм, про ном, слу зйдйн) и отсутствуют нетривиальные МЛЭ. Пример значения переменной отношения приведен на рис. 8.3. 147 Основы баз данных Курс Как показано на рис. 8.3, результат естественного соединения проекций спуж ДРО ном и про ном зАдАн почти совпадает с телом исходного отношения СЛУЖ ПРО ЗАДАН, но в нем присутствует один лишний кортеж, который исчезнет после выполнения заключительного естественного соединения с проекцией служ зАДАние.
Читателям предлагается убедиться, что исходное отношение будет восстановлено при любом порядке естественного соединения трех проекций. Зависимость проекции/соединения Утверждение о том, что тело отношения сдуж ДРО зАДАн восстанавливается без потерь путем естественного соединения его проекций спуд про ном, про ном зАПАн и спуд зАдАние эквивалентно следующему утверждению (тспз, тспн, тпнз и тсз обозначают тела значений переменных отношений служ пго з~длн, служ про ном, пРо ном злд~н н спуж злдАПИЕ соответственно): 1Р (<сн, пн> < тСПН АМР <пн, сз> 6 тПНЗ АМР <сн, сз> С ТОЗЕ тНЕМ -сн, пн, сз> Е тСПЗ Чтобы возможность восстановления без потерь отношения сдуж пРо злдлн путем естественного соединения его проекций СЛУЖ ПРО НОМ, ПРО НОМ ЗАДАН и СЛУЖ ЗАДАНИЕ существовала при любом допустимом значении переменной отношения СЛУЖ ПРО ЗАДАН, должно поддерживаться следующее ограничение: 1Р 1<сны пн,, сз;> Е тСПЗ АНР <сн„ пны сз,> < ТСПЗ АИР <сн,, пнв, сз~> Е ТСПЗ1 ТНЕУ <сн,, пн,, сз,> Е ТСПЗ Это обычное ограничение реального мира, которое для отношения СПУЖ пго злдлнможетбытьсформулированонаесгественном языкеследующим образом: Если служащий с номером сн участвует в проекте пн, и в проекте пнвыполняется задание сз, и служащий с номером сн выполняет задание сз, то служащий с номером сн выполняет задание сз в проекте пн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
