ВВЕДЕНИЕ В СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ


Корректность процедуры нормализации - декомпозиция без потерь. Теорема Хеза - часть 3


Например, предположим, что отношение
перешло в состояние:

НОМЕР

ФАМИЛИЯ

ЗАРПЛАТА

1 Иванов 1000
2 Петров 1000
2 Сидоров 2000

Таблица 13 Отношение

Кажется, что этого не может быть, т.к. значения в атрибуте "НОМЕР" повторяются. Но мы же ничего не говорили о ключе этого отношения! Сейчас проекции будут иметь вид:

НОМЕР

ФАМИЛИЯ

1 Иванов
2 Петров
2 Сидоров

Таблица 14 Отношение

НОМЕР

ЗАРПЛАТА

1 1000
2 1000
2 2000

Таблица 15 Отношение

Естественное соединение этих проекций будет содержать лишние кортежи:

НОМЕР

ФАМИЛИЯ

ЗАРПЛАТА

1 Иванов 1000
2 Петров 1000
2 Петров 2000
2 Сидоров 1000
2 Сидоров 2000

Таблица 16 Отношение

Вывод. Таким образом, без дополнительных ограничений на отношение

нельзя говорить о декомпозиции без потерь.

Такими дополнительными ограничениями и являются функциональные зависимости. Имеет место следующая теорема Хеза [54]:

Теорема (Хеза). Пусть

является отношением, и
- атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость
, то проекции
и
образуют декомпозицию без потерь.

Доказательство. Необходимо доказать, что

для любого состояния отношения
. В левой и правой части равенства стоят множества кортежей, поэтому для доказательства достаточно доказать два включения для двух множеств кортежей:
и
.

Докажем первое включение. Возьмем произвольный кортеж

. Докажем, что он включается также и в
. По определению проекции, кортежи
и
. По определению естественного соединения кортежи
и
, имеющие одинаковое значение
общего атрибута
, будут соединены в процессе естественного соединения в кортеж
. Таким образом, включение доказано.

Докажем обратное включение. Возьмем произвольный кортеж

. Докажем, что он включается также и в
. По определению естественного соединения получим, что в имеются кортежи
и
. Т.к.
, то существует некоторое значение
, такое что кортеж
. Аналогично, существует некоторое значение
, такое что кортеж
.


Начало  Назад  Вперед