Базы данных Лекция 7 Элементы теории реляционных баз данных: функциональные зависимости и декомпозиция без потерь. - презентация

1 Базы данных Лекция 7 Элементы теории реляционных баз данных: функциональные зависимости и декомпозиция без потерь

2 Базы данных Функциональные зависимости Лекция 7 Пусть задана переменная отношения R, и X и Y являются произвольными подмножествами заголовка R («составными» атрибутами). В значении переменной отношения R атрибут Y функционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y. В этом случае говорят также, что атрибут X функционально определяет атрибут Y ( X является детерминантом (определителем) для Y, а Y является зависимым от X ). Будем обозначать это как R.X R.Y.

3 Базы данных Функциональные зависимости Лекция 7 Для примера будем использовать отношение СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК}. Очевидно, что если СЛУ_НОМ является первичным ключом отношения СЛУЖАЩИЕ, то для этого отношения справедлива функциональная зависимость (Functional Dependency – FD) СЛУ_НОМ СЛУ_ИМЯ.

4 Базы данных Функциональные зависимости Лекция 7 Для тела отношения СЛУЖАЩИЕ_ПРОЕКТЫ выполняются следующие FD: СЛУ_НОМ СЛУ_ИМЯ СЛУ_НОМ СЛУ_ЗАРП СЛУ_НОМ ПРО_НОМ СЛУ_НОМ ПРОЕКТ_РУК {СЛУ_НОМ, СЛУ_ИМЯ} СЛУ_ЗАРП {СЛУ_НОМ, СЛУ_ИМЯ} ПРО_НОМ {СЛУ_НОМ, СЛУ_ИМЯ} {СЛУ_ЗАРП, ПРО_НОМ} ПРО_НОМ ПРОЕКТ_РУК и т. д. Эти FD должны быть верны для любого допустимого значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ и могут рассматриваться как инварианты, или ограничения целостности этой переменной отношения.

5 Базы данных Функциональные зависимости Лекция 7 Поскольку имена всех служащих различны, то выполняются и такие FD : СЛУ_ИМЯ СЛУ_НОМ СЛУ_ИМЯ СЛУ_ЗАРП СЛУ_ИМЯ ПРО_НОМ и т. д. Т. к. никакие двое служащих, участвующие в разных проектах, не получают одинаковую зарплату, выполняется FD: СЛУ_ЗАРП ПРО_НОМ Если атрибут A отношения R является возможным ключом, то для любого атрибута B этого отношения всегда выполняется FD A B.

6 Базы данных Функциональные зависимости Лекция 7 FD A B называется тривиальной, если A B (т. е. множество атрибутов A включает множество B или совпадает с множеством B ). Любая тривиальная FD всегда выполняется. Например, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ всегда выполняется FD {СЛУ_ЗАРП, ПРО_НОМ} СЛУ_ЗАРП Тривиальные FD нельзя трактовать как ограничения целостности.

7 Базы данных Замыкание множества функциональных зависимостей Лекция 7 Замыканием множества FD S является множество FD S +, включающее все FD, логически выводимые из FD множества S. Два примера FD, из которых следуют (или выводятся) другие FD: Для отношения СЛУЖАЩИЕ_ПРОЕКТЫ выполняется, например, FD СЛУ_НОМ СЛУ_ЗАРП, ОТД_НОМ}. Из этой FD выводятся FD СЛУ_НОМ СЛУ_ЗАРП и СЛУ_НОМ ОТД_НОМ. Имеется также пара FD СЛУ_НОМ ОТД_НОМ и ОТД_НОМ ПРОЕКТ_РУК. Из них выводится FD СЛУ_НОМ ПРОЕКТ_РУК. FD вида СЛУ_НОМ ПРОЕКТ_РУК называются транзитивными, поскольку ПРОЕКТ_РУК зависит от СЛУ_НОМ «транзитивно», через ПРО_НОМ. FD A C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A B и B C и отсутствует функциональная зависимость C A.

8 Базы данных Аксиомы Армстронга Лекция 7 Пусть A, B и C являются (в общем случае, составными) атрибутами отношения R. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда: если B A, то A B (рефлексивность); если A B, то AC BC (пополнение); если A B и B C, то A C (транзитивность).

9 Базы данных Аксиомы Армстронга Лекция 7 Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами: A A (самодетерминированность); если A BC, то A B и A C (декомпозиция); если A B и A C, то A BC (объединение); если A B и C D, то AC BD (композиция); если A BC и B D, то A BCD (накопление).

10 Базы данных Замыкание множества атрибутов Лекция 7 Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R ) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Z + таких атрибутов Y отношения R, что FD Z Y входит в S +. Суперключом отношения R называется любое подмножество K заголовка R, включающее, по меньшей мере, хотя бы один возможный ключ R. Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD K A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K + совпадает с заголовком R.

11 Базы данных Минимальное покрытие множества FD Лекция 7 Множество FD S 2 называется покрытием множества FD S 1, если любая FD, выводимая из S 1, выводится также из S 2. S 2 является покрытием S 1 тогда и только тогда, когда S 1 + S 2 +. Два множества FD S 1 и S 2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S 1 + = S 2 +. Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам: правая часть любой FD из S является множеством из одного атрибута (простым атрибутом); детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S +, т. е. порождению множества FD, не эквивалентного S ; удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.

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

13 Базы данных Корректные и некорректные декомпозиции отношений Лекция 7

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

15 Базы данных Минимальные FD Лекция 7 Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD A B. Минимальной слева называется FD с минимальным детерминантом. Например, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ выполняются FD СЛУ_НОМ СЛУ_ЗАРП и {СЛУ_НОМ, СЛУ_ИМЯ} СЛУ_ЗАРП. Первая FD является минимальной слева, а вторая нет. Поэтому СЛУ_ЗАРП минимально зависит от СЛУ_НОМ, а для {СЛУ_НОМ, СЛУ_ИМЯ} свойство минимальной зависимости не выполняется.

16 Базы данных Диаграммы функциональных зависимостей Лекция 7