4. Модели данных

4.1. Реляционная модель данных

Модель данных - указание множества допустимых информационных конструкций, операций над данными и множества ограничений для хранимых значений данных.

Концепция реляционной модели данных была предложена Е.Ф. Коддом в 1970 г. в связи с необходимостью обеспечить независимость представления и описания данных от прикладных программ.

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

Схема отношения: СОТРУДНИКИ (Фамилия, Должность, Возраст). Число атрибутов - степень отношения, число кортежей - мощность отношения.

Реляционная база данных - набор взаимосвязанных отношений. Каждое отношение (таблица) представляется в памяти компьютера в виде файла.

Существуют следующие соответствия понятий:

Сущность (класс)	Отношение	Таблица	Файл
Экземпляр (объект) Атрибут	Кортеж Атрибут	Строка Столбец	Запись Поле

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

Основных операций над отношениями насчитывается 8:

- традиционные операции над множествами (объединение, пересечение, разность (вычитание), декартово произведение, деление);

- специальные реляционные операции: проекция, соединение и выбор (селекция, ограничение).

Языки для выполнения операций над отношениями делят на 2 класса:

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

2) языки реляционного исчисления, предоставляющие пользователю набор правил для записи “запросов” к базе данных, в которых содержится только информация о желаемом результате. Пример - языки запросов SQL (Structured Query Language).

4.2. Свойства отношений

Различают 2 класса отношений в зависимости от содержания:

Объектное отношение хранит данные об объектах (экземплярах сущности). Один из атрибутов однозначно идентифицирует каждый объект. Этот атрибут называется ключом отношения или первичным атрибутом. Для удобства его записывают в 1-м столбце. Ключ может состоять из нескольких атрибутов (составной ключ) или быть частью значения атрибута (частичный ключ).

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

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

СТУДЕНТ ПРЕДМЕТ

Студент	Курс		Название	Курс
Иванов	1		Математика	1
Петров	2		История	1
			Физика	2

Примеры объектных отношений:

Пример связного отношения:

ИЗУЧАЕТ

	Студент	Предмет
	Иванов	Математика
	Иванов	История
	Петров	Физика

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

ИЗУЧАЕТ

	Студент	Предмет	Оценка
	Иванов	Математика	4
	Иванов	История	5
	Петров	Физика	3

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

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

Отношение, у которого все атрибуты простые, называется приведенным к первой нормальной форме (1НФ).

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

1. Не может быть одинаковых первичных ключей, т.е. в таблице все строки (записи) должны быть уникальными.

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

3. Имена столбцов таблицы должны быть различны, а значения столбцов должны быть однородными (однотипными).

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

5. Должна соблюдаться ссылочная целостность для внешних ключей.

6. Порядок следования строк в таблице несущественен, т.к. влияет только на скорость доступа к строке.

4.3. Операции над отношениями

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

Исходные отношения обозначим R1, R2 и т.д., результирующее отношение - буквой T. Будем сопровождать рассматриваемые операции командами языков программирования семейства xBase, если такие команды имеются.

1. Объединение (для совместимых отношений) - результат включает все кортежи первого отношения и недостающие кортежи из второго. T = R1R2.

2. Пересечение (для совместимых отношений) - результат содержит только те кортежи, которые есть в обоих отношениях. T=R1R2.

3. Разность (для совместных отношений) T = R1\R2 - результат содержит только те строки первого отношения, которых нет во втором.

Для этих трех операций в языках xBase нет специальных средств. Их можно реализовать сочетаниями команд языка.

Примеры: пусть имеем 2 отношения R1 и R2.

R1 R2

A	B		A	B
x	1		x	1
w	3		x	4
e	2		y	5
x	4		s	2

Далее приводятся таблицы - результаты выполнения операций объединения T1, пересечения - T2 и разности - T3 отношений R1 и R2.

T1 T2 T3

A	B		A	B		A	B
x	1		x	1		w	3
w	3		x	4		e	2
e	2
x	4
y	5
s	2

4. Декартово произведение (отношения могут иметь разные схемы). Степень результирующего отношения равна сумме степеней отношений операндов, а мощность - произведению их мощностей. T = R1  R2.

Пусть имеем два исходных отношения:

СТУДЕНТЫ ЭКЗАМЕНЫ

Фамилия		Предмет	Дата
Иванов		Математика	10.01.97
Петров		Физика	15.01.97
Сидоров

Декартовым произведением этих отношений будет отношение:

ВЕДОМОСТИ

	Фамилия	Предмет	Дата
	Иванов	Математика	10.01.97
	Иванов	Физика	15.01.97
	Петров	Математика	10.01.97
	Петров	Физика	15.01.97
	Сидоров	Математика	10.01.97
	Сидоров	Физика	15.01.97

5. Деление. Отношение - делитель R2 должно содержать подмножество атрибутов отношения - делимого R1. Результат содержит только те атрибуты делимого, которых нет в делителе. T = D(R1, R2).

Пусть имеем исходное отношение СПИСОК.

Фамилия	Язык
Иванов	Си
Иванов	Паскаль
Петров	Си
Петров	Фортран
Петров	Паскаль
Семин	Паскаль
Семин	Фортран

Требуется выделить фамилии программистов, владеющих одновременно Си и Паскалем. Попытка выбрать нужные строки по условию

Язык = “Си” .AND. Язык = “Паскаль”

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

Определим операцию образ. В отношении T(A,B) образом значения a атрибута А является множество значений атрибута В, и каждый элемент b этого множества образует вместе с а некоторую строку (или часть строки) отношения Т. Эта операция обозначается следующим образом:

im B(a) = {b₁, b₂,...,b_k},

где: im - обозначение операции “образ”, а - значение, образ которого вычисляется, В - имя атрибута для образа значения а, b₁, b₂,...,b_k - значения атрибута В.

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

im Фамилия (“Си”) = {“Иванов”, “Петров”}

im Фамилия (“Паскаль”) = {“Иванов”, “Петров”, “Семин” }

im Фамилия (“Си”)  im Фамилия (“Паскаль”)={“Иванов”, “Петров”}

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

ЯП СПИСОК1

Язык		Фамилия
Си		Иванов
Паскаль		Петров

В нашем примере отношение-делитель обозначим ЯП. Результатом операции деления является отношение СПИСОК1, содержащее пересечение всех строк отношения-делителя ЯП, вычисленных на основе отношения-делимого СПИСОК.

6. Проекция. Это операция, которая переносит в результирующее отношение столбцы исходного отношения, указанные в условии операции. Кортежи-дубликаты в результате должны отсутствовать. T = R[X], где X - список атрибутов в схеме отношения T (условие проекции).

На языке xBase эта операция реализуется последовательностью команд (F1 - исходный файл, F2 - результирующий):

Use F1

Copy to F2 fields <список проектируемых полей>

7. Выборка (селекция, ограничение). Это операция, которая переносит в результирующее отношение те строки из исходного отношения, которые удовлетворяют условию выборки УВ. T = R[УВ]. Условие проверяется в каждой строке выборки и не может охватывать информацию из нескольких строк. Оно имеет 2 простейшие разновидности:

1. Имя_атрибута <знак сравнения> константа;

2. Имя_атрибута <знак сравнения> имя_атрибута2.

Соответствующие примеры: Цена>100, План<Факт.

На языке xBase эта операция реализуется последовательностью команд:

USE F1

Copy to F2 for <условие выборки>

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

Фамилия	Таб_номер	Пол	Должность	Оклад
Алексеев	35006	М	Инженер	350000
Бакин	35001	М	Директор	800000
Коврова	38015	Ж	Экономист	380000
Сергеев	45004	М	Электрик	300000
Шубина	38010	Ж	Бухгалтер	320000

Примеры выполнения операций проекции и выборки: пусть имеем исходное отношение ШТАТ

Создаем проекцию T = ШТАТ[Фамилия, Таб_номер, Должность]

Фамилия	Таб_номер	Должность
Алексеев	35006	Инженер
Бакин	35001	Директор
Коврова	38015	Экономист
Сергеев	45004	Электрик
Шубина	38010	Бухгалтер

Выборка из отношения T = ШТАТ[Пол = «М»] имеет вид

Фамилия	Таб_номер	Пол	Должность	Оклад
Алексеев	35006	М	Инженер	350000
Бакин	35001	М	Директор	800000
Сергеев	45004	М	Электрик	300000

8. Соединение. Выполняется над двумя исходными отношениями. Каждая строка первого отношения сопоставляется по очереди со всеми строками второго, и если для этой пары соблюдается условие соединения УС, то они сцепляются и образуют очередную строку в результирующем отношении. Обозначение операции - T = R1 [УС] R2. Условие соединения имеет вид:

Имя_атрибута1 <знак сравнения>Имя_атрибута2,

причем атрибут1 находится в одном исходном отношении, а атрибут2 - в другом.

Практически наиболее важный частный случай соединения называется натуральным (естественным) соединением и имеет следующие особенности:

- знак сравнения в условии соединения - равенство,

- параметры Имя_атрибута1 и Имя_атрибута2 должны совпадать,

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

СПИСОК ОКЛАДЫ

Фамилия	Таб_номер	Занимаемая должность		Должность	Оклад
Алексеев	35006	Инженер		Директор	800000
Бакин	35001	Директор		Бухгалтер	320000
Коврова	38015	Бухгалтер		Инженер	350000
Сергеев	45004	Инженер
Шубина	38010	Бухгалтер

Возьмем два исходных отношения

Выполним их натуральное соединение по атрибутам «Занимаемая должность» и «Должность» в таблицу СПИСОК1:

СПИСОК1

Фамилия	Таб_номер	Занимаемая должность	Оклад
Алексеев	35006	Инженер	350000
Бакин	35001	Директор	800000
Коврова	38015	Бухгалтер	320000
Сергеев	45004	Инженер	350000
Шубина	38010	Бухгалтер	320000

Кроме натурального существуют еще два вида соединений:

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

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

Реализация приведенного примера на языке xBase будет выглядеть следующим образом: пусть СПИСОК и ОКЛАДЫ - имена файлов базы данных, хранящих соответствующие таблицы и открываемых в областях 1 и 2 соответственно, а СПИСОК1 - имя файла, в который будет помещаться результат соединения; получаем последовательность команд

Select 1

Use СПИСОК

Select 2

Use ОКЛАДЫ

Select 1

Join with ОКЛАДЫ to СПИСОК1 ;

For Занимаемая_должность = ОКЛАДЫ.Должность ;

Fields Фамилия, Таб_номер, Занимаемая_должность, ОКЛАДЫ.Оклад

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

Операция натурального соединения обладает свойствами коммутативности и ассоциативности. Свойство коммутативности означает, что операции R [УС] S и S [УС] R порождают одно и то же отношение. Свойство асоциативности означает, что операции (R [УС] S) [УС] T и R [УС] (S [УС] T) дают одинаковый результат.

4.4. Нормализация отношений

Центральная задача проектирования базы данных экономической информационной системы - определение количества отношений (или иных СЕИ) и их атрибутного состава.

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

- множество отношений должно обеспечивать минимальную избыточность представления информации;

- корректировка отношений не должна приводить к двусмысленности или потере информации;

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

Удовлетворение этих требований достигается нормализацией отношений БД. Нормализация - это пошаговый обратимый процесс декомпозиции (разложения) исходных отношений на другие, более мелкие и простые отношения. При этом выясняются все возможные функциональные зависимости между атрибутами.

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

Реляционная база данных в целом характеризуется Первой Нормальной Формой (1НФ), если все ее отношения соответствуют 1НФ. Приведение данных, имеющих форму СЕИ, к 1НФ всегда осуществимо.

4.5. Функциональные зависимости

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

Пусть в отношении R1 имеются 2 атрибута А и В. Атрибут В функционально зависит от атрибута А, если в любой момент времени каждому значению А соответствует единственное значение В. Функциональная зависимость обозначается А  В. Отсутствие функциональной зависимости обозначается А  В.

Ситуацию А  В можно определить операцией “Образ”, сказав, что множество imB(a) должно содержать один элемент для любого значения а атрибута А.

Будем рассматривать отношение

ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ

Таб_Ном	Предмет	Кол. часов	Фамилия	Должность	Оклад	Кафе-дра	Теле-фон
1	ТЭИС	51	Иванов	доцент	450	ИС	1-15
1	БД	68	Иванов	доцент	450	ИС	1-15
2	ЭВМ	48	Петров	доцент	450	ИС	1-15
3	ЭВМ	48	Семин	профессор	550	ЭВМ	2-43
4	МатАн	68	Бакин	ст.преп.	350	ВМ	2-75
4	ТеорВер	102	Бакин	ст.преп.	350	ВМ	2-75

В данном отношении нельзя выбрать в качестве ключа один атрибут, поэтому будем использовать составной ключ ТабНом+Предмет.

В отношении можно выделить ряд функциональных зависимостей:

Должность  Оклад

Таб_Ном  Фамилия  взаимно однозначное

Таб_Ном  Фамилия  соответствие АВ

Предмет  КолЧас

Кафедра  Телефон и т.д.

Если отношение находится в 1НФ, то все неключевые атрибуты функционально зависят от ключа, но степень зависимости может быть различной: если неключевой атрибут зависит только от части ключа, это частичная зависимость (пример, Предмет  КолЧас); если атрибут зависит от всего составного ключа и не находится в частичной зависимости от его частей, то говорят о полной функциональной зависимости от всего составного ключа. В примере таких нет.

Если для атрибутов А, В, С выполняются условия АВ и ВС, но обратная зависимость отсутствует, то говорят, что С зависит от А транзитивно. Пример:

Фамилия  Кафедра  Телефон

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

Многозначная зависимость возможна при наличии в отношении хотя бы 3 атрибутов: ключа и не менее 2 независимых друг от друга атрибутов.

Рассмотрим отношение ПРЕПОДАВАТЕЛЬ с ключом Фамилия

Фамилия	Группа	Предмет
Иванов	3	ТЭИС
Иванов	3	СУБД
Иванов	4	ТЭИС
Иванов	4	СУБД
Петров	5	СУБД

Между преподавателем и группами студентов существует связь “один-ко-многим” (1 : М), т.е. один преподаватель может вести занятия в нескольких группах, но каждая группа закреплена за одним преподавателем. Между преподавателем и предметом имеется связь “многие-ко-многим” (М : N), т.е. один преподаватель может вести несколько предметов и один предмет могут вести несколько преподавателей. Эти связи можно условно изобразить в виде

Фамилия ¹  ^М Группа

Фамилия ^М  ^N Предмет

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

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

А, В, С  D.

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

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

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

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

Экономические документы, как правило, содержат единственный вероятный ключ, который является и первичным.

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

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

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

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

1. А,ВА и А,ВВ.

2. АВ и АС, тогда и только тогда, когда АВ, С.

3. Если АВ и ВС, то АС.

4. Если АВ, то АСВ (С произвольно).

5. Если АВ, то АСВС (С произвольно).

6. Если АВ и ВСD, то АСD.

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

4.6. Нормальные формы

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

Рассмотрим отношение ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ.

В этом отношении существует частичная функциональная зависимость атрибутов Фамилия, Должность, Оклад, Кафедра, Телефон от части составного ключа “Таб_Ном”.

Такая частичная зависимость приводит к следующим аномалиям:

1) Дублирование данных о преподавателе, т.к. преподаватель может вести несколько предметов.

2) Проблема контроля избыточности данных, т.к. изменение, например, оклада влечет за собой необходимость поиска и изменения значений окладов во всех кортежах.

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

Таким образом, первая нормальная форма (1НФ) требует дальнейших преобразований.

4.7. Вторая нормальная форма (2НФ)

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

Чтобы устранить частичную зависимость и провести рассмотренное отношение к 2НФ, разложить его на 2 отношения следующим образом:

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

- построить проекцию на часть составного ключа и атрибуты, зависящие от этой части.

ПРЕДМЕТ

Таб_Ном	Предмет	Кол.часов
1	ТЭИС	51
1	БД	68
2	ЭВМ	48
3	ЭВМ	48
4	МатАн	68
4	ТеорВер	102

В итоге получим 2 отношения. ПРЕДМЕТ и ПРЕПОДАВАТЕЛЬ, находящиеся в 2НФ.

ПРЕПОДАВАТЕЛЬ

Таб_Ном	Фамилия	Должность	Оклад	Кафе-дра	Теле-фон
1	Иванов	доцент	450	ИС	1-15
1	Иванов	доцент	450	ИС	1-15
2	Петров	доцент	450	ИС	1-15
3	Семин	профессор	550	ЭВМ	2-43
4	Бакин	ст.преп.	350	ВМ	2-75
4	Бакин	ст.преп.	350	ВМ	2-75

В последнем отношении есть транзитивные зависимости, например:

Таб_Ном  Кафедра  Телефон

Таб_Ном  Должность  Оклад

Их наличие порождает неудобства и аномалии следующего характера (на примере “Телефон”):

1) дублирование информации о телефоне для всех преподавателей,

2) проблема контроля избыточности при изменении номера телефона,

3) нельзя включить данные о новой кафедре, если на ней еще отсутствуют преподаватели; и наоборот, при увольнении всех преподавателей данные о кафедре нельзя сохранить.

Для решения указанных проблем требуются дальнейшие преобразования отношений.

4.8. Третья нормальная форма (3НФ)

Отношение находится в 3НФ, если оно находится во 2НФ и нем отсутствуют транзитивные функциональные зависимости неключевых атрибутов от ключа.

Для рассматриваемого примера можно получить 3 отношения: ПРЕПОДАВАТЕЛЬ, ДОЛЖНОСТЬ и КАФЕДРА.

ПРЕПОДАВАТЕЛЬ ДОЛЖНОСТЬ КАФЕДРА

Таб_Ном	Фамилия	Должность	Кафедра		Должность	Оклад		Кафе-дра	Теле-фон
1	Иванов	доцент	ИС		доцент	450		ИС	1-15
2	Петров	доцент	ИС		профессор	550		ЭВМ	2-43
3	Семин	профессор	ЭВМ		ст.преп.	350		ВМ	2-75
4	Бакин	ст.преп.	ВМ

База данных находится в 3НФ, если все ее отношения имеют 3НФ.

Алгоритм получения 3НФ

Исходные данные для алгоритма - список атрибутов, охватывающий одно отношение, базу данных или ее часть. В любом случае предполагается (хотя бы теоретически) существование одного отношения с заданным списком атрибутов. В противном случае нельзя применять некоторые теоремы о функциональных зависимостях и нельзя гарантировать, что одна и та же функциональная зависимость, например, АВ, справедливая в разных отношениях R и S, соответствует равным отношениям R[A,B] и S[A,B].

Алгоритм обладает следующими свойствами:

1) сохраняет все первоначальные функциональные зависимости, что гарантирует получение осмысленных отношений с легко интегрируемой структурой;

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

3) результат декомпозиции в 3НФ обычно содержит меньше значений атрибутов, чем исходное отношение (уменьшается избыточность).

Алгоритм состоит из следующих шагов:.

1. Получить исходное множество функциональных зависимостей для атрибутов рассматриваемой базы данных.

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

3. Для каждой функциональной зависимости, полученной на шаге 2, создать проекцию исходного отношения R_i=R[X_i], где X_i - объединение атрибутов из левой и правой частей функциональной зависимости f_i.

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

Для практического применения алгоритма существенны два вопроса:

- как учесть наличие взаимно однозначных соответствий,

- как сократить объем перебора вариантов при первоначальном определении множества функциональных зависимостей.

Для решения первого вопроса принято выделение старшего (по объему представляемого понятия) атрибута, который затем представляет все атрибуты взаимно однозначного соответствия.

Для решения второго не рассматривается зависимость, которая является следствием уже доказанных зависимостей и теорем 1-6; используется ряд закономерностей об отсутствии функциональных зависимостей. Среди них:

теорема: если АB и DC, то ABDC

правило: функциональные зависимости с атрибутом-основанием в левой части не рассматриваются.

В нашем примере имеют место функциональные зависимости:

Таб_ном  Фамилия 

Таб_Ном  Должность  ТН  Фамилия, Должность, Кафедра

Таб_Ном  Кафедра 

Должность  Оклад

Кафедра  Телефон

На основе функциональных зависимостей можно установить более сильную нормальную форму Бойса-Кодда (БКНФ). Практически она применяется редко. Во первых, база данных в БКНФ не всегда существует, во-вторых, ее отличие от 3НФ обычно связано с наличием нескольких ключей в отношении, что в экономических приложениях встречается исключительно редко. Считается, что отношение находится в НФБК, если оно находится в 3НФ и в нем отсутствуют зависимости ключевых атрибутов от неключевых;

Существуют еще четвертая и пятая нормальные формы. Определим их на уровне понятий.

Отношение находится в 4НФ, если оно находится в НФБК и в нем отсутствуют многозначные зависимости, не являющиеся функциональными.

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

4.9. Доступ к реляционной БД

Реляционная база данных в целом соответствующая 3НФ, обладает рядом свойств, знание которых облегчает и упорядочивает процедуры обработки хранящейся в ней информации. Типичные процедуры, выполняемые с базой данных: выборка, корректировка и арифметические вычисления.

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

А - имя неключевого атрибута,

V - одно из его значений,

e- соответствующее значение первичного ключа,

@ - один из знаков сравнения =, #, <, >, >=, <=

? - величины e или V, которые должны быть найдены.

Различают 3 класса запросов:

1. А(e)=? - найти значение атрибута по известному значению ключа;

2. А(?)@V - найти записи с заданным значением неключевого атрибута;

3. А(?)=? - перечислить значения данного атрибута для каждой записи.

Условия запросов второго типа могут комбинироваться с помощью логических операций И, ИЛИ, НЕ.

В запросах используют следующие понятия:

оболочка запроса - множество имен атрибутов, упоминаемых в формулировке запроса:

вход запроса - множество имен атрибутов, для которых заданы условия вида А(?)@V;

выход запроса - результат запроса.

Пример запроса: какие предприятия, расположенные в Киеве, поставляют свою продукцию на завод КЭМЗ по железной дороге? Здесь оболочку составляют атрибуты: Предприятия (поставщик), Город (поставщика), Продукция, Завод (потребитель), Вид_Транспорта. Вход запроса: - Город, Завод, Вид_Транспорта.

Допустим, что запрос реализуется на отношении R(Предприятие, Город, Продукция, Завод, Вид_Транспорта) с ключом Предприятие, Продукция, Завод. Атрибут Завод является частью первичного ключа, значит, данный запрос относится к типу 2.

Выход запроса - Предприятие.

Существуют правила реализации запросов к базе данных с помощью операторов реляционной алгебры:

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

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

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

4. Если запрос можно разделить на части (подзапросы), то его реализация также делится на части, где результатом подзапроса является отдельное отношение.

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

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

Для соединения по условию равенства двух произвольных отношений из БД в 3НФ справедлива закономерность: соединение является корректным, если атрибут (или группа атрибутов), по которому производится соединение, служит первичным ключом в одном из соединяемых отношений.

Рассмотрим систему отношений:

ДЕТАЛЬ (код_детали, наименование);

ПОСТАВЩИК (код_поставщика, город, вид_транспорта);

ПЕРЕВОЗКА (код_поставщика, код_потребителя, код_детали, дата, количество).

Покажем примеры запросов к этой системе отношений. Необходимые для выполнения запросов действия будем иллюстрировать последовательностями команд языка СУБД семейства FoxPro.

1. Получить коды всех поставляемых деталей.

Атрибут код_детали есть в отношениях 1 и 3. По смыслу запроса выполняется проекция 3-го отношения.

Use ПЕРЕВОЗКА

Copy to П1 fields Код_детали

В отношении П1 могут повторяться коды, их надо исключить. Это можно сделать с помощью индексирования:

Use ПЕРЕВОЗКА

Index on Код_детали to ПЕРЕВОЗКА.idx

Copy to R1 fields Код_детали

2. Выделить коды всех поставщиков из Перми, перевозящих детали автотранспортом.

Список атрибутов в формулировке запроса: Код_поставщика, Город, вид_транспорта. Все они содержатся в одном отношении ПОСТАВЩИК.

Use ПОСТАВЩИК

Copy to R2 field Код_поставщика;

for Город = “Пермь”.and.Вид_транспорта = “Автотранспорт”

3. Получить названия деталей, поставляемых заводом “Маяк” (код поставщика - 175).

Атрибуты запроса находятся в разных отношениях: Название - в отношении ДЕТАЛЬ, Код_поставщика - в отношении ПЕРЕВОЗКА. Следовательно, требуется их соединение по атрибуту Код_детали.

Select 1

Use ПЕРЕВОЗКА

Select 2

Use ДЕТАЛЬ

Join with B to R3 for Код_детали = ПЕРЕВОЗКА. Код_детали.and. ;

ПЕРЕВОЗКА. Код_поставщика = 175 fields Название

4. Получить коды всех поставщиков, поставляющих детали с кодами 15 или 38.

Атрибуты запроса: Код_поставщика и Код_детали. Они находятся в одном отношении ПЕРЕВОЗКА.

Use ПЕРЕВОЗКА

Copy to R4 fields Код_поставщика ;

for Код_детали=15.or. Код_детали=38

Если список деталей достаточно длинный, то целесообразно хранить его в некотором отношении, например, Z1 (Код_детали) и применить следующие команды:

Select 1

Use ПЕРЕВОЗКА

Select 2

Use Z1

Join with ПЕРЕВОЗКА to R4 ;

for Код_детали = ПЕРЕВОЗКА.Код_детали ;

fields Код_поставщика

5. Получить коды всех поставщиков, поставляющих детали с кодами 15 и 38 одновременно.

Use ПЕРЕВОЗКА

Copy to R5 fields Код_поставщика ;

for Код_детали = 15. and. Код_детали = 38

R5 в этом случае будет пустым отношением. Чтобы этого избежать, можно рекомендовать следующий набор команд:

Select 1

Use ПЕРЕВОЗКА

Copy to W1 fields Код_поставщика for Код_детали = 15

Copy to W2 fields Код_поставщика for Код_детали = 38

Use W1

Select 2

Use W2

Join with W1 to R5 for Код_поставщика = W1. Код_поставщика;

fields Код_поставщика

6. Для каждой поставляемой детали выбрать ее название и местонахождение поставщика.

Атрибуты запроса Название и Город находятся в разных отношениях Деталь и Поставщик. Соединить их невозможно, т.к. у них нет общих атрибутов. При использовании отношения Перевозка задача решается следующим образом.

Select 1

Use ПЕРЕВОЗКА

Select 2

Use ДЕТАЛЬ

Join with ПЕРЕВОЗКА to R7 ;

for Код_детали = ПЕРЕВОЗКА. Код детали ;

fields Код_детали, ПЕРЕВОЗКА. Код поставщика, Название

Use Поставщик

Select 1

Use R7

Join with ПОСТАВЩИК ;

for Код_поставщика = ПОСТАВЩИК. Код_поставщика ;

fields Код_детали, Название, ПОСТАВЩИК. Город

4.10. Иерархическая модель данных

Структура данных называется иерархической, если ее схема представлена в виде дерева. Узлами дерева-схемы являются записи, дугами - иерархические связи между записями. Иерархическая связь предполагает, что одной «верхней» записи соответствует несколько реализаций «нижней», т.е. структура использует связи вида «один-ко-многим».

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

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

Если два узла дерева соединены дугой, то узел более высокого уровня называется порождающим, а узел более низкого уровня - порожденным (или подчиненным). Всякий узел иерархической структуры (кроме корня дерева) имеет один порождающий узел. Ниже изображен пример схемы иерархической структуры.

Определяем ключи (для каждого типа записей в узлах схемы):

ФАКУЛЬТЕТ - Р1; КАФЕДРА - Р1, Р5; ПРЕДМЕТ - Р1, Р5, Р9;

ГРУППА - Р1, Р5, Р12; СТУДЕНТ - Р16.

Ключ подчиненного узла не может совпадать с ключом порождающего узла, но может включать его.

Если в записи «СТУДЕНТ» заменить уникальный атрибут «№ зачетной книжки» на порядковый номер студента в группе, то ключ типа записей СТУДЕНТ будет Р1, Р5, Р12, Р16.

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

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

Для нашего примера получим совокупность файлов в 3НФ со следующими схемами (в схемах подчеркнуты ключевые атрибуты):

Р1, Р2, Р3, Q4

Р1, Р5, Р6, Р7, Q8

Р1, Р5, Р12, Р13, Р14, Q15

Р1, Р5, P9, Q10, Q11

P16, P17, Q18, Q19

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

Р1, Р5, P9, Q10, Q11

P16,P17, Q18, Q19, P1, P2, P3, Q4, P5, P6, P7, Q8, P12, P13, P14, Q15

Эти файлы тоже можно рассматривать как результат нормализации иерархической базs данных.

Преобразование нормализованных файлов в иерархическую базу данных также неоднозначно и зависит от запроса к ней.

№ пп	Дата	Участок	Материал	Номенкл. номер	Цена	Колич-во	Сумма
P1	P2	P3	P4	P5	Q6	Q7	Q8

Пусть имеем нормализованный файл ТРЕБОВАНИЯ:

Из него можно сформировать, например, следующие иерархические структуры:

Левая схема представляет вариант запроса по порядковому номеру и дате. В первый уровень выносятся общие значения атрибутов Р1, Р2, Р3. Правая схема соответствует варианту запроса по дате. В ней в первый уровень выносится общее значение атрибута Р2.

Отметим, что вынесение общих атрибутов - общий прием построения иерархической структуры по нормализованной схеме.

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

4.11. Сетевая модель данных

Рассмотрим табель учета рабочего времени

Исходный документ не нормализован. В клетках указано количество рабочих часов данного сотрудника в данный день.

Таблица позволяет получать ответы на запросы двух типов:

1. По заданной фамилии сотрудника сообщить его рабочие часы на различные даты.

2. По заданной дате сообщить рабочие часы на эту дату для различных сотрудников.

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

ТАБЕЛЬ_1

Дата		Сотрудник		Рабочие
S12		S34		часы
Число	День недели	ФИО	Таб.номер
Р1	Р2	Р3	Р4	Q5
1 1 2 2	Понедельник Вторник Понедельник Вторник	Иванов Иванов Петров Петров	01 01 02 02	8 9 10 0

Обозначим запрос Зп=(Усл)(П), П - проекция, которая является результатом запроса, Усл - условие запроса (ключ поиска или ключ запроса). Тогда

Зп1 = (S₃₄)(S₁₂,Q₅)

Зп2 = (S₁₂)(S₃₄,Q₅)

В составе нормализованного файла можно выделить СЕИ, которые располагаются то в ключе, то в результате запроса, и атрибут Q5, всегда относящийся к результату запроса. Запросы такого вида называются инверсными по отношению друг к другу, СЕИ S₁₂ и S₃₄ назовем инверсным условием поиска, атрибут Q5 - информацией связи. Этим запросам можно поставить в соответствие следующие иерархические структуры.

В обоих случаях информация связи располагается в подчиненном сегменте. Структура, обеспечивающая ответы на запросы обоих типов, имеет вид:

Такая структура называется V-образной сетевой схемой. Она содержит два порождающих сегмента и один подчиненный. Тип связей, соответствующий схеме - “один-ко-многим”.

Подчиненный сегмент Q5 является информацией связи между S₁₂ и S₃₄.

Правило: если заданы СЕИ С1, С2 и С3, то С3 может считаться информацией связи между С1 и С2 тогда и только тогда, когда отсутствует как функциональная зависимость С1  С3, так и С2  С3. Допускается, но не обязательна, полная функциональная зависимость (С1, С2)  С3.

Экземпляр рассматриваемой V-образной сетевой схемы называется сетевой БД. Его нормализованное представление - таблица ТАБЕЛЬ_1, а двухвходовое - ТАБЕЛЬ (двухвходовая таблица).

Введем новые понятия.

Разбиение. Пусть задано множество S и совокупность его подмножеств , удовлетворяющая условиям:

1) 2) для всех i  j S_i  S_j = 

Тогда совокупность  называется разбиением множества S.

Таблица ТАБЕЛЬ определяет два разбиения на множества реализаций атрибута Q5. Элементами одного из этих разбиений являются столбцы таблицы, другого - ее строки.

