Минимальное покрытие множества функциональных зависимостей

Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.

Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+

S2+. Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1+ = S2+.

Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

1. правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);
2. детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т. е. порождению множества FD, не эквивалентного S1);
3. удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.

Чтобы продемонстрировать минимальные и неминимальные множества FD, вернемся к примеру отношения СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК} с рис. 6.1. Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ

СЛУ_ИМЯ, СЛУ_НОМСЛУ_ЗАРП, СЛУ_НОМПРО_НОМ, ПРО_НОМПРОЕКТ_РУК} будет минимальным. Действительно, в правых частях FD этого множества находятся множества, состоящие ровно из одного атрибута; каждый из детерминантов тоже является множеством из одного атрибута, удаление которого, очевидно, недопустимо; удаление каждой FD явно приводит к изменению замыкания множества FD, поскольку утрачиваемая информация не выводится с помощью аксиом Армстронга.

С другой стороны, множества FD

1. {СЛУ_НОМ
   
   {СЛУ_ИМЯ, СЛУ_ЗАРП}, СЛУ_НОМ
   
   ПРО_НОМ, СЛУ_НОМ
   
   ПРОЕКТ_РУК, ПРО_НОМ
   
   ПРОЕКТ_РУК},
2. {СЛУ_НОМ
   
   СЛУ_ИМЯ, {СЛУ_НОМ, СЛУ_ИМЯ}
   
   СЛУ_ЗАРП, СЛУ_НОМ
   
   ПРО_НОМ, СЛУ_НОМ
   
   ПРОЕКТ_РУК, ПРО_НОМ
   
   ПРОЕКТ_РУК} и
3. {СЛУ_НОМ
   
   СЛУ_НОМ, СЛУ_НОМ
   
   СЛУ_ИМЯ, СЛУ_НОМ
   
   СЛУ_ЗАРП, СЛУ_НОМ
   
   ПРО_НОМ, СЛУ_НОМ
   
   ПРОЕКТ_РУК, ПРО_НОМ
   
   ПРОЕКТ_РУК}

не являются минимальными. Для множества (1) в правой части первой FD присутствует множество из двух элементов. Для множества (2) удаление атрибута СЛУ_ИМЯ из детерминанта второй FD не меняет замыкание множества FD.

Содержание  Назад  Вперед

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---