Проблема дублирования, операторы реляционной алгебры для декомпозиции и объединения таблиц

В БД возможно дублирование информации, т.е. многократноt повторение значений полей. Это нецелесообразно, так как:

· перерасходуются ресурсы ЭВМ (память, время обработки);

· корректировка данных требует одновременного изменения всех копий.

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

Исключение дублирования возможно проведением полной декомпозиции реляционных таблиц (РТ).

Полной декомпозицией реляционной таблицы R называется ее адекватное представление совокупностью некоторого числа проекций R_i (i = 1, 2,..., n), получаемых в результате последовательного применения операции " Проектирование" реляционной алгебры. При полной декомпозиции в результате применения операции " Объединение" должна вновь образоваться исходная реляционная таблица R.

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

из исходной РТ R оператор рroj выбирает заданные домены и размещает их в новой таблице R1 в задаваемом оператором порядке.

Синтаксис:      

(6.1) R1 = proj a1,..., ar(R),  

где r < = n.

Пример.

Из РТ " Разработчики" (см. Рис. 0.1) выбрать домены ГодРождения, ФИО.

R1 = proj ГодРождения, ФИО(Разработчики)

Результирующая таблица R1 приведена на Рис. 0.2.

 

№Разработчика	ФИО	Год Рождения	Стаж
R1	Белов А.	1940	21
R2	КрыловГ	1962	17
R3	Фатов Р.	1964	11
R4	Белов А.	1953	21
R5	КрыловГ	1964	10

Рис. 0.1

ГодРождения	ФИО
1940	Белов А.
1962	Крылов Г.
1964	Фатов Р.
1953	Белов А.
1964	Крылов Г.

Рис. 0.2

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

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

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

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

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

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

Синтаксис:

R = R1 join R2.

Пример 1.

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

 

R1:	A	B	R2:	B	С	Ответ: R:	A	B	C
	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.

Рассмотрим БД

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

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

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

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

 

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

Рис. 0.3

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

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

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

и

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

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

 

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

 

а)

Рис. 0.4

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

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

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

Рассмотрим два набора полей 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.

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

Теорема Хита

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

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

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

 

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

Рис. 0.5

 

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

(6.2) R11 =  proj База, Товар(Склад);

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

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

 

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

        а)

Рис. 0.6

 

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

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

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

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

 

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

 

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

                                                                                           б)

                   а)

Рис. 0.7

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

 

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

Рис. 0.7, в

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

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

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

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

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

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

 

P1	P2	P3	P4
S1		S2	S3
R1
		R2

 

Рис. 6.8

 

В этом случае справедлива теорема, называемая теоремой Хита.

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

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

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

т.е. имеет место полная декомпозиция реляционной таблицы R.

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

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

и

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

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

а₁                                                                                       а₁

а₂                                                                                       а₂

а₃                                                                                       а₂

                                                                                           а₃

              а)                                            б)

Рис. 0.8

Из Рис. 0.8, а следует, что в БД можно рассматривать три непересекающихся набора S_i , соответствующие трем атрибутам а_i., причем а₃ функционально зависит от а₂. Это означает, что декомпозиция, выполненная в соответствии с Рис. 0.8, б, обеспечивает выполнение условий теоремы Хита и, следовательно, будет полной.

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

а₁                а₁                                       а₁

а₂                а₂                                       а₃

а₃                а₂                                       а₂

                   а₃                                       а₃

а)           б)                        в)

 

Рис. 0.9

 

Из Рис. 0.9, а следует, что в БД также можно рассматривать три непересекающихся набора S_i , соответствующие трем атрибутам а_i.. Отметим однако, что в этой БД нет ключа, т.е. она не в 1НФ, и лишь а₃ функционально зависит от а₂. Тем не менее, декомпозиция, выполненная в соответствии с Рис. 0.9, б на подмножества (а_1, а₂ ) и (а_2, а₃), обеспечивает выполнение условий теоремы Хита, так как а₂ входит в оба подмножества, и, следовательно, декомпозиция будет полной. Однако, как видно из Рис. 0.9, б, дублирование значений полей не удалось исключить. Декомпозиция же, выполненная в соответствии с Рис. 0.9, в, не обеспечивает выполнение условий теоремы Хита, т.к. от общего атрибута а₃ атрибут а₂  функционально не зависит, и, следовательно, полученный результат не является полной декомпозицией.

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

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: