Базы данных Лекция 9 Проектирование реляционных баз данных на основе принципов нормализации: дальнейшая нормализация. - презентация

1 Базы данных Лекция 9 Проектирование реляционных баз данных на основе принципов нормализации: дальнейшая нормализация

2 Базы данных Многозначные зависимости и четвёртая нормальная форма Лекция 9 Предположим, что каждый служащий может участвовать в нескольких проектах, но в каждом проекте, в котором он участвует, им должны выполняться одни и те же задания.

3 Базы данных Аномалии обновлений при наличии многозначных зависимостей Лекция 9 В переменной отношения СЛУЖ_ПРО_ЗАДАН единственным возможным ключом является заголовок отношения {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}. Кортеж {сн, пн, сз} входит в тело отношения в том и только в том случае, когда служащий с номером сн выполняет в проекте пн задание сз.

4 Базы данных Аномалии обновлений при наличии многозначных зависимостей Лекция 9 При работе с отношением СЛУЖ_ПРО_ЗАДАН проявляются аномалии обновления: Добавление кортежа. Если уже участвующий в проектах служащий присоединяется к новому проекту, то к телу значения переменной отношения СЛУЖ_ПРО_ЗАДАН требуется добавить столько кортежей, сколько заданий выполняет этот служащий. Удаление кортежей. Если служащий прекращает участие в проектах, то отсутствует возможность сохранить данные о заданиях, которые он может выполнять. Модификация кортежей. При изменении одного из заданий служащего необходимо изменить значение атрибута СЛУ_ЗАДАН в стольких кортежах, в скольких проектах участвует служащий.

5 Базы данных Аномалии обновлений при наличии многозначных зависимостей Лекция 9 Трудности, связанные с обновлением переменной отношения СЛУЖ_ПРО_ЗАДАН, решаются путём его декомпозиции на две переменных отношений: СЛУЖ_ПРО_НОМ {СЛУ_НОМ, ПРО_НОМ} и СЛУЖ_ЗАДАНИЕ {СЛУ_НОМ, СЛУ_ЗАДАН}.

6 Базы данных Аномалии обновлений при наличии многозначных зависимостей Лекция 9 Аномалии обновления отсутствуют: Добавление кортежа. Если некоторый уже участвующий в проектах служащий присоединяется к новому проекту, то к телу значения переменной отношения СЛУЖ_ПРО_НОМ требуется добавить один кортеж, соответствующий новому проекту. Удаление кортежей. Если служащий прекращает участие в проектах, то данные о заданиях, которые он может выполнять, остаются в отношении СЛУЖ_ЗАДАНИЕ. Модификация кортежей. При изменении одного из заданий служащего необходимо изменить значение атрибута СЛУ_ЗАДАН в одном кортеже отношения СЛУЖ_ЗАДАНИЕ.

7 Базы данных Многозначные зависимости Лекция 9 В отношении СЛУЖ_ПРО_ЗАДАН мы имеем дело с новым видом зависимости, впервые обнаруженным Роном Фейджином в 1971 г. Фейджин назвал зависимости этого вида многозначными (multi-valued dependency MVD). В отношении СЛУЖ_ПРО_ЗАДАН выполняются две MVD: СЛУ_НОМ ПРО_НОМ и СЛУ_НОМ СЛУ_ЗАДАН. В переменной отношения R с атрибутами A, B, C (в общем случае, составными) имеется многозначная зависимость B от A ( A B ) в том и только в том случае, когда множество значений атрибута B, соответствующее паре значений атрибутов A и C, зависит от значения A и не зависит от значения C.

8 Базы данных Лемма Фейджина Лекция 9 В отношении R {A, B, C} выполняется MVD A B в том и только в том случае, когда выполняется MVD A C. FD является частным случаем MVD, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется FD A B, то выполняется и MVD A B.

9 Базы данных Теорема Фейджина Лекция 9 Теорема Фейджина уточнение и обобщение теоремы Хита. Пусть имеется переменная отношения R с атрибутами A, B, C (в общем случае, составными). Отношение R декомпозируется без потерь на проекции {A, B} и {A, C} тогда и только тогда, когда для него выполняется MVD A B|C. Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей «аномальные» многозначные зависимости, с приведением отношений в четвёртую нормальную форму.

10 Базы данных Четвёртая нормальная форма Лекция 9 Переменная отношения r находится в четвёртой нормальной форме (4NF) в том и только в том случае, когда она находится в BCNF, и все MVD r являются FD с детерминантами возможными ключами отношения r. В сущности, 4NF является BCNF, в которой многозначные зависимости вырождаются в функциональные.

