Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Декомпозиция отношения без потерь. Теорема Хеза


Как было показано выше, алгоритм нормализации состоит в выявлении функциональных зависимостей предметной области и соответствующей декомпозиции отношений. Предположим, что мы уже имеем работающую систему, в которой накоплены данные. Пусть данные корректны в текущий момент, т.е. факты предметной области правильно отражаются текущим состоянием базы данных. Если в предметной области обнаружена новая функциональная зависимость (либо она была пропущена на этапе моделирования предметной области, либо просто изменилась предметная область), то возникает необходимость заново нормализовать данные. При этом некоторые отношения придется декомпозировать в соответствии с алгоритмом нормализации. Возникают естественные вопросы – что произойдет с уже накопленными данными? Не будут ли данные потеряны в ходе декомпозиции? Можно ли вернуться обратно к исходным отношениям, если будет принято решение отказаться от декомпозиции, восстановятся ли при этом данные?

Для ответов на эти вопросы нужно ответить на вопрос – что же представляет собой декомпозиция отношений с точки зрения операций реляционной алгебры? При декомпозиции мы из одного отношения получаем два или более отношений, каждое из которых содержит часть атрибутов исходного отношения. В полученных новых отношениях необходимо удалить дубликаты строк, если таковые возникли. Это в точности означает, что декомпозиция отношения есть не что иное, как взятие одной или нескольких проекций исходного отношения так, чтобы эти проекции в совокупности содержали (возможно, с повторениями) все атрибуты исходного отношения. Т.е., при декомпозиции не должны теряться атрибуты отношений. Но при декомпозиции также не должны потеряться и сами данные. Данные можно считать не потерянными в том случае, если возможна обратная операция – по декомпозированным отношениям можно восстановить исходное отношение в точности в прежнем виде. Операцией, обратной операции проекции, является операция соединения отношений. Имеется большое количество видов операции соединения. Т.к. при восстановлении исходного отношения путем соединения проекций не должны появиться новые атрибуты, то необходимо использовать естественное соединение.

Определение. Проекция отношения на множество атрибутов называется собственной, если множество атрибутов является собственным подмножеством множества атрибутов отношения (т.е. множество атрибутов не совпадает с множеством всех атрибутов отношения ).

Определение. Собственные проекции и отношения называются декомпозицией без потерь, если отношение точно восстанавливается из них при помощи естественного соединения для любого состояния отношения :



.

Рассмотрим пример, показывающий, что декомпозиция без потерь происходит не всегда.

Пример. Пусть дано отношение :

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

НОМЕР ФАМИЛИЯ ЗАРПЛАТА
Иванов
Петров

Рассмотрим первый вариант декомпозиции отношения на два отношения:

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

НОМЕР ЗАРПЛАТА

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

ФАМИЛИЯ ЗАРПЛАТА
Иванов
Петров

Естественное соединение этих проекций, имеющих общий атрибут "ЗАРПЛАТА", очевидно, будет следующим (каждая строка одной проекции соединится с каждой строкой другой проекции):

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

НОМЕР ФАМИЛИЯ ЗАРПЛАТА
Иванов
Петров
Иванов
Петров

Итак, данная декомпозиция не является декомпозицией без потерь, т.к. исходное отношение не восстанавливается в точном виде по проекциям.

 

Рассмотрим другой вариант декомпозиции:

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

НОМЕР ФАМИЛИЯ
Иванов
Петров

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

НОМЕР ЗАРПЛАТА

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

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

НОМЕР ФАМИЛИЯ ЗАРПЛАТА
Иванов
Петров
Сидоров

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

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

НОМЕР ФАМИЛИЯ
Иванов
Петров
Сидоров

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

НОМЕР ЗАРПЛАТА

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

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

НОМЕР ФАМИЛИЯ ЗАРПЛАТА
Иванов
Петров
Петров
Сидоров
Сидоров

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

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

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

Т.к. алгоритм нормализации (приведения отношений к 3НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т.е. в ходе нормализации не происходит потери информации.

<== предыдущая лекция | следующая лекция ==>
Алгоритм нормализации отношений (приведение к 3НФ) | И их характеристика

Дата добавления: 2014-01-03; Просмотров: 1289; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.