Bazy_dannykh_i_znanii_UP_SHirokov_L.A._2000

собами:

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

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

Если у таблиц R1 и R2 типы полей, по которым выполняется соединение, имеют идентичные имена, то соединение называется естественным. В этом случае в результирующей записи общий тип поля помещается лишь один раз. Если имена разные, то в результирующей

записи остается каждый тип поля.

Синтаксис:

R = R1 join R2.

Пример 1.

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

R1:

R2:

Ответ: R:

A

B

C

B

A

B

C

d

3

3

a

d

3

a

h

7

3

b

d

3

b

y

4

7

a

h

7

a

Пример 2.

9

c

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

R1:

R2:

Ответ: R:

A

B

C

B

C

D

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

5.6.1.Запрос с соединением по одному полю

ВБД " Разработчики ПП" (см. рис.5.1) указать названия ПП, созданных в период с 1970 по 1984 гг. включительно, ФИО и стаж разработчиков.

5.6.2.Алгоритм реализации

1)Выделим названия РТ, задействованных в реализации запроса. Это РТ: "Разработанные ПП" (R3) и "Разработчики" (R1).

2)Из К3 выберем записи по условию в запросе:

RT1 = sel <(ГодСозд-я >= 1970) and (ГодСозд-я <= 1985)> (R3).

RT1:	№ПП	НазваниеПП	№Разр-ка	ГодСозд-я
	P1	ПП1	R5	1982
	P2	ПП2	R2	1984

3) Соединим RT1 и R1 по общему полю №Разр-ка: RT2 = RT1 join R1.

61

Таблица RT2 будет иметь вид: RT2:

№ПП	Назв-еПП	№Разр-ка	ГСозд-я	ФИОРазр-ка	ГРожд-я	Стаж
P1	ПП1	R5	1982	Крылов Г.	1964	10
P2	ПП2	R2	1984	Крылов Г.	1962	17

4) Выбрать из RT2 Название ПП, ФИО и стаж разработчиков: R = proj НазваниеПП, ФИОРазр-ка, Стаж (RT2).

Результирующая таблица R как ответ на запрос примет вид:

R:	НазваниеПП	ФИОРазр-ка	Стаж
	ПП1	Крылов Г.	10
	ПП2	Крылов Г.	17

Общий алгоритм реализации запроса можно представить в виде:

proj Назв-еПП, ФИОРазр-ка, Стаж (sel <ГодСозд-я >= 1970 and ГодСозд-я <= 1984> (Разработанные ПП) join Разработчики).

5.6.3.Запрос с соединением по нескольким полям

ВБД "Разработчики ПП" (рис. 5.1) указать Названия ПП, № и ФИО разработчиков, выступающих и как руководители ВТК, и как программисты в них.

5.6.4.Алгоритм реализации

Выделим названия РТ, задействованных в реализации запроса. Это РТ: "Разработанные ПП" (R3), "Разработчики" (R1), "Временные трудовые коллективы (ВТК)" (R4), "Составы ВТК" (R5), "Программи-

сты" (R2).

Для выявления разработчиков ПП, выступающих одновременно и как руководители ВТК, объединим таблицы R3 и R4. Здесь общим полем является №Разр-ка - №Разр-каРук-ляВТК:

RT1 = R3 join R4:

RT1:

№ПП	Назв-еПП	№Разр-ка-Рук-	ГодСзд-я	№ВТ	Назв-е	№Ком-ты
		ляВТК		К	ВТК
P1	ПП1	R5	1982	B1	Луч	12
P2	ПП2	R2	1984	B3	Взлет	12
P4	ПП3	R2	1987	B3	Взлет	12
P5	ПП4	R3	1985	B2	Стрела	18

Для экономии памяти ПК и увеличения быстродействия выберем

62

из RT1 лишь участвующие в запросе поля:

RT2 = proj Назв-еПП, №Разр-ка-Рук-ляВТК, №ВТК(RT1):

RT2:	НазваниеПП	№Рразр-ка-	№ВТК
		Рук-ляВТК
	ПП1	R5	B1
	ПП2	R2	B3
	ПП3	R2	B3
	ПП4	R3	B2

Для определения Разработчиков-Руководителей ВТК, являющихся одновременно и программистами, соединим RT2 и R2 по одному общему полю: №Разр-каРук-ляВТК - №Разр-ка-Прогр-та:

RT3 = RT2 join R2:

RT3:

Назв-еПП	№Разр-ка-	№ВТК	№Прог-та	Язык-	Категория-
	Рук-ля ВТК			Прогр-я	Прогр-та
ПП1	R5	B1	A3	Pas	3
ПП2	R2	B3	A2	C	2
ПП2	R2	B3	A5	Pas	2
ПП3	R2	B3	A2	C	2
ПП3	R2	B3	A5	Pas	2

Выберем из RT3 лишь участвующие в запросе поля:

RT4=projНазв-еПП,№Разр-ка-Рук-ляВТК,№ВТК,№Пр-та(RT3):

RT4:

НазваниеПП	№Разр-ка-Рук-ляВТК	№ВТК	№Прогр-та
ПП1	R5	B1	A3
ПП2	R2	B3	A2
ПП2	R2	B3	A5
ПП3	R2	B3	A2
ПП3	R2	B3	A5

Для определения разработчиков-руководителей ВТК, являющихся программистами именно в своих ВТК, сделаем соединение таблиц RT4 и R5 по двум полям: №ВТК и №Прогр-та:

RT5 = RT4 join R5:

RT5:

НазваниеПП	№Разр-ка-Рук-ляВТК	№ВТК	№Прогр-та
ПП1	R5	B1	A3
ПП2	R2	B3	A5
ПП3	R2	B3	A5

Выберем из RT5 участвующие в запросе поля:

RT6 = proj Назв-еПП, №Разр-ка-Рук-ляВТК (RT5):

63

RT6:	НазваниеПП	№Разр-ка-Рук-ляВТК
	ПП1	R5
	ПП2	R2
	ПП3	R2

Для полного ответа на запрос объединим таблицы RT6 и R1 с последующим выделением полей, указанных в запросе:

RT7 = RT6 join R1: RT7:

Назв-еПП	№Разр-ка	№Разр-ка-	ФИО	Год-	Стаж
ПП1	R5	Рук-ля ВТК	Разр-ка	Рождения	10
		R5	Крылов Г.	1964
ПП2	R2	R2	Крылов Г.	1962	17
ПП3	R2	R2	Крылов Г.	1962	17

RT8 = proj Назв-еПП, №Разр-ка, ФИОРазр-ка (RT7):

RT8:	НазваниеПП	№Разр-ка	ФИОРазр-ка
	ПП1	R5	Крылов Г.
	ПП2	R2	Крылов Г.
	ПП3	R2	Крылов Г.

Таким образом, алгоритм ответа на запрос можно записать в ви-

де:

proj Назв-еПП,№Разр-ка-Рук-ляВТК(proj Назв-еПП,

6

4

№Разр-ка-Рук-ляВТК,№ВТК,№Прогр-та(proj Назв-еПП,

2

№Разр-ка-Рук-ляВТК(Разр-ыеПП joinВТК) join Прогр-ты)

1 3

join СоставыВТК) join Разр-ки

5

7

Примечание: Цифры под операторами обозначают порядковые номера их выполнения.

5.6.5. Оператор "соединение по условию"

Функция: из двух РТ R1 и R2 формируется результирующая R оператором join (см. п.5.6), если выполняется заданное условие V: V = P1i G P2j, где G - арифметический оператор сравнения, выбираемый из множества: {=, >, <, >=, <=, <>}; P1i, P2j - типы полей в реляционных таблицах R1 и R2 соответственно. Для оператора G типа равенство оператор join называется эквисоединением.

Синтаксис: R = R1 join R2

P1i G P2j

Пример.

Соединить таблицы R1 и R2 по условию B=D:

R = R1 join R2.

B=D

64

R1:

A

B

C

R2:

D

E

Ответ: R:

A

B

C

D

E

a

b

c

a

u

g

e

z

e

k

d

u

p

e

k

g

e

z

5.7. ОПЕРАТОР "УМНОЖЕНИЕ" (PRODUCT)

Функция: для двух РТ R1 и R2 соответственно арности К1 и К2 формируется результирующая R арности (К1 + К2), записи которой представляют собой конкатенацию каждой записи из таблицы R1 с каждой записью из таблицы R2. В таблице R имена полей формируются из двух частей, разделенных точкой. Префиксом имени поля принимается имя таблицы R1 или R2 в зависимости от того, из какой таблицы взято значение поля, а афиксом - соответствующие имена полей из этой таблицы.

Синтаксис: R = R1 product R2.

Пример.

R1:	A	B	R2:	C	D	Ответ: R:	R1,A	R1,B	R1,C	R1,D
	b	4		c	4		b	4	c	4
	d	7		d	R		b	4	d	R
							d	7	c	4
							d	7	d	R

Запросы с оператором умножения используются в ответах на запросы, требующие сравнения значений полей различных файлов.

5.7.1.Запрос с оператором умножения

ВБД "Разработчики ПП" перечислить названия и годы создания ПП, разработанных до рождения Фатова Р.

5.7.2.Алгоритм реализации

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

1) Выделим названия РТ, задействованных в реализации запроса. Это РТ: "Разработчики" (R1), "Разработанные ПП" (R3).

Сформируем таблицу с годом рождения Фатова Р. Для этого сначала выделим его запись из таблицы R1, а затем выберем поле ГодРождения:

RT1 = sel <ФИОРазр-ка = 'Фатов Р.'> (R1)

RT1:	№Разр-ка	ФИОРазр-ка	ГодРожд-я	Стаж
	R3	Фатов О.	1964	11

RT2 = proj ГодРожд-я(RT1)

65

RT2:	ГодРожд-я
	1964

3) Из R3 выделим поля Назв-еПП и ГодСозд-я: RT3 = proj Назв-еПП, ГодСозд-я(R3)

RT3:	Назв-еПП	ГодСозд-я
	ПП1	1982
	ПП2	1984
	ПП1	1960
	ПП3	1987
	ПП4	1985

4) Для реализации сравнения по сути запроса выполним произведение таблиц RT2 и RT3:

RT4 = RT2 product RT3

RT4:	RT2.ГодРожд-я	RT3.Назв-еПП	RT3.ГодСозд-я
	1964	ПП1	1982
	1964	ПП2	1984
	1964	ПП1	1960
	1964	ПП3	1987
	1964	ПП4	1985

5) Из RT4 выберем запись по критерию запроса:

RT5 = sel <RT3.ГодСозд-я < RT2.ГодРожд-я> (RT4)

RT5:	RT2.ГодРожд-я	RT3.Назв-еПП	RT3.ГодСозд-я
	1964	ПП1	1960

6) Из RT5 выберем поля, необходимых и достаточных для ответа на запрос:

RT6 = proj RT3.Назв-е, RT3.ГодСозд-я(RT5)

RT6:	RT3.Назв-еПП	RT3.ГодСозд-я
	ПП1	1960

Таким образом, алгоритм ответа на запрос можно записать в ви-

де:

projRT3.Назв-еПП,RT3.ГодСозд-я(sel<RT3.ГодСозд-я<RT2.Год

6

5

Рожд-я>(projГодРожд-я(sel<ФИОРазр-ка='Фатов'>(R1)product

2

1

4

proj Назв-еПП,ГодСозд-я(R3))).

3

Примечание.

Цифры под операторами обозначают порядковые номера их выполнения.

66

5.8. ОПЕРАТОР "ДЕЛЕНИЕ" (DIVISION)

Функция: для двух реляционных таблиц соответственно делимого R1 и делителя R2 таких, что:

а) каждому типу поля в делителе найдется соответствующий тип поля в делимом;

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

а) включает типы полей из числа содержащихся в делимом, но отсутствующих в делителе;

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

Синтаксис: R = R1 division R2.

Пример.

R1:	D	E	F	R2:	E	F	Ответ: R:	D
1	A	h	3		h	3		A
2	C	a	7		a	7		B
3	B	a	7		e	4
4	B	e	4
5	A	e	4
6	A	a	7
7	B	h	3
8	C	e	4

Примечание.

1)В таблице R лишь одно поле D, так как оно входит в делимое и отсутствует в делителе;

2)Значения А и В входят в R, так как в делимом они соответственно конкатенированы с каждой из трех записей делителя (см. в табл.R1 записи №№ 1, 5, 6 для D=А и №№ 3, 4, 7 для D=В);

3)Значение С отсутствует в R, так как в R1 нет записи Ch3.

5.9.ОПТИМИЗАЦИЯ АЛГОРИТМОВ РЕАЛИЗАЦИИ ЗАПРОСОВ

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

Пусть P11 - одно из возможных значений поля P таблицы R1, которая должна быть объединена с таблицей R2 для получения таблицы R с выполнением нижесформулированного условия: для таблицы R должны быть выбраны из таблицы, полученной объединением R1 и R2, записи со значением поля P, равным P11.

Для получения ответа возможно два алгоритма:

67

R = (sel <P = P11> (R1)) join R2	(5.1)
и
R = sel <P = P11> (R1 join R2),	(5.2)

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

Применение формулы (5.2) в случае результата операции соединения с количеством записей большим, чем в R1, приведет к увеличению времени реализации процедуры sel, что замедлит работу системы. При таком положении предпочтительнее алгоритм (5.1). В обратной ситуации целесообразнее алгоритм (5.2).

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Что понимается под реляционной алгеброй, ее операторами и операндами?

2.Приведите характеристику оператора UNION и пример.

3.Приведите характеристику оператора DIFFERENCE и пример его применения.

4.Приведите характеристику оператора INTERSECTION и пример его применения.

5.Приведите характеристику оператора PROJ и пример.

6.Приведите характеристику оператора SEL и пример.

7.Приведите характеристику оператора JOIN и пример его применения.

8.Приведите характеристику оператора PRODUCT и пример его применения.

9.Приведите характеристику оператора DIVISION и пример.

10.Каковы цели и критерии оптимизации реализаций алгоритмов запросов?

68

ГЛАВА 6. НОРМАЛИЗАЦИЯ РЕЛЯЦИОННЫХ БД

6.1. ЗАДАЧИ НОРМАЛИЗАЦИИ БД

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

Врезультате нормализации обеспечивается:

•регулярность описаний данных;

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

•максимальная гибкость при обработке произвольных запросов с рабочих мест пользователей.

Нормализация базируется на представлении данных двухмерны-

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

Процесс нормализации реализуется поэтапно путем формирования последовательности так называемых нормальных форм (НФ).

6.2. ПЕРВАЯ НОРМАЛЬНАЯ ФОРМА

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

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

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

69

6.3.ДЕКОМПОЗИЦИЯ РЕЛЯЦИОННЫХ ТАБЛИЦ

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

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

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

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

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

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

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

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

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

Синтаксис: R1 = proj a1,...,ar(R), (6.1) где r <= n.

Пример.

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

R1 = proj ГодРождения, ФИО(Разработчики) Результирующая таблица R1 приведена на рис. 6.2.

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

Рис. 6.2

70