20

Дана переменная-отношение NADDR (NAME , STREET, CITY, STATE, ZIP), где каждому индексу соответствует только один город и штат, а каждой улице, городу и штату соответствует только один индекс. Найдите неприводимое множество функциональных зависимостей для NADDR.

(min покрытие == ФЗ (функциональные зависимости) явл. неприводимым)

Множество ФЗ явл. неприводимым (min покрытие) тогда и только тогда, когда обладает след. свойствами:

Детерминант - левая часть. Зависимая часть - правая.

1. Для любой ФЗ X->Y, Y - один элемент.
2. Ни одну ФЗ нельзя удалить без изменения замыкания. (Пробуем удалить и смотрим на замыкание, поменялось?)
3. Ни один атрибут не может быть удален из детирминанта без изменения замыкания.

Введем обозначения: N = NAME, T = STREET, C = CITY, E = STATE, Z = ZIP

ZIP - Это индекс?

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

S = {Z -> CE, TCE -> Z}

1. S = { Z -> C, Z -> E, TCE -> Z }

2. Удаляем избыточные ФЗ:

Удаляем Z -> C => S = {Z -> E, TCE -> Z } {Z}+ = {Z,E} - C не входит в {Z}+, значит не можем удалить.

Удаляем Z -> E => S = {Z -> C, TCE -> Z } {Z}+ = {Z,С} - E не входит в {Z}+, значит не можем удалить.

Удаляем TCE -> Z => S = { Z -> C, Z -> E} {T,C,E}+={T,C,E} - Z не входит в {T,C,E}+, значит не можем удалить.

3. Удаляем атрибуты из детирминанта и смотрим, изменилось ли замыкание?

S = { Z -> C, Z -> E, TCE -> Z }

• Для T: Удаляем TCE -> Z и добавляем CE -> Z {C,E}+ = {C,E,Z} не содержит T - не избыточный атрибут.
• Для C: Удаляем TCE -> Z и добавляем TE -> Z {T,E}+ = {T,E,Z,C...} - Содержит C, значит заменяем.

S = { Z -> C, Z -> E, CE -> Z }

• Для C: Заменяем CE -> Z на E -> Z {E}+={E,Z,C...} - Содержит C, значит заменяем.

Результат: S = { Z -> C, Z -> E, E -> Z }

<- or ->