. Элементы теории нормальных форм реляционных баз данных.

Работа добавлена на сайт samzan.net:

3.1. Элементы теории нормальных форм реляционных баз данных.

В реляционных базах данных схема содержит как структурную, так и семантическую информацию.

Структурная информация связана с объявлением отношений.

Семантическая выражается множеством известных функциональных зависимостей между атрибутами отношений, объявленных в схеме.

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

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

Нормализация – это пошаговый обратимый процесс замены данной схемы (или совокупности отношений) другой схемой, в которой отношения имеют более простую и регулярную структуру.

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

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

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

Нормализация отношений базируется на понятиях функциональной зависимости и полной функциональной зависимости.

Функциональная зависимость.

Атрибут B в отношении R функционально зависит от атрибута A того же отношения если в каждый момент времени каждому значению атрибута A соответствует не более чем одно значение атрибута B, связанного с A в отношении R.

Утверждение, что В функционально зависит от А, означает то же самое, что А однозначно определяет В, т.е. если в какой-то момент времени известно значение А, то можно получить и значение В.

Обозначение функциональной зависимости:

Рассмотрим отношение:

Служащий (номер_служащего, ФИО_служащего, зарплата, номер_проекта, дата_окончания).

Рассмотрим функциональные зависимости этого отношения:

ФИО_служащего	→ (определяет атрибут)	номер_служащего
номер_служащего	→	ФИО_служащего
ФИО_служащего или номер_служащего	→	зарплата
ФИО_служащего или номер_служащего	→	номер_проекта
ФИО_служащего или номер_служащего	→	дата_окончания
номер_проекта	→	дата_окончания

Атрибут номер_служащего не является функционально зависимым от атрибута зарплата, т.к. несколько служащих могут иметь одинаковую зарплату.

Представим функциональные зависимости нашего отношения в виде диаграммы.

Все функциональные зависимости обозначим в виде стрелок:

Ключом данного отношения, т.е. атрибутом однозначно идентифицирующем кортеж, могут быть номер_служащего или ФИО_служащего.

Мы будем их называть первичными атрибутами.

Полная функциональная зависимость.

Функциональная зависимость А → В называется полной функциональной зависимостью, если В зависит от всей группы атрибутов А, а не от ее части (подмножества).

Например, если А = А1, А2, А3, …, Ак и А1, А2 → В, то функциональная зависимость В от А неполная.

3.2. 1-я нормальная форма (1НФ).

Отношение находится в первой нормальной форме, если значения всех атрибутов простые (атомарны), т.е. значение атрибута не должно быть множеством или повторяющейся группой.

Ненормализованному отношению соответствует многоуровневая таблица, в отличие от однородной табличной структуры нормализованного отношения.

Пример.

Рейсы (номер, пункт_отправления, пункт_назначения, расписание).

Расписание (день, время_вылета).

Для преобразования этого ненормализованного отношения в 1НФ необходимо в составном отношении Рейсы заменить отношение расписание соответствующими атрибутами.

Рейсы (номер, пункт_отправления, пункт_назначения, день, время_вылета).

3.3. 2-я нормальная форма (2НФ).

Почему проект базы данных может быть плохим.

Рассмотрим для этого следующий пример.

Дана схема отношения:

Поставщики (номер_пост, фирма_пост, адрес_пост, товар, цена).

Перейдем к табличному представлению этой схемы и заполним эту таблицу несколькими записями:

номер_пост	фирма_пост	адрес_пост	товар	цена
N1	Ф1	А1	Т11	Ц11
N1	Ф1	А1	Т12	Ц12
N2	Ф2	А1	Т21	Ц21

Есть ли проблемы у этой таблицы с точки зрения ее компьютерной реализации. Оказывается есть. 4 проблемы:

1.  Избыточность. Адрес поставщика повторяется для каждого его товара.
2.  Потенциальная противоречивость (аномалии обновления). Вследствие избыточности мы может обновить адрес поставщика в одном кортеже, оставляя его неизменным в другом. Таким образом, может оказаться, что для некоторых поставщиков нет единого адреса.
3.  Аномалии включения. В базу данных не может быть записан адрес поставщика если он не поставляет по меньшей мере один товар.
4.  Аномалии удаления. Если поставщик прекращает поставки, то мы утрачиваем и его адрес.

Выводы:

1.  Итак, если мы хотим проанализировать таблицу базы данных, нужно заполнить ее несколькими записями и провести анализ заполненной базы.
2.  Мы обнаружили, что есть три вида аномалий у баз данных:
   1.  Аномалии обновления
   2.  Аномалии включения
   3.  Аномалии удаления
3.  таблицы с аномалиями нельзя включать в базу данных при ее реализации на компьютере.

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

Для декомпозиции отношения необходимо построить функциональные зависимости этого отношения.

Для нашего примера будем иметь следующую схему функциональных зависимостей.

Первичным ключом отношения являются атрибуты номер_пост + товар, т.е. ключ сложный.

Проведем декомпозицию исходного отношения на 2 отношения.

Атрибут цена полностью определяется ключом отношения (номер_пост, товар). Атрибут адрес_пост определяется частью ключа, а именно атрибутом номер_пост. Т.е. имеет место неполная функциональная зависимость.

ПТЦ (номер_пост, товар, цена).

ПФА (номер_пост, фирма_пост, адрес_пост).

ПТЦ	ПФА

Благодаря декомпозиции исходного отношения мы избавляемся:

1.  От избыточности данных.
2.  Теперь можно ввести адрес поставщика, даже если в настоящее время он не поставляет товар, т.е. мы ушли от аномалий включения, удаления и оновления.

Посмотрим, как будут выглядеть новые таблицы.

ПТЦ		ПФА
номер_пост	товар	цена		номер_пост	фирма_пост	адрес_пост
N1	Т11	Ц11		N1	Ф1	А1
N1	Т12	Ц12		N2	Ф2	А2
N2	Т21	Ц21

Анализ таблиц подтверждает, что нет аномалий включения, удаления и обновления.

Теперь определение 2НФ.

Отношение находится в 2НФ, если оно находится в 1НФ и каждый атрибут, который является неключевым, полностью зависит от первичного ключа (составного).

Наше отношение Поставщики имело неполную функциональную зависимость. Поэтому оно не находилось во 2НФ и имело 3 вида аномалий.

3.4. 3-я нормальная форма (3НФ).

Определение 3НФ: отношение находится в 3НФ если оно находится во 2НФ и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.

Следующий шаг нормализации – это 3 нормальная форма отношений.

На этом шаге отношекние во 2НФ преобразуется в 3НФ путем ликвидации транзитивной зависимости.

Транзитивная зависимость.

Пусть А, В, С – три атрибута или три набора атрибутов отношения R.

Зависимости между ними изобразим на диаграмме.

Если А → В и В → С В !→ А (В не является ключом), то А → С. В этом случае С транзитивно зависит от А. Преобразование в 3НФ состоит в декомпозиции исходного отношения на 2.

R1	R2

Пусть имеется отношение служащий (номер_служ, фамилия, зарплата, номер_проекта, дата_оконч).

Аномалии отношения служащий.

1.  Включения. До момента привлечения конкретгого служащего к конкретной работе над данным проектом дату окончания проекта записывать некуда.
2.  Удаления. Если проект был приостановлен для привлечения новых сотрудников, т.е. все кортежи были удалены, то в базе уничтожены все записи с датой окончания проекта.
3.  Модификации. Изменение даты окончания проекта ведет к необходимости поиска всех кортежей содержащих данную дату и их модификация.

Разложим отношение на 2:

R1 (номер_служ, фамилия, зарплата, номер_проекта)

R2 (номер_проекта, дата_оконч)

Мы получим отношение в 3НФ. Аномалии уже не будет в R1 и R2.

3.5. Нормальная форма Бойса-Кодда. Алгоритм декомпозии отношений в НФБК.

Если отношение находится в 3Нф, то в некоторых случаях у этих отношений могут быть аномалии обновления. Эта ситуация относится к редким случаям, когда отношение имеет несколько возможных сложных ключей (т.е. состоящих из нескольких атрибутов) и части этих ключей содежрат общие атрибуты. Проблему решает усиленная 3НФ или нормальная форма Бойса-Кодда.

3.5.1. НФБК (определение) – отношение находится в НФБК, если и только если каждый детерминант отношения является возможным ключом.

1.  Возможный ключ (термин). Возможный ключ представляет собой атрибут или набор атрибутов, который может быть использован для данного отношения в качестве первичного (основного) ключа. Однако не исключено наличие других возможных ключей, которые могли бы быть, но не были использованы в качестве первичного ключа.
2.  Детерминант (термин). Если А → В есть функциональная зависимость и В не зависит функционально от любого подмножества А, то говорят, что А представляет собой детерминант R.

3.5.2. Алгоритм проектирования отношений, находящихся в НФБК.

Пусть задано отношение R (A, B, C, D, E) с набором функциональных зависимостей F.

