Тема_6 (1122348), страница 2

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

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

Кузнецов. Базы данных.18 Проектирование РБДMVD и 4NF (12)MVD, теорема Фейджина, 4NF (6)Теорема ФейджинаПусть имеется переменная отношения r с атрибутами A, B, C (вобщем случае, составными). Тогда r = (r PROJECT {A, B}) NATURALJOIN (r PROJECT {A, C}) в том и только в том случае, когда любогозначения r выполняется MVD A →→ B | CСначала докажем достаточность условия теоремы,т.е., что если для любого значения r выполняется MVD A →→ B | C, то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 через R329.10.2009С.Д.

Кузнецов. Базы данных.19 Проектирование РБДMVD и 4NF (13)MVD, теорема Фейджина, 4NF (7)Пусть a обозначает значение атрибута A в некотором кортеже BR,{b} и {c} – множества значений атрибутов B и C соответственно,взятых из всех кортежей тела BR, в которых значением атрибута Aявляется aТогда очевидно, что в BR1 будут входить все кортежи вида {<A, a>,<B, b>}, где b ∈ {b}, и если некоторый кортеж {<A, a>, <B, b>} входитв BR1 , то b ∈ {b}Аналогичные рассуждения применимы к BR2Следовательно, для данного значения a в BR3 будут входить те итолько те кортежи {<A, a>, <B, b>, <C, c>}, для которых b ∈ {b} и c ∈{c}Но по определению MVD и в BR для данного значения входят те итолько те кортежи {<A, a>, <B, b>, <C, c>}, для которых b ∈ {b} и c ∈{c}Следовательно, R = R3 и достаточность условия теоремы доказана29.10.2009С.Д.

Кузнецов. Базы данных.20 Проектирование РБДMVD и 4NF (14)MVD, теорема Фейджина, 4NF (8)Докажем необходимость условия теоремы, т.е. что если дляпроизвольного значения R переменной отношения rвыполняется соотношениеr = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}),то в нем существует MVD A →→ B | C Другими словами, нам требуется показать, что в BRподдерживается следующее ограничение:IF({<A, a>, <B, b1>, <C, c1>} ∈ BR AND{<A, a>, <B, b2>, <C, c2>} ∈ BR)THEN({<A, a>, <B, b1>, <C, c2>} ∈ BR AND{<A, a>, <B, b2>, <C, c1>} ∈ BR)29.10.2009С.Д. Кузнецов.

Базы данных.21 Проектирование РБДMVD и 4NF (15)MVD, теорема Фейджина, 4NF (9)Действительно, пусть{<A, a>, <B, b1>, <C, c1>} ∈ BR и{<A, a>, <B, b2>, <C, c2>} ∈ BRПредположим, что{<A, a>, <B, b1>, <C, c2>} ∉ BR или{<A, a>, <B, b2>, <C, c1>} ∉ BRЕсли воспользоваться ранее введенными обозначениями, то, очевидно, что{<A, a>, <B, b1>} ∈ BR1 и{<A, a>, <B, b2>} ∈ BR1, а также{<A, a>, <C, c1>} ∈ BR2 и{<A, a>, <C, c2>} ∈ BR2По свойствам операции естественного соединения{<A, a>, <B, b1>, <C, c2>} ∈ BR3 и{<A, a>, <B, b2>, <C, c1>} ∈ BR3Поскольку по условию теоремы R = R3, это противоречит предположению оботсутствии, по крайней мере, одного из этих кортежей в BRТем самым, теорема Фейджина полностью доказана29.10.2009С.Д.

Кузнецов. Базы данных.22 Проектирование РБДMVD и 4NF (16)MVD, теорема Фейджина, 4NF (10)Обсудим теперь, почему и в каком отношении теоремаФейджина является обобщением теоремы ХитаВ соответствии с теоремой Хита, достаточным условиемдекомпозиции без потерь переменной отношения r {A, B, C}на проекцииr PROJECT {A, B} иr PROJECT {A, C}является наличие функциональной зависимости A → BНо поскольку функциональная зависимость являетсячастным случаем многозначной зависимости, то по лемме Фейджина в переменной отношения,удовлетворяющей условию теоремы Хита, имеетсяMVD A →→ B | C, и, следовательно, теорема Хита является следствием теоремы Фейджина29.10.2009С.Д. Кузнецов.

Базы данных.23 Проектирование РБДMVD и 4NF (17)MVD, теорема Фейджина, 4NF (11)Из теоремы же Фейджина следует, что теоремаХита задает только достаточное условиедекомпозиции без потерь, потому чтоиз того, что для произвольного значения R переменнойотношения r выполняется соотношениеr = (r PROJECT {A, B}) NATURAL JOIN(r PROJECT {A, C}),выводится наличие MVD A →→ B | C, но совсем необязательно FD A → BТеорема Фейджина обеспечивает основу длядекомпозиции отношений, удаляющей«аномальные» многозначные зависимости, сприведением отношений в четвертуюнормальную форму29.10.2009С.Д.

Кузнецов. Базы данных.24 Проектирование РБДMVD и 4NF (18)MVD, теорема Фейджина, 4NF (12)Определение 6.2. Четвертая нормальная формаПеременная отношения r находится в четвертой нормальнойформе (4NF) в том и только в том случае, когда она находится вBCNF, и все MVD r являются FD с детерминантами – возможнымиключами отношения rВ сущности, 4NF является BCNF, в которой многозначныезависимости вырождаются в функциональныеПонятно, что отношение СЛУЖ_ПРО_ЗАДАН не находится в 4NF,поскольку детерминант MVD СЛУ_НОМ →→ ПРО_НОМ иСЛУ_НОМ →→ СЛУ_ЗАДАН не является возможным ключом, и этиMVD не являются функциональнымиС другой стороны, отношения СЛУЖ_ПРО_НОМ иСЛУЖ_ЗАДАНИЕ находятся в BCNF и не содержат MVD, отличныхот FD с детерминантом – возможным ключомПоэтому они находятся в 4NF29.10.2009С.Д.

Кузнецов. Базы данных.25 Проектирование РБДЗависимости проекции/соединения 5NF (1)Приведение отношения к 4NF предполагает егодекомпозицию без потерь на две проекции (как ив случае 2NF, 3NF и BCNF)Однако бывают (хотя и нечасто) случаи, когдадекомпозиция без потерь на две проекцииневозможна, но можно произвести декомпозициюбез потерь на большее число проекцийБудем называть n-декомпозируемымотношением отношение, которое может бытьдекомпозировано без потерь на n проекцийДо сих пор мы имели дело с 2декомпозируемыми отношениями29.10.2009С.Д.

Кузнецов. Базы данных.26 Проектирование РБДЗависимости проекции/соединения и 5NF (2)N-декомпозируемые отношения (1)Определение 6.3. Тривиальная многозначнаязависимостьВ переменной отношения r с атрибутами(возможно, составными) A и B MVD A →→ Bназывается тривиальной, если либо A ⊆ B, либоA UNION B совпадает с заголовком отношения rТривиальная MVD всегда удовлетворяетсяПри A ⊆ B она вырождается в тривиальную FDВ случае A UNION B = Hr требования многозначнойзависимости соблюдаются очевидным образом29.10.2009С.Д. Кузнецов.

Базы данных.27 Проектирование РБДЗависимости проекции/соединения и 5NF (3)N-декомпозируемые отношения (2) В отношении СЛУЖ_ПРО_ЗАДАН имеется единственный возможный ключ{СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} и отсутствуют нетривиальные MVD29.10.2009С.Д. Кузнецов. Базы данных.28 Проектирование РБДЗависимости проекции/соединения и 5NF (4)N-декомпозируемые отношения (3) Тело результата естественного соединения проекций RСП и RПС почти совпадаетс телом исходного значения-отношения RСПС, но в нем присутствует один лишнийкортеж, который исчезнет после выполнения заключительного естественногосоединения с проекцией RСС Легко убедиться, что исходное отношение будет восстановлено при любомпорядке естественного соединения трех проекций29.10.2009С.Д.

