2.9. Составные функциональные зависимости и кольцевые покрытия
Составная зависимость – краткая запись одного класса эквивалентности.
В левую часть входит список всех левых частей функциональной зависимости класса эквивалентности.
Правая часть – объединение атрибутов правых частей функциональных зависимостей одного класса эквивалентности
(A, B) →ABC,
из которого исключаются атрибуты, содержащиеся в левой части всех зависимостей.
Любое множество функциональных зависимостей, на основании которого построена составная зависимость, называется характеристическим.
Рис. 2.1 - Кольцевое характеристическое множество функциональных зависимостей.
Две составные зависимости эквивалентны, если эквивалентны их характеристические множества.
Две системы составных функциональных зависимостей эквивалентны, если эквивалентны объединения систем характеристических множеств для каждой зависимости. Для системы составных функциональных зависимостей определено понятие минимального кольцевого редуцированного покрытия.
Если система составных зависимостей получена по минимальному покрытию функциональных зависимостей, то эта система будет минимальной кольцевой, но не всегда редуцированной справа и слева.
Правая редукция для составных зависимостей: пытаются последовательным перебором удалить хотя бы один атрибут из правой части хотя бы одной из функциональных зависимостей.
Удалить атрибут из правой части можно будет только в том случае, если в модифицированной системе система характеристических множеств будет эквивалентна исходной.
Пример.
.
Составная зависимость для f:
.
Проверяем правую редукцию:
,
,
fd≡fd’,
fd’ |= D1D2→A.
3. Нормализация баз данных
3.1. Декомпозиция таблицы на две таблицы без потери информации и с потерей информации
g=g(A B C) – исходная таблица.
a1 b1 c1
a2 b1 c1
a1 b1 c2
r=pr(A B)g=r(A B) – операция проекции.
a1 b1
a2 b1
s=pr(A C)g=s(A C)
a1 c1
a2 c1
a1 c2
g’=r
s
– операция естественного соединения.
g(A B C)
a1 b1 c1
a1 b1 c2
a2 b1 c1
r=pr(A B)=r(A B)
a1 b1
a2 b1
s=pr(B C)=s(B C)
b1 c1
b1 c2
r
s=g’(A
B C)
a1 b1 c1
a1 b1 c2
a2 b1 c1
a2 b1 c2
Мы получили декомпозицию с потерей информации(получилось в g’ на одну запись больше, чем в g).
1) R={A,B}
S={A,C}
2) R={A,B}
S={B,C}
Правило для проверки разбиения:
если R
S→S
\ R
или R
S→R
\ S,
то разбиение без потери информации.
1) R S={A},
S \ R={C},
R \ S={B}.
A→C не выполняется, A→B. Следовательно, возможно разбиение без потери информации.
2) R S={B},
S \ R={C},
R \ S={A}.
B→C не выполняется, B→A не выполняется. Следовательно, невозможно разбиение без потери информации.
- неизбыточное
леворедуцированное и праворедуцированное
покрытие.
Два класса эквивалентности:
Ef(A)={A→C},
Ef(B)={B→C}.
Составные зависимости:
g=(ABC)
Декомпозиция на две таблицы:
r=(A,C)
s=(B,C)
R S={С}
R \ S={A}
S \ R={B}
C→A – не выполняется
C→B – не выполняется
Следовательно, получили декомпозицию с потерей информации.
Метод проектирования структуры БД при помощи синтеза (альтернативно называется метод декомпозиции) позволяет получить структуру БД в 3НФ, но при этом в общем случае возможно разбиение исходных представлений (таблиц) с потерей информации. В результате естественного соединения базовых таблиц, таблица представления будет иметь больше строк, чем ее исходное представление.
Универсальная зависимость – это зависимость из всех аргументов всех функциональных зависимостей.
|=
.
Левая редукция:
.
Классы эквивалентности:
Ef(A)={A→C},
Ef(B)={B→C},
Ef(AB)={AB }.
Кольцевое покрытие:
.
Получим декомпозицию на 3 таблицы.
r=(A,C),
s=(B,C),
t=(A,B).
1) t s={B},
s \ t={C},
t \ s={A}.
B→C, B→A выполняются.
2) r s={C},
r \ s={A},
s \ r={B},
C→A, C→B не выполняются.
3) t r={A},
t \ r={B},
t \ r={C},
A→B, A→C выполняются.
Следовательно, получим декомпозицию с потерей информации.
Для того чтобы соединение было без потерь информации, к исходной системе функциональных зависимостей добавляется универсальная зависимость.
Универсальная зависимость – это функциональная зависимость, у которой левая часть – объединение атрибутов всех зависимостей системы, а правая часть – это имя этой системы (таблицы).