Раздел 4. Нормализация отношений.

Основной проблемой при проектировании баз данных является ответ на вопрос: такие атрибуты должны вместе формировать отношения, а для таких атрибутов это не допустимо. Некорректное формирование отношений приводит к двум основным проблемам:

1. Аномалия дополнения (модификации)

2. Аномалия удаления

Дублирование значений неключевых атрибутов приводит к непротиворечивости значений при дополнении и модификации. При удалении какого-либо объекта автоматически удаляются сведения о других объектах.

Раздел 4.1. Функциональная зависимость.

Основой для проектирования схемы БД являются различные виды зависимости между данными, из которых главной является функциональная зависимость.

Принцип независимости данных:

Задано отношение , определенное на множестве

Совокупность кортежей в таблице называется реализацией и обозначается .

Пусть . функционально определяет ( ), если для любой реализации отношение не существует кортежей , таких что

Такой интерпретацией оказывается эквивалентно операции проекции

– таблица номера сотрудника

– ФИО сотрудника

– должность сотрудника

–функциональная зависимость существует, но область ее только для уволенных сотрудников

– дата увольнения сотрудника

– день недели {1,2,3,…}

- если такой зависимости нет, то других зависимостей точно нет

– номер пары

– номер группы

– номер аудитории

Для установления зависимости воспользуемся обратным методом.

Удаляем лишние атрибуты.

Основой вид ограничения целостности на данных, который не может быть определен какими-либо формальными алгоритмами.

Для этого требуется участие человека, обладающего абстрактным мышлением.

Раздел 4.2. Правила логического следствия.

Если множество атрибутов , , тогда .

Доказательство:

Предположим противное, не выполнено. Тогда по определению существует реализация r два кортежа , таких что .

Возможны два варианта:

1. 

2. 

Рассмотрим 1 вариант. Противоречит .

Рассмотрим 2 вариант. Противоречит .

Полученные противоречия доказывают исходное утверждение.

Рассмотренное свойство функциональной зависимости позволяет интерпретировать функциональную зависимость как логическое высказывание, а саму функциональную зависимость – как логическую операцию импликации. Т.о. можем применить аппарат математической логики для исследования свойств функциональной зависимости.

Раздел 4.3. Аксиомы функциональных зависимостей.

Впервые аксиомы функциональных зависимостей были сформулированы Армстронгом. Впоследствии была построена более компактная система аксиом:

А1. Рефлексивность.

Если , тогда

А2. Пополнение

Если , тогда

А3. Транзитивность

Если , тогда

Замечание. Относительно любой системы аксиом должно быть доказано, что она полна и непротиворечива.

Эти свойства доказываются в рамках метатеории, которой в нашем случае являются свойства таблицы. Доказательство надежности аксиомы А3 является доказательство логического следствия.

Наиболее важными являются следующие правила, выводимые из системы аксиом.

П1. Синтез отношений

Если , тогда

П2.

Если , тогда

Пусть F – множество функциональных зависимостей, установленных прикладной областью, тогда множество F⁺ называется множеством замыкания функциональных зависимостей и содержит ВСЕ зависимости, выводимые из F посредством аксиом.

Замечания. Построение множество F⁺ является экспонициальной задачей. Как следствие правило декомпозиции отношений основано на использовании F+ также является экспонициальной задачей.

Дано: Отношение R, определенное на множестве атрибутов Множество зависимостей F, которому удовлетворяет отношение R.

Пусть: X – подмножество U.

Тогда: Множество U называется первичным ключом отношения R, если и для любого Y – истинного подмножества X, .

В отношении R может быть несколько первичных ключей. Из определения следует, что эти ключи будут эквиваленты, каждый из ключей определяет остальные ключи функционально.