Введение в системы БД (542480), страница 99
Текст из файла (страница 99)
(Упражнение. Попробуйте записать полное множество функциональных зависимостей, существующих в переменной-отношении ЯСР.) Большая часть оставшегося в этой главе материала посвящена поискам методов сокращения обширного множества функциональных зависимостей до некоторых допустимых размеров. Почему эта цель столь важна". Как уже отмечалось, одна из причин состоит в том, что функциональные зависимости являются ограничениями целостности, поэтому при каждом обновлении данных в базе СУБД вынуждена будет проверять соблюдение всех этих ограничений. Следовательно, для каждого заданного множества функциональных зависимостей Я желательно найти такое множество Т, которое (в идеальной ситуации) было бы суи)ественна меньше множества Я и при этом каждая функциональная зависимость в множестве Б могла бы быть заменена функциональной зависимостью из множества Т.
Если бы такое множество Т было найдено, то СУБД достаточно было бы контролировать выполнение функциональных зависимостей из множества Т, что автоматически подразумевало бы соблюдение всех функциональных зависимостей из множества Я. Именно поэтому задача поиска подходящего множества Т представляет большой практический интерес.
10.3. Тривиальные и нетривиальные зависимости Замечание. Дичее в эпюй главе выражение "функиианачьная зависимость" будет иногда для краткости заменяться сяавоч "эависичость", а "функционачьна зависим апч" — славачи "функцианачьяа определяется как" и т.п. Очевидным .способом сокрашения существующего набора функциональных зависимостей является исключение из него тривиатьных зависимостей. Зависимость называется тривиальной, если она не может не выполняться. В качестве примера приведем тривиальную функциональную зависимость, существующую в переменной- отношении ЯСР, которая обсуждалась в предыдущем разделе. ( Я((, Р() ) — э Я(( ( Эта функциональная зависимость не является тривиальной (раздел )0.3), причем А не являенкя супсрключом (раздел )05), а К содержит по краиней мере два корныжа.
404 Часо|ь П1. Проектирование базы данных Действительно, функциональная зависимость является тривиальной тогда и только тогда, когда правая часть ее символической записи является подмножеством (необязательно правильным подмножеством) левой части. Как следует из определения, с практической точки зрения подобные зависимости не представляют никакого интереса — в отличие от нетривиальных зависимостей, которые действительно являются реальными ограничениями целостности.
Однако в формальной теории зависимостей необходимо учитывать все зависимости, как тривиальные, так и нетривиальные. 10.4. Замыкание множества зависимостей Как упоминалось выше, одни функциональные зависимости могут подразумевать другие функциональные зависимости. Например, рассмотрим приведенную ниже зависимость.
(Б», р» ) -э(С1ту, О~у) Она подразумевает следующие функциональные зависимости. ( Б», К» ) -э СТту ( Б», Р» ) э Яту В качестве более сложного примера можно привести переменную-отношение К с атрибутами А, В и С, для которых выполняются функциональные зависимости А э В и В э С. Нетрудно заметить, что в этом случае также выполняется функциональная зависимость А †> С, которая называется транзитивной функциональной зависимостью, т.е.
С зависит от А транзитиано, через В. Множество всех функциональных зависимостей, которые подразумеваются заданным множеством функциональных зависимостей Б, называется замыканием множества Б и обозначается символом Б'. Из приведенного определения следует, что для решения сформулированной задачи необходимо найти способ вычисления Б' на основе Б. Первая попытка решить эту проблему была предпринята в статье Армстронга (Аппмгопй) [10.1], в которой автор предложил набор правил вывода новых функциональных зависимостей на основе заданных (эти правила также называются аксиомами Армстронга). Правила вывода могут формулироваться разными способами, и самым простым из них является следующий. Пусть А, В и С вЂ” произвольные подмножества множества атрибутов заданной переменной-отношения К. Условимся также, что символическая запись АВ означает объединение множеств А и В.
Тогда правила вывода определяются следующим образом. 1. Правило рефлексивности: если множество В является подмножеством множества А,то А — э В. 2. Правило дополнения: если А — > В, то АС вЂ” э ВС. 3. Правило транзитивностн: если А — э В и  — э С, то А — э С.
Каждое из этих трех правил может быть непосредственно доказано на основе определения функциональной зависимости (первое из них — просто определение тривиальной зависимости). Более того, эти правила являются полными в том смысле, что 405 Глава 10. Функциональные зависимости для заданного множества функциональных зависимостей Я минимальный набор функциональных зависимостей, которые подразумевают все зависимости из множества Я, может быть выведен из ФЗ множества Я на основе этих правил.
Они также являются исчерпывающими, поскольку никакие дополнительные функциональные зависимости (т.е, зависимости, которые не подразумеваются функциональными зависимостями множества Я) с их помощью не могут быть выведены. Иначе говоря, эти правила могут использоваться для получения замыкания Я . С целью упрощения задачи практического вычисления замыкания Я из трех приведенных выше правил можно вывести несколько дополнительных правил. (Примем, что Р— это другое произвольное подмножество множества атрибутов К.) 4. Правило самоопределения: А — > А. 5.
Правилодекомпозиции: еслиА — э ВС,тоА — э ВиА -э С. 6. Правило объединения: если А — э В иА -э С,то А -э ВС. 7. Правило композиции: если А — > В и С -э Р, тоАС вЂ” э ВР. Кроме того, Дарвен (Рагзнеп) в своей работе ~10.6] доказал следующее правило, которое называется общей теоремой обьединения.
8. Если А — > В и С вЂ” > Р, то А з (С - В) — > ВР (здесь символ "н'* обозначает операцию объединения множеств, а символ "-" — операцию разности множеств). Название "общая теорема объединения" указывает на то, что некоторые из перечисленных выше правил могут быть выведены как частные случаи этой теоремы 110.6]. Пример. Пусть дана некоторая переменная-отношение К с атрибутами А, В, С, Р, Е, Е и следующими функциональными зависимостями. А — э ВС В вЂ” э Е СР -+ ЕЕ Обратите внимание, что способ записи несколько изменился (без ущерба для смысла); например, символы ВС означают множество, состоящее из атрибутов В и С, хотя ранее они означали объединение В и С, где В и С были множествами атрибутов.
Замечание. Если необходимо, то этому примеру можно придать более конкретный смысл, а именно: А — личный номер сотрудника,  — номер отдела, С вЂ” личный номер руководителя (начальника) данного сотрудника, Р— номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно взятого руководителя), Š— название отдела, à — доля времени, уделяемая данным руководителем заданному проекту.
Теперь можно показать, что для переменной-отношения К также выполняется функциональная зависимость АР— > Е, которая вследствие этого принадлежит к замыканию заданного множества функциональных зависимостей. 1. А — > ВС (дано) 2. А — > С (следует из п. 1 согласно правилу декомпозиции) 3. АР— э СР (следует из п. 2 согласно правилу дополнения) 406 Часть Ш. Проектирование базы данных 4.
СВ -з ЕЕ (дано) 5. А — з ЕЕ (следует из пп, 3 и 4 согласно правилу транзитивности) 6. АР— > Е (следует из п. 5 согласно правилу декомпозиции) ° 10.5. Замыкание множества атрибутов В принципе, замыкание Б для заданного множества функциональных зависимостей Б можно вычислить с помощью слелуюшего алгоритма: "Применять правила из предыдущего раздела до тех пор, пока создание новых функциональных зависимостей не прекратится".
На практике релко требуется вычислить замыкание само по себе, а потому и только что упомянутый алгоритм вряд ли будет достаточно эффективным. Однако из этого раздела вы узнаете, как можно вычислить некоторое подмножество замыкания, а именно — то подмножество, которое состоит из всех функциональных зависимостей с некоторым (указанным) множеством 2 атрибутов, расположенных слева, Точнее говоря,мы покажем, что для заданной переменной- отношения й, заланного множества атрибутов этой переменной-отношения 2 и заданного множества функциональньгх зависимостей Б, выполняющихся лля переменной-отношения й, можно найти множество всех атрибуюв переменной-отношения й, которые функционально зависимы от 2, т.е.
так называемое замыкание 2 множества 2 в пределах Бз. Простой алгоритм вычисления этого замыкания показан на рис. 10.2. Упражнеггие. Докажите правильность этого алгоритма. Рис. 20.2. Вычисление заиыкания 2 .иножества 2 в пределак Б Пример. Предположим, что дана переменная-отношение й с атрибутами А, В, С, О, Е и Е и следующими функциональными зависимостями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
