Информационное обеспечение систем управления

       

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


Для отношения

Аксиомы вывода функциональных зависимостей
 в любой момент существует некоторое семейство F-зависимостей, которым это отношение удовлетворяет. Здесь может возникнуть та же проблема, что и с ключами: одно состояние отношения может удовлетворять F-зависимости, а другое – нет.

Требуется выявить семейство F-зависимостей

Аксиомы вывода функциональных зависимостей
, которому удовлетворяют все допустимые состояния
Аксиомы вывода функциональных зависимостей
. Чтобы найти
Аксиомы вывода функциональных зависимостей
, необходимы семантические знания об отношении
Аксиомы вывода функциональных зависимостей
. Поэтому можно считать семейство F-зависимостей заданным в схеме отношения
Аксиомы вывода функциональных зависимостей
. В этом случае любое отношение
Аксиомы вывода функциональных зависимостей
 должно удовлетворять всем F-зависимостям из
Аксиомы вывода функциональных зависимостей
. Не всегда ясно, что является первичным: множество допустимых состояний отношения, которое определяет F-зависимости, или F-зависимости накладывают ограничения на схему отношения [10].

Множество функциональных зависимостей, применимых к отношению

Аксиомы вывода функциональных зависимостей
, конечно, так как существует только конечное число подмножеств множества
Аксиомы вывода функциональных зависимостей
. Таким образом, всегда можно найти все F-зависимости, которым удовлетворяет
Аксиомы вывода функциональных зависимостей
. Однако этот подход требует большого количества шагов и, соответственно, много времени.

Если известны некоторые F-зависимости из

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

Множество F-зависимостей

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

Аксиома вывода – это правило, устанавливающее, что если отношение удовлетворяет определенным F-зависимостям, то оно должно удовлетворять и некоторым другим F-зависимостям.

Сформулировано шесть аксиом вывода F-зависимостей [10]. В этих формулировках используется обозначение r для отношения на

Аксиомы вывода функциональных зависимостей
 и
Аксиомы вывода функциональных зависимостей
,
Аксиомы вывода функциональных зависимостей
,
Аксиомы вывода функциональных зависимостей
 и
Аксиомы вывода функциональных зависимостей
 – для подмножеств
Аксиомы вывода функциональных зависимостей
.

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

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

F2. Пополнение.

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

F3. Аддитивность.

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

F4. Проективность.

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

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

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

F6. Псевдотранзитивность.

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

Некоторые аксиомы вывода могут быть получены из других. Например, транзитивность F5 является частным случаем псевдотранзитивности F6 при

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

Приведенная система аксиом F1-F6 является полной. Это означает, что каждая F-зависимость, которая следует из множества Р, может быть выведена путем одно- или многократного применения к F этих аксиом.


Из аксиом Fl, F2 и F6 можно вывести остальные, а значит, они образуют полное подмножество для F1-F6. Аксиомы Fl, F2 и F6 являются также независимыми: ни одна из этих аксиом не может быть получена из двух других. Иногда эти три аксиомы называются аксиомами Армстронга.

Пусть
Аксиомы вывода функциональных зависимостей
 – множество F-зависимостей для отношения
Аксиомы вывода функциональных зависимостей
. Замыкание
Аксиомы вывода функциональных зависимостей
, обозначаемое
Аксиомы вывода функциональных зависимостей
, - это наименьшее содержащее
Аксиомы вывода функциональных зависимостей
 множество, такое, что при применении к нему аксиом Армстронга нельзя получить ни одной F-зависимости, не принадлежащей
Аксиомы вывода функциональных зависимостей
. Так как
Аксиомы вывода функциональных зависимостей
 должно быть конечно, то можно вычислить его, начиная с
Аксиомы вывода функциональных зависимостей
 путем применения Fl, F2 и F6 и добавления полученных F-зависимостей к
Аксиомы вывода функциональных зависимостей
 до тех пор, пока не перестанут получаться новые зависимости. Замыкание
Аксиомы вывода функциональных зависимостей
 зависит от схемы
Аксиомы вывода функциональных зависимостей
.

Из множества
Аксиомы вывода функциональных зависимостей
 можно вывести F-зависимость  
Аксиомы вывода функциональных зависимостей
, если
Аксиомы вывода функциональных зависимостей
 принадлежит
Аксиомы вывода функциональных зависимостей
. Так как аксиомы вывода порождают только функциональные зависимости, то
Аксиомы вывода функциональных зависимостей
 влечет за собой
Аксиомы вывода функциональных зависимостей
, если
Аксиомы вывода функциональных зависимостей
 выводится из
Аксиомы вывода функциональных зависимостей
.

Пример 2.5. Пусть
Аксиомы вывода функциональных зависимостей
 – множество F-зависимостей на
Аксиомы вывода функциональных зависимостей
.

Тогда:

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


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


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


В свете   новых знаний об F-зависимостях, следует уточнить понятия ключа и суперключа.

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

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

Суперключ – это любая совокупность атрибутов, содержащая ключ.

Нормализация – формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей) и существующих функциональных зависимостей [2, 7,10].

Цель нормализации – получение такого проекта базы данных, в котором каждый факт хранится в одном месте, т.е. исключена избыточность информации. Это делается не столько с целью экономии памяти, сколько для исключения возможной противоречивости хранимых данных из-за их избыточности.

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



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

В теории реляционных баз данных разработано несколько нормальных форм (НФ), которые подчиняются правилу вложенности (рис. 2.25).

Аксиомы вывода функциональных зависимостей
-я нормальная форма не обладает некоторыми недостатками, свойственным
Аксиомы вывода функциональных зависимостей
-й нормальной форме. Общий смысл дополнительного условия, налагаемого на
Аксиомы вывода функциональных зависимостей
-ю нормальную форму по отношению к
Аксиомы вывода функциональных зависимостей
-й нормальной форме, состоит в исключении этих недостатков.

При реализации реляционной БД важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщика. Однако чтобы избежать аномалий обновления, описываемых ниже, нормализацию рекомендуется проводить как минимум до 3НФ.


Содержание раздела