Многозначные зависимости и четвертая нормальная форма

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

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

HCTX

COURSE	TEACHERS	TEXTS
Физика	TEACHERS Профессор Иванов Доцент Колосов	TEXT Механика Основы оптики
Математика	TEACHERS Профессор Иванов	TEXT Векторный анализ Тригонометрия Дифференцирование

Рис. 12.1. Пример значений данных в переменной-отношении HCTX

Исключив из переменной-отношения значения атрибутов, принимающих в качестве значений отношения, получим переменную-отношение, представленную на рис. 12.2. Данные, помещаемые в переменную-отношение CTX, имеют следующий смыл: кортеж {COURSE:c, TEACHER:t, TEXT:x} появляется в переменной-отношении CTX тогда и только тогда, когда курс c читается преподавателем t с использованием учебника x. Тогда верно ограничение:

ЕСЛИ кортежи (c,t1,x1) и (c,t2,x2) присутствуют одновременно,

ТО кортежи (c,t1,x2) и (c, t2, x1) также присутствуют одновременно.

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

CTX

COURSE	TEACHERS	TEXTS
Физика	Профессор Иванов	Механика
Физика	Профессор Иванов	Основы оптики
Физика	Доцент Колосов	Механика
Физика	Доцент Колосов	Основы оптики
Математика	Профессор Иванов	Векторный анализ
Математика	Профессор Иванов	Тригонометрия
Математика	Профессор Иванов	Дифференцирование

Рис. 12.2. Переменная-отношение CTX, эквивалентная по набору данных переменной-отношению HCTX

Рассматриваемые проблемы возникают в результате того, что преподаватели и учебники совершенно не зависят друг от друга. Ситуация может быть улучшена путем выполнения декомпозиции переменной-отношения CTX на две проекции с атрибутами {COURSE, TEACHER} и {COURSE, TEXT}, как это показано на рис. 12.3.

CT

COURSE	TEACHERS
Физика	Профессор Иванов
Физика	Доцент Колосов
Математика	Профессор Иванов

CX

COURSE	TEXTS
Физика	Механика
Физика	Основы оптики
Математика	Векторный анализ
Математика	Тригонометрия
Математика	Дифференцирование

Рис. 12.3. Значения данных в проекциях CT и CX, соответствующих содержанию переменной-отношения CTX

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

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

Существование «проблем», которые связаны с переменными-отношениями в НФБК, подобными переменной-отношению CTX, было замечено достаточно давно, и способы их разрешения также вскоре были сформулированы Фейгином (Fagin) в строгом теоретическом виде с использованием понятия многозначной зависимости (МЗЗ), которое является обобщением понятия функциональной зависимости в том смысле, что каждая функциональная зависимость является многозначной.

Пусть A, B и C являются произвольными подмножествами множества атрибутов переменной-отношения R. Тогда подмножество B многозначно зависит от подмножества A, что символически выражается записью:

A ®® B

(читается как «A многозначно определяет B» или «A двойная стрелка B»), тогда и только тогда, когда множество значений B, соответствующее заданной паре (значение A, значение C) переменной-отношения R, зависит от A, но не зависит от C.

Для данной переменной-отношения R {A,B,C} многозначная зависимость A ®® B выполняется тогда и только тогда, когда также выполняется многозначная зависимость A®®C. Таким образом, многозначные зависимости всегда образуют связанные пары.

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

COURSE ®® TEACHER | TEXT

Описанная ранее проблема с переменной-отношения CTX возникает из-за того, что она содержит многозначные зависимости, которые не являются функциональными. Проекции CT и CX не содержат многозначных зависимостей, а поэтому представляют некоторое усовершенствование исходной структуры. Подобная декомпозиция основывается на применении теоремы Фейгина.

Теорема Фейгина. Пусть A, B и C являются множествами атрибутов переменной-отношения R{A,B,C}. Переменная-отношение R будет равна соединению ее проекций {A,B} и {A,C} тогда и только тогда, когда для переменной-отношения R выполняется многозначная зависимость A ®® B | C.

Теперь стало возможным дать определение четвертой нормальной формы.

Переменная-отношение R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда в случае существования таких подмножеств A и B атрибутов этой переменной-отношения R, для которых выполняется нетривиальная многозначная зависимость A ®® B, все атрибуты переменной-отношения R также функционально зависят от атрибута A.

МЗЗ A ®® B называется тривиальной, если либо A является супермножеством B, либо объединение A и B образует весь заголовок отношения.

Иначе говоря, переменная-отношение R находится в 4НФ, если она находится в НФБК и все многозначные зависимости в переменной-отношении R фактически представляют собой функциональные зависимости от ее ключей.

Переменная-отношение CTX не находится в 4НФ, поскольку содержит многозначную зависимость, которая не является функциональной, не говоря уже о том, что последняя должна быть еще и функциональной зависимостью от ключа. Однако обе проекции CT и CX находятся в 4НФ. Следовательно, 4НФ обеспечивает лучшую структуру данных по сравнению с НФБК, поскольку позволяет исключить некоторые нежелательные зависимости. Фейгин показал, что 4НФ всегда является достижимой.

Дата добавления: 2015-05-09