3.1. Функциональные зависимости

Проектирование связано с построением логической структуры БД. Иными словами, нужно решить вопрос, какие базовые отношения, с какими атрибутами следует задать.

Суть этой проблемы сводится, в конечном счете, к нормализации отношений.

Сначала рассмотрим основные понятия, необходимые для обсуждения вопросов нормализации отношений.

3.1.1. Понятие функциональной зависимости

Вспомним, что любое отношение рассматривается как переменная, принимающая определенные значения в определенные моменты времени.

Пусть R – переменная отношения, X, Y – произвольные подмножества множества всех атрибутов R. Y функционально зависит от X тогда и только тогда, когда для любого допустимого значения R каждое значение X связано только с одним значением Y.

Обозначается: X→Y

Говорится: «X функционально определяет Y» или «Y функционально зависит от X».

Левая часть выражения называется детерминантом (детерминантой) функциональной зависимости (ФЗ), правая – зависимой частью ФЗ.

Например, в отношении Студенты (№ЗачетнойКнижки, Фамилия, Имя, Отчество, Адрес, КодГруппы) существуют такие ФЗ

{№ ЗачетнойКнижки} → {Фамилия, Имя, Отчество}

{№ ЗачетнойКнижки} → {Адрес, КодГруппы}

{№ ЗачетнойКнижки, Фамилия, Имя, Отчество} → {Адрес, КодГруппы}

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

Еще пример: в отношении Кафедры (КодКафедры, НазваниеКафедры, Кабинет, Телефон) существуют ФЗ

{КодКафедры} → {Кабинет, Телефон}

{НазваниеКафедры} → {Кабинет, Телефон}

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

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

Рассмотрим еще один пример: если в то же отношение Студенты добавить атрибут СтаростаГруппы, то появятся такие ФЗ:

{КодГруппы} → {СтаростаГруппы}

{СтаростаГруппы} → {КодГруппы}

(причем, ни атрибут КодГруппы, ни атрибут СтаростаГруппы не являются потенциальными ключами)

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

Фактически, если в отношении имеется ФЗ, в которой детерминант не является суперключом, то отношение избыточно.

Существуют такие ФЗ, которые учитываются только формально, т.к. они всегда существуют и подразумеваются самим определением ФЗ. Это тривиальные ФЗ.

Тривиальная функциональная зависимость – это такая ФЗ, зависимая часть которой является подмножеством детерминанта.

Например,

{№ЗачетнойКнижки, Фамилия, Имя, Отчество} → {Фамилия, Имя, Отчество}

{КодГруппы, Курс} → {Курс}

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

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

Из некоторого множества ФЗ конкретного отношения можно получить производные ФЗ.

Например, из ФЗ отношения Студенты

{№ЗачетнойКнижки, Фамилия, Имя, Отчество} → {Адрес, Телефон}

можно получить такие ФЗ:

{№ ЗачетнойКнижки, Фамилия, Имя, Отчество} → {Адрес}

{№ ЗачетнойКнижки, Фамилия, Имя, Отчество} → {Телефон}

Пусть S – некое множество ФЗ. Тогда множество всех ФЗ, которые можно получить из S называется замыканием множества S и обозначается S+.

Чтобы получить замыкание некоторого множества ФЗ нужны правила вывода ФЗ. Такие правила вывода сформулировал Армстронг (Швеция), поэтому их называют правилами Армстронга (или аксиомами Армстронга).

Обозначим за А, В, С произвольные подмножества множества атрибутов заданного отношения R, а записью АВ будем обозначать объединение А и В.

Правила вывода ФЗ Армстронга:

1) Рефлексивность: если В является подмножеством А, то А → В

2) Дополнение: если А → В, то АС → ВС

3) Транзитивность: если А → В и В → С, то А → С

Каждое из этих правил может быть доказано на основе определения ФЗ, а первое правило – это определение тривиальной ФЗ.

Эти правила полны, т.к. их достаточно для вывода замыкания (т.е. всех ФЗ) начального множества ФЗ.

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

Но из этих правил для упрощения практического вывода ФЗ можно вывести несколько дополнительных правил (следствий):

4) Самоопределение: А → А

5) Декомпозиция: если А → ВС, то А → В и А → С

6) Объединение: если А → В и А → С, то А → ВС

7) Композиция: если А → В и С → D, то АС → ВD

8) Теорема всеобщего объединения: если А → В и С → D, то А(С-В) → ВD

(названо это правило так, потому что многие другие правила могут быть выведены как частные случаи этой теоремы)

Пример: рассмотрим отношение Группы (КодГруппы, Специальность, Курс,Староста).

В качестве начального множества ФЗ возьмем множество из следующих двух ФЗ:

(1) {КодГруппы} → {Специальность, Курс}

(2) {КодГруппы} → {Староста}

Выведем замыкание этого множества ФЗ.

·По правилу 1 можно записать все тривиальные зависимости:

(3) {Специальность, Курс} → {Специальность}

(4) {Специальность, Курс} → {Курс}

·По правилу 2:

(5) {КодГруппы, Староста} → {Специальность, Курс, Староста}

(6) {КодГруппы, Специальность} → {Староста, Специальность}

(7) {КодГруппы, Курс} → {Староста, Курс}

(8) {КодГруппы, Специальность, Курс} → {Староста, Специальность, Курс}

·По правилу 3 напрямую ничего не выведем.

·По правилу 4:

(9) {КодГруппы} → {КодГруппы}

(10) {Специальность} → {Специальность}

и т.д. (11), (12)

·По правилу 5:

(13) {КодГруппы} → {Специальность}

(14) {КодГруппы} → {Курс}

·По правилу 6:

(15) {КодГруппы} → {Специальность, Курс, Староста}

·По правилу 7 напрямую ничего не выведем

·По правилу 8 тоже.

Однако, знание этих правил и умение ими пользоваться не обеспечивают вывода замыкания множества ФЗ, т.к. не существует четкого алгоритма такого вывода.

3.1.3. Неприводимые функциональные зависимости

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

Например: ФЗ {№ЗачетнойКнижки, Фамилия, Имя, Отчество} → {Адрес} приводима, т.к. из детерминанта можно исключить атрибуты Фамилия, Имя, Отчество без нарушения ФЗ.

А ФЗ {КодГруппы, Дисциплина} → {Преподаватель} отношения Занятия (КодГруппы, Дисциплина, Преподаватель) неприводима, т.к. из детерминанта нельзя исключить ни атрибут КодГруппы, ни атрибут Дисциплина без нарушения зависимости.

Множество ФЗ называется неприводимым тогда и только тогда, когда выполняются три свойства:

1) зависимая часть каждой ФЗ из данного множества содержит только один атрибут;

2) каждая ФЗ из данного множества является неприводимой слева;

3) ни одна ФЗ из данного множества не может быть опущена.

Например, рассмотрим множество ФЗ отношения Группы из примера в предыдущем п.3.1.2.

(1) {КодГруппы} → {Специальность, Курс}

(2) {КодГруппы} → {Староста}

(3) {Специальность, Курс} → {Специальность}

(4) {Специальность, Курс} → {Курс}

(5) {КодГруппы, Староста} → {Специальность, Курс, Староста}

(6) {КодГруппы, Специальность} → {Староста, Специальность}

(7) {КодГруппы, Курс} → {Староста, Курс}

(8) {КодГруппы, Специальность, Курс} → {Староста, Специальность, Курс}

(9) {КодГруппы} → {КодГруппы}

(10) {Специальность} → {Специальность}

(11) {Курс} → {Курс}

(12) {Староста} → {Староста}

(13) {КодГруппы} → {Специальность}

(14) {КодГруппы} → {Курс}

(15) {КодГруппы} → {Специальность, Курс, Староста}

По первому свойству исключаем из этого множества следующие ФЗ: (1), (5), (6), (7), (8), (15).

По второму свойству исключаем следующие ФЗ: (3), (4).

По третьему свойству исключаем: (9), (10), (11), (12).

Остались:

(2) {КодГруппы} → {Староста}

(13) {КодГруппы} → {Специальность}

(14) {КодГруппы} → {Курс}

Полученное множество ФЗ неприводимо. Можно сделать вывод, что полученное множество ФЗ выражает то, что отношение Группы содержит атрибуты КодГруппы, Староста, Специальность, Курс, и КодГруппы – первичный ключ.

3.1.4. Диаграммы (схемы) функциональных зависимостей

Множество неприводимых ФЗ некоторого отношения можно представить в виде диаграммы функциональных зависимостей.

Из таких диаграмм лучше видно, какие ФЗ включить в множество ФЗ, а какие исключить, чтобы оно было неприводимо. Исключить нужно те стрелки (обозначающие ФЗ), которые идут не от потенциального ключа.


Таким образом, с помощью диаграмм можно привести множество ФЗ к неприводимому состоянию.

В качестве примера рассмотрим диаграмму первоначального множества ФЗ из п. 3.1.2.


После того, как лишние стрелки будут убраны, получим диаграмму:

Из нее как раз и следуют перечисленные ранее три оставшиеся ФЗ:

{КодГруппы} → {Курс}

{КодГруппы} → {Специальность}

{КодГруппы} → {Староста}

Таким образом, существует как минимум два способа преобразования множества ФЗ к неприводимому состоянию - путем проверки всех свойств их определения и путем анализа диаграмм ФЗ.

Проектирование реляционных баз данных


*****
Новосибирск © 2009-2017 Банк лекций siblec.ru
Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки.