3.15 Продолжение алгоритма нормализации (приведение к 5 nf)

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

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

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

Подводя итоги, отметим, что обобщением 3NF на случай, когда отношение имеет более одного потенциального ключа, является нормальная форма Бойса-Кодда.

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

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

Дальнейшая нормализация связана с обобщением понятия функциональной зависимости.

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

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

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

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

Отношение находится в четвертой нормальной форме (4NF) тогда и только тогда, когда отношение находится в NFBK и не содержит нетривиальных многозначных зависимостей.

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

Отношение находится в пятой нормальной форме (5NF) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.

4 Реляционная алгебра

4.1 Операции над отношениями: общие сведения

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

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

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

2. Специальные реляционные операции, такие как выборка, проекция, соединение и деление.

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

Реляционное исчисление – это декларативный теоретический язык запросов, реализованный на основе исчисления предикатов первого порядка (логических высказываний в виде функции, принимающей значения «истинно» или «ложно»), которым должны удовлетворять искомые кортежи или домены отношений. Существует два варианта исчислений: исчисление кортежей и исчисление доменов. В первом случае для описания отношений используются переменные, допустимыми значениями которых являются кортежи отношения, а во втором случае  элементы домена.

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

В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SEQUEL(SQL  Structured Query Language), который представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления, использующий синтаксис, близкий к фразам английского языка и расширенный дополнительными возможностями, отсутствующими в реляционной алгебре и реляционном исчислении.

Современные языки манипулирования данными SQL, QBE, ISBL и др., используемые в СУБД, реализуют широкий набор операций:

 операции с данными: включение, модификация, удаление данных;

 операции обработки данных:

 арифметические выражения (вычисления, сравнения);

 команды присваивания и печати;

 агрегатные функции.

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

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

Рассмотрим операторы реляционной алгебры на примере РБД «Разработчики проектов» [9].

Пример 5. Пусть РБД «Разработчики проектов» состоит из шести таблиц:

 

Таблица 35.  РАЗРАБОТЧИКИ (R1)						Таблица 36.  ПРОГРАММИСТЫ (R2)
N_R	ФИО	Г_Р	Стаж				N_A	N_R_A	Я_П	Категория
R1	Белов А.	1940	21				A1	R4	Pas	1
R2	Крылов Г.	1962	17				A2	R2	C	2
R3	Фатов Р.	1964	11				A3	R5	Pas	3
R4	Белов А.	1953	21				A4	R4	C	1
R5	Крылов Г.	1964	10				A5	R2	Pas	2

 

Таблица 37.  ПРОЕКТЫ (R3)

Таблица 38.  ВТК (R4)

N_P

Назв_P

N_R_P

Г_Созд

N_ВТК

Назв_ВТК

N_комн

N_рук_ВТК

P1

ПР-1

R5

1982

B1

Луч

12

R5

P2

ПР-2

R2

1984

B2

Стрела

18

R3

P3

ПР-1

R1

1960

B3

Взлет

12

R2

P4

ПР-3

R2

1987

P5

ПР-4

R3

1985

Таблица 39.  СОСТАВЫ_ВТК(R5)

Таблица 40.ИСПОЛЬЗОВАНИЕ_В_ГИП(R6)

N_ВТК

N_А_ВТК

N_P_ГИП

N_ГИП

N_R_ГИП

N_ВТК_ГИП

B1

A1

P5

TR1

R1

B3

B1

A3

P3

TR2

R4

B1

B1

A4

P5

TR5

R3

B3

B2

A2

P2

TR1

R1

B2

B2

A5

P4

TR2

R4

B1

B3

A1

B3

A5