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

Презентация:



Advertisements
Похожие презентации
Модуль 1. Математические основы баз данных и знаний 1.
Advertisements

Базы данных Лекция 9 Проектирование реляционных баз данных на основе принципов нормализации: дальнейшая нормализация.
Проектирование РБД на основе учета функциональных зависимостей С.Д. Кузнецов. Базы данных. Тема 5.
Базы данных Лекция 4 Базисные средства манипулирования реляционными данными: реляционная алгебра Кодда.
Функциональные зависимости Нормализация отношений.
Базы данных Лекция 5 Базисные средства манипулирования реляционными данными: алгебра A Дейта и Дарвена.
Модуль 1. Математические основы баз данных и знаний 1.
Реляционная алгебра – механизм манипулирования реляционными данными Все операции производятся над отношениями, и результатом операции является отношение.
Проектирование БД. Нормальные формы В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм: первая нормальная.
Элементы общей алгебры Подгруппа, кольцо, поле, тело, решетка.
Тема 1. Базы данных специального назначения Лекция 4: Нормализация баз данных Учебные цели занятия: Сформировать представление о: 1)Функциональных зависимостях.
БАЗЫ ДАННЫХ ЛЕКЦИЯ 8. тема: ТЕОРИЯ НОРМАЛЬНЫХ ФОРМ.
Учебная дисциплина «Базы данных» для студентов специальности Бизнес-информатика (бакалавриат) ЛЕКЦИЯ 3 ВВЕДЕНИЕ В РЕЛЯЦИОННУЮ МОДЕЛЬ ДАННЫХ Вопрос.
Базы данных Лекция 6 Базисные средства манипулирования реляционными данными: реляционное исчисление.
Модуль 1. Математические основы баз данных и знаний.
1 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность.
Четвёртая нормальная форма (4NF). 1. Определения Четвёртая нормальная форма (4NF) одна из возможных нормальных форм отношения реляционной базы данных.
Теория проектирования реляционных баз данных. Цели проектирования Понизить избыточность данных Повысить надежность и достоверность данных (т.е. устранить.
Функции и отображения Отображения. N-местные функции. Понятие образов и прообразов элементов. Свойства функций: инъекция, сюръекция и биекция. Обратные.
Элементы общей алгебры Группа, кольцо, поле, тело, решетка.
Транксрипт:

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

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

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

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

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

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

Базы данных Замыкание множества функциональных зависимостей Лекция 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.

Базы данных Аксиомы Армстронга Лекция 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 (транзитивность).

Базы данных Аксиомы Армстронга Лекция 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 (накопление).

Базы данных Замыкание множества атрибутов Лекция 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.

Базы данных Минимальное покрытие множества 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.

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

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

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

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

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