Модуль2_Проектирование БД

Модуль 2. Проектирование баз данных

Лекция 11. Декомпозиция схем отношений

Аномалии операций включения и удаления данных

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

Рассмотрим пример аномалии для включения данных.

Пусть дано отношение Студент, имеющее следующую структуру:

СТУДЕНТ (Факультет, Специальность, ФИО, Успеваемость, Стипендия).

Атрибуты Специальность и ФИО вместе образуют первичный ключ отношения.

При организации приема по вновь вводимой специальности (пока еще не принят ни один студент и ФИО является NUUL) оказывается невозможным добавить строку с названием специальности и факультета, на котором планируется осуществлять обучение.

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

80

Поставки (Продукция, Количество, Дата, Потребитель, Адрес)

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

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

Введем понятие декомпозиции схемы отношения.

Пусть задана С(А1, А2,…, Аn) – схема произвольно отношения (шапка таблицы), где С - имя отношения,

А1, А2, . . . , Аn – имена атрибутов в отношении.

Тогда, декомпозицией схемы С называется множество новых схем отношений

S = { С1, С2, …, Cn },
где Сi, i =		1, n - схемы отношений, удовлетворяющие условиям:
Ci C	,
			= n
C 1 C 2		... C n		C i	= C
			i =	1	.

Таким образом, декомпозиция схемы – это разложение множества ее

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

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

81

Декомпозиция схемы отношения с сохранением информации

Как следует из названия, декомпозиция с сохранением информации преобразует исходное отношение R со схемой C(А1, А2, … Аn) в систему новых отношений ri , где i=1, m со схемами Ci таких, что по ним могут быть восстановлены все строки исходного отношения R.

Декомпозиции с сохранением информации схемы С на схемы Ci (i=1,

m)соответствует преобразование отношения R в отношения ri (i=1, m)

операциями проектирования ri = Pci (R) по множествам атрибутов, входящих в схемы Ci (i=1, m). Для сохранения информации в новых отношениях ri

		m
должно выполняться условие:	R	>< ri ,
		i =	1

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

Определяемая декомпозиция и соответствующие ей отношения показаны на рис. 11.1.

82

Исходная схема Исходное отношение

C(А1,А2,…,Аn)	→		R
Декомпозиция схемы			Декомпозиция
			отношения
С1 С2 … Сm	→	r1 r2	rm

					Отношение, восстановленное
	Исходное отношение R				естественным соединением
		А1 А2 …. Аn
			rm				А1 А2 …. Аn
				А1
					…….

. . . . . .

r1 Аk ……

Отношения, полученные проекцией отношения R

Рис. 11.1. Декомпозиция отношения с сохранением информации Обратите внимание, декомпозиция с сохранением информации требует,

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

83

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

Пусть дано отношение R со схемой C(А1, А2, А3), имеющее два кортежа:

	А1	А2	А3
R =
	a	в1	с1
	a	в2	с2

Декомпозиция схемы C на схемы С1 (А1, А2) и С2 (А1, А3) создает из исходного отношения R с помощью операции проекции два новых отношения r1 и r2

	А1	А2
r1 =PС1(R) =
	a	в1
	a	в2
r2 =PС2(R) =	А1	А3
	a	с1
	a	с2

Проверим, можно ли путем естественного соединения по атрибуту А1 отношений r1 и r2 восстановить исходное отношение. В результате соединения и удаления дублирующего столбца имеем:

			А1	А2	А3
			a	в1	с1
	r1 >< r2	=	a	в2	с1
			a	в1	с2
			a	в1	с2

Полученное естественным соединением отношение содержит все кортежи исходного отношения R и дополнительно два новых кортежа.

84

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

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

При декомпозиции отношения важно иметь в виду, что информация в таблицах представлена не только значениями данных в ячейках (полях) таблицы, но и тем, что данные расположены в соседних ячейках, а значит, принадлежат одному объекту. Например, запись в соседних ячейках фамилии Толстой, имени Лев и романа «Война и мир» определяет книгу одного определенного автора, а значения атрибутов Толстой, Алексей и «Князь Серебряный», находясь в другой строке таблицы, - книгу другого автора. Т.е. значения определенных атрибутов отношения (названия книги) могут быть зависимы от других атрибутов (фамилия и имя автора) и должны находиться в одном отношении для сохранения соответствия авторов их книгам. В то же время независимые группы атрибутов во избежание аномалий включения и удаления предпочтительно размещать в разных отношениях.

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

Функциональная зависимость атрибутов отношения

Пусть задано произвольное отношение R со схемой С, причем Х и У -

подмножества атрибутов из схемы С, т.е. X C	и	Y C .
Тогда говорят, подмножество атрибутов Х функционально определяет
подмножество атрибутов У (записывается	Х	Æ У ), или атрибуты У

85

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

Функциональную зависимость атрибутов демонстрирует следующий рис 11.2.

ХУ

Совпадают между собой значения атрибутов Х из разных строк

Совпадают между собой значения атрибутов У

	Атрибуты X			Атрибуты Y
	равны			равны
		Рис. 11.2. Функциональная зависимость атрибутов Y от X
	Функциональная зависимость (ФЗ) однозначна, т.е. конкретному
значению		аргумента Х всегда соответствует определенное			значение
функции		У. При этом значение атрибута У (функции) может совпадать для
разных аргументов Х.				Например, свойство предметной области, состоящее в
том, что конкретному номеру паспорта гражданина (атрибут Х)					соответствует
определенная фамилия (атрибут У) задается ФЗ

{ №паспорта } Æ {Фамилия}. Причем наличие одинаковых фамилий в разных паспортах не противоречит требованиям функциональной зависимости. Данное свойство демонстрирует рис. 11.3.

86

ХУ

- такое (однозначное) отображение Х в У может быть функциональной зависимостью

ХУ

- неоднозначное отображение не является функциональной зависимостью

Рис.11.3.Виды отображений атрибутов для функциональных зависимостей

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

Для создания базы данных об успеваемости студентов примера (1) из раздела 6.3.1. введена сущность СТУДЕНТ, схема которой включает атрибуты: Факультет, Специальность, Фамилия И. О., Успеваемость (оценки), Стипендия (сумма стипендии).

Схема соответствующего отношения имеет вид:

СТУДЕНТ (Факультет, Специальность, Фамилия И.О., Успеваемость, Стипендия)

Ключом данного отношения примем атрибуты {Специальность, Фамилия И.О.}, полагая, что на одной специальности не появятся студенты с совпадающими фамилией, именем и отчеством.

Для отражения свойств данной предметной области введем набор функциональных зависимостей между атрибутами отношения СТУДЕНТ:

1. {Специальность} Æ {Факультет} - зависимость, означающая принадлежность специальности одному определенному факультету в составе вуза.

87

2. {Специальность, Фамилия И.О.} Æ {Успеваемость} - по специальности и ФИО однозначно определяется студент, а значит, и его успеваемость.

3. {Специальность, Фамилия И.О.} Æ {Стипендия}.

4.{Успеваемость} Æ {Стипендия} - представляет правило назначения стипендии, размер которой зависит только от успеваемости студента.

5.{Специальность, Фамилия И.О.} Æ {Факультет} - по специальности и ФИО однозначно определяется студент, а значит, и факультет, на котором он учится.

Лекция 12. Минимизация функциональных зависимостей

Требования к декомпозиции с сохранением ФЗ

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

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

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

88

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

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

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

Эти правила справедливы для ФЗ в любом отношении.

Пусть Х, У и Z - подмножества атрибутов схемы отношения С, т.е.

X C, Y C и Z C .

1.	Правило рефлективности функциональной зависимости.
	Если X C, Y X , то	X →Y ,	тривиальное правило, означающее:
	значения любого набора атрибутов X определяют значения любого своего
	подмножества атрибутов Y.
2.	Правило пополнения ФЗ.
	Если X →Y , то X Z →Y Z , т.е. добавление к аргументу и функции
	одинакового набора атрибутов сохраняет функциональную зависимость.
3.	Правило расширения ФЗ.
	Если X → Y , то X Z → Y		– добавление к аргументу
	дополнительных атрибутов сохраняет функциональную зависимость.
4.	Транзитивность ФЗ.
	Если X →Y и Y → Z,	то X → Z – из цепочки последовательных ФЗ
	следует зависимость между аргументом первой и функцией последней
	зависимости в цепи.

5.Объединение (аддитивность) ФЗ.

Если X → Y и X → Z , то X → Y Z .

6.Декомпозиция функциональной зависимости.

89