Кузнецов. Базы данных.29 Проектирование РБДЗависимости проекции/соединения и 5NF (4)Зависимость проекции/соединения (1)Утверждение о том, что значение-отношениеRСПС восстанавливается без потерь путеместественного соединения его проекций RСП, RПСи RСС эквивалентно следующему утверждению:IF({<СЛУ_НОМ, сн>, <ПРО_НОМ, пн>} ∈ BRсп AND{<ПРО_НОМ, пн>, <СЛУ_ЗАДАН, сз>} ∈ BRпс AND{<СЛУ_НОМ, сн>, <СЛУ_ЗАДАН, сз>} ∈ BRсс)THEN{<СЛУ_НОМ, сн>, <ПРО_НОМ, пн>,<СЛУ_ЗАДАН, сз>} ∈ BRспс29.10.2009С.Д. Кузнецов.

Базы данных.30 Проектирование РБДЗависимости проекции/соединения и 5NF (5)Зависимость проекции/соединения (2)Чтобы возможность восстановления без потерь значенияRСПС переменной отношения СЛУЖ_ПРО_ЗАДАН путеместественного соединения значений ее проекций RСП, RПС иRСС существовала при любом допустимом RСПС, длязначений переменной СЛУЖ_ПРО_ЗАДАН должноподдерживаться следующее ограничение:IF({<СЛУ_НОМ, сн1>, <ПРО_НОМ, пн1>, <СЛУ_ЗАДАН, сз2>} ∈ BRспсAND{<СЛУ_НОМ, сн2>, <ПРО_НОМ, пн1>, <СЛУ_ЗАДАН, сз1>} ∈ BRспс AND{<СЛУ_НОМ, сн1>, <ПРО_НОМ, пн1>, <СЛУ_ЗАДАН, сз1>} ∈ BRспс)THEN{<СЛУ_НОМ, сн1>, <ПРО_НОМ, пн1>, <СЛУ_ЗАДАН, сз1>} ∈ BRспс29.10.2009С.Д.

Кузнецов. Базы данных.31 Проектирование РБДЗависимости проекции/соединения и 5NF (6)Зависимость проекции/соединения (3)Это обычное ограничение реального мира, котороедля переменной отношения СЛУЖ_ПРО_ЗАДАНможет быть сформулировано на естественном языкеследующим образом:Если служащий с номером сн участвует в проектепн, и в проекте пн выполняется задание сз, ислужащий с номером сн выполняет задание сз, тослужащий с номером сн выполняет задание сз впроекте пнВ общем виде такое ограничение называетсязависимостью проекции/соединения29.10.2009С.Д. Кузнецов. Базы данных.32 Проектирование РБДЗависимости проекции/соединения и 5NF (7)Зависимость проекции/соединения (4)Определение 6.4.

Зависимость проекции/соединенияПусть задана переменная отношения r, и A, B, …, Zявляются произвольными подмножествами заголовка r(составными, перекрывающимися атрибутами).В переменной отношения r удовлетворяетсязависимость проекции/соединения (Project-JoinDependency – PJD) *(A, B, …, Z) тогда и только тогда,когда любое допустимое значение r можно получитьпутем естественного соединения проекций этогозначения на атрибуты A, B, …, Z29.10.2009С.Д. Кузнецов. Базы данных.33 Проектирование РБДЗависимости проекции/соединения и 5NF (8)Аномалии, вызываемые наличием PJD (1)Предположим, что для переменной отношенияСЛУЖ_ПРО_ЗАДАН выполняется PJD*({СЛУ_НОМ, ПРО_НОМ}, {ПРО_НОМ,СЛУ_ЗАДАН}, {СЛУ_НОМ, СЛУ_ЗАДАН})Наличие такой PJD обеспечивает возможностьдекомпозиции этой переменной отношения натри проекции, но возникает вопрос, зачем этонужно?Чем плохо исходное отношениеСЛУЖ_ПРО_ЗАДАН?Ответ обычный: этому отношению свойственныаномалии обновления29.10.2009С.Д. Кузнецов.

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

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