1.  Выделим в наборе функциональных зависимостей F, присущих заданному отношению R, функциональные зависимости, имеющие детерминанты не являющиеся возможным ключом.
2.  Создадим 2 новых отношения R1 и R2 таким образом: Если R (A, B, C, D, E) исходное отношение и C → D выделенная функциональная зависимость, то схема R1 будет иметь вид: R1 (A, B, C, E) и схема R2 будет иметь вид: R2 (C, D). R2 находится в НФБК и называется проекцией R.
3.  Проверим находится ли в НФБК отношение R1.
4.  Если да, то декомпозиция заканчивается, если нет, то возвращается к 1-ому шагу анализируем отношение R1.

Пример 1. на применение алгоритма проектирования отношений, находящихся в НФБК.

	A	B	E	C	D
служащий	(номер_служ,	фамилия,	зарплата,	номер_проекта,	дата_оконч)

Функциональные зависимости F:

{номер_служ → фамилия

номер_служ → зарплата

номер_служ → номер_проекта

номер_служ → дата_оконч

номер_проекта → дата_оконч}

номер_служ – возможный ключ

Выделим номер_проекта → дата_оконч

R2 (номер_проекта, дата_оконч)

R1 (номер_служ, фамилия, зарплата, номер_проекта)

3.6. Корректные и некорректные декомпозиции отношений.

Схема отношения R разложена без потерь на отношения R1, R2, …, RN, если потем естественного соединения полученных отношений мы получим исходное отношение R. Разработаны алгоритмы проверки правильности проведенной декомпозиции.

3.6.1. Аналитическое условие отсутствия потерь при соединении.

Если R1 и R2 являются результатом разложения R с сохранением множетсятва функциональных зависимотей, это разложе6ие обеспечивает соединение без потерь с сохранением функциональных зависимостей тогда и только тогда, если:

(R1 пересечение R2) определяет разность R1 и R2. Операции пересечения и разности определены над списками атрибутов отношений.

Пример.

Дано отношение R

Служащие (сл*, отд, город)

сл* - служащий

отд – отдел, место работы

Семантика: каждый служащий может работать лишь в одной организации и жить лишь в одном городе.

сл* → отд

сл* → город

Декомпозиция 1.

R1 (сл*, отд)

R2 (сл*, город)

= сл*

= отд

= город

сл* → отд

сл* → город.

Значит разложение без потерь.

Декомпозиция 2.

R1 (сл*, отд)

R2 (отд, город)

= отд

= сл*

= город

отд → сл*

отд → город

Таких зависимостей в исходном множестве F нет, поэтому декомпозиция 2 является разложением с потерями.

Проверим это утверждение на данных отношения R.

служащие	(сл*,	отд,	город)
	525-11	обувь	Финикс
	345-055	обувь	Чикаго

Декомпозиция 1.

R1	(сл*,	отд)		R2	(сл*,	город)
	525-11	обувь			525-11	Финикс
	345-055	обувь			345-055	Чикаго

Т.е. R1 [ сл* = сл* ] R2 = R

R	(сл*,	отд,	город)
	525-11	обувь	Финикс
	345-055	обувь	Чикаго

Получили соединение без потерь.

Декомпозиция 2.

R1	(сл*,	отд)		R2	(отд,	город)
	525-11	обувь			обувь	Финикс
	345-055	обувь			обувь	Чикаго

R = R1 [ отд = отд ] R2 =	525-11	обувь	Финикс
	525-11	обувь	Чикаго
	345-055	обувь	Финикс
	345-055	обувь	Чикаго

Для 20ого случая декомпозиции естественное соединение R1*R2 является соединением с потерями.

Под потерями поминается потеря исходного состояния, которое может проявляться и в лишних записях.

3.6.2. Метод табло.

Когда мы имеем дело с разложениями, состоящими более чем из 2-х отношений, используется метод табло – алгоритм проверки на соединение без потерь.

Рассмотрим пример.

Пусть задано отношение R со схемой R (A, B, C, D) и функциональные зависимости A →C, B→ C, CD →B, C → D.

Схема после разложения имеет вид R1 (A, B), R2 (B, D), R3 (A, B, C), R4 (B, C, D)

Построим следующую таблицу:

				j
				→
				1	2	3	4
				A	B	C	D
i	→	1	R1	a1	a2	b13	b14
		2	R2	b21	a2	b23	a4
		3	R3	a1	a2	a3	b34
		4	R4	b41	a2	a3	a4

Алгоритм проверки на соединение без потерь состоит из 3-х разделов. Сформулируем каждый из них и применим его к нашему примеру.

Раздел 1.

Заполним таблицу следующим образом:

1.  Если отношение содержит один из атрибутов А÷0 ставим а с индексом столбца.
2.  Если отношение не содержит атрибут А÷0, то ставим b с 2-мя индексами (1 – строки, 2  -столбца).

Раздел 2.

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

1.  А → С. Если для атрибутов из А найдутся строки, где стоят аj, то элементы bij соответствующие столбцам атрибутов C заменяются на аj.

				j
				→
				1	2	3	4
				A	B	C	D
