В этом разделе опускается упрощающее допущение о том, что каждое отношение имеет только один потенциальный ключ (а именно первичный ключ), и рассматривается более общий случай. Оригинальное определение Кодда для ЗНФ не совсем подходит для отношений с перечисленными ниже условиями.
1. Отношение имеет два (или более) потенциальных ключа.
2. Два потенциальных ключа являются сложными.
3. Они перекрываются (т.е. имеют, по крайней мере, один общий атрибут).
Поэтому оригинальное определение ЗНФ было впоследствии заменено более строгим определением Бойса-Кодда (Boyce/Codd), для которого было принято отдельное название – нормальная форма Бойса-Кодда, НФБК. (На самом деле строгое определение "третьей" нормальной формы, эквивалентное определению нормальной формы Бойса-Кодда, было впервые дано Хезом (Heath) в 1971 году, и этой форме следовало бы дать название "нормальная форма Хеза".)
Замечание. Комбинация условий 1, 2 и 3 не часто встречается на практике, и для отношения без этих условий ЗНФ и НФБК эквивалентны.
Отношение находится в нормальной форме Бойса-Кодда тогда и только тогда, когда каждая нетривиальная и неприводимая слева ФЗ обладает потенциальным ключом в качестве детерминанта.
Менее формальное определение имеет другую формулировку: отношение находится в нормальной форме Бойса-Кодда тогда и только тогда, когда детерминанты являются потенциальными ключами.
Иначе говоря, на диаграмме ФЗ стрелки будут начинаться только с потенциальных ключей. Согласно данному определению никакие другие стрелки не допускаются.
Примером отношения, которое находится в НФБК может служить отношение Students, в которое добавлен атрибут IdCode – идентификационный код.
Students {StNo, IdCode, GrNo, StName, CityNo}
рис. 6.6 Диаграмма ФЗ расширенного отношения, Students, находящегося в НФБК.
В этом отношении детерминанты являются потенциальными ключами, а все стрелки начинаются с потенциальных ключей. Рассмотрим отношение, не находящееся в НФБК.
Предположим, что информация об идентификационных кодах студентов хранится в отношении Marks. Назовем модифицированное отношение MI {StNo, IdCode, SubjNo, DocNo, Mark} (рис. 6.7).
| MI | ||||
| StNo | IdCode | SubjNo | DocNo | Mark |
| 1 | 2895764537 | 1 | 127 | 5 |
| 1 | 2895764537 | 5 | 128 | 4 |
| 2 | 3094769520 | 1 | 127 | 3 |
| 2 | 3094769520 | 5 | 128 | 3 |
| 3 | 2984267527 | 1 | 127 | 5 |
рис. 6.7 Данные отношения MI.
В этом отношении присутствуют 2 потенциальных ключа {StNo, SubjNo, DocNo} и {IdCode, SubjNo, DocNo}. Отношение находится в 3-й НФ, но не находится в НФБК, так как содержит два детерминанта, которые не являются потенциальными ключами этого отношения (StNo и IdCode детерминанты, поскольку они определяют друг друга). Как видно, в отношении MI присутствует доля избыточности, которая имелась и в ранее рассмотренных отношениях (SM и CNR), поэтому оно характеризуется такими же аномалиями обновления. Для решения этой проблемы отношение MI следует разбить на две проекции:
SI {StNo, IdCode} и Marks {StNo, SubjNo, DocNo, Mark}
или другим способом
SI {StNo, IdCode} и Marks {IdCode, SubjNo, DocNo, Mark}
Т.о. присутствуют две, в одинаковой мере допустимые декомпозиции, причем все проекции отношения MI находятся в НФБК. Исходя из соображений здравого смысла первая декомпозиция лучше, поскольку в учебной БД для идентификации студента используется его код StNo.
Литература:
1. Дейт К.Дж. Введение в системы баз данных. –Пер. с англ. –6-е изд. –К. Диалектика, 1998. Стр. 279–301.
ЛЕКЦИЯ 7. Проектирование БД. Нормальные формы отношений (продолжение)
7.1 Многозначные зависимости
7.2 Четвертая нормальная форма
7.3 Зависимости соединения
7.4 Пятая нормальная форма
7.5 Итоговая схема процедуры нормализации
Многозначные зависимости
Пусть дано ненормализованное отношение UCTX (т.е. отношение, которое не находится в 1НФ), содержащее информацию о курсах обучения, преподавателях и учебниках. Каждый кортеж такого отношения состоит из названия курса (Course), a также групп имен преподавателей (Teachers) и названий учебников (Texts) – на рис. 7.1 показаны два таких кортежа. Под этим подразумевается, что каждый курс может преподаваться любым преподавателем соответствующей группы с использованием всех указанных учебников. Предположим, что для заданного курса может существовать любое количество соответствующих преподавателей и соответствующих учебников. Более того, допустим, хотя это и не совсем реалистичное допущение, что преподаватели и рекомендуемые учебники совершенно независимы друг от друга. Это значит, что независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Наконец, допустим, что определенный преподаватель или определенный учебник могут быть связан с любым количеством курсов.
| UCTX | ||
| COURSE | TEACHERS | TEXTS |
| Физика | проф. Иванов проф. Петров | основы механики оптика |
| Математика | проф. Иванов | основы механики дискретная математика тригонометрия |
рис. 7.1 Ненормализованное отношения UCTX
Преобразуем это отношение в эквивалентное нормализованное отношение. Следует заметить, что для рассматриваемых данных функциональные зависимости не заданы (за исключением тривиальных зависимостей типа Course ® Course). Поэтому высказанные в предыдущей главе идеи не позволяют создать никакой формальной основы для выполнения декомпозиции данного отношения на проекции.
| CTX | ||
| COURSE | TEACHER | TEXT |
| Физика | проф. Иванов | основы механики |
| Физика | проф. Иванов | оптика |
| Физика | проф. Петров | основы механики |
| Физика | проф. Петров | оптика |
| Математика | проф. Иванов | основы механики |
| Математика | проф. Иванов | дискретная математика |
| Математика | проф. Иванов | тригонометрия |
рис. 7.2 Таблица нормализованного отношения CTX.
В простейшей формулировке нормализованное отношение CTX означает, что кортеж {Course:c, Teacher:t, Техт:x} появляется в данном отношении тогда и только тогда, когда курс c читается преподавателем t с использованием учебника x. Тогда, принимая во внимание допустимость существования для данного отношения всех возможных комбинаций преподавателей вместе с учебниками, можно утверждать, что для отношения CTX верно следующее ограничение: если присутствуют оба кортежа (c,tl,xl) и (c,t2,x2), тогда присутствуют также оба кортежа (c,tl,x2) и (c,t2,xl)
Очевидно, что отношение CTX характеризуется значительной избыточностью и приводит к возникновению аномалий обновления. Например, для добавления информации о том, что курс физики может читаться новым преподавателем, необходимо создать два новых кортежа, по одному для каждого учебника. Тем не менее, отношение CTX находится в НФБК, поскольку является "полностью ключевым".
Можно заметить, что ситуация может быть исправлена к лучшему, если заменить отношение СТХ его проекциями {Course, Teacher} и {Course, Text}, показанными на рис. 7.3. Обе проекции являются "полностью ключевыми" и находятся в НФБК; более того, отношение СТХ может быть восстановлено с помощью обратного соединения проекций СТ и СХ и потому данная композиция выполняется без потерь. Однако только в 1971 году эти интуитивные идеи были сформулированы Фейгином (Fagin) в строгом теоретическом виде с помощью понятия многозначных зависимостей.
| CT | СХ | |||
| COURSE | TEACHER |
| COURSE | TEXT |
| физика | проф. Иванов | физика | основы механики | |
| физика | проф. Петров | физика | оптика | |
| математика | проф. Иванов | математика | основы механики | |
| математика | дискретная математика | |||
| математика | тригонометрия | |||
рис. 7.3 Таблицы проекций СТ и СХ
Возвращаясь к рассматриваемому примеру с действительно корректной и желательной декомпозицией, показанной на рис. 7.3, следует, однако, отметить, что такая декомпозиция не может быть выполнена на основе функциональных зависимостей, поскольку они не существуют в данном отношении (кроме тривиальных зависимостей). Однако ее можно осуществить на основе нового типа зависимости, а именно упомянутой выше многозначной зависимости. Многозначные зависимости можно считать обобщением функциональных зависимостей в том смысле, что каждая функциональная зависимость является многозначной (однако обратное утверждение не верно, поскольку существуют многозначные зависимости, которые не являются функциональными). В отношении СТХ есть две многозначные зависимости:
Course—>>Teacher
Course—>>Text
Обратите внимание на двойную стрелку, которая в многозначной зависимости A—>>B означает, что "B многозначно зависит от A" или "A многозначно определяет B".
Пусть A, B и C являются произвольными подмножествами множества атрибутов отношения R. Тогда B многозначно зависит от A, что символически выражается записью
А—>>В
тогда и только тогда, когда множество значений B, соответствующее заданной паре (значение A, значение C) отношения R, зависит только от A, но не зависит от C.
Для данного отношения R{A, B, C} многозначная зависимость A—>>B выполняется тогда и только тогда, когда также выполняется многозначная зависимость A —>> C. Таким образом, многозначные зависимости всегда образуют связанные пары и потому их обычно представляют вместе в символическом виде:
А—>>В|С.
Для рассматриваемого примера такая запись будет иметь следующий вид:
Course—>>Teacher|Text
Возвращаясь к исходной задаче с отношением СТХ, теперь можно отметить, что описанная ранее проблема с отношением типа СТХ возникает из-за того, что оно содержит многозначные зависимости, которые не являются функциональными. (Следует отметить совсем неочевидный факт, что именно наличие таких МЗ требует вставлять два кортежа, когда необходимо добавить данные еще об одном преподавателе физики.) Проекции СТ и СХ не содержат многозначных зависимостей, а потому они действительно представляют собой некоторое усовершенствование исходной структуры. Поэтому было бы желательно заменить отношение СТХ двумя этими проекциями. Это можно сделать, исходя из теоремы Фейгина, которая приведена ниже.
Теорема Фейгина (эта теорема является более строгой версией теоремы Хеза). Пусть А, В и С являются множествами атрибутов отношения R{A, В, С}. Отношение R будет равно соединению его проекций {А, В} и {А, С} тогда и только тогда, когда для отношения R выполняется многозначная зависимость А—>>В|С.
Четвертая нормальная форма
Отношение R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда существуют такие подмножества А и В атрибутов отношения R, что выполняется (нетривиальная) многозначная зависимость А —>> В. Тогда все атрибуты отношения R также функционально зависят от атрибута A.
Зависимости соединения
До сих пор предполагалось, что единственной операцией в процессе декомпозиции является замена данного отношения (при декомпозиции без потерь) двумя его проекциями. Это допущение успешно выполнялось вплоть до определения 4НФ. Однако существуют отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или более проекции.
На рисунке представлен пример конкретного набора данных, соответствующих некоторому моменту времени. Однако, если данное отношение удовлетворяет некоторому не зависящему от времени ограничению, то 3-декомпозируемость отношения TSG может быть более фундаментальным и не зависящим от времени свойством, т.е. свойством, которое удовлетворяется для всех допустимых значений данного отношения. Для того чтобы понять, каким должно быть такое отношение, прежде всего отметим, что утверждение "отношение TSG равно соединению трех проекций TS, SG и TG" эквивалентно следующему утверждению:
Если пара (t1,s1) находится в отношении TS и пара (s1,g1) находится в отношении SG и пара (t1,g1) находится в отношении TG то тройка (t1,s1,g1) находится в отношении TSG.
| TSG | ||
| TEACHER | SUBJECT | GROUP |
| Иванов | Математика | А-98-51 |
| Иванов | Физика | Б-00-51 |
| Петров | Математика | А-99-51 |
| Петров | Физика | А-98-51 |
| TS |
| SG |
| TG | ||||||||||
| TEACHER | SUBJECT | SUBJECT | GROUP | TEACHER | GROUP | |||||||||
| Иванов | Физика | Математика | А-99-51 | Иванов | А-98-51 | |||||||||
| Иванов | Математика | Математика | А-98-51 | Иванов | Б-00-51 | |||||||||
| Петров | Физика | Физика | А-98-51 | Петров | А-99-51 | |||||||||
| Петров | Математика | Физика | Б-00-51 | Петров | А-98-51 | |||||||||
| ëСоединение по Subjectû ¯ |
|
| ||||||||||||
|
| TEACHER | SUBJECT | GROUP |
|
| |||||||||
| Иванов | Физика | А-98-51 |
|
| ||||||||||
| Иванов | Физика | Б-00-51 |
|
| ||||||||||
| Иванов | Математика | А-99-51 |
|
| ||||||||||
| Иванов | Математика | А-98-51 |
|
| ||||||||||
| Петров | Физика | А-98-51 |
|
| ||||||||||
| Петров | Физика | Б-00-51 |
|
| ||||||||||
| Петров | Математика | А-99-51 |
|
| ||||||||||
| Петров | Математика | А-98-51 |
|
| ||||||||||
|
| ëСоединение по комбинации Teacher и Groupû ¯ |
| ||||||||||||
|
|
| Исходное TSG |
|
| ||||||||||
рис. 7.4 Отношение TSG является соединением трех бинарных проекций.
Исходя из этих заключений можно сказать, что пара (t1,s1) присутствует в отношении TS тогда и только тогда, когда тройка (t1, s1, g2) присутствует в отношении TSG для некоторого значения g2. Тогда приведенное выше утверждение можно переписать в виде ограничения, накладываемого на отношение SPJ:
Если (t1,s1,g2), (t2,s1,g1), (t1,s2,g1) находятся в отношении TSG то (t1,s1,g1) также находится в отношении TSG.
Если это утверждение выполняется всегда, т.е. для всех допустимых значений отношения TSG, то тем самым будет получено независящее от времени (хотя и несколько странное) ограничение для данного отношения. Обратите внимание на циклическую структуру этого ограничения. Отношение будет n-декомпозируемым для n>2 тогда и только тогда, когда оно удовлетворяет некоторому циклическому ограничению.
Циклическое ограничение с практической точки зрения обозначает, что, например, если:
1. Петров преподает математику;
2. математика преподается в А-98-51;
3. Петров преподает в А-98-51
то:
4. Петров преподает математику в А-98-51.
Обратите внимание, что из взятых вместе условий (1), (2) и (3) не следует (4).
Пусть R является отношением, а А, В,..., Z— произвольными подмножествами множества атрибутов отношения R. Отношение R удовлетворяет зависимости соединения
* (A, B, ..., Z)
тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов А, В, ..., Z.
Отсюда ясно, что отношение TSG с зависимостью соединения *(TS, SG, TG) может быть 3-декомпозируемым. Однако следует ли выполнять такую декомпозицию? По всей видимости, да, так как отношение TSG характеризуется многочисленными аномалиями обновления, которые можно устранить с помощью 3-декомпозиции. Пример был приведен при определении циклического ограничения, из-за наличия которого, в отношении TSG должен присутствовать следующий кортеж (рис. 7.5)
| TEACHER | SUBJECT | GROUP |
| Петров | Математика | А-98-51 |
рис. 7.5 Дополнительный кортеж.
Также теорема Фейгина может быть сформулирована следующим образом: отношение R{A, В, С} удовлетворяет зависимости соединения *(АВ, АС) тогда и только тогда, когда оно удовлетворяет многозначной зависимости А —>> В | С.
Эту теорему можно использовать в качестве определения многозначной зависимости, отсюда следует, что многозначная зависимость является частным случаем зависимости соединения. Более того, из определения зависимости соединения следует, что из всех возможных форм это наиболее общая форма зависимости.
Возвращаясь к рассматриваемому примеру, можно обнаружить следующую проблему: отношение TSG содержит зависимость соединения, которая не является ни многозначной, ни функциональной зависимостью. Можно также заметить, что рекомендуется декомпозировать такое отношение на меньшие компоненты, а именно на проекции, заданные зависимостью соединения. Такой процесс декомпозиции может повторяться до тех пор, пока все результирующие отношения не будут находиться в пятой нормальной форме.
Пятая нормальная форма
Отношение R находится в пятой нормальной форме (5НФ), которая также называется проекционно-соединительной нормальной формой, тогда и только тогда, когда каждая зависимость соединения в отношении R подразумевается потенциальными ключами отношения R.
Отношение TSG не находится в 5НФ. Оно удовлетворяет некоторой зависимости соединения, а именно ЗД-ограничению, которое, конечно, не подразумевается его единственным потенциальным ключом. Наоборот, после 3-декомпозиции проекции TS, SG и GT находятся в 5НФ, поскольку для них вовсе нет зависимостей соединения.
Дата: 2019-07-30, просмотров: 257.
