Следуя этим допущениям нужно создать концептуальную схему, т.е. абстрактный логический макет, не зависящий от аппаратного обеспечения, операционной системы, СУБД, языка программирования, пользователя и т.д.
Для демонстрации основных идей данного раздела используется несколько измененная версия отношения Students из учебной БД, которое в дополнение к обычным атрибутам StNo, GrNo, StName, CityNo будет содержать также атрибут RgNo, представляющий город соответствующего поставщика. Во избежание путаницы далее это измененное отношение будет называться SR. В виде таблицы оно представлено на рис. 5.1.
| SR | ||||
| StNo | GrNo | StName | CityNo | RgNo |
| 1 | 1 | Иванов | 3 | 1 |
| 2 | 1 | Петров | 3 | 1 |
| 3 | 1 | Сидоров | 3 | 1 |
| 4 | 2 | Стрельцов | 1 | 1 |
| 5 | 2 | Кузнецов | 4 | 2 |
рис. 5.1 Данные отношения SR.
Следует четко различать:
1. значение этого отношения (т.е. значение переменной отношения) в определенный момент времени;
2. набор всех возможных значений, которые данное отношение (переменная) может принимать в различные моменты времени.
При рассмотрении переменных отношения, например базовых отношений, интерес представляют не столько функциональные зависимости для определенного в некоторый момент времени значения, сколько функциональные зависимости, выполняющиеся для всех возможных значений данной переменной.
Ниже приведено определение концепции функциональной зависимости для второго пункта.
Пусть R является переменной отношения, а X и Y – произвольными подмножествами множества атрибутов отношения R. Тогда Y функционально зависимо от X, что в символическом виде записывается как
X®Y
(и читается либо как "X функционально определяет Y ", либо как "X стрелка Y "), тогда и только тогда, когда для любого допустимого значения отношения R каждое значение Х связано в точности с одним значением Y.
Иначе говоря, для любого допустимого значения отношения R, когда бы два кортежа отношения R ни совпадали по значению X, они также совпадают и по значению Y. Далее термин "функциональная зависимость" будет использоваться в последнем безотносительном ко времени смысле (за исключением особо оговоренных случаев).
Например, в случае отношения SR функциональная зависимость
{StNo}®{GrNo}
выполняется для всех возможных значений SR, поскольку в любой момент времени данному студенту соответствует в точности одна группа; таким образом, любые два кортежа отношения SR в один и тот же момент времени и с одним и тем же номером студента должны соответствовать одной и той же группе. Практически утверждение, что данная функциональная зависимость выполняется "всегда" (т.е. для всех возможных значений SR), является ограничением целостности для отношения SR, поскольку при этом накладываются определенные ограничения на все допустимые значения.
Ниже перечислено несколько безотносительных ко времени функциональных зависимостей для переменной отношения SR
{StNo}®{GrNo}
{StNo}®{StName}
{StNo}®{CityNo}
{StNo}®{RgNo}
{StNo}®{GrNo, StName}
{StNo}®{GrNo, StName, CityNo, RgNo}
{StNo, GrNo}® {StName}
и другие.
Левая и правая стороны символической записи функциональной зависимости иногда называются детерминантом и зависимой частью соответственно. Как говорится в определении, детерминант и зависимая часть являются множествами атрибутов. Когда множество содержит только один атрибут, он называется одноэлементным множеством, скобки опускаются и символическая запись принимает вид:
StNo®GrNo
Обратите внимание, в частности, на функциональные зависимости, которые выполняются для таблицы на рис. 5.1, но не выполняются "всегда":
GrNo®CityNo
Следует отметить, что если X является потенциальным ключом отношения R, например X является первичным ключом, то все атрибуты Y отношения R должны быть обязательно функционально зависимы от Х (это следует из определения потенциального ключа). В обычном отношении студентов Students, например, необходимо, чтобы выполнялась зависимость
StNo®{GrNo, StName, CityNo}
Фактически, если отношение R удовлетворяет функциональной зависимости A ® B и A не является потенциальным ключом, то R будет характеризоваться некоторой избыточностью. Например, в случае отношения SR сведения о том, что каждый данный город находится в данной области, будут повторяться много раз (это хорошо видно на рис. 5.1).
На практике важно сократить множество ФЗ до компактных размеров, поскольку, функциональные зависимости являются ограничениями целостности, поэтому при каждом обновлении данных в СУБД все они должны быть проверены.
Очевидным способом сокращения размера множества ФЗ было бы исключение тривиальных зависимостей, т.е. таких, которые не могут не выполняться. В качестве примера приведем тривиальную ФЗ для отношения SR:
{StNo, GrNo} ® {StNo}
Фактически ФЗ тривиальна тогда и только тогда, когда правая часть символической записи данной зависимости является подмножеством (не обязательно собственным подмножеством) левой части.
Некоторые функциональные зависимости обозначают другие функциональные зависимости. Например, функциональная зависимость:
{StNo}®{GrNo, StName}
подразумевает следующие функциональные зависимости:
{StNo}®{GrNo}
{StNo}®{StName}
Множество всех ФЗ, которые задаются данным множеством функциональных зависимостей S, называется замыканием S и обозначается символом S+.
Поскольку функциональные зависимости являются ограничениями целостности, которые должны быть проверены СУБД, желательно для заданного множества ФЗ S найти такое множество ФЗ которое было бы гораздо меньшего размера, чем множество S, причем каждая ФЗ множества S могла бы быть заменена функциональной зависимостью множества T. Для решения этой задачи следует найти способ вычисления S+ на основе S.
Первой попыткой решить эту проблему была статья Армстронга (Armstrong), в которой представлен набор правил вывода функциональных зависимостей на основе заданных (эти правила также называются аксиомами Армстронга).
Правила вывода Армстронга. Пусть в перечисленных ниже правилах А, В, С и D – произвольные подмножества множества атрибутов заданного отношения R, а символическая запись АВ означает объединение А и В.
1. Рефлексивность: если В является подмножеством А, то А®В.
2. Дополнение: если А®В, то АС®ВС.
3. Транзитивность: если А®В и В®С, то А®С.
Каждое из этих правил может быть непосредственно доказано на основе определения функциональной зависимости (первое из них — это всего лишь определение тривиальной зависимости). Более того, эти правила являются полными в том смысле, что для заданного множества функциональных зависимостей S минимальный набор ФЗ, которые подразумевают все зависимости S, может быть выведен из S на основе этих правил. Они также являются исчерпывающими, поскольку никакие дополнительные ФЗ не могут быть выведены (т.е. ФЗ, которые не подразумеваются зависимостями множества S). Иначе говоря, эти правила могут быть использованы для получения замыкания S+.
Из трех описанных выше правил для упрощения задачи практического вычисления замыкания S можно вывести несколько других правил. (Пусть D – это другое произвольное подмножество множества атрибутов R.).
1. Самоопределение: А®А.
2. Декомпозиция: если А®ВС, то А®В и А®C.
3. Объединение: если A®В и А®С, то А®ВС.
4. Композиция: если А®В и С®D, то AC®BD.
5. Если А®В и С®D, то А È (С – В) ®BD (где символ "È" обозначает объединение множеств, а символ "–" – их разность).Это правило называют также теоремой всеобщего объединения.
Например. Пусть дано некоторое отношение R с атрибутами А, В, С, D, Е, F и следующими ФЗ:
А®{ВС}
В®Е
{CD}®{EF}
Далее символами, записанными подряд, например ВС, будем обозначать множество, состоящее из атрибутов В и С, а не объединение В и С.
Этому примеру можно придать более конкретный смысл, а именно: А – номер сотрудника, В – номер отдела, С – номер руководителя (начальника) данного сотрудника, D – номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно взятого руководителя), Е – название отдела, F – доля времени, уделяемая данным руководителем заданному проекту.
Показать, что зависимость AD ® F выполняется для отношения R и таким образом принадлежит замыканию данного множества ФЗ.
1. А®ВС (дано);
2. А®С (из 1 согласно декомпозиции);
3. AD®CD (из 2 согласно дополнению);
4. CD®EF (дано);
5. AD®EF (из 3 и 4 согласно транзитивности);
6. AD®F (из 5 согласно декомпозиции).
Пусть S1 и S2 являются двумя множествами ФЗ. Если любая ФЗ, которая является зависимостью множества S1, также является зависимостью множества S2, т.е. если S1+ является подмножеством S2+ то S2 называется покрытием для S1. Это значит, что если накладываемые в СУБД ограничения представлены зависимостями множества S2, то в этой СУБД также наложены ограничения на основе зависимостей множества S1.
Далее, если S2 является покрытием для S1, а S1 – покрытием для S2, т.е. если S1+=S2+ , то S1 и S2 эквивалентны. Ясно, что если S1 и S2 эквивалентны и наложенные в СУБД ограничения представлены зависимостями множества S2, то эти ограничения также могут быть представлены зависимостями множества S1, верно также и обратное утверждение.
Множество ФЗ называется неприводимым тогда и только тогда, когда выполняются перечисленные ниже свойства.