i	→	1	R1	a1	a2	а3	b14
		2	R2	b21	a2	b23	a4
		3	R3	a1	a2	a3	b34
		4	R4	b41	a2	a3	a4

1.  В → С.

				j
				→
				1	2	3	4
				A	B	C	D
i	→	1	R1	a1	a2	а3	b14
		2	R2	b21	a2	а3	a4
		3	R3	a1	a2	a3	b34
		4	R4	b41	a2	a3	a4

1.  C → D.

				j
				→
				1	2	3	4
				A	B	C	D
i	→	1	R1	a1	a2	а3	а4
		2	R2	b21	a2	а3	а4
		3	R3	a1	a2	a3	а4
		4	R4	b41	a2	a3	а4

Раздел 3.

Если появляется строка таблицы, полностью заполненная аj, то данное соединение без потерь, в противном случае – это соединение с потерями.

3.7. 4-я нормальная форма (4НФ).

Пусть в отношении R (x, y, z) присутствует многозначная зависимость x →→ y и

x →→ z.

Проведем анализ этого отношения, заполнив отношение записями.

R	(x,	y,	z)
1	x1	y1	z1
2	x1	y1	z2
3	x1	y2	z2
4	x1	y2	z3

Элементы y1 во второй записи и y2 в 4-ой записи избыточны. Избыточность приводит к аномалиям обновления.

Если в отношении R (x, y, z) существует MV-зависимость x →→ y, то оно без потерь информации разлагается на отношение со схемами R1 (x, y) и R2 (x, z).

Заполним эти отношения R1 и R2 нашими данными.

R1	(x,	y)		R2	(x,	z)
	x1	y1			x1	z1
	x1	y2			x1	z2
					x1	z3

Избыточность в отношениях R1 и R2 исчезает, т.е. нет аномалий обновления. Отсутствие аномалий есть признак того, что отношение находится в нормальной форме.

Отношения R1 и R2 находятся в 4НФ.

Определение: Если в отношении R(x, y), где x и y непересекающиеся подмножества, существует только зависимость x →→ y, и если правая и левая части зависимости содержат все атрибуты R, то отношение находится в 4НФ.

3.8. Алгоритм проектирования баз данных методом анализа функциональных и множественных зависимостей.

1.  На основании системно-комплексного анализа объекта автоматизации и исходя из концептуальной модели структурного аспекта информационной страты объекта 1-ого уровня

определяются информационные элементы объекта (или отношения) – Ei.

1.  Исходя из концептуальной модели структурного аспекта информационной страты второго утовня:

определяются атрибуты каждого отношения (eij) и все F-зависимости и MV-зависимости каждого из отношений (Vijk).

1.  MV-зависимости каждого из отношений используются для декомпозиции отношений. Выделяются отношения, находящиеся в 4НФ и отношения, имеющие только F-зависимости.
2.  Из каждого набора F-зависимостей каждого отношения удаляются избыточные функциональные зависимости (ФЗ) на основании вывода с целью получения минимального покрытия этого отношения.
3.  Проводится декомпозиция каждого отношения в набор отношений, находящихся в НФБК (нормальной форме Бойса-Кодда).
4.  Методом табло проверятся правильность декомпозиции.
5.  Полученный набор отношений контролируется на предмет невыявленных проблем.

1. тема зашифровки наследственной информации в молекулах нуклеиновых кислот
2. НА ТЕМУ- ЗАСОБИ ДОГЛЯДУ ЗА НОВОНАРОДЖЕНИМИ використання одноразових підгузників при догляді за новона
3. Осетинская литература
4. носителе по адресу- Вологодская обл
5. Классификация сигналов- Все сигналы разделяют на две крупных группы- детерминированные и случайные
6. 25 РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата біологічних наук1
7. Что там хранится Какие неведомые силы скрываются в человеческом подсознании Как оно влияет на нашу жизнь Н
8. Система государственного управления
9. хорошим воскресным папой
10. Красная Пресня
11. Проблема применения моделей устойчивого развития на региональном уровне
12.  Співполімер полімеризація суміші молекул різних мономерів
13.  Рисунок 3
14. Образ города в поэме Мертвые души
15. Бригадна форма організації та оплати праці
16. Евгений Онегин первый русский реалистический социальнопсихологический роман причем что существенно н
17. Утверждаю Согласовано Проректор по УМР Г1
18. Болотников Иван Исаевич
19. Целью таких вызовов может стать банальное хулиганство желание прославиться срыв работы важного объекта ил
20. утверждать выкрикивать протестовать

Материалы собраны группой SamZan и находятся в свободном доступе