500_Goncharov_S._A._Informatsionnye_tekhnologii_v_mediaindustrii_Upravlenie_dannymi_

Отношение, или таблица, – это набор кортежей. Если кортежи являются n

– мерными, то есть, если таблица имеет n столбцов, отношение называется отношением степени n, или n – арным отношением.

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

Столбец с номером j называется j – м доменом отношения.

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

Схема БД древовидной структуры.

Отдел

№	Наименование	Отчетность	Руководитель	Бюджет
отдела	отдела

Работа

Служащий

№

Описание

№

Имя

№

Пол

З/п

Звание

Адрес

работы

работы

служащего

служащего

отдела

Трудовая

Дети

деятельность

Дата

Должность

Имя

Возраст

Пол

назначения

ребенка

ребенка

ребенка

Изменение оклада

Дата установления з/п

Размер з/п

Рисунок 6.1 – Представление дерева нормализованной схемой

Каждый кортеж должен иметь ключ – идентификатор. Ключ должен обладать двумя свойствами:

А) Однозначная идентификация кортежа: кортеж должен однозначно определяться значением ключа.

31

Б) Отсутствие избыточности: никакой атрибут нельзя удалить из ключа, не нарушая при этом свойства однозначной идентификации.

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

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

Нормализованная форма схемы:

Отдел (№_отдела, название_отдела, отчетность, руководитель, бюджет), Работа (№_отдела, №_работы, описание_работы), Служащий (№_служащего, имя_служащего, №_отдела, пол, з/пл., звание,

адрес), Изменение оклада (№_служащего, дата_установления_з/пл.,

размер_з/пл.), Дети (№_служащего, имя_ребенка, возраст_ребенка, пол_ребенка),

Трудовая деятельность (№_служашего, дата_назначения, должность).

Манипулирование отношениями (Реляционная алгебра)

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

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

Формат записи операции следующий: рroj «список имен полей» (*ИФ*)

В список имен полей входят только те поля, которые должны составлять структуру файла ИФ.

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

a.Из файла ИФ удаляются все поля, имена которых не фигурируют в списке;

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

Пример 1 приведен на рисунке 6.2.

32

Студент

№_Студента	Фамилия	№_группы	Средний	Город
	студента		балл	рождения
53702	Котов	402	5	Улан-Удэ
53703	Лукьянов	721	4,3	Новосибирск
53791	Кузнецов	007	3	Коченево
53800	Борисов	402	3.38	Улан-Удэ
53805	Попов	721	4.56	Новосибирск
53806	Алейников	721	3.2	Новосибирск

Студ.= proj №_студента, Имя_студента, №_группы, Средний балл (Студент)

Груп. = proj №_группы, город рождения (Студент)

Студ.

№_Студента			Имя_Студента			№_группы	Средний балл
53702		Котов			402		5
53703		Лукьянов			721		4,3
53791		Кузнецов			007		3
53800		Борисов			402		3.38
53805		Попов			721		4.56
53806		Алейников			721		3.2
Груп.
	№_группы			Адрес
	721			Новосибирск
	007			Коченево
	402			УланУдэ

Рисунок 6.2 – Операция проекции

Б: Операция соединения отношений является обратной к операции разрезания (проекции). В операции соединения участвуют два операнда, обозначаемые ИФ1 и ИФ2.

Формат записи операции: ИФ1 join ИФ2.

Результатом операции соединения является конкатенация (слияние двух строк в одну) каждой записи ИФ1 с каждой записью ИФ2, у которых совпадают данные в общем поле, причем само это поле в образующейся записи помещается лишь однажды. Общее поле должно иметь одинаковое имя и тип в обоих файлах.

a. Для простоты возьмем одно общее поле. Пример 2: Студ. join Груп.

33

Результатом операции будет восстановление файла Студент.

b.Соединение двух файлов, не имеющих ни одного общего поля, является пустое множество.

c.Если у файлов ИФ1 и ИФ2 несколько общих полей, то соединение включает конкатенацию каждой записи ИФ1 с каждой записью ИФ2, у которой совпадают с первой значения всех общих полей.

Пример 3

ИФ1

ИФ2

G1

F1

F2

F1

F2

G2

d

3

H

3

H

A

h

7

N

3

H

B

y

4

H

7

N

A

4

H

C

4

H

B

ИФ1 join ИФ2

G1

F1

F2

G2

d

3

H

A

d

3

H

B

h

7

N

A

y

4

H

C

y

4

H

b

Рисунок 6.3 – Операция соединения

Можно вывести еще целый ряд операций над отношениями.

В: Операция выбора. Имеет один операнд – ИФ. Синтаксис операции выбора: sel условие (ИФ).

Результатом операции является совокупность записей ИФ, объединяющая лишь те из них, которые удовлетворяют заданному условию.

Пример 4: sel №_группы > 100 (Груп.) Результат операции

№_группы	Город рождения
721	Новосибирск
402	Улан-Удэ

Рисунок 6.4 – Операция выбора

34

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

Условие, определяющее результат выбора, представляет собой выражение, которое может включать операции сравнения >, =, <, < >, < =, > =, а также логические операции and(«и»), or(«или») и not(«не»).

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

Г: Операция объединения. Синтаксис: ИФ1 union ИФ2.

Результат – совокупность записей, входящих в один, а возможно и в два операнда.

Пример 5:

ИФ1				ИФ2		ИФ1 union ИФ2
	F1	G2		F1	G1		F1	G1
	a	4		d	2		a	4
	b	5		b	5		b	5
	c	6		e	4		c	6
				c	6		d	2
							e	4

Рисунок 6.5 – Операция объединение

При ответах на некоторые запросы вместо объединения предпочтительнее пользоваться выбором, включая в его условие операцию «ИЛИ». Это замечание для тех запросов, которые используют информацию из одного файла. В примере, демонстрирующем такую ситуацию, использованы файлы с рисунка 6.1.

Пример 6: определить номера отделов, в которых используются номера работ 7 и 12.

proj №_отдела (sel (№_работы = 7) оr (№_работы = 12)(Работа))

Д. Операция пересечения. Синтаксис: ИФ1 intersection ИФ2.

Результат – набор записей, входящих в состав обоих файлов.

Пример:

ИФ1

ИФ2

ИФ1 intersection ИФ2

35

F1	G1			F1	G1		F1	G1
a	8		e		12		b	5
b	5		b		5		c	6
c	6		d		1
			c		6

Рисунок 6.6 – Операция пересечения

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

Пример 7: определить №_отдела, в котором выполняют работу вида 2 и 4. рroj №_отдела (sel (№_работы = 2) and (№_работы = 4)(Работа)). Пример 8: определить № отдела, в которой выполняют работу 9 и ведут

отчетность по форме 5

proj №_отдела(sel отчетность = 5 (отдел)) intersection proj №_отдела(sel№_работы = 9 (Работа)).

Е. Операция вычитания. Синтаксис: ИФ1 difference ИФ2

Результат – совокупность записей, имеющихся в ИФ1, но отсутствующих в ИФ2.

Пример 9: составить список сотрудников, у которых нет детей

proj Имя_служащего((proj №_служащего (Служащий) difference proj №_служащего (Дети)) join Служащий).

Ж. Операция деления. Синтаксис: ИФ1 division ИФ2

Условия выполнения – каждое поле ИФ2 имело те же имя и тип, что и одно из полей ИФ1. В результате деления получается файл, поля которого содержатся в ИФ1, но отсутствуют в ИФ2. Запись включается в результат только при том условии, что в ИФ1 она сцеплена с каждой записью из ИФ2.

Пример10:

ИФ1

ИФ2

ИФ1 division ИФ2

36

G2	F1	G1		F1	G1
							G2
A	d	3		3	d
							A
C	h	7		7	h
							B
B	h	7		4	y
B	y	4
A	y	4
A	h	7
B	d	3
C	y	4

Запись А, В включена в результат, так как в ИФ1 есть записи,

G2	G1	F1
A	d	3
A	h	7
A	y	4

аналогично для записи В, запись С отсутствует, так как в ИФ1 нет записи

С d З.

Рисунок 6.7 – Операция деления

Пример 11:

Определить список отделов, в которых выполняются все виды работ. Работа division (proj №_работы, описание работы (Работа)).

З. Операция умножение (декартово произведение). Синтаксис: ИФ1 product ИФ2

Результат – совокупность записей, представляющих конкатенацию каждой записи ИФ1 с каждой записью ИФ2.

	Пример 12:
	ИФ1				ИФ2			ИФ1 product ИФ2
F1		F2			F3	F4		ИФ1.F1	ИФ1.F2	ИФ1.F3	ИФ1.F4
B		4			A	4		b	4	A	4
D		7			C	R		b	4	C	R
								d	7	A	4
								d	7	C	R

Рисунок 6.8 – Операция умножения В образованном файле каждое поле сохраняет прежнее имя, но оно

дополняется именем файла, из которого взято. Это делается, чтобы избежать совпадения имен полей в одноименном файле.

37

Пример 12: определить список лиц, которые получили повышение оклада после того, как Иванов (№_служащего 15) занял должность главного инженера. proj Имя_служащего (proj №_служащего (sel Изм, Окл. Дата_устр.> Труд. Деятельность. Дата_назначения (Изм. оклада product (sel №_служащего = 15 and должность = «главный инженер» (Труд. деятельность)))) join служащий). Систему операций, используемую для манипулирования отношениями, называют алгеброй отношений. Оператор в ней имеет одно или несколько отношений в качестве операнда и образует новое отношение по определенному

правилу.

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

Символика в исчислении отношений.

Таблица 6.1 – Символика в исчислении отношений

Символ	Объяснение
x • y	Множество значений элементов данных из доменов у отношения
	х
A(x1·y1,	Отношение с именем А задано над доменами, которые являются
x2·y2… )	множествами значений х1·у1, х1·у2, … соответственно
:	«Существует»
	«Такой, что». Выражение слева от двоеточия означает то, что
	должно быть найдено выражение справа – условие
	Для любого
	«И» должны выполняться одновременно условия слева и справа
	от знака
	«ИЛИ» должно выполняться хотя бы одно из двух условий
−	«НЕ» условие, записанное справа от знака должно не
	выполняться
≠, =, <, >.	Не равно, равно, меньше, больше
‘x’	Символьное значение х

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

Пример 1: из отношения служащий образовать отношение Q, включающее признаки Имя_студента и средний балл для всех студентов группы 721 со средним баллом более 4:

Q(Студент · Имя_Студента, Студент· средний балл): Студент· №_группы

=721 Студент· средний балл > 4.

38

Пример 2: с помощью отношений Р123 (учетный_№, Дата_преступления, вид_преступления,

срок_заключения)

А117(учетный_№, Имя, адрес, почтовый_индекс) А125(учетный_№, Имя, профессия, годовой_доход)

образовать отношение Q, содержащее признаки: вид_преступления и срок_заключения лиц с профессией Бухгалтер:

Q(Р123·вид_преступления, Р123·срок_заключения) : А125 (А125 · профессия = «Бухгалтер» А125 · учетный номер = Р123 · Учетный_№).

Пример 3: используя отношения Студент (№_студента, Имя_студента, прочие_сведения_о_студенте).

Преподаватель (№_преподавателя, Имя_преподавателя, прочие_сведения_о_преподавателе)

Студ_Преп(№_студента, №_преподавателя)

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

Q(Студент·№_студента, Студент·Имя_студента) : преподаватель Студ_Преп (Студ_преп·№_студента = Студент · №_студента · Студ_Преп №_преподавателя = Преподаватель · №_преподавателя).

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

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

Итак, можно выделить три уровня автоматизации, применяемые в языках пользователя БД:

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

2.Алгебра. Пользователь вводит набор операций высокого уровня над отношениями (или другими группами данных).

3.Кортеж. Низший уровень. Программист работает с записями или кортежами.

Преимущества реляционной базы (базы, заданной в третьей нормальной форме):

39

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

b.Гибкость. Операции реляционной алгебры позволяют ПП – листам получать разнообразные файлы в нужной им форме.

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

d.Секретность. Контроль секретности упрощается. Для каждого отношения задается правомерность доступа.

e.Связность. Реляционное представление дает явную картину взаимосвязей атрибутов из различных отношений и файлов.

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

g.Независимость данных. Структура БД должна допускать возможность ее роста, то есть добавление новых атрибутов и отношений. Методы использования данных также изменчивы. Могут добавляться новые кортежи и удаляться старые. То же касается и элементов данных.

При задании базы в нормализованной форме с независимым ПО перестройка данных не потребует изменения ПП – м.

h.ЯМД. С помощью алгебры отношений или исчисления отношений можно построить простой и гибкий ЯМД. Для данных в виде неплоский структур язык манипулирования либо получается необоснованно сложным для пользователя, либо ограничен по своим возможностям.

i.Ясность. Логическая схема БД при изображении связей с помощью стрелок выглядит ясной, пока количество стрелок невелико.

Принципы нормализации

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

Необходимы еще шаги нормализации.

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

40