ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.03.2024
Просмотров: 100
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Операция модификации (UPDАТЕ). В отношении СNR код и название области для каждого города повторяется несколько раз (поэтому оно имеет некоторую избыточность). Следовательно, при изменении кода области возникнет либо проблема необходимости поиска в отношении СNR всех кортежей для этой области (для внесения соответствующих изменений), либо проблема получения несовместимого результата.
Чтобы разрешить эти проблемы, необходимо заменить отношение СNR двумя проекциями:
Сities{СityNо, СitуNаmе, RgNo}
Rеgiлns{RgNо, RgNаmе}
Таким образом, преобразованная структура отношений позволит преодолеть все приведенные проблемы с операциями обновления.
Третья нормальная форма
Только тогда отношение находится в третьей нормальной форме (3НФ),когда оно находится во второй нормальной форме и каждый неключевой атрибут нетранзитивно зависит от первичного ключа, Под «нетранзитивной зависимостью» подразумевается отсутствие какой-либо взаимной зависимости в изложенном выше смысле.
Отношения Сitiеs и Rеgiоns находятся в третьей нормальной форме. Значит, вторым этапом нормализации является создание проекций для исключения транзитивных зависимостей.
Сохранение зависимости.
В процессе приведения отношений часто возникают ситуации, когда данное отношение может быть подвергнуто операции декомпозиции разными способами. Рассмотрим снова приведенное выше отношение CNR с функциональными зависимостями СitуNо
СitуNаmе, СitуNо RgNо, CitуNо RgNаmе, RgNо RgNаmе и, следовательно, транзитивной зависимостью СitуNо RgNаmе. На рисунке 6.5 транзитивная зависимость показана пунктирной стрелкой:
Рисунок 0.5 – Функциональные зависимости в отношении СNR
Ранее отмечалось, что аномалии обновления, которые сопровождают отношение СNR, можно преодолеть с помощью декомпозиции с заменой этого отношения двумя проекциями в ЗНФ.
Сitiеs{СitуNо, СitуNаmе, RgNо} и Rеgiоns{RgNо, RgNаmе}
Обозначим эту декомпозицию «декомпозицией №1», имея в виду, что для нее существует альтернативная «декомпозиция №2»:
Сitiеs{СitуNо, СitуNаmе, RgNо} и Rеgiоns{СitуNо, RgNаmе}
При этом обе проекции Сities одинаковы как для №1, так и для №2. Декомпозиция №2 происходит также без потери информации, а обе ее проекции находятся в ЗНФ. Однако по некоторым причинам декомпозиция №2 менее желательна, чем декомпозиция №1. После выполнения декомпозиции №2 все еще невозможно вставить информацию о том, что некоторая область имеет определенный код, без указания города, который находится в этой области.
Рассмотрим этот пример подробнее. Необходимо отметить, что зависимости проекций в декомпозиции №1 отмечены сплошными стрелками, тогда как одна, из зависимостей проекций декомпозиции №1 отмечена пунктирной стрелкой. В декомпозиции №1 две проекции независимы друг от друга в следующем смысле: обновления в каждой из проекций могут быть выполнены совершенно независимо друг от друга (за исключением ограничения целостности для Сitiеs и Rеgiоns). Если такое обновление допустимо только в контексте данной проекции, т.е. не нарушается уникальность первичного ключа для этой проекции, то соединение этих двух проекций после обновления всегда будет равносильно отношению СNR (т.е. при соединении не будут нарушены ограничения, наложенные на ФЗ в отношении CNR). И наоборот, в декомпозиции №2 обновление любой из двух проекций необходимо тщательно фиксировать, чтобы гарантировать отсутствие нарушения зависимости RgNо
RgNаmе (два города, находящиеся в одной и той же области, должны иметь один код области). Иначе говоря, обе проекции декомпозиции №2 не являются независимыми одна от другой.Проблема состоит в том, что в декомпозиции №2 функциональная зависимость RgNо
RgNаmе становится ограничением между отношениями. Заметим, что во многих современных программных продуктах это ограничение возможно поддержать с помощью процедурной обработки. В декомпозиции №1 транзитивная зависимость SitуNо RgNаmе является ограничением между отношениями, которое автоматически выполняется при задействовании двух ограничений внутри отношений: СitуNо RgNо и RgNо RgNаmе. Привести в действие эти ограничения не сложно за счет соответствующих условий, ограничивающих уникальность первичных ключей.Концепция независимых проекций, таким образом, предоставляет критерий выбора одной из нескольких возможных декомпозиции. Декомпозиция с независимыми проекциями в представленном выше общем смысле лучше той, в которой проекции зависимы. Риссанен (Rissаnеn) показал, что проекции R1 и R2 отношения R независимы, в упомянутом выше смысле, только в том случае, когда:
- каждая ФЗ в отношении R - это логическое следствие функциональных зависимостей в проекциях R1 и R2;
- общие атрибуты проекций R1 и R2 создают потенциальный ключ, хотя бы, для одной из них.
Атомарным называется отношение, которое не может быть подвергнуто декомпозиции с получением независимых проекций. Из этого не следует, что любое неатомарное отношение может быть разбито на атомарные компоненты. Идея нормализации с декомпозицией на независимые проекции называется декомпозицией с сохранением зависимости.
Нормальная форма Бойса-Кодда.
Исключим упрощающее предположение о том, что каждое отношение имеет лишь один потенциальный ключ (а именно первичный ключ), и рассматривается более общий случай. Определение Кодда для ЗНФ, в данном случае, не совсем подходит для отношений с перечисленными ниже условиями.
Отношение имеет два (или более) потенциальных ключа. Два потенциальных ключа являются сложными. Они перекрываются (т.е. имеют, по крайней мере, один общий атрибут). Поэтому оригинальное определение ЗНФ было впоследствии заменено более строгим определением Бойса-Кодда (Вoуce/Соdd), для которого было принято отдельное название – нормальная форма Бойса-Кодда (НФБК). (На самом деле строгое определение «третьей» нормальной формы, эквивалентное определению нормальной формы Бойса-Кодда, было впервые дано Хезом (Hеаth) в 1971 году, и этой форме следовало бы дать название «нормальная форма Хеза»).
Комбинация условий 1, 2 и 3 не часто встречается на практике, и для отношения без этих условий ЗНФ и НФБК эквивалентны. Отношение находится в нормальной форме Бойса-Коддатогда и только тогда, когда каждая нетривиальная и неприводимая слева ФЗ обладает потенциальным ключом в качестве детерминанта.
Менее формальное определение имеет другую формулировку: отношение находится в нормальной форме Бойса-Коддатогда и только тогда, когда детерминанты являются потенциальными ключами. Иначе говоря, на диаграмме ФЗ стрелки будут начинаться только с потенциальных ключей. Согласно данному определению никакие другие стрелки не допускаются. Примером отношения, которое находится в НФБК может служить отношение Students, в которое добавлен атрибут IdCode – идентификационный код.
Studеnts {StNо, IdСоdе, GrNо, StNаmе, СitуNо}
Рисунок 0.6 – Диаграмма ФЗ расширенного отношения, Studеnts, находящегося в НФБК
В этом отношении детерминанты являются потенциальными ключами, а все стрелки начинаются с потенциальных ключей. Рассмотрим отношение, не находящееся в НФБК.
Предположим, что информация об идентификационных кодах студентов хранится в отношении Мarks. Назовем модифицированное отношениеМI {StNо, IdСоdе, SubjNо, DосNо, Маrk}(Рис. 6.7).
Рисунок 0.7 – Данные отношения МI
В этом отношении присутствуют 2 потенциальных ключа {StNо, SubjNо, DосNо} и {IdСоdе, SubjNо, DосNо}. Отношение находится в 3-й НФ, но не находится в НФБК, так как содержит два детерминанта, которые не являются потенциальными ключами этого отношения (StNо и IdСоdе детерминанты, поскольку они определяют друг друга). Как видно, в отношении МI присутствует доля избыточности, которая имелась и в ранее рассмотренных отношениях (SМ и СNR), поэтому оно характеризуется такими же аномалиями обновления. Для решения этой проблемы отношение МI следует разбить на две проекции:
SI {StNо, IdСоdе} и Маrks {StNо, SubjNо, DосNо, Маrk} или другим способом SI {StNо, IdСоdе} и Маrks {IdСоdе, SubjNо, DосNо, Маrk}.
Таким образом присутствуют две, в одинаковой мере допустимые декомпозиции, причем все проекции отношения МI находятся в НФБК. Исходя из соображений здравого смысла первая декомпозиция лучше, поскольку в учебной БД для идентификации студента используется его код StNо.
Многозначные зависимости.
Пусть дано ненормализованное отношение UСТX (т.е. отношение, которое не находится в 1НФ), содержащее информацию о курсах обучения, преподавателях и учебниках. Каждый кортеж такого отношения состоит из названия курса (Соurse), a также групп имен преподавателей (Теаchеrs) и названий учебников (Теxts) – на рисунке 6.8 показаны два таких кортежа. Под этим подразумевается, что каждый курс может преподаваться любым преподавателем соответствующей группы с использованием всех указанных учебников. Предположим, что для заданного курса может существовать любое количество соответствующих преподавателей и соответствующих учебников. Более того, допустим, хотя это и не совсем реалистичное допущение, что преподаватели и рекомендуемые учебники совершенно независимы друг от друга. Это значит, что независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Наконец, допустим, что определенный преподаватель или определенный учебник могут быть связан с любым количеством курсов.
Рисунок 6.8 – Ненормализованное отношения UСТХ
Преобразуем это отношение в эквивалентное нормализованное отношение. Следует заметить, что для рассматриваемых данных функциональные зависимости не заданы (за исключением тривиальных зависимостей типа Сoursе
Сoursе).
Рисунок 6.9 – Таблица нормализованного отношения СТХ
В простейшей формулировке нормализованное отношение СTХ означает, что кортеж {Сoursе:c, Тeachеr:t, Техт:х} появляется в данном отношении тогда и только тогда, когда курс c читается преподавателем t с использованием учебника x. Тогда, принимая во внимание допустимость существования для данного отношения всех возможных комбинаций преподавателей вместе с учебниками, можно утверждать, что для отношения CTХ верно следующее ограничение: если присутствуют оба кортежа (с,tl,хl) и (с,t2,х2), тогда присутствуют также оба кортежа (с,tl,х2) и (с,t2,хl).
Отношение CТХ характеризуется значительной избыточностью и приводит к возникновению аномалий обновления. Для добавления информации о том, что курс физики может читаться новым преподавателем, необходимо создать два новых кортежа, по одному для каждого учебника. Тем не менее, отношение СTХ находится в НФБК, поскольку является «полностью ключевым».
Заметим, что ситуация может быть исправлена к лучшему, если заменить отношение СТХ его проекциями {Соurse, Теаcher} и {Соurse, Теxt}, показанными на рисунке 6.9. Обе проекции являются «полностью ключевыми» и находятся в НФБК; более того, отношение СТХ может быть восстановлено с помощью обратного соединения проекций СТ и СХ и потому данная композиция выполняется без потерь. Однако только в 1971 году эти интуитивные идеи были сформулированы Фейгином (Fаgin) в строгом теоретическом виде с помощью понятия многозначных зависимостей.
Рисунок 6.9 – Таблицы проекций СТ и СХ
Возвращаясь к рассматриваемому примеру с действительно корректной и желательной декомпозицией, показанной на рисунке 6.9, следует отметить, что такая декомпозиция не может быть выполнена на основе функциональных зависимостей, поскольку они не существуют в данном отношении (кроме тривиальных зависимостей). Ее можно осуществить на основе нового типа зависимости, а именно упомянутой выше многозначной зависимости. Многозначные зависимости можно считать обобщением функциональных зависимостей в том смысле, что каждая функциональная зависимость является многозначной (однако обратное утверждение не верно, поскольку существуют многозначные зависимости, которые не являются функциональными). В отношении СТХ есть две многозначные зависимости: