Лекция № 4

Лекция № 4.

Ранее было сказано, что в процессе проектирования с помощью проекции декомпозицию следует осуществлять путём поиска цепочек ФЗ, а именно:

А® В, В ® С

с последующим проецированием, порождаемым ФЗ, замыкающей цепочку. В данном случае первой ФЗ будет В ® С. Другой путь обоснования процедуры выбора состоит в утверждении, что следует избегать выбора ФЗ, зависимостная часть которой сама - целиком или частично - является детерминантом другой ФЗ.

Пример:

Исходные данные

Отношение: R(А,В, С) ФЗ: А ® В

В ® С

Один возможный проект	R1	R2
R1 (A, C)	R2 (A, B)	A	C	A	B
A ® C	A ® B	9	4	9	2
		8	3	8	2

Корректные экземпляры R1 и R2

Соединение R1 и R2

A	B	C
9	2	4
8	2	3

Результат: Отношения, удовлетворяющие ФЗ отношений R1 и R2, но противоречащие ФЗ, представленной в исходных спецификациях.

Если положить, что отношение имеет вид R(А, В, С) и ФЗ А ® В выбрана для проекции в первую очередь, то полученные в результате отношения будут R1(А, С) и R2(А, В). Хотя оба эти отношения находятся в НФБК, но обнаруживается следующее:

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

Такая ситуация возникает из-за проекции, порождённой ФЗ, зависимостная часть которой сама является детерминантом другой ФЗ. При использовании правила цепочки эта проблема не возникает.

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

Пример:

A R (A, B, C)

B

C

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

Это отношение не находится в НФБК, т. к. имеется только один возможный ключ <А, С>, в то время как детерминантами являются <А> и <С>. Правило цепочек здесь неприемлемо по причине их отсутствия. Кроме того, если одна из ФЗ будет выделена обычным способом, то другая будет потеряна. Например, при выделении из R(А, В, С) зависимости А ® В будут получены отношения R1(А, С) и R2(А, В), ни одно из которых не будет содержать зависимости С ® В. Наоборот, при первоочередном выделении С ® В будет утеряна зависимость А ® В. Необходимо найти способ разбиения отношения R(А, В, С) на R1(А, В) и R2(С, В), не приводящий к утере ни одной ФЗ. Этот путь не соответствует стандартному методу декомпозиции, но может привести к лучшему результату.

Один из путей - проверить три возможных набора отношений и оценить, какой из трёх наиболее соответствует поставленной цели.

Второй метод разбиения отношения, называется методом синтеза, основан на утверждении, что необходимо все ФЗ с одинаковыми детерминантами выделять в группы и каждой группе отводить своё собственное отношение. Получаемые отношения проверяются на их соответствие НФБК.

Для последнего примера согласно методу синтеза каждой ФЗ следует выделить её собственное отношение - R1 (А, В) и R2(С, В).

Метод синтеза может быть использован как самостоятельно, так и в сочетании с методом декомпозиции.

Одна из проблем алгоритма проектирования БД, рассмотренная ранее, заключается в том, что процесс декомпозиции может осложниться в результате присутствия избыточных ФЗ.

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

Пример: упрощения набора ФЗ при помощи исключения транзитивных зависимостей

A ® B B ® C A ® C B ® E A ® E C ® E

A C E

B

Удаляем А ® Е, т. к. А ® С и С ® Е

A ® B B ® E A ® C B ® E B ® C

A C E

B

Удаляем В ® Е, т. к. В ® С, С ® Е

A ® B B ® C A ® C C ® E

A C E

B

А ® С удаляем, т. к. А ® В и В ® С

A ® B B ® C C ® E

A C E

B

R(А, В, С, Е)

Извлечение зависимости С ® Е, т. к. она является последней в цепочке

R1(С, Е) C E

R2(А, В, С) A B C

Извлечение зависимости В ® С из R2(А, В, С)

R1(С, Е) C E

R3(В, С) B C

R4(А, В) A B

Отношения R1, R3 и R4 находятся в НФБК.

Правила вывода, связанные с объединением и декомпозицией ФЗ, которые определяются следующим образом:

Объединение ФЗ: если А ® В и А ® С, то А ® В, С

Декомпозиция ФЗ: если А ® В, С, то А ® В и А ® С.

Пример. Упрощение ФЗ с помощью правил вывода.

Исходный набор ФЗ:

A ® B, C A ® D A ® K K ® C B ® D B, C ® D

A B D

K C

Удаление В, С ® Д:

A ® B, C A ® D A ® K K ® C B ® D

A B D

K C

Удаление А ® В, С

A ®B A ® C A ® D A ® K K ® C B ® D

(замена на A ® B & A ® C декомпозиция)

A B D

K C

А ® С и А ® Д удаляются

A ®B A ® K K ® C B ® D

(замена на A ® K & K ® C и A ® B & B ® D транзитивность)

A B D

K C

Полное множество правил вывода состоит из трёх аксиом Армстронга - рефлексивности (для любого множества атрибутов А и Х АХ ® Х), транзитивности, дополнения, а также трёх следующих из этих аксиом правил объединения, декомпозиции и псевдотрнзитивности.

Второй путь возникновения избыточных ФЗ связан с концепцией добавления (в литературе используется также термин "пополнение"). Эта форма избыточности имеет несколько видов. Рассмотрим два самых простых.

Вид 1. Если А ® В, то А, Z ® В является корректной, по избыточной ФЗ. Атрибут Z был добавлен к детерминанту А без привнесения какой либо новой информации в процесс проектирования.

Здесь А, В и Z - атрибуты, каждый из которых может быть составным.

Вид 2. Возникает в случае добавления к обеим частям данной ФЗ одного и того же атрибута с целью формирования новой зависимости:

Если А ® В, то А, Z ® В, Z является корректной, но избыточной зависимостью.

Примеры добавления:

A B

Z Добавление ФЗ (избыточная)

Добавление ФЗ (избыточное)

A B

Z

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

Ещё одно правило вывода называется псевдотранзитивностью:

Определение. Если X ® Y и Y, W ® Z, то X, W ® Z является избыточной в силу псевдотранзитивности.

Этот тип избыточности возникает в тех случаях, когда в получаемых ФЗ обнаруживаются составные детерминанты.

Пример на псевдотранзитивность:

Псевдотранзитивная ФЗ

(избыточная)

X W

Z

Y

или:

Псевдотранзитивная ФЗ

(избыточная)

Преподав. Время

Аудит.

Курс

Примеры на объединение и декомпозицию:

Если: то:

B B

A A

C C

Рис. 1. Объединение

Если: то:

B B

A A

C C

или:

Если: то:

Курс Курс

Фамилия Фамилия

Комната Комната

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

R1 - избыточное, т. к. все его атрибуты присутствуют в R3

R1 (A, B) R2 (B, C, Y, Z) R3 (A, B, K)

Пример:

R8 - избыточное, т. к. применение операции объединения над R5 и R7 (общим атрибутом является D) дает в результате отношение R9 (A, B, D, E, G, H), которое содержит все атрибуты R8

R1 (A, C, X) R3 (D, K, F) R5 (D, E, G, H) R7(A, B, D) R8 (A, B, E, G)

Пример:

Отношение является избыточным, если

а). все атрибуты в избыточном отношении могут быть найдены в одном другом отношении проектного набора;

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

Если устанавливается избыточность отношения, его следует исключить из проектного набора.

Определение. Набор не избыточных ФЗ, полученный путём удаления всех избыточных ФЗ из исходного набора с помощью 6 правил вывода, называется минимальным покрытием.

Декомпозиция без потерь.

Рассмотрим алгоритм проектирования с использованием декомпозиции, который выполняет разложение одного отношения, например R(X, Y, Z), на два новых отношения R1(X, Y) и R2(Y, Z). Отношения, полученные с помощью декомпозиции, всегда будут приводить к получению согласующихся данных, в том случае, когда декомпозиция была проведена способом, при котором естественное соединение отношений R1(X, Y) и R2(Y, Z) даёт в итоге в точности исходное отношение R(X, Y, Z). Декомпозиция, характеризующаяся этим качеством, называется "декомпозицией без потерь при естественном соединении". Если естественное соединение R1 и R2 приводит к появлению большего, чем в отношении R, числа кортежей, то декомпозиция называется декомпозицией с потерями. Отсутствие потерь при декомпозиции отношения R(X, Y, Z) на R1(X, Y) и R2(Y, Z) гарантируется при условии, если от общего атрибута двух получаемых отношений - в данном случае атрибута Y - зависит хотя бы один атрибут из двух оставшихся. В нашем случае, если Y® X или Y® Z, то декомпозиция осуществляется без потерь.

Пример. Декомпозиция с потерями:

R (X, Y, Z)	ни X, ни Y не зависят функционально от Z
X	Y	Z
1	2	3
3	2	6
5	4	2

Декомпозиция:	R1 (X, Y)	R2 (Y, Z)
	X	Y	Y	Z
	1	2	2	3
	3	2	2	6
	5	4	4	2

Cоединение R1 и R2	R (X, Y, Z)
	X	Y	Z
	1	2	3
	1	2	6	} новые кортежи
	3	2	3
	3	2	6
	5	4	2

В этом примере ни Y ® X, ни Y® Z не являются корректными ФЗ и естественное соединение R1 и R2 порождает два новых кортежа.

Пример. Декомпозиция без потерь:

R (X, Y, Z)			R1 (X, Y)	R2 (Y, Z)
X	Y	Z			X	Y	Y	Z
1	2	3	Y ® Z	Декомпо	1	2	2	3
3	2	3	является	зиция	3	2	4	2
5	4	2	ФЗ		5	4

	R (X, Y, Z)
	X	Y	Z
Cоединение	1	2	3	Те же кортежи, что и в
R1 и R2	3	2	3	отношении R (X, Y, Z)
	5	4	2

В этом примере предполагалось, что Y® Z является корректной ФЗ и значения R(X, Y, Z) отражают это. Естественное соединение R1 и R2 в этом случае даёт в результате в точности исходное отношение.

В общем случае X, Y, Z могут быть как простыми, так и составными атрибутами. В нашем примере атрибуты X, Y, Z были простыми.

Обобщённый алгоритм декомпозиции:

1. Построение универсального отношения для БД.

2. Определение всех ФЗ, существующих между атрибутами универсального отношения.

3. Удаление всех избыточных ФЗ из исходного набора ФЗ с целью получения минимального покрытия. Эта процедура проводится путём поочерёдного удаления избыточных ФЗ с последующей проверкой получаемого на каждом шаге набора ФЗ на наличие хотя бы одной избыточной ФЗ.

4. Использование ФЗ из минимального покрытия для декомпозиции универсального отношения в набор НФБК - отношений.

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

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

а). выбор оставшихся ФЗ и создание одного отношения для каждых детерминанта и набора зависящих от него атрибутов;

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