нормальные формы в бд. Лаб.3 Нормальные формы. Нормализация реляционной модели
 Скачать 0.71 Mb.
|
|
5 . НОРМАЛИЗАЦИЯ РЕЛЯЦИОННОЙ МОДЕЛИ 5.1. Функциональные зависимости Функциональные зависимости– это особый вид ограничений це- лостности, а потому они предоставляют проектировщику способ отразить семантические зависимости между данными. Распознавание функцио- нальных зависимостей представляет собой часть процесса выяснения смысла тех или иных данных. Например, тот факт, что поставщик прожи- вает точно в одном городе можно отразить с помощью функциональной зависимости Номер поставщика Адрес поставщика. По сути, функциональная зависимость является связью типа «мно- гие-к-одному» между множествами атрибутов внутри отношения. Дадим определение функциональной зависимости. Пусть R является отношением, а X и Y – произвольные подмноже- ства множества атрибутов отношения R. Тогда Y функционально зави- симо от X (или X функционально определяет Y) Y X тогда и только тогда, когда каждое значение множества X отношения R связано в точно- сти с одним значением множества Y отношения R. Иначе говоря, если два кортежа отношения R совпадают по значению X, они совпадают и по значению Y. Например, отношение «Поставщик» удовлетворяет требованиям нескольких функциональных зависимостей: {№ поставщика} {Имя поставщика} {№ поставщика} {Статус поставщика} {№ поставщика} {Адрес поставщика} {№ поставщика} {Имя поставщика, Статус поставщика, Адрес по- ставщика} {Имя поставщика} {Адрес поставщика} {Имя поставщика} {Статус поставщика} {Имя поставщика} {Адрес поставщика, Статус поставщика } Левая и правая части символической записи функциональной за- висимости называются детерминантом и зависимой частью соответ- ственно. Как следует из определения, детерминант и зависимая часть яв- ляются множествами атрибутов. Если множество содержит один атрибут, оно называется одноэлементным множеством и тогда фигурные скобки могут быть опущены: № поставщика Имя поставщика Утверждение, что данная функциональная зависимость выполня- ется всегда, для всех возможных значений отношения, является ограниче- нием целостности для отношения, а это значит, что при этом накладыва- ются определенные ограничения на все его допустимые значения. Даже если ограничиться рассмотрением функциональных зависимостей, име- ющих место в любой момент, полный набор функциональных зависимо- 2 стей, выполняющихся для всех допустимых значений заданной перемен- ной-отношения, может быть очень большим. Необходимо минимизиро- вать множество функциональных зависимостей до некоторых пределов. Задача поиска такого подходящего множества представляет практический интерес. Очевидным способом сокращения существующего набора функ- циональных зависимостей является исключение из него тривиальных зависимостей, т.е. зависимостей, которые не могут не выполняться. Функциональная зависимость является тривиальной тогда и только то- гда, когда правая часть ее символической записи является подмноже- ством левой части. Одни функциональные зависимости подразумевают другие зави- симости. Для данного множества зависимостей S замыканием S+ называ- ется множество всех функциональных зависимостей, подразумеваемых зависимостями множества S. Полную и исчерпывающую основу для вы- числения замыкания S+ для заданного множества S обеспечивают прави- ла логического вывода (аксиомы) Армстронга. Пусть заданы A,B,C – произвольные подмножества множества ат- рибутов отношения R. Тогда правила вывода Армстронга определяются следующим образом: 1. Правило рефлексивности: если B является подмножеством множества A, то A B. 2. Правило дополнения: если A B, то AC BC. (Здесь запись AC означает объединение множеств A и C). 3. Правило транзитивности: если A B и B C, то A C. Каждое из этих правил можно доказать непосредственно на основе определения функциональной зависимости. Из приведенных правил можно вывести несколько дополнительных правил, полезных для практи- ческого вычисления замыкания S+. 4. Правило самоопределения: A A. 5. Правило декомпозиции: если A BC, то A B и A C. 6. Правило объединения: если A B и A C, то A BC. 7. Правило композиции: если A B и C D, то AС BD. Кроме того, Дарвен доказал правило, называемое всеобщей тео- ремой объединения. 8. Если A B и C D, то A (С-B) BD. Приведенные правила являются полными в том смысле, что для за- данного множества функциональных зависимостей S минимальный набор функциональных зависимостей, которые подразумевают все зависимости из множества S, может выведен из функциональных зависимостей мно- жества S на основе этих правил. Они также являются исчерпывающими, поскольку никакие дополнительные функциональные зависимости с их 3 помощью не могут быть выведены. Иначе говоря, все эти правила могут быть использованы для получения замыкания S+. Пусть задано отношение R и его некоторое множество функцио- нальных зависимостей. Удобнее всего представлять это множество функ- циональных зависимостей в виде диаграммы функциональных зависимо- стей. Например диаграмма функциональных зависимостей отношения «Поставщик» представлена на Рис.11. Рис.11. Диаграмма функциональных зависимостей отношения «Постав- щик» Каждая стрелка начинается с детерминанта, а ведет к атрибутам зависимой части отношения. 5.2. Суть процесса нормализации Реляционная схема отношений содержит как структурную, так и семантическую информацию. Структурная информация связана с объяв- лением отношения, а семантическая выражается множеством известных функциональных зависимостей между атрибутами отношений. Однако некоторые функциональные зависимости могут быть нежелательными из- за побочных эффектов или аномалий, которые они вызывают при моди- фикации базы данных. В связи с этим возникает вопрос о корректности представленной схемы отношений. Корректной считается схема отношений, в которой отсутствуют нежелательные функциональные зависимости. В противном случае при- ходится прибегать к процедуре, называемой декомпозицией (разложени- ем), при которой данное множество отношений заменяется другим мно- жеством отношений, являющихся проекциями первых. Цель этой проце- дуры – устранение нежелательных функциональных зависимостей, а, значит, аномалий операций обновления данных. В этом заключается суть процесса нормализации. Иначе говоря, нормализация – это пошаговый обратимый процесс замены данной схемы (совокупности) отношений другой схемой, в которой эти отношения имеют более простую, регуляр- ную форму. В теории нормальных форм определяются различные нор- мальные формы, которые ограничивают типы допустимых функциональ- ных зависимостей. № поставщика Имя поставщика адрес поставщика Статус поставщика 4 5.3. Нормальные формы Нормализация – это формальный метод анализа отношений на ос- нове их первичного ключа (или потенциальных ключей) и существующих функциональных зависимостей. Нормализация включает ряд правил, ко- торые могут использоваться для проверки отдельных отношений таким образом, чтобы вся база данных могла быть нормализована до желаемой степени. Если некоторое требование не удовлетворяется, то нарушающее данное требование отношение должно быть декомпозировано на отноше- ния, каждое из которых (в отдельности) удовлетворяет всем требованиям нормализации. Нормализация осуществляется в несколько последовательно вы- полняющихся этапов, каждый из которых соответствует некоторой нор- мальной форме, обладающей известными свойствами. В ходе нормализа- ции структура отношений становится все более строгой и менее уязвимой по отношению к аномалиям обновления. Схема взаимосвязей между от- дельными нормальными формами приведена на Рис. 10. Рис. 10. Уровни нормализации Из схемы следует, что все нормализованные отношения находятся в 1НФ, некоторые из них также находятся в 2НФ, а некоторые отношения в 2НФ также находятся в 3НФ и т.д. Первые три нормальные формы (1НФ, 2НФ, 3НФ) были предло- жены Коддом (Codd), в определении последующих принимали также уча- стие Бойс (Boyce) (НФБК) и Фейгин (Fagin) (4НФ, 5НФ). 5.3.1. Первая нормальная форма (1НФ) 1НФ 2НФ 3НФ НФБК 4НФ 5НФ Высшие нормальные формы 5 Отношение находится в 1НФ, если значения всех его атрибутов простые, атомарные, т.е. не являются множеством или повторяющейся группой. При проектировании осуществляется преобразования данных из формата источника в формат ненормализованной таблицы. Ненормали- зованной таблицей является таблица, содержащая повторяющиеся груп- пы данных. Повторяющейся группой называется группа, состоящая из одного или более атрибутов таблицы, в которой возможно наличие не- скольких значений для единственного значения ключа. Например, ненор- мализованной является таблица Табл.4. № рейса Пункт от- правления Пункт назначе- ния День недели Время вылета А-45 Краснодар Москва понедельник 8-30 среда 8-30 пятница 9-00 А-67 Краснодар Санкт-Петербург суббота 17-50 воскресенье 17-50 Табл.4. Ненормализованная таблица «Рейсы» Существует простой способ приведения ненормализованной таб- лицы к 1НФ путем «размножения» значений атрибутов, т.е. ввода данных в каждую строку и каждый столбец отношения. В результате в получен- ное отношение вносится некоторая избыточность данных, которая в ходе дальнейшей нормализации будет устранена. Результат приведения отно- шения «Рейсы» к 1НФ отражен в Табл.5. № рейса Пункт от- правления Пункт назначе- ния День недели Время вылета А-45 Краснодар Москва понедельник 8-30 А-45 Краснодар Москва среда 8-30 А-45 Краснодар Москва пятница 9-00 А-67 Краснодар Санкт-Петербург суббота 17-50 А-67 Краснодар Санкт-Петербург воскресенье 17-50 Табл.5. Нормализованная таблица «Рейсы» (1НФ) 5.3.2. Вторая нормальная форма (2НФ) Вторая нормальная форма (2НФ) основана на понятии полной функциональной зависимости. В некотором отношении множество атрибутов В называется пол- ностью функционально зависимым от множества атрибутов А, если множество В функционально зависит от полного значения множества А и не зависит ни от какого подмножества значений атрибутов А. Отношение является отношением во 2НФ, если оно находится в первой нормальной форме и каждый неключевой атрибут функциональ- но полно зависит от первичного ключа. 6 Рассмотрим пример отношения «Поставки», приведенного в Табл.6. № поставщика Товар Цена П1 лимоны 35 П1 апельсины 22 П2 лимоны 35 П2 мандарины 27 Табл. 6. Отношение «Поставки» Известно, что поставщики могут поставлять разные товары, при этом один и тот же товар могут поставлять разные поставщики. Цена на один и тот же товар фиксирована. Семантические ограничения можно от- разить при помощи функциональных зависимостей. Представим их диа- граммой функциональных зависимостей, приведенной на Рис. 11. Рис.11. Диаграмма функциональных зависимостей отношения «Постав- ки» В этом отношении первичным ключом является комбинация атри- бутов «№ поставщика», «Товар». Очевидно, что в отношении «Поставки» имеет место неполная функциональная зависимость атрибута «Цена» от первичного ключа, поскольку атрибут «Цена» зависит только от атрибута «Товар». В отношении «Поставки» имеют место аномалии, выявляемые при выполнении операций манипулирования данными: добавления – при добавлении данных о поставке некоторым постав- щиком товара, необходимо указать фиксированную цену товара; обновления – если меняется цена на некий товар, необходимо про- смотреть все кортежи отношения, поскольку один и тот же товар мо- жет поставляться многими поставщиками; удаления – при удалении кортежа с некоторой поставкой можно по- терять информацию о цене товара, если этот товар поставлялся един- ственным поставщиком. Очевидной причиной аномалий в отношении является неполная функциональная зависимость атрибута «Цена» от первичного ключа. Чтобы привести отношение «Поставки» ко 2НФ необходима декомпози- ция на два отношения, приведенные на Рис 12. Функциональные зависи- мости, описанные диаграммой (Рис. 11), очевидно, сохранены. Т.е. де- композиция выполнена без потерь. Каждое полученное отношение нахо- дится во 2НФ, поскольку первичные ключи в отношении – простые. № поставщика Товар Цена 7 Поставки товаров Цена товара № поставщика Товар Товар Цена П1 лимоны лимоны 35 П1 апельсины апельсины 22 П2 лимоны мандарины 27 П2 мандарины Рис.12. Отношения «Поставки товаров» и «Цена товара» 5.3.3. Третья нормальная форма (3НФ) Третья нормальная форма (3НФ) основана на понятии транзитив- ной функциональной зависимости. Если для атрибутов A, B и C некоторого отношения существуют зависимости вида A B и B C, то говорят, что атрибут C транзитив- но зависит от атрибута A через атрибут B (при этом A функционально не зависит ни от B, ни от C). Отношение находится в 3НФ, если оно находится во 2НФ и каж- дый неключевой атрибут нетранзитивно зависит от первичного ключа. Рассмотрим пример приведения отношения «Хранение товаров» (Табл. 7) к 3НФ. Фирма Склад Объем Сонар-система С1 100000 Пионер С2 20000 Цель С1 100000 Эльдорадо С2 20000 Табл.7. Отношение «Хранение товаров» Известно, что каждая фирма может хранить товары только на од- ном складе, но на одном и том же складе могут храниться товары, при- надлежащие нескольким фирмам. Естественно, каждый склад имеет определенный объем (м 3 ). Семантические ограничения описанного при- мера можно отразить при помощи функциональных зависимостей. Пред- ставим их диаграммой функциональных зависимостей, приведенной на Рис. 13. Рис.13. Диаграмма функциональных зависимостей отношения «Хранение товаров» Фирма Склад Объем 8 Атрибут «Фирма» является первичным ключом отношения «Хра- нение товаров». В данном отношении имеется транзитивная зависимость атрибута «Объем» от атрибута «Склад». В связи с этим имеют место ано- малии, выявляемые при выполнении операций манипулирования данны- ми: добавления – при добавлении данных о хранении некоторой фирмой товаров на складе требуется также указать фиксированный объем данного склада; обновления – если меняется объем некоторого склада (например, в ре- зультате реконструкции), необходимо просмотреть все кортежи от- ношения, поскольку на одном и том же складе могут храниться това- ры многих фирм; удаления – в случае, когда некоторая фирма перестала хранить това- ры на складе, вместе с удалением соответствующего кортежа можно потерять информацию об объеме склада, если на данном складе хра- нились товары только этой фирмы. Причиной аномалий в отношении «Хранение товаров» является транзитивная зависимость атрибута «Объем» от не ключевого атрибута «Склад». Чтобы привести отношение «Хранение товаров» к 3НФ необхо- дима декомпозиция на два отношения, приведенные на Рис 14. Функцио- нальные зависимости, описанные диаграммой (Рис. 13), очевидно, сохра- нены. Т.е. декомпозиция выполнена без потерь. Каждое полученное от- ношение находится в 3НФ, поскольку в каждом отношении имеется толь- ко два атрибута, один из которых – первичный ключ. Склады Объемы складов Фирма Склад Склад Объем Сонар-система С1 С1 100000 Пионер С2 С2 20000 Цель С1 Эльдорадо С2 Рис.14. Отношения «Склады» и «Объемы складов» 5.3.4. Нормальная форма Бойса-Кодда (НФБК) Нормальная форма Бойса-Кодда (НФБК) учитывает функциональ- ные зависимости, в которых участвуют все потенциальные ключи отно- шения, а не только его первичный ключ. Для отношения с единственным потенциальным ключом его 3НФ и НФБК являются эквивалентными. Отношение находится в НФБК тогда и только тогда, когда каж- дый его детерминант является потенциальным ключом. Нарушения требований НФБК происходят крайне редко, посколь- ку это возможно в следующих случаях: имеются два или более составных потенциальных ключа; 9 эти потенциальные ключи перекрываются, т.е. ими совместно ис- пользуется, по крайней мере, один общий атрибут. Рассмотрим пример приведения отношения «Проекты» (Табл. 8) к НФБК. Наименование проекта № детали № поставщика Сонар-система С1 10 Сонар-система С2 20 Пионер С2 30 Пионер С1 40 Эльдорадо С2 50 Табл.8. Отношение «Проекты» Известно, что в проекте используется несколько деталей, но каж- дая деталь проекта при этом поставляется только одним поставщиком. Каждый поставщик обслуживает единственный проект, но проекты могут обеспечиваться несколькими поставщиками (разных деталей). Семанти- ческие ограничения отношения можно отразить при помощи функцио- нальных зависимостей. Представим их диаграммой функциональных за- висимостей, приведенной на Рис. 15. Рис.15. Диаграмма функциональных зависимостей отношения «Проекты» В качестве первичного ключа отношения «Проекты» принята ком- бинация атрибутов «Наименование проекта», «№ детали». Данное отно- шение находится в 1НФ, 2НФ, 3НФ и не находится в НФБК. В связи с этим имеют место аномалии, выявляемые при выполнении операций ма- нипулирования данными, например аномалии: добавления – при добавлении данных о некотором поставщике необ- ходимо создавать фиктивный проект, а также деталь для этого по- ставщика изменения – при изменения наименования проекта в некотором кор- теже, также необходимо просмотреть все отношение и поменять наименование проекта для всех используемых деталей. удаления – при удалении информация о некотором поставщике, уда- ляется также информация о деталях, которые он поставлял. Причиной аномалий в отношении «Проекты» является то, что не все его детерминанты являются потенциальными ключами (это относится № детали Наименование проекта № поставщика 10 к атрибуту «№ поставщика». Для приведения отношения «Проекты» к НФБК необходима декомпозиция на два отношения, приведенные на Рис 16. Функциональные зависимости, описанные диаграммой (Рис. 15), оче- видно, сохранены. Т.е. декомпозиция выполнена без потерь. Каждое по- лученное отношение находится в НФБК, поскольку в каждом отношении имеется только два атрибута, один из которых – первичный ключ. Поставщики-детали Проекты –поставщики № поставщика № детали № поставщика Наименование Проекта 10 С1 10 Сонар-система 20 С2 20 Сонар-система 30 С2 30 Пионер 40 С1 40 Пионер 50 С2 50 Эльдарадо Рис.16. Отношения «Поставщики-детали» и «Проекты-поставщики» 5.3.5. Четвертая нормальная форма (4НФ) Многозначные зависимости (multi-valued dependency) возникают, например, когда необходимо привести к первой нормальной форме отно- шение, с независимыми многозначными атрибутами. Пусть имеется два таких атрибута Y и Z. Тогда для получения 1НФ необходимо для каждого набора значений остальных атрибутов X повторить эту строку для каждо- го сочетания атомарного значения Y с каждым атомарным значением Z, что называется выравниванием таблицы. Образуется многозначная зависимость в которой: • каждому значению X соответствует набор значений Y; • каждому значению X соответствует набор значений Z; • значения атрибутов Y и Z не зависят один от другого. Многозначную зависимость принято обозначать X→→Y|Z, хотя можно было бы указать наличие двух существующих одновременно обычных функциональных зависимостей X→Y и X→Z. Иногда обозна- чают многозначную зависимость X→→Y или X→→Z. Определение 1 MV-зависимость X→→Y называется тривиальной если 𝑋 𝑌, ли- бо 𝑋 ∪ 𝑌 = {𝑋, 𝑌, 𝑍}. Определение 2: Пусть r – отношение со схемой R(S), а X,Y,Z - непересекающиеся множества его атрибутов, такие, что 𝑋 ∪ 𝑌 ∪ 𝑍 = 𝑆. Атрибуты Y и Z мно- гозначно зависят от X (обозначение X→→Y|Z) если из того, что в отно- шении r содержатся кортежи r 1 = (x, y, z 1 ) и r 2 = (x, y 1 , z) следует, что в отношении r содержится также кортеж r 3 = (x, y, z). Замечание 1: По симметрии определения в r содержится и кортеж r 4 = (x, y 1 , z 1 ). Атрибуты Y и Z как бы симметричны по отношению к X. 11 Замечание 2: При наличии MV-зависимости кортежи обязаны вставляться и удаляться одновременно целыми наборами. Определение 3. Переменная отношения R находится в четвёртой нормальной фор- ме, если она находится в НФБК и все нетривиальные многозначные зави- симости фактически являются функциональными зависимостями от её потенциальных ключей. Эквивалентная формулировка определения: Переменная отношения R находится в четвёртой нормальной фор- ме тогда и только тогда, когда в случае существования подмножеств A и B атрибутов этой переменной отношения R, для которых выполняется нетривиальная многозначная зависимость A →→ B, все атрибуты пере- менной отношения R также функционально зависят от А. Пример: Предположим, что рестораны производят разные виды пиццы, а службы доставки ресторанов работают только в определенных районах города. Составной первичный ключ соответствующей переменной отно- шения включает три атрибута: {Ресторан, Вид пиццы, Район доставки}. Такая переменная отношения не соответствует 4НФ, так как суще- ствует следующая многозначная зависимость: {Ресторан} →→ {Вид пиццы} {Ресторан} →→ {Район доставки} То есть, например, при добавлении нового вида пиццы придется внести по одному новому кортежу для каждого района доставки. Воз- можна логическая аномалия, при которой определенному виду пиццы бу- дут соответствовать лишь некоторые районы доставки из обслуживаемых рестораном районов. Для предотвращения аномалии нужно декомпозировать отноше- ние, разместив независимые факты в разных отношениях. В данном при- мере следует выполнить декомпозицию на {Ресторан, Вид пиццы} и {Ре- сторан, Район доставки}. Однако, если к исходной переменной отношения добавить атри- бут, функционально зависящий от потенциального ключа, например цену с учётом стоимости доставки ({Ресторан, Вид пиццы, Район доставки} → Цена), то полученное отношение будет находиться в 4НФ и его уже нель- зя подвергнуть декомпозиции без потерь (смотри ниже). Указанные выше многозначные зависимости в данном случае называются внедрёнными зависимостями. 5.3.6. Пятая нормальная форма (5НФ) Декомпозиция без потерь 12 Декомпозицией отношения 𝑅 называется замена 𝑅 на совокуп- ность отношений {𝑅 1 , 𝑅 2 , … , 𝑅 𝑛 } такую, что каждое из них есть проекция 𝑅, и каждый атрибут R входит хотя бы в одну из проекций декомпозиции. Например, для отношения 𝑅 с атрибутами {𝑎, 𝑏, 𝑐} существуют следующие основные варианты декомпозиции: {𝑎}, {𝑏}, {𝑐} {𝑎}, {𝑏, 𝑐} {𝑎, 𝑏}, {𝑐} {𝑏}, {𝑎, 𝑐} {𝑎, 𝑏}, {𝑏, 𝑐} {𝑎, 𝑏}, {𝑎, 𝑐} {𝑏, 𝑐}, {𝑎, 𝑐} {𝑎, 𝑏}, {𝑏, 𝑐}, {𝑎, 𝑐} Рассмотрим теперь отношение 𝑅′, которое получается в результате операции естественного соединения, применённой к отношениям, полу- ченным в результате декомпозиции 𝑅. Декомпозиция называется декомпозицией без потерь, если 𝑅′ в точности совпадает с 𝑅. Неформально говоря, при декомпозиции без потерь отношение «разделяется» на отношения-проекции таким образом, что из полученных проекций возможна «сборка» исходного отношения с помощью операции естественного соединения. Далеко не всякая декомпозиция является декомпозицией без по- терь. Проиллюстрируем это на примере отношения 𝑅 с атрибутами {𝑎, 𝑏, 𝑐}, приведённом выше. Пусть отношение 𝑅 имеет вид: 𝑅 a b c 𝑎 1 𝑏 1 𝑐 1 𝑎 1 𝑏 2 𝑐 2 𝑎 2 𝑏 3 𝑐 1 𝑎 2 𝑏 2 𝑐 2 Декомпозиция 𝑅 1 = {𝑎, 𝑐}, 𝑅 2 = {𝑏, 𝑐} имеет вид: 𝑅 1 𝑅 2 a b 𝑎 1 𝑐 1 𝑎 1 𝑐 2 𝑎 2 𝑐 1 𝑎 2 𝑐 2 Результат операции соединения этих отношений: 𝑅 ′ = 𝑗𝑜𝑖𝑛 =𝑐 (𝑅 1 , 𝑅 2 ) a b c 𝑎 1 𝑏 1 𝑐 1 b c 𝑏 1 𝑐 1 𝑏 2 𝑐 2 𝑏 3 𝑐 1 13 𝑎 1 𝑏 2 𝑐 2 𝑎 2 𝑏 3 𝑐 1 𝑎 2 𝑏 2 𝑐 2 𝑎 1 𝑏 3 𝑐 1 𝑎 2 𝑏 1 𝑐 1 Очевидно, что 𝑅′ не совпадает с 𝑅, а значит такая декомпозиция не является декомпозицией без потерь. Рассмотрим теперь декомпозицию 𝑅 1 = {𝑎, 𝑏}, 𝑅 2 = {𝑏, 𝑐}: 𝑅 1 𝑅 2 a b 𝑎 1 𝑏 1 𝑎 1 𝑏 2 𝑎 2 𝑏 3 𝑎 2 𝑏 2 Такая декомпозиция является декомпозицией без потерь, в чём чи- татель может убедиться самостоятельно. В некоторых случаях отношение вовсе невозможно декомпозиро- вать без потерь. Существуют также примеры отношений, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или большее количе- ство проекций. Зависимость соединения. Пусть R — переменная отношения, а A, B, …, Z — некоторые подмножества множества её атрибутов. Если декомпозиция любого допустимого значения R на отноше- ния, состоящие из множеств атрибутов A, B, …, Z, является декомпози- цией без потерь, говорят, что переменная отношения R удовлетворяет за- висимости соединения *{А, В, . . . , Z}. Иными словами, переменная отношения R удовлетворяет зависи- мости соединения *{А, В, . . . , Z} тогда и только тогда, когда любое до- пустимое значение переменной отношения R эквивалентно соединению её проекций по подмножествам A, B, …, Z множества атрибутов. Подобно тому, как функциональная зависимость есть частный случай многозначной зависимости, многозначная зависимость является частным случаем зависимости соединения. Зависимость соединения явля- ется предельным обобщением понятий многозначной и функциональной зависимости, то есть это наиболее общая форма зависимости между атри- бутами отношения. b c 𝑏 1 𝑐 1 𝑏 2 𝑐 2 𝑏 3 𝑐 1 14 Важно понимать, что зависимость соединения определяется не для конкретного значения переменной отношения в тот или иной момент времени, а по всем возможным значениям. Поэтому понятие зависимости соединения определено не для отношения (конкретного значения), а для переменной отношения. Зависимость соединения определяется не меха- нически по текущим значениям, а следует из внешнего знания о природе и закономерностях данных, которые могут находиться в переменной от- ношения. То же самое относится к многозначной и функциональной зави- симостям. Зависимость соединения *{A, B,…, Z} является тривиальной тогда и только тогда, когда по крайней мере одно из подмножеств A, B, …, Z является множеством всех атрибутов отношения (включает все атрибу- ты). В противном случае зависимость соединения является нетривиаль- ной. Формулировка определения Отношение находится в пятой нормальной форме (иначе — в про- екционно-соединительной нормальной форме) тогда и только тогда, когда каждая нетривиальная зависимость соединения в нём определяется по- тенциальным ключом (ключами) этого отношения. Зависимость соединения *{A, B,…, Z} определяется потенциаль- ным ключом (ключами) тогда и только тогда, когда каждое из подмно- жеств A, B, …, Z множества атрибутов является суперключом отношения. Условие «каждое из подмножеств A, B,…, Z множества атрибутов является суперключом отношения» можно эквивалентно сформулировать так: «каждое из подмножеств A, B, …, Z множества атрибутов включает некоторый потенциальный ключ отношения». Свойства 5НФ Любое отношение в 5НФ автоматически находится также в 4НФ и, следовательно, во всех других нормальных формах. 5НФ является окон- чательной нормальной формой (по крайней мере в контексте операций проекции и соединения). Рональд Фейгин в 1979 г. показал, что любая переменная отноше- ния может быть подвергнута декомпозиции без потерь на эквивалентный набор переменных отношения в 5НФ, то есть 5НФ всегда достижима. Од- нако Кристофер Дейт отмечает, что процедура определения того, что не- которая переменная отношения находится в 4НФ, а не в 5НФ, и, таким образом, существует возможность её дальнейшей выгодной декомпози- ции, всё ещё остаётся не вполне ясной. Это связано с тем, что задача определения всех зависимостей соединения для отношения может ока- заться очень сложной, а по поводу отношения можно утверждать, что оно находится в 5НФ, только при условии известности всех его потенциаль- ных ключей и всех его зависимостей соединения. 15 Очень редко отношение, находящееся в 4НФ, не соответствует 5НФ. Это те ситуации, в которых реальные правила, ограничивающие до- пустимые комбинации атрибутов, никак не выражены в структуре отно- шения (см. пример ниже). В таком случае, если отношение не приведено к 5НФ, бремя обеспечения логической целостности данных отчасти пере- кладывается на приложение, отвечающее за добавление, удаление и из- менения данных. В этом случае существует риск возникновения ошибок. Пятая нормальная форма исключает возникновение таких аномалий. Пример: схема из трёх сущностей со связями многие-ко-многим, а именно -- автомобиль; -- цвет кузова; -- модель. Ассоциативные сущности: модель – цвет, автомобиль – цвет, ав- томобиль – модель. Добавляем ассоциативную сущность модель – цвет – автомобиль 16 5.4. Задания по нормализации для аудиторной и самостоятельной ра- боты Задано отношение и множество функциональных зависимостей. Определить ключ, выявить текущую нормальную форму и преобразо- вать это отношение к 2НФ, 3НФ, НФБК, 4НФ, подтверждая на каж- дом шаге правильность результата. Задача 1. Задано отношение Рабочий: Рабочий Код_раб очего Имя_рабоче го Специ- альность Код_ру ководи- теля Почасо- вая_став ка Код_здан ия 1235 М. Фарадей Электрик 1311 3,50 {312,515} 1412 К Немо Штукатур 3,00 {312,460,43 5, 515} 1311 Х. Колумб Электрик 3,50 435 и множество функциональных зависимостей: Код_рабочего→Имя_рабочего, Специальность, Код_руководителя Код_рабочего→→Код_здания Специальность→→Код_рабочего Код_здания→→Код_рабочего Специальность→Почасовая_ставка. Задача 2. Задано отношение Рабочий: Рабочий Код_ рабо- чего Имя_рабо чего Специ- альность Почасо- вая_ставк а Да- та_начала_ работы Код_зда ния 1235 М. Фара- дей Электрик 3,50 10.10.99 312 1412 К Немо Штукатур 3,00 07.10.99 312 1235 М. Фара- дей Электрик 3,50 17.10.99 515 1412 К. Немо Штукатур 3,00 08.12.99 460 1412 К. Немо Штукатур 3,00 15.10.99 435 и множество функциональных зависимостей: Код_рабочего→Имя_рабочего, Специальность Код_рабочего→→Код_здания Специальность→→Код_рабочего Код_здания, Код_рабочего→Дата_начала_работы Специальность→Почасовая_ставка. 17 Задача 3. Дано отношение в 1НФ и множество функциональных зависимостей: Студент(№_студента, предмет, повт_предмет, возраст, курс) №_студента→возраст №_студента→курс №_студента→→предмет №_студента→→повт_предмет возраст→курс Задача 4. Дано отношение в 1НФ и множество функциональных зависимостей: Поставки(№_поставщика, №_детали, №_проекта, объем_поставки, ста- тус, город) №_поставщика→№_проекта №_поставщика→→№_детали №_поставщика, №_детали, №_проекта→объем_поставки №_поставщика→статус №_поставщика→город город→статус Задача 5. Дано отношение в 1НФ и множество функциональных зависимостей: Преподаватель(№_преподавателя, ФИО_преподавателя, уч_степень, должность, возможный_предмет, предмет_в_нагрузке, вид_занятий, ко- личество_часов) №_преподавателя → ФИО, уч_степень, должность №_преподавателя →→ возможный_предмет №_преподавателя →→ предмет_в_нагрузке предмет_в_нагрузке →→ вид_занятий №_преподавателя, предмет_в_нагрузке, вид_занятий → количе- ство_часов уч_степень → должность Задача 6. Дано отношение в 1НФ и множество функциональных зависимостей: Фильм (Название_фильма, Год_выхода, Длительность_фильма, Тип_фильма, Доходность_фильма, Название_киностудии, Ад- рес_киностудии, Имя_кинозвезды, Лучший_фильм_кинозвезды) 18 Название_фильма, Год_выпуска → Длительность_фильма, Тип_фильма, Доходность_фильма, Название_киностудии, Адрес_киностудии Название_киностудии → Адрес_киностудии Название_фильма →→ Имя_кинозвезды Название_фильма →→ Год_выпуска Название_киностудии →→ Название_фильма, Год_выпуска Имя_кинозвезды → Лучший_фильм_кинозвезды |