Базы Данных, 14 лекция (от 20 октября)
Материал из eSyr's wiki.
БД 20.10.06
Лектор не читает лекцию, если на неё приходит менее 3 человек
2НФ
СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_УРОВ, СЛУ_ЗАРП, ПРО_НОМ, СЛУ_ЗАДАН}
СЛУ_УРОВ – разряд, Уровень служащего – определяет размер зарплаты
СЛУ_ЗАДАН – задание
Зависимости:
Таблица:
СЛУ_НОМ |
СЛУ_УРОВ |
СЛУ_ЗАРП |
ПРО_НОМ |
СЛУ_ЗАДАН |
2934 |
2 |
22400 |
1 |
A |
2935 |
3 |
29600 |
1 |
B |
2936 |
1 |
20000 |
1 |
C |
2937 |
1 |
20000 |
1 |
D |
2935 |
3 |
29600 |
1 |
B |
2936 |
1 |
20000 |
2 |
C |
2937 |
1 |
20000 |
2 |
D |
Кодд называет это аномалиями обновления, когда есть зависимости от части ключа, когда при изменениях надо делать дополнительные действия.
Тут есть ошибка добавления, так как считается, что человек может имеет задание, когда берём на работу. - на самом деле это не так. Проблема возникает в том
Удаление – человек завершает работу над последним проектом или удаляем последнего человека из проекта.
Изменение – при измении уровня человека надо поменять его во всех кортежах.
Номер проекта – характеристика проекта.
Это первый случай, когда можно с аномалиями побороться путём декомпозиции на два.
СЛУЖ {СЛУ_НОМ, СЛУ_ЗАРП, СЛУ_УРОВ}
СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}
В результате получаем хорошие ФЗ.
Если где-то при проектировании попалось бинарное отношение, то на него можно больше внимания не обращать. Они обладают всеми хорошие свойствами.
После выполнения такой декомпозиции все неприятноти пропали. Мы можем запросто принять нового человека. Мы можем спокойно оставить данные о человеке, который перестаёт учавствует в проектах. И если у человека меняется разряд, то это надо изменить только в одном месте. И теперь мы в этой БД можно сохранять такую информацию, которые мы не могли сохранять раньше. Более того, те кортежи, у которых не найдётся пара, не попадут в соединение.
Мы получили БД, которая в 2НФ.
2НФ – переменные отношения находятся в 2НФ, когда каждый ключевой атрибут минимально зависит от возможного ключа.
Можно доказать, что любая переменная отношения, в которй присутствуют неминим зависимости от возм ключа, может быть приведена ко 2НФ декомпозицией.
Если посмотреть на СЛУЖ, то там всё равно есть аномалии обновления. Там зарплата зависит от уровня. Эффекты те же самые. Может быть потеряна об информации о соотв разряда и зарплаты, может поменяться зарплата за разряд. Зарплата является характеристикой не человека, а разряда. Тут проблема тоже решается простой декомпозицией.
СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ}
УРОВ {СЛУ_УРОВ, СЛУ_ЗАРП}
В рез-те получим два бинарных отношения. На этом нормализацию можно закончить.
Мы получили 3НФ.
3НФ – это когда перем отн в 2НФ и каждый неключевой атрибут нетранзитивно зависит от возм ключа.
ФЗ называется нетранзитивной, если она не является транзитивной.
Как правило, на 3 НФ проектирование заканчивается. Даже несмотря на то, что на практике часто бывают отношения,Ю в которых много ключей, обычно эти ключи не связаны.
Когда лектор читал курс на комбинате, ему один человек в перерывах расказывал, что на трубопрокатном заводе в бд есть полтора десятка возможных ключей, так как вид трубы определяется маркой стали, станом, типом транспорта, и т. д.
В действительности можно формально одно и то же отношение приводить к 3НФ разными способами. То, что нарисовал лектор – хороший способ. Мы получили в результате две рпоекции, которвые могут обновляться независимо друг от друга. Но может быть другая позиция:
СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ}
СЛУЖ_ЗАРП {СЛУ_НОМ, СЛУ_ЗАРП}
Тут всё вроде правильно, но аномалии остаются. Проблема в том, что мы потеряли ФЗ СЛУ_УРОВ -> СЛУ_ЗАРП.
Почему ограничения возможного ключа простенькие. Мы должны гарантировать, что не возникнет два кортеда с одинаковыми значениями номера и разряда. Существует механизм, который позволяет этого избегать – индекс. Это используется в СУБД, это б-деревья. Они так устроены, что и-дерево работает эффективнее, когда ключ в этом дереве уникален. Эта проверка даётся забесплатно. Тут надо определить ограничение, которое является ограничение базы данных. Это ограничение зарплатфы отн уровня. Из этого примера следует, что когда мы выполн нормализацию, нужно следить не только за формальной стороной, но и за тем, что получающиеся проекции были хорошими в этом отношении. Такие проекции называются независимыми. По этому поводу существует вторая теорема (из трёх на курсе):
Теорема Риссанена (о независимых проекциях). Проекции r1 и r2 отношения r являются независимыми т и тт, когда
Каждая ФЗ в r логически следует из ФЗ в r1 и r2
Общие атрибуты r1 и r2 образуют возможный ключ хотя бы в одном из них
Лектор сам удивляется, почему он не будет её доказывать, но он решил, что доказывать её не надо.
Атомарными назыв отношения, которые невозможно декомпозировать на независимые проекции.
Пример:
СЛУЖ2 {СЛУ_НОМ, СЛУ_ЗАРП, ПРО_НОМ}
Конечно, мы можем разбить это отношение на два, это может принести вам счастье, но аномалий здесь и так нет.
Если делаем декомп в 3НФ, то надо, чтобы проекции были независимые. Для этого надо помнить теорему Р. Есть понытие атомарного отношения, которое нельзя декомп. Хорошо, ели есть атомарные, но если их нет, то это не есть плохо.
//педедыв
Через 4 занятия будет контрольная. Неявка на контрольную означает вероятность, что её придётся писать на экзамене.
В том случае, когда воз ключей несколько, далека не всегда это приводит к неприятностяям. И вот Б. И К. Ввели дополнительную НФ, воторая охватывает всё, что было в первых двух, но и ещё немного. Она охватывает случай, когда у ключи сост из неск атрибутов и даже когда эти атрибуты пересекаются.
Само по себе изм. Возможного ключа – не такая страшная вещь. Если при изм уник не меняется, то всё нормально. Да, придётся делать каскадное обновление (обновить все ссылки на этот ключ). В некрых случаях изменения в возможных ключах может приводить к аномалиям.
СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ, СЛУ_ИМЯ, ПРО_НОМ, СЛУ_ЗАДАН}
Формально требования первых 3 нф соблюдаются.
BCNF:
Перем отн в BCNF т. и т. т., когда у нетривиальной и минимальной ФЗ детерминантом является возможный ключ.
СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ}
СЛУЖ_НОМ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}
В результате у нас снова получились бинарные зависимости, хотя мы к этому не стремились.
Вопрос, нужно ли всегда к этому (к BCNF) стремиться.
Каждый человек может участвовать в нескольких проектов, но выполнять только одно задание в каждом
Задание могут выполнять несколько служащих
СЛУ_НОМ |
ПРО_НОМ |
СЛУ_ЗАД |
---|---|---|
2934 |
1 |
A |
2934 |
2 |
B |
2935 |
1 |
A |
2941 |
2 |
C |
2941 |
1 |
D |
Возм ключи:
{СЛУ_НОМ, ПРО_НОМ}
{СЛУ_НОМ, СЛУ_ЗАДАН}
Это отношение не находятся в BCNF, Есть
аномалии обновления. Это отншоние можно декомпозировать так, чтобы от
аномалии избавится.
СЛУЖ_НОМ_ЗАДАН {СЛУ_НОМ, СЛУ_ЗАДАН}
ПРО_НОМ_ЗАДАН {СЛУ_ЗАДАН, ПРО_НОМ}
СЛУЖ_НОМ_ЗАДАН |
ПРО_НОМ_ЗАДАН |
||
|
|
|
|
2934 |
A |
1 |
A |
2934 |
C |
1 |
D |
2941 |
B |
2 |
B |
2941 |
D |
2 |
C |
2935 |
A |
|
|
Вроде бы всё нормально, но. Каждый может выполнять в каждом проекте только одно задание. Поэтому, если мы хотим добавить кортеж 2934, D, то мы этого сделать не можем, атк как он уже выполняет задание A. Мы получили две проекции, которые не явл независимыми. Получается, чтло в исх отношении были аномалии и оно не было нормализовано, но нормализовать его не удаётся. Более того, она не удовл теореме Р. Поэтому 3НФ всегда можно получить, а BCNF – нет. И нужно определиться, что лучше – аномалии обновления или ограничения в БД.
Наличие перекрывающихся ключей не всегда мешает находиться в BCNF. От предыдущего он отличается тем, что в одном задании только один человек. Ключи здесь перекрываются, а BCNF выполняется. Легко видеть, что этому отношению, со схемой, которая была ранее, аномалии обновления не свойствены.
ФЗ являются основными во всех отношениях. И в определениях – они простые, и в утверждениях. Просто потому, что человек к понятию фугкция хорошо приспособлен. Ем не менее бывают случаи, когда трив зависимочтей нет, а аномалии обновления случаются. Пример: когда есть таблица, в которой перечислены все лектора, все учебные курсы, и все учебники. Три поля: имя курса, имя препода, имя учебника. Ограничение: все преподы, которые читают курс, должны пользоваться одними и теми учебниками. Это то, что называется многозначной зависимостью. В действительности, Кузнецов и Марков зависят исключительно от предмета, БД. У курса фик кол-во преподов, фик количество учебников. Эта зависимость назыв многозначной. И если она есть, то получается не очень-то здорово. В этом отношении есть только один возм ключ, который совпадает с заголовком. Тем не менее, аномалии возникают. Вот приходит распоряжение от Минобразовании: предписано в качестве основного учебника по курсу БД надо использовать учебник Васи Пупкина. Но пока не найдётся идиот, который не согласится по этой книге, в ьбазе эту информацию сохранить нельзя. С этим разобрался ... . Вокруг многозначных зависимостей есть некоторая теория, которая похожа на теорию ФЗ. (Фейджин). На след лекции лектор приведёт два утверждения (т. и лемму Фейджина), покажет, из-за чего возникает некая громоздкость, но всё останется также просто.
Базы Данных
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