Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

Пример 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; Просмотров: 520; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.