11 Базы данных Зависимости проекции/соединения Лекция 9 Приведение отношения к 4NF предполагает его декомпозицию без потерь на две проекции (как и в случае 2NF, 3NF и BCNF). Однако бывают (хотя и нечасто) случаи, когда декомпозиция без потерь на две проекции невозможна, но можно произвести декомпозицию без потерь на большее число проекций.

12 Базы данных N-декомпозируемые отношения Лекция 9 N-декомпозируемые отношения отношения, которые могут быть декомпозированы без потерь на n проекций. В переменной отношения R с атрибутами (возможно, составными) A и B MVD A B называется тривиальной, если либо A B, либо A UNION B совпадает с заголовком отношения R. Тривиальная MVD всегда удовлетворяется.

13 Базы данных N-декомпозируемые отношения Лекция 9 Рассмотрим вариант переменной отношения СЛУЖ_ПРО_ЗАДАН, в которой имеется единственно возможный ключ {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} и отсутствуют нетривиальные MVD.

14 Базы данных Зависимость проекции/соединения Лекция 9 Чтобы возможность восстановления без потерь отношения СЛУЖ_ПРО_ЗАДАН путём естественного соединения его проекций СЛУЖ_ПРО_НОМ, ПРО_НОМ_ЗАДАН и СЛУЖ_ЗАДАНИЕ существовала при любом допустимом значении переменной отношения СЛУЖ_ПРО_ЗАДАН, должно поддерживаться следующее ограничение: если служащий с номером сн участвует в проекте пн, и в проекте пн выполняется задание сз, и служащий с номером сн выполняет задание сз, то служащий с номером сн выполняет задание сз в проекте пн. В общем виде такое ограничение называется зависимостью проекции/соединения.

15 Базы данных Зависимость проекции/соединения Лекция 9 Пусть задана переменная отношения R, и A, B, …, Z являются произвольными подмножествами заголовка R. В переменной отношения R удовлетворяется зависимость проекции/соединения (Project-Join Dependency PJD) *( A, B, …, Z) тогда и только тогда, когда любое допустимое значение r переменной отношения R можно получить путём естественного соединения проекций этого значения на атрибуты A, B, …, Z.

16 Базы данных Аномалии, вызываемые наличием зависимости проекции/соединения Лекция 9 В переменной отношения СЛУЖ_ПРО_ЗАДАН выполняется PJD *({СЛУ_НОМ, ПРО_НОМ}, {ПРО_НОМ, СЛУ_ЗАДАН}, {СЛУ_НОМ, СЛУ_ЗАДАН}). Аномалии обновления: Добавление кортежей. Если к ТСПЗ1 добавляется кортеж, то должен быть добавлен и кортеж. Удаление кортежа. Если из ТСПЗ2 удаляется кортеж, то должен быть удалён и кортеж, поскольку в соответствии с ограничением целостности наличие второго кортежа означает наличие первого.

17 Базы данных Аномалии, вызываемые наличием зависимости проекции/соединения Лекция 9

18 Базы данных Устранение аномалий обновления в 3-декомпозиции Лекция 9 Декомпозируем отношение СЛУЖ_ПРО_ЗАДАН на три отношения: СЛУЖ_ПРО_НОМ {СЛУ_НОМ, ПРО_НОМ} ; СЛУЖ_ЗАДАНИЕ {СЛУ_НОМ, СЛУ_ЗАДАН} ; ПРО_НОМ_ЗАДАН {ПРО_НОМ, СЛУ_ЗАДАН}.

19 Базы данных Устранение аномалий обновления в 3-декомпозиции Лекция 9

20 Базы данных Пятая нормальная форма Лекция 9 В переменной отношения R PJD *( A, B, …, Z) называется подразумеваемой возможными ключами в том и только в том случае, когда каждый составной атрибут A, B, …, Z является суперключом R, т. е. включает хотя бы один возможный ключ R. В переменной отношения R зависимость проекции/соединения *(A, B, …, Z) называется тривиальной, если хотя бы один из составных атрибутов A, B, …, Z совпадает с заголовком R. Переменная отношения R находится в пятой нормальной форме, или в нормальной форме проекции/соединения (5NF, или PJ/NF Project- Join Normal Form) в том и только в том случае, когда каждая нетривиальная PJD в R подразумевается возможными ключами R. 5NF является «окончательной» нормальной формой, которой можно достичь в процессе нормализации на основе проекций.