Коллектив Авторов - Базы данных: конспект лекций

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

Теперь дадим строгое определение функциональной зависимости.

Определение : пусть X, Y – подсхемы схемы отношения S, определяющие над схемой S схему функциональной зависимости X→ Y(читается «X стрелка Y»). Определим ограничения функциональной зависимости inv→ Y>как утверждение о том, что в отношении со схемой S любые два кортежа, совпадающие в проекции на подсхему X, должны совпадать и в проекции на подсхему Y.

Запишем это же определение в формулярном виде:

Inv→ Y> r ( S ) = t 1, t 2∈ r ( t 1[ X ] = t 2[ X ] ⇒ t 1[ Y ] = t 2[ Y ]), X , Y ⊆ S;

Любопытно, что в этом определении использовано понятие унарной операции проекции, с которым мы сталкивались раньше. Действительно, как еще, если не использовать эту операцию, показать равенство друг другу двух столбцов таблицы-отношения, а не строк? Поэтому мы и записали в терминах этой операции, что совпадение кортежей в проекции на какой-то атрибут или несколько атрибутов (подсхему X) непременно влечет за собой совпадение этих же столбцов-кортежей и на подсхеме Y в том случае, если Y функционально зависит от X.

Интересно заметить, что в случае функциональной зависимости Y от X, говорят также, что X функционально определяетY или что Y функционально зависитот X. В схеме функциональной зависимости X → Y подсхема X называется левой частью, а подсхема Y – правой частью.

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

Конец определения .

В частном случае, когда правая часть функциональной зависимости, т. е. подсхема Y, совпадает со всей схемой отношения, ограничение функциональной зависимости переходит в ограничение уникальности первичного или кандидатного ключа. Действительно:

Inv < K → S > r ( S ) = ∀ t 1, t 2∈ r ( t 1[ K ] = t 2[ K ] → t 1( S ) = t 2( S )), K ⊆ S ;

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

Приведем примеры изображения функциональной зависимости:

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

{№ зачетной книжки, Предмет} → {Оценка};

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

Хорошим примером таких специальных правил являются правила вывода Армстронга.

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

Сформулируем теперь сами правила вывода Армстронга в виде следующей теоремы.

Теорема. Справедливы следующие правила, называемые правилами вывода Армстронга.

Правило вывода 1.├ X → X;

Правило вывода 2.X → Y├ X ∪ Z → Y;

Правило вывода 3.X → Y, Y ∪ W → Z ├ X ∪ W → Z;

Здесь X, Y, Z, W – произвольные подсхемы схемы отношения S. Символ метаутверждения о выводимости разделяет списки посылок и списки утверждений (заключений).

1. Первое правило вывода называется « рефлексивность» и читается следующим образом: «выводится правило: “X функционально влечет за собой X”». Это самое простое из правил вывода Армстронга. Оно выводится буквально из воздуха.

Интересно заметить, что функциональная зависимость, обладающая и левой, и правой частями, называется рефлексивной. Согласно правилу рефлексивности ограничение рефлексивной зависимости выполняется автоматически.

2. Второе правило вывода называется « пополнение» и читается таким образом: «если X функционально определяет Y, то выводится правило: “объединение подсхем X и Z функционально влечет за собой Y”». Правило пополнения позволяет расширять левую часть ограничения функциональных зависимостей.

3. Третье правило вывода называется « псевдотранзитивность» и читается следующим образом: “если подсхема X функционально влечет за собой подсхему Y и объединение подсхем Y и W функционально влекут за собой Z, то выводится правило: «объединение подсхем X и W функционально определяют подсхему Z»”.

Правило псевдотранзитивности обобщает правило транзитивности, соответствующее частному случаю W: = 0. Приведем формулярную запись этого правила:

X →Y, Y → Z ├X → Z.

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

Правило вывода 1.inv r(S);

Правило вывода 2.inv r(S) ⇒ inv r(S);

Правило вывода 3.inv r(S) & inv r(S) ⇒ inv r(S);

Проведем доказательстваэтих правил вывода.

1. Доказательство правила рефлексивностиследует непосредственно из определения ограничения функциональной зависимости при подстановке вместо подсхемы Y – подсхемы X.

Действительно, возьмем ограничение функциональной зависимости:

Inv r(S) и подставим в него X вместо Y, получим:

Inv r(S), а это и есть правило рефлексивности.

Правило рефлексивности доказано.

2. Доказательство правила пополненияпроиллюстрируем на диаграммах функциональной зависимости.

Первая диаграмма – это диаграмма посылки:

посылка: X → Y

Вторая диаграмма: