Bazy_dannykh_i_znanii_UP_SHirokov_L.A._2000

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

Операция "Соединение" реализуется оператором join, выполняющим следующую функцию:

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

Следовательно, соединение может быть реализовано двумя способами:

•по одному полю;

•по нескольким полям.

Синтаксис:

R = R1 join R2.

Пример 1.

Соединить таблицы R1 и R2 с одним общим полем.

R1:	A	B	R2:	B	С	Ответ:	A	B	C
						R:
	d	3		3	a		d	3	a
	h	7		3	b		d	3	b
	y	4		7	a		h	7	a
				9	c

Пример 2.

Соединить таблицы R1 и R2 с двумя общими полями

R1:

A

B

C

R2:

B

C

D

Ответ: R:

A

B

C

D

d

3

a

3

a

c

d

3

a

c

h

7

b

3

a

d

d

3

a

d

y

4

a

4

a

e

y

4

a

e

g

2

c

Пример 3. Рассмотрим БД

Поставщики (№КИ, Фирма, Телефон),

71

приведенную на рис.6.3, при следующих условиях:

•любое КИ поставляется не более, чем одной фирмой;

•все фирмы разноименны.

№КИ	Фирма	Телефон
A4	СИМ	1516512
B17	СИМ	1516512
C1	ВК	2611380
D14	ВК	1902316
D16	ВК	2611380

Рис. 6.3

Из рис. 6.3 видно, что в таблице рассматриваемой БД номера телефонов многократно повторяются, т.е. имеется дублирование информации.

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

R11 = proj №КИ, Фирма (Поставщики)

и

R12 = proj Фирма, Телефон (Поставщики).

Первую проекцию составляют домены №КИ и Фирма исходного файла (рис. 6.4,а), а вторую - домены Фирма и Телефон (рис. 6.4,б). Поскольку выполнение операции join над этими двумя проекциями восстанавливает исходную таблицу "Поставщики", изображенную на рис. 6.3, то декомпозиция является полной.

№КИ	Фирма
A4	СИМ
B17	СИМ
C1	ВК
D14	ВК
D16	ВК

а)

Фирма		Телефон
СИМ		1516512
ВК		2611380
	б)

Рис. 6.4

Анализ полученных таблиц показывает, что в результате декомпозиции удалось полностью исключить дублирование номеров телефонов фирм. Это приводит к тому, что в случае смены, например, номера телефона фирмы ВК достаточно его однократной коррекции в таблице на рис. 6.1,б. В исходной же таблице на рис. 6.3 требовалась

72

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

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

Склад(База, Товар, Поставщик),

приведенную на рис. 6.5. Ее декомпозицию можно реализовать двумя способами.

База	Товар	Поставщик
28	Р4	INT
28	М3	MT
38	Р6	INT
38	М3	MT

Рис. 6.5

По первому способу получаем проекции:

R11 = proj База,Товар(Склад); (6.2) R12 = proj Товар,Поставщик(Склад),

приведенные соответственно на рис. 6.6,а и рис. 6.6,б.

База		Товар
28		Р4
28		М3
38		Р6
38		М3
	а)

Товар		Поставщик
Р4		INT
М3		MT
Р6		INT
	б)

Рис. 6.6

При объединении, т.е. композиции полученных проекций, образуется исходная БД "Склад". Это означает, что результатом первого способа (6.2) была полная декомпозиция. Однако, как видно из рис. 6.6, при декомпозиции в записях полученных таблиц не удалось исключить дублирование значений полей М3 и INT.

При декомпозиции по второму способу получаем проекции:

73

R21 = proj База, Поставщик(Склад);

R22 = proj Товар,Поставщик(Склад),

для которых соответствующие таблицы приведены на рис. 6.7,а и рис. 6.7,б.

База Поставщик

28 INT

28 MT

38 INT

38 MT

а)

Товар	Поставщик
Р4	INT
М3	MT
Р6	INT

б)

Рис. 6.7

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

База	Товар	Поставщик
28	Р4	INT
28	М3	MT
38	Р6	INT
38	М3	MT
28	Р6	INT
38	Р4	INT

Рис. 6.8

Следовательно, полная декомпозиция возможна лишь по первому способу (6.2), однако в полученных проекциях не исключено дублирование значений полей МЗ и INT, т.е. поставленная задача осталась нерешенной.

Из изложенного вытекают следующие основные проблемы теории декомпозиции:

•формирование правил выбора одной из альтернатив: либо хранить БД в исходном виде, либо выполнить полную декомпозицию БД и хранить ее проекции;

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

74

6.3.2. Присоединенные записи

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

Рассмотрим два набора полей S1 и S2 из реляционной таблицы R, причем в S1 содержится ключ, и выполняется условие

R = proj S1(R) join proj S2(R).

Запись будет присоединенной, если она занесена в проекцию proj S2(R), но не занесена в проекцию proj S1(R) и, следовательно, не войдет в соединение этих проекций.

Пример.

Рассмотрим для БД "Поставщики КИ" (см. рис.6.5) с проекциями S1 = (№КИ, Фирма) и S2 = (Фирма, Телефон)

в качестве присоединенной запись для фирмы РОС с телефоном

2462475: (РОС, 2462475).

Фирма РОС еще не приступила к поставке товаров и, следовательно, еще не имеет значения ключевого поля №КИ. Это означает, что ее запись можно хранить в проекции S2, т.е. в полной декомпозиции, но не в исходной реляционной таблице R.

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

6.3.3. Теорема Хита

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

Рассмотрим БД в виде реляционной таблицы R с тремя непересекающимися наборами полей: S1, S2 и S3, т.е. таких, что каждое поле таблицы принадлежит лишь одному из этих типов, причем S3 функционально зависит от S2. В этом случае справедлива теорема, называемая теоремой Хита.

Теорема Хита.

Если в реляционной таблице R существуют наборы Si (i = 1,2,3), не пересекающиеся между собой, и набор S3 функционально зависит от набора S2, то справедливо тождество:

R = proj S1, S2 (R) join proj S2, S3 (R),

75

т.е. имеет место полная декомпозиция реляционной таблицы R. Проанализируем с позиций теоремы Хита функциональные зави-

симости для рассмотренных выше БД

Поставщики (№КИ, Фирма, Телефон)

и

Склад(База, Товар, Поставщик).

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

Рис. 6.9

Из рис. 6.9,а следует, что в БД можно рассматривать три непересекающихся набора Si , соответствующие трем атрибутам аi., причем а3 функционально зависит от а2. Это означает, что декомпозиция, выполненная в соответствии с рис. 6.9,б, обеспечивает выполнение условий теоремы Хита и, следовательно, будет полной.

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

Рис.6.10

Из рис. 6.10,а следует, что в БД также можно рассматривать три непересекающихся набора Si , соответствующие трем атрибутам аi.. Отметим однако, что в этой БД нет ключа, т.е. она не в 1НФ, и лишь а3 функционально зависит от а2. Тем не менее декомпозиция, выполненная в соответствии с рис. 6.10,б на подмножества (а1, а2) и (а2, а3), обеспечивает выполнение условий теоремы Хита, так как а2 входит в оба подмножества, и, следовательно, декомпозиция будет полной. Однако, как видно из рис. 6.10,б, дублирование значений полей не

76

удалось исключить. Декомпозиция же, выполненная в соответствии с рис. 6.10,в, не обеспечивает выполнение условий теоремы Хита, т.к. от общего атрибута а3 атрибут а2 функционально не зависит, и, следовательно, полученный результат не является полной декомпозицией.

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

6.3.4.Критерий полной декомпозиции с исключением дублирования

Необходимыми и достаточными условиями полной декомпозиции исходной реляционной таблицы с исключением дублирования значений полей являются представление БД в 1НФ и выполнение теоремы Хита при одновременном формировании проекций таким образом, чтобы они не содержали какого-либо общего ключакандидата.

Пример.

В рассмотренной выше БД

Поставщики (№КИ, Фирма, Телефон)

декомпозиция по принятому варианту была полной и дублирование было полностью устранено, так как исходно БД представлена в 1НФ, принятые структуры полей удовлетворяли теореме Хита и вместе с тем в них не содержалось какого-либо общего ключа - кандидата.

В случае же применения другого варианта декомпозиции на две проекции:

R21 = proj №КИ,Телефон(Поставщики)

и

R22 = proj №КИ,Фирма(По-ставщики),

каждая из которых содержит ключ-кандидат NКИ, декомпозиция не удовлетворяет необходимым и достаточным условиям критерия и, следовательно, не приводит к ликвидации дублирования.

6.4. ВТОРАЯ НОРМАЛЬНАЯ ФОРМА

Отношение в 1НФ в ряде случаев может приводить к аномалиям из-за наличия сцепленных ключей. Для их исключения необходимо привести отношение ко второй нормальной форме.

Схема отношения R находится во второй нормальной форме (2НФ), если она находится в 1НФ и каждый ее непервичный атрибут,

77

функционально полностью зависит от соответствующего ключакандидата.

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

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

Пример. Отношение

Поставщики (№КИ, Фирма, Телефон),

имеет простой ключ №КИ и, следовательно, находится в 2НФ. Действительно, его непервичные атрибуты: Фирма, Телефон функционально полностью зависят от первичного ключа №КИ.

Если в отношении имеются сцепленные ключи, то это отношение, являясь отношением в 1НФ, может и не быть отношением в 2НФ.

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

Поставки(№Поставщика, №Изделия,		(6.3)
а1	а2

ИмяПоставщика, ИнфОПост-ке, Цена)

а3 а4 а5 где а1,...,а5 - символьные имена атрибутов (рис. 6.11).

Вэтом отношении:

•поставщики имеют изделия с уникальными номерами;

•одному и тому же поставщику в различных регионах могут быть присвоены различные номера;

•имеется один составной ключ а1+а2, так как он в целом и отдельные его компоненты определяют все остальные неключевые атрибуты записи. Это иллюстрирует рис. 6.11,а, где приведены функциональные зависимости для отношения Поставки.

• На рис. 6.11,б приведена реализация отношения Поставки. Из рис. 6.11,а видно, что атрибуты а3 и а4, не относящиеся к первичным, функционально зависят только от атрибута а2, который является лишь подмножеством составного ключа а1+а2. Это означает, что в отношении нет полной функциональной зависимости всех непервичных атрибутов от сцепленного ключа в целом. Следовательно, отношение не находится в

2НФ.

Нарушение условий 2НФ приводит к ряду затруднений при манипулировании данными в БД:

•невозможен ввод информации о поставщике, пока он не реализует поставки какого-либо изделия, т.к. при этом невозможно задать значение всего сцепленного ключа а1+а2;

•в случае временного прекращения каким-либо поставщиком поставок изделий, т.е. при отсутствии значения поля а2 запись с этим поставщи-

78

ком из-за отсутствия ключа удаляется, и, следовательно, теряются все сведения о нем, что нежелательно;

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

						а1	а2	а3	а4	а5
						1	10	А5	C1	12
а1	*					1	15	А1	С4	22
а2	*					1	25	А4	С2	52
а3						1	19	А3	С3	30
а4						2	31	А2	С5	55
а5						2	10	А5	С1	13
						2	25	А4	C2	59
	а)					3	25	А4	С2	55
						4	10	А5	С1	14
						4	31	А2	С5	59
						5	19	А3	С3	35
						5	15	А1	С4	24
						5	10	А5	C1	14
								б)

Рис. 6.11

С целью устранения перечисленных аномалий необходимо исходное отношение Поставки (см. рис. 6.11,а) привести к 2НФ. Для этого требуется реализовать его полную декомпозицию на два отношения, каждое из которых должно быть в 2НФ. Результат нормализации приведен на рис.6.12, где а) и б) - схемы полученных отношений

в2НФ, в) и г) - их соответствующие реализации.

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

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

79

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

	а1 *					а1	*			а1	а2	а5
	а3					а2	*			1	10	12
	а4					а5				1	15	22
		а)						б)		1	25	52
										1	19	30
										2	31	55
										2	10	13
										2	25	59
										3	25	55
а2		а3				а4
										4	10	14
10		А5				C1
15		А1				С4				4	31	59
25		А4				С2				5	19	35
19		А3				С3				5	15	24
31		А2				C5				5	10	14
					в)						г)

Рис. 6.12

6.5. ТРЕТЬЯ НОРМАЛЬНАЯ ФОРМА

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

Рассмотрим отношение R с тремя типами атрибутов или тремя наборами типов атрибутов, для которых имеет место транзитивная зависимость. Обозначим эти наборы соответственно через С1, С2 и С3.

Тогда свойство транзитивной зависимости можно представить соотношениями:

С1

C2, С2

С3 и С1 С3.

При этом отметим, что обратное соответствие неоднозначно, т.е. С1 не зависит от С2 или С2 не зависит от С3.

Диаграмму транзитивной зависимости для рассматриваемого случая отражает рис. 6.13,а.

Для ликвидации возможных аномалий из-за транзитивной зависимости необходимо исключить эти зависимости. С этой целью необ-

80