Базы Данных, 15 лекция (от 26 октября)
Материал из eSyr's wiki.
БД 24.10.06
4НФ
Многозначные зависимости ближе всего к функционалам.
Наличие многознач завис в БД обнаружил Рональд Фейджин. Многозначные зависимости обнаруживаются достаточно трудно.
5НФ настолько далека от интуитивного понимая, что лектор не знает примеров, где её хорошо использовать. Во многом она искусственна. Хотя мы увидим, что те ограничение, коотрые порождаются, довольно естественны.
Многознач завис:
Есть отношение СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ., ПРО_НОМ, СЛУ_ЗАДАН}
Служащий может учавствовать в различных проектах, но выполнять только одно задание. Например, если вы усеете мыть посуду или подметать, то будете востребованы в любом проекте.
Что ещё делать менеджеру проекта, кроме как посуду мыть.
СЛУ_НОМ |
ПРО_НОМ |
СЛУ_ЗАРП |
---|---|---|
2934 |
1 |
A |
2934 |
1 |
B |
2934 |
2 |
A |
2934 |
2 |
B |
... |
|
|
2941 |
1 |
A |
2941 |
1 |
D |
Как выглядит ограничение:
Для каждого кортежа ПРО_ЗАДАН должно выполняться ограничпение: IF (<сн, пн1, сз1>) принадлежит Bспз and <сн, пн2, сз2> принадлежит Bспз then (<сн, пн1, сз2>) принадлежит Bспз and <сн, пн2, сз1> принадлежит Bспз
Наличие такого рода зависимостей приводит к аномалиям изменений.
Если вдруг менеджер, Котолько только моет посуду, Вдруг научидлся программировать на Джаве, То придётся добавить количество кортежей по количеству проектов.
Понятно, что эти проблемы решаются декомпозицией отношения.
СЛУЖ_ПРО_НОМ:
СЛУ_НОМ |
ПРО_НОМ |
---|---|
2934 |
1 |
2934 |
2 |
2941 |
1 |
Заметим, что было унарное отношение с единственным возмоджным ключом, а стало бинарное с нетривиальной ФЗ. Но это честная бинарная зависимость.
СЛУЖ_ЗАДАН
СЛУ_НОМ |
СЛУ_ЗАДАН |
---|---|
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
Br, знач A в некотором кортеже Br
{b} – множество значений отрибута B, соотв a
Пусть для a A->->C не выполняется, Тогда существует с атрибута с и такое b принадлежит {B}, что <a, b, c> не принадлжеит Br
Необходимость аналогично
Теорема Фейджина
Пусть имеется перем. Отн. r{A, B, C}
r декомпозируется без потерь на r{A, B} и r{A, C} т и тт, когда выполн MVD A->->B|C
Достаточность:
Br – тело r, a – значение А, {b} – множество значений B, соотв а; {c} – множество С, соотв а
r PROJECT {A, B} -> {a, b}, где bi принадлежит {b} и если /**/
Необходимость:
Пусть декомпозиция является декомпозицией без потерь для всякого значения Br
IF (<a, b1, c1> принадлежит Br AND <a, b2, c2> принадлежит Br>) THEN <a, b2, c1> принадлежит Br AND <a, b1, c2> принадлежит Br) Пусть <a, b2, c1> не принадлежит Br OR <a, b1, c2> не принадлежит Br но в r PROJECT {A, B} входит <a,b1> и <a, b2>
r PROJECT {A, C} входят <a, c1> и <a, c2>
Контрольная будет через неделю, 9 ноября. Очень хороший день, после октябрьской революции.
Будет запрос
Будет что-то из теоретических вещей
Нельзя пользоваться только соседями.
4НФ
r находится в 4НФ т и тт, когда находится в БКНФ и все MVD являются FD с детерминантами – возможными ключами
Гречушкин выпендривается, задавая умный вопрос. Благодаря этому лектор не сможе рассказать сегодня про 5НФ.
Отнош называется N-композируемым, если его можно разбить на N независимых проекций.
Тривиальная MVD:
r{A, B} MVD A->-> B триивальна, если либо А содержит или равно B? Либо A UNION B = Hr
Базы Данных
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Календарь
пт | чт | пт | чт | пт | чт | пт | чт | пт | чт | |
Сентябрь
| 01 | 07 | 14 | 15 | 21 | 22 | 28 | 29 | ||
Октябрь
| 05 | 06 | 12 | 13 | 19 | 20 | 26 | 27 | ||
Ноябрь
| 02 | 03 | 09 | 16 | 17 | 23 | 24 | 30 | ||
Декабрь
| 07 | 08 | 14 | 15 |
Вопросы к экзамену
1999
2000
2001
2002
2003
2004
2005
2006