Базы Данных, 15 лекция (от 26 октября)

Материал из eSyr's wiki.

БД 24.10.06

4НФ

Многозначные зависимости ближе всего к функционалам.

Наличие многознач завис в БД обнаружил Рональд Фейджин. Многозначные зависимости обнаруживаются достаточно трудно.

5НФ настолько далека от интуитивного понимая, что лектор не знает примеров, где её хорошо использовать. Во многом она искусственна. Хотя мы увидим, что те ограничение, коотрые порождаются, довольно естественны.

Многознач завис:

Есть отношение СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ., ПРО_НОМ, СЛУ_ЗАДАН}

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

Что ещё делать менеджеру проекта, кроме как посуду мыть.

<COL WIDTH=85*> <COL WIDTH=85*> <COL WIDTH=85*> <THEAD> </THEAD> <TBODY> </TBODY>

СЛУ_НОМ	ПРО_НОМ	СЛУ_ЗАРП
2934	1	A
2934	1	B
2934	2	A
2934	2	B
...
2941	1	A
2941	1	D

Как выглядит ограничение:

Для каждого кортежа ПРО_ЗАДАН должно выполняться ограничпение: IF (<сн, пн₁, сз₁>) принадлежит B_спз and <сн, пн₂, сз₂> принадлежит B_спз then (<сн, пн₁, сз₂>) принадлежит B_спз and <сн, пн₂, сз₁> принадлежит B_спз

Наличие такого рода зависимостей приводит к аномалиям изменений.

Если вдруг менеджер, Котолько только моет посуду, Вдруг научидлся программировать на Джаве, То придётся добавить количество кортежей по количеству проектов.

Понятно, что эти проблемы решаются декомпозицией отношения.

СЛУЖ_ПРО_НОМ:

<COL WIDTH=128*> <COL WIDTH=128*> <THEAD> </THEAD> <TBODY> </TBODY>

СЛУ_НОМ	ПРО_НОМ
2934	1
2934	2
2941	1

Заметим, что было унарное отношение с единственным возмоджным ключом, а стало бинарное с нетривиальной ФЗ. Но это честная бинарная зависимость.

СЛУЖ_ЗАДАН

<COL WIDTH=128*> <COL WIDTH=128*> <THEAD> </THEAD> <TBODY> </TBODY>

СЛУ_НОМ	СЛУ_ЗАДАН
2934	A
2934	B
...
2941	A
2941	D

То, что это декомпозиция правильная, ни из чего не следует.

Почему так, объяснил Фэйджин. Он заметил, что дано отношения с тремя атрибутами, причём мнодество значений третьего зависит от первого и не зависит от второго – ситуация многозначной зависимости. Множество значений второго атрибут зависит от первого, и множество третькего зависит от первого, а друг от друга они никак.

(Служ_ПРО_НОМ WHERE (СЛУ_НОМ=СН and СЛУ_ЗАДАН=СЗ)) PROJECT {ПРО_НОМ}

Определение, которое нравится лектору

MVD (Multi-Valued Dependency)

r{A, B, C} MVD B от A (A->-> B) т и тт когда множество значений B, соотв. Паре знач. A и C, зависит от А и не зависит от С.

Записывают A->->B|C

Лема Фейджина. B отн r{A, B, C} выполн MVD->->B <=> выполн MVD A->->C

Многие годы лектор не доказывал ни теорему лектора, Ни лемму, Но теперь понял, Что надо доказывать, что это просто. Будь бы лектор Фейджином, он бы назвал эту лемму теоремой.

Лектор любит задавать вопрос на экзамене: как будет звучать лемма, если есть ФЗ В от А.

Достаточность:

пусть выполняется MVD A->-> B

B_r, знач A в некотором кортеже B_r

{b} – множество значений отрибута B, соотв a

Пусть для a A->->C не выполняется, Тогда существует с атрибута с и такое b принадлежит {B}, что <a, b, c> не принадлжеит B_r

Необходимость аналогично

Теорема Фейджина

Пусть имеется перем. Отн. r{A, B, C}

r декомпозируется без потерь на r{A, B} и r{A, C} т и тт, когда выполн MVD A->->B|C

Достаточность:

B_r – тело r, a – значение А, {b} – множество значений B, соотв а; {c} – множество С, соотв а

r PROJECT {A, B} -> {a, b}, где b_i принадлежит {b} и если /**/

Необходимость:

Пусть декомпозиция является декомпозицией без потерь для всякого значения B_r

IF (<a, b₁, c₁> принадлежит B_r AND <a, b₂, c₂> принадлежит B_r>) THEN <a, b₂, c₁> принадлежит B_r AND <a, b₁, c₂> принадлежит B_r) Пусть <a, b₂, c₁> не принадлежит B_r OR <a, b₁, c₂> не принадлежит B_r но в r PROJECT {A, B} входит <a,b1> и <a, b2>

r PROJECT {A, C} входят <a, c₁> и <a, c₂>

Контрольная будет через неделю, 9 ноября. Очень хороший день, после октябрьской революции.

Будет запрос

Будет что-то из теоретических вещей

Нельзя пользоваться только соседями.

4НФ

r находится в 4НФ т и тт, когда находится в БКНФ и все MVD являются FD с детерминантами – возможными ключами

Гречушкин выпендривается, задавая умный вопрос. Благодаря этому лектор не сможе рассказать сегодня про 5НФ.

Отнош называется N-композируемым, если его можно разбить на N независимых проекций.

Тривиальная MVD:

r{A, B} MVD A->-> B триивальна, если либо А содержит или равно B? Либо A UNION B = H_r