Модуль 1. Математические основы баз данных и знаний 1

Лекция 7 Ф ункциональные зависимости и декомпозиция без потерь 1. Функциональные зависимости 2. Декомпозиция без потерь и функциональные зависимости 2

1. Функциональные зависимости Общие определения Пусть задана переменная отношения r, и X и Y являются произвольными подмножествами заголовка r ("составными" атрибутами). атрибут Y функционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y. Будем обозначать это как r.X r.Y. 3

1. Функциональные зависимости Пример 4

1. Функциональные зависимости Пример (FD 1) 5 СЛУ_НОМ СЛУ_ИМЯ СЛУ_НОМ СЛУ_ЗАРП СЛУ_НОМ ПРО_НОМ СЛУ_НОМ ПРОЕКТ_РУК СЛУ_НОМ, СЛУ_ИМЯ СЛУ_ЗАРП СЛУ_НОМ, СЛУ_ИМЯ ПРО_НОМ СЛУ_НОМ, СЛУ_ИМЯ СЛУ_ЗАРП, ПРО_НОМ

1. Функциональные зависимости Пример 6 СЛУ_ИМЯ СЛУ_НОМ СЛУ_НОМ СЛУ_ЗАРП СЛУ_НОМ ПРО_НОМ и т.д. СЛУ_ЗАРП ПРО_НОМ (FD 2) (FD 3) FD А В называется тривиальной, если А В

7 мы будем иметь дело с FD, которые выполняются для всех возможных состояний тела соответствующего отношения и могут рассматриваться как ограничения целостности FD A B называется тривиальной, если A B (т. е. множество атрибутов A включает множество B или совпадает с множеством B). 1. Функциональные зависимости

Имеется: FD СЛУ_НОМ {СЛУ_ЗАРП, ОТД_НОМ}. Из этой FD выводятся FD СЛУ_НОМ СЛУ_ЗАРП СЛУ_НОМ ОТД_НОМ 8 1. Функциональные зависимости

9 Имеется: FD СЛУ_НОМ ОТД_НОМ ОТД_НОМ ПРОЕКТ_РУК Из этих FD выводится FD СЛУ_НОМ ПРОЕКТ_РУК FD вида СЛУ_НОМ ПРОЕКТ_РУК называются транзитивными 1. Функциональные зависимости

10 FD A C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A B и B C и отсутствует функциональная зависимость C A 1. Функциональные зависимости

11 Подход к решению проблемы поиска замыкания S + множества FD S впервые предложил Вильям Армстронг. Им был предложен набор правил вывода новых FD из существующих 1. Функциональные зависимости

12 Пусть A, B и C являются (в общем случае, составными) атрибутами отношения r. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B 1. Функциональные зависимости

Тогда: если B A, то A B (рефлексивность) если A B, то AC BC (пополнение) если A B и B C, то A C (транзитивность) применение этих аксиом не может привести к выводу лишней FD 13 1.Функциональные зависимости Аксиомы Армстронга

14 4. A A (самодетерминированность) 5. если A BC, то A B и A C (декомпозиция) 6. если A B и A C, то A BC (объединение) 7. если A B и C D, то AC BD (композиция) 8. если A BC и B D, то A BCD (накопление) 1. Функциональные зависимости Дополнение Дейта к аксиомам Армстронга

15 подход к проектированию реляционных баз данных основан на нормализации, т. е. декомпозиции (разбиения путем проецирования) отношения, находящегося в предыдущей нормальной форме, на два или более отношений, удовлетворяющих требованиям следующей нормальной формы. 2. Декомпозиция без потерь и функциональные зависимости

16 Считаются правильными такие декомпозиции отношения, которые обратимы, т. е. имеется возможность собрать исходное отношение из декомпозированных отношений без потери информации. Такие декомпозиции называются декомпозициями без потерь. 2. Декомпозиция без потерь и функциональные зависимости

17 Теорема Хита Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD A B. Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}). 2. Декомпозиция без потерь и функциональные зависимости

18 2. Декомпозиция без потерь и функциональные зависимости

19 Диаграммы функциональных зависимостей 2. Декомпозиция без потерь и функциональные зависимости