Веерное множество. Пусть задана схема АВ, причем в ее экземпляре каждому значению А соответствует более чем одно значение В (связь типа один-ко-многим). Тогда экземпляр АВ будет называться веерным множеством, а подмножества этого экземпляра, соответствующие одному значению А - веером. Значения А - оси вееров, В - лепестки вееров. Нетрудно видеть, что:

- веерное множество определяет разбиение на множестве реализаций В;

- таблица ТАБЕЛЬ определяет два веерных множества, состоящих каждое из двух вееров.

Рассмотрим схему ( * ). Если в ней понимать сегменты как множества значений, соответствующих СЕИ, а стрелки - как изображение отношений “один-ко-многим”, то можно считать, что экземпляр схемы ( * ) - это таблица ТАБЕЛЬ, причем:

а) левая стрелка соответствует веерному множеству “дата - часы работы сотрудников”, а правая - “сотрудник - часы работы в разрезе дат”;

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

в) количество лепестков в каждом веере соответствует количеству элементов в строке или столбце таблицы ТАБЕЛЬ;

г) на множестве реализаций сегмента “рабочие часы” (Q5) имеется два разбиения, соответствующих двум веерным множеством.

Таким образом, каждой паре вида “исходный сегмент - подчиненный сегмент” в сетевой схеме соответствует веерное множество в ее экземпляре. При описании сетевых схем сегмент называют типом записи, а пару “исходный - подчиненный” - набором.

Рассмотрим некоторый ориентированный граф. Каждая дуга помечена

парой чисел: номер дуги и вес дуги. Пусть это будет условным изображением сборочного машиностроительного изделия, где: вершина А соответствует самому изделию; остальные вершины обозначают сборочным единицам; каждая дуга показывает входимость сборочной единицы в другую сборочную единицу (E, F - детали, в них не входят другие сборочные единицы). Вес дуги - количество, в котором нижняя вершина вхо­дит в верхнюю.

Входная (ниж-	Исходная (верхняя) вершина
няя) вершина	A	B	D
B	1, AB, 2
C	2, AC, 4	4, BC, 2	5, DC, 4
D	3, AD, 1
E			6, DE, 7
F			7, DF, 3

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

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

Согласно таблице инверсными условиями поиска являются названия верхней или нижней вершины, а информацией связи - указанные в клетках данные о дуге. Здесь возможны запросы типа: “Какие дуги исходят из данной вершины?” и “Какие дуги входят в данную вершину?”

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

На множестве S={AB, AC, AD, BC, DC, DE, DF} возможны 2 разбиения:

1) разбиение, соответствующее веерному множеству, осями которого будут веерные вершины дуг

₁={{AB, AC, AD}, {BC}, {DC, DE, DF}} ,

назовем его веерным множеством (разбиением) по «что». Оно соответствует столбцам таблицы и указывает для каждой вершины “что” входит в нее при сборке.

2) разбиение и веерное множество, соответствующее срокам таблицы

₂={{AB}, {AC, BC, DC}, {AD}, {DE}, {DF}}

назовем его разбиением по «куда», т.к. оно показывает, «куда» входит при сборке каждая вершина.

Отметим, что наименования строк и столбцов таблицы относятся к одному и тому же множеству - множеству вершин графа.

В получаемой схеме будет один исходный сегмент (тип записи) - вершина. Сетевая структура содержит 2 типа записей и 2 типа наборов. Подобная структура называется двухвходовой П-образной структурой.

С помощью такой структуры может быть изображен любой ориентированный граф.

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

№ позиции	Ключ	Указатель
0 1 2 3 4 5 6	43 67 52 25 91 08	6 3 5 2 1 0 4

Рассмотрим следующую структуру в памяти произвольного доступа.

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

Последняя в логическом порядке запись (в примере - 5-я запись) может иметь указатель на якорь. В таком случае список называется кольцевым. Если такая запись имеет признак конца списка, список называется цепным.

Нетрудно видеть, что список можно рассматривать как веер, осью которого является якорь, а лепестками - элементы списка.

4.12. Сравнение различных моделей данных

Критерии учитывают как собственно модели, так и особенности СУБД.

1. Реляционная модель

Достоинства:

- простота (всего одна информационная конструкция);

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

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

Недостатки:

- низкое быстродействие при выполнении операции соединения;

- большой расход памяти для представления базы данных (по сравнению с другими моделями).

2. Иерархическая модель

Достоинства:

- простота, естественность иерархического принципа;

- независимость данных;

- минимальный расход памяти (среди всех моделей).

Недостатки:

- неуниверсальность (модель применима не для всех вариантов взаимосвязи данных, реализация может быть связана с повышением избыточности в базе данных);

- допустимость только навигационного принципа доступа к данным;

- доступ к данным производится только через корневое отношение.

3. Сетевая модель

Достоинства:

- универсальность;

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

Недостатки:

- высокая сложность;

- допустимость только навигационного принципа доступа к данным.