Главная » SQL, Базы данных » ЗАМЫКАНИЕ МНОЖЕСТВА АТРИБУТОВ

0

В принципе, замыкание S+ для заданного множества функциональных зависимостей S можно вычислить с помощью следующего алгоритма: "Повторно применять правила из предыдущего раздела до тех пор, пока остается  возможным  создание новых функциональных зависимостей". Но на практике редко требуется вычислить замыкание как таковое, а потому и только что упомянутый алгоритм вряд ли будет достаточно эффективным. Однако из этого раздела вы узнаете, как можно вычислить некоторое подмножество замыкания, а именно то подмножество, которое состоит из всех функциональных зависимостей с некоторым (указанным) множеством z атрибутов, расположенных в  левой части выражения зависимости. Точнее говоря, мы покажем, что для заданной переменной отношения R, заданного множества атрибутов этой переменной отношения z и заданного множества функциональных зависимостей S, выполняющихся для переменной

Глава 11. Функциональные зависимости                                         445 отношения R, можно найти множество3 всех атрибутов переменной отношения R, которые функционально зависимы от Z, т.е. так называемое замыкание Z+  множества Z в пределах S. Простой алгоритм вычисления этого замыкания показан на рис. 11.2. Упражнение. Докажите правильность этого алгоритма.

Рис. 11.2. Вычисление замыкания Z+ множества Z в пределах S

Пример. Предположим, что дана переменная отношения R с атрибутами А, В, С, D, Е и

F и следующими функциональными зависимостями.

А    →  ВС

Е     →  CF В     →  Е CD  →  EF

Вычислим   замыкание   {А,   В } +     множества   атрибутов   {А,   В}   исходя   из заданного множества функциональных зависимостей.

9.          Присвоим замыканию CLOSURE [ Z, S ] начальное значение — множество

{А, В}.

10.    Выполним внутренний цикл четыре раза — по одному разу для каждой заданной функциональной зависимости. После первой итерации (для зависимости А → ВС) будет обнаружено, что левая часть действительно является подмножеством замыкания CLOSURE [ Z, S ]. Таким образом, к результату можно добавить атрибуты B и C. Теперь замыкание CLOSURE

[Z,  S] представляет собой множество {А, В, С }.

11.    После второй итерации (для зависимости Е → CF)  обнаруживается,  что левая часть не является подмножеством полученного до этого момента результата, который, таким образом, остается неизменным.

12.    После третьей итерации (для зависимости В → Е) к замыканию CLOSURE

[Z, S] будет добавлено множество Е, поэтому замыкание теперь будет иметь вид {А, B, С, Е}.

13.    После четвертой итерации (для зависимости CD → EF) замыкание CLOSURE [Z , S] останется неизменным.

3   Обратите внимание, что тем самым определены два типа замыканий: замыкание множества  функциональных зависимостей  и замыкание множества  атрибутов, которые определены в множестве  функциональных зависимостей. Следует также отметить, что для тех и других применяется одна и та же  система обозначений в виде знака "плюс" в позиции  верхнего  индекса.  Автор  надеется,  что  такое  двойное  применением  одинаковой  системы  обозначений  не приведет к путанице.

14.   Далее внутренний цикл выполняется еще четыре раза. После первой итерации ре зультат останется прежним, после второй он будет расширен до {A,B,C,E,F },a после третьей и четвертой — снова не изменится.

15.   Наконец, после еще одного четырехкратного прохождения цикла замыкание

CLOSURE [ Z, S ] останется неизменным и весь процесс завершится с результатом

{А,В}+                                        =    {A ,B, C ,E,F }.

Следует отметить, что если Z (как было указано выше) — множество атрибутов переменной отношения R, a S — множество функциональных зависимостей, которые соблюдаются в R, то множество функциональных зависимостей,  которые  соблюдаются в R и содержат z в левой части, представляет собой  множество, состоящее из всех функциональных зависимостей в форме Z →  Z’,  где Z’ — некоторое подмножество замыкания Z+ множества z, принадлежащего к S. В таком случае замыкание S+  первоначального множества функциональных зависимостей S представляет собой объединение всех подобных множеств функциональных зависимостей, взятых по всем множествам атрибутов Z.

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

Еще одно важное заключение основано на следующем факте. Прежде всего, вспомним определение понятия суперключа из главы 9. Суперключ переменной отношения R — это множество атрибутов переменной отношения R, которое в виде подмножества (но не обязательно строгого подмножества) содержит по крайней  мере один потенциальный ключ. Из этого определения непосредственно следует, что суперключи для данной переменной отношения R — это такие подмножества к множества атрибутов переменной отношения R, что функциональная зависимость

К →  А

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии