Нормализация » Буквы.Ру Научно-популярный портал<script async custom-element="amp-auto-ads" src="https://cdn.ampproject.org/v0/amp-auto-ads-0.1.js"> </script>

Нормализация

<

110313 2216 1 Нормализация

6.1. Цель нормализации

С целью разработки логической модели данных, создания точного представления данных, связей между ними и требуемых ограничений (в т.ч. целостности) необходимо определить, прежде всего, подходящий набор отношений. Для решения этой задачи используется специальный метод, который называется нормализацией.

Нормализация  

Метод создания набора отношений с заданными свойствами на основе заданных требований к данным 

Процесс нормализации был впервые предложен Э. Ф. Коддом в 1972г. Нормализация осуществляется в виде последовательности тестов для некоторого отношения с целью проверки его соответствия (или несоответствия) требованиям заданной нормальной формы. Сначала были предложены только три вида нормальных форм: первая (1НФ), вторая (2НФ) и третья (ЗНФ). Затем Р. Бойсом и Э. Ф. Коддом (Codd, 1974) было сформулировано более строгое определение третьей нормальной формы, которое получило название нормальной формы Бойса-Кодда (НФБК). Все эти нормальные формы основаны на функциональных зависимостях, существующих между атрибутами отношения.

Вслед за НФБК появились определения четвертой (4НФ) и пятой (5НФ) нормальных форм. Однако на практике эти нормальные формы более высоких порядков используются крайне редко.

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

6.2. Избыточность данных и аномалии обновления

Основная цель проектирования реляционной базы данных заключается в группировании атрибутов в отношения так, чтобы минимизировать избыточность данных и, таким образом, сократить объем памяти, необходимый для физического хранения отношений, представленных в виде таблиц. Проблемы, связанные с избыточностью данных, можно проиллюстрировать, сравнив сокращенные отношения Сотрудники (S) и Отделения (B), с отношением S_B, показанным в табл. 6.1.

Таблица 6.1

B

KodO 

Address 

B5

Тюмень, Береговая, 22 

B7

Нижневартовск, Новая, 15 

B3

Тюмень, Северная, 34 

B4

Ишим, Окружная, 44 

B2

Надым, Садовая 74 

S

KodS

Name 

Dol 

ZP 

KodO 

S21 

Иванов 

Руководитель 

500 

B5

S37

Петрова 

Агент 

250 

B3

S14

Сидоров

Менеджер 

400 

B3

S09

Зотова 

Агент 

240 

B7

S05

Степанова 

Секретарь 

200 

B3

S41

Петров 

Менеджер 

450 

B5

S_B

KodS 

Name 

Dol 

ZP 

KodO 

Address 

S21

Иванов 

Руководитель 

500 

B5

Тюмень, Береговая, 22 

S37

Петрова 

Агент 

250 

B3

Тюмень, Северная, 34 

S14

Сидоров 

Менеджер

400 

B3

Тюмень, Северная, 34 

S09

Зотова 

Агент 

240 

B7 

Нижневартовск, Новая, 15 

S05 

Степанова 

Секретарь 

200 

B3 

Тюмень, Северная, 34 

S41 

Петров 

Менеджер 

450 

B5

Тюмень, Береговая,22 

 

Отношение S_B является альтернативной формой представления отношений S и B. Эти отношения можно описать следующим образом:

Staff (KodS, Name, Dol, ZP, KodO)

Branch (KodO, Address)

Staff_Branch (KodS, Name, Dol, ZP, KodO, Addrass)

В отношении S_B содержатся избыточные данные, поскольку сведения об отделении компании повторяются в записях, относящихся к каждому сотруднику данного отделения. В противоположность этому, в отношении B сведения об отделении содержатся только в одной строке, а в отношении S повторяется только номер отделения компании (KodO), который представляет собой место работы каждого сотрудника. При работе с отношениями, содержащими избыточные данные, могут возникать проблемы, которые называются аномалиями обновления и подразделяются на аномалии вставки, удаления и модификации.

5.2.1. Аномалии вставки

Существует два основных типа аномалий вставки, которые иллюстрируются с помощью отношения S_B, показанного в табл. 6.1.

  1. При вставке сведений о новых сотрудниках в отношение S_B необходимо указать и сведения об отделении компании, в котором эти сотрудники работают. Например, при вставке сведений о новом сотруднике отделения ‘B7’ потребуется ввести сведения о самом отделении ‘B7’, которые должны соответствовать сведениям об этом же отделении в других строках отношения S_B. Отношения S и D, не могут пострадать от такого несоответствия данных, поскольку для каждого сотрудника в отношение S потребуется ввести только соответствующий номер отделения компании. Кроме того, сведения об отделении компании с номером ‘В7’ заносятся в базу данных однократно, в виде единственной строки отношения B.
  2. Для вставки сведений о новом отделении компании, которое еще не имеет собственных сотрудников, потребуется присвоить значение NULL всем атрибутам описания персонала отношения S_B, включая и личный номер сотрудника KodO. Однако, поскольку этот атрибут является первичным ключом отношения S_B, то попытка ввести значение NULL вызовет нарушение целостности сущностей и потому будет отклонена. Структура отношений, представленных в S и B, позволяет избежать возникновения этой проблемы, поскольку сведения об отделениях компании вводятся в отношение B независимо от ввода сведений о сотрудниках. Сведения о сотрудниках, которые будут работать в новом отделении компании, могут быть введены в отношение S позже.

    6.2.2. Аномалии удаления

    При удалении из отношения S_B строки с информацией о последнем сотруднике некоторого отделения компании, сведения об этом отделении будут полностью удалены из базы данных. Структура отношений S и B позволяет избежать возникновения этой проблемы, поскольку строки со сведениями об отделениях компании хранятся отдельно от строк со сведениями о сотрудниках. Связывает этих два отношения только общий атрибут KodO. При удалении из отношения S строки с номером сотрудника ‘S09’ сведения об отделении ‘В7’ в отношении B останутся нетронутыми.

    6.2.3. Аномалии обновления

    При попытке изменения значения одного из атрибутов для некоторого отделения компании в отношении S_B (например, адреса) необходимо обновить соответствующие значения в строках для всех сотрудников этого отделения. Если такой модификации будут подвергнуты не все требуемые строки отношения, то в этом случае база данных будет содержать противоречивые сведения. В частности, в нашем примере для отделения компании с номером ‘B3’ в строках, относящихся к разным сотрудникам, ошибочно могут быть указаны разные значения номера телефона этого отделения.

    Все приведенные выше примеры иллюстрируют то, что представленные в отношения S и B обладают более приемлемыми свойствами, чем отношение S_B.

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

    Свойства соединения без потерь и сохранения зависимости

    Выше было продемонстрировано, что отношение S_B подвержено аномалиям обновления и, дабы избежать этих аномалий, лучше всего выполнить его декомпозицию на отдельные отношения S и B. Однако процесс декомпозиции имеет два важных свойства, которые следует учитывать.

    Первое из них — это свойство соединения без потерь (lossless-join), которое позволяет восстановить любой кортеж исходного отношения, используя соответствующие кортежи отношений, полученных в результате декомпозиции.

    Второе — свойство сохранения зависимости (dependency preservation), которое позволяет сохранить ограничения, наложенные на исходное отношение, посредством наложения некоторых ограничений на каждое из меньших отношений, полученных после декомпозиции. В результате отпадает необходимость выполнения соединения результирующих отношений с целью проверки того, не нарушается ли ограничение, наложенное на исходное отношение.

    6.3. Функциональные зависимости

    6.3.1. Определение функциональной зависимости

    Функциональная зависимость (functional dependency) описывает связь между атрибутами и является одним из основных понятий нормализации.

    Функциональная зависимость 

    Описывает связь между атрибутами отношения.

    Если каждое значение атрибута (или группы атрибутов) А связано только с одним значением атрибута B (или группы атрибутов), то говорят, что атрибут B функционально зависит от атрибута А

    Функциональная зависимость обозначается как A®В.

    Функциональная зависимость является смысловым (или семантическим) свойством атрибутов отношения.

    Рассмотрим отношение с атрибутами A и В, где атрибут В функционально зависит от атрибута А. Если две строки имеют одно и то же значение атрибута А, то они обязательно имеют одно и то же значение атрибута В. Однако для заданного значения атрибута В может существовать несколько различных значений атрибута А.

    Детерминант 

    Детерминантом функциональной зависимости называется атрибут или группа атрибутов, расположенная слева от символа стрелки. 

    Дальше в этой главе мы будем игнорировать тривиальные функциональные зависимости, т.е. зависимости типа А®В, где атрибут В является подмножеством атрибута А.

    Рассмотрим следующие примеры функциональных зависимостей.

    Пример 6.1. Функциональные зависимости.

    В отношении S:    KodS®Dol, (но НЕ Dol®KodS);

    Связь между атрибутами KodS и Dol относится к типу 1:1, поскольку для каждого номера сотрудника имеется только одна должность. А связь между атрибутами Dol и KodS имеет тип 1:М, так как существует сразу несколько номеров сотрудников.

    Атрибут KodS является детерминантом функциональной зависимости KodS®Dol.

    В отношении S_B:    KodS®Name;

        KodO®Address

    Для выявления потенциальных ключей отношения S_B необходимо найти атрибут (или группу атрибутов), который уникальным образом идентифицирует каждую строку этого отношения. Если отношение обладает несколькими потенциальными ключами, то нужно выбрать среди них тот, который станет первичным ключом отношения. Все атрибуты, которые не являются частью, первичного ключа должны функционально зависеть от него.

    Единственным потенциальным ключом отношения S_B, а значит, и его первичным ключом, является атрибут KodS, так как все другие атрибуты этого отношения функционально зависят от него. Хотя атрибут KodO является детерминантом этого отношения, он не являются его потенциальным ключом.

    Концепция функциональной зависимости является центральным понятием процесса нормализации.

    6.4. Процесс нормализации

    Нормализация — это формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей, как в случае НФБК) и существующих функциональных зависимостей. Он включает ряд правил, которые могут использоваться для проверки отдельных отношений таким образом, чтобы вся база данных стала нормализована до желаемой степени. Если некоторое требование не удовлетворяется, то нарушающее данное требование отношение должно быть декомпозировано на отношения, каждое из которых удовлетворяет всем требованиям нормализации.

    Зачастую нормализация осуществляется в несколько последовательно выполняющихся этапов, каждый из которых соответствует некоторой нормальной форме, обладающей известными свойствами. В ходе нормализации формат отношений становится все более строгим и менее уязвимым по отношению к аномалиям обновления. При работе с реляционной моделью данных важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщиков. Однако, для того чтобы избежать аномалий обновления, нормализацию рекомендуется выполнять как минимум до ЗНФ.

    На рис. 6.1 показана схема процесса нормализации.

    110313 2216 2 Нормализация

    Рис. 6.1. Схема взаимосвязей между отдельными нормальными формами

    Ниже процесс нормализации показан на примере преобразования данных, которые в исходном состоянии имели вид формы табличного формата со строками и столбцами.

    6.5. Первая нормальная форма (1HO)

    Ненормализованная форма 

    Таблица, содержащая одну или несколько повторяющихся (ННФ) групп данных. 

    Первая нормальная форма (1НФ) 

    Отношение, в котором на пересечении каждой строки и каждого столбца содержится только одно значение.

     

    Процесс нормализации начинается с преобразования данных из формата источника (например, из формата стандартной формы) в формат таблицы со строками и столбцами. На исходном этапе таблица находится в ненормализованной форме (ННФ) и часто называется ненормализованной таблицей. Для преобразования ненормализованной таблицы в первую нормальную форму (1НФ) в исходной таблице следует найти и устранить все повторяющиеся группы данных. Повторяющейся группой называется группа, состоящая из одного и более атрибутов таблицы, в которой возможно наличие нескольких значений для единственного значения ключевого атрибута таблицы. В данном контексте термин «ключ» равным образом относится и к одному атрибуту, и к группе атрибутов, которые единственным образом идентифицируют каждую строку ненормализованной таблицы. Существует два подхода исключения повторяющихся групп из ненормализованных таблиц.

    В первом подходе повторяющиеся группы устраняются путем ввода соответствующих данных в пустые столбцы строк с повторяющимися данными. Иначе говоря, пустые места при этом заполняются дубликатами неповторяющихся данных. Этот подход часто называют «выравниванием» таблицы. Полученная в результате этих действий таблица, которая теперь будет называться отношением, содержит атомарные (или единственные) значения на пересечении каждой строки с каждым столбцом, а потому находится в первой нормальной форме. В результате такого подхода в полученное отношение вносится некоторая избыточность данных, которая в ходе дальнейшей нормализации будет устранена.

    Во втором подходе один атрибут или группа атрибутов назначаются ключом ненормализованной таблицы, а затем повторяющиеся группы изымаются и помещаются в отдельные отношения вместе с копиями ключа исходной таблицы. Далее в новых
    отношениях устанавливаются первичные ключи. Иногда ненормализованные отношения могут содержать одну или несколько повторяющихся групп внутри повторяющихся групп первого порядка. В таких случаях данный прием применяется до тех пор, пока повторяющихся групп совсем не останется. Полученный набор отношений будет находиться в первой нормальной форме только тогда, когда ни в одном из них не будет повторяющихся групп атрибутов.

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

    Пример. Первая нормальная форма (1НФ)

    Рассмотрим форму, которая заполняется в отделении об арендуемых помещениях.

    Фамилия арендатора 

    Саблев 

    Код арендатора 

    R76

     

    Код

    помещения 

    Адрес 

    Дата

    начала 

    Дата окончания 

    Стоимость 

    Код

    владельца 

    Фамилия

    владельца 

    KodP 

    Address 

    RStart 

    Rfinish 

    Rent 

    KodO 

    OName 

    P04

    Адрес 1 

    1.06.94 

    30.08.96 

    350 

    С40 

    Кротова 

    P16 

    Адрес 2

    1.09.96 

    1.09.98 

    450 

    С93 

    Зимина 

     

    Форма
    содержит сведения об объектах недвижимости, арендованных клиентом по имени ‘Саблев’. Для упрощения этого примера предположим, что клиент арендует некоторый объект только один.

    Данные об объектах, арендованных двумя клиентами, ‘Саблев’ и ‘Рубин’ преобразуются из формы в таблицу со строками и столбцами, формат которой представлен в табл. 6.2. Эта исходная таблица данных является примером ненормализованной таблицы (ННФ).

     

    Отношение R_O

    KodR 

    RName 

    KodP 

    Address 

    RStart 

    Rfinish

    Rent 

    KodO 

    OName 

    R76

    Саблев 

    P04

    Адрес 1

    1.06.94 

    30.08.96 

    350 

    С40 

    Кротова 

       

    P16

    Адрес 2 

    1.09.96 

    1.09.98 

    450 

    С93 

    Зимина 

    R56

    Рубин 

    P04

           

    C40 

    Кротова 

       

    P36 

           

    C93 

    Зимина 

       

    P16

           

    C93 

    Зимина 

    Рис. 6.4. Ненормализованная таблица

    Ключевой атрибут в отношении R_O – KodR.

    Повторяющаяся группа=(KodP, Address, RStart, Rfinish, Rent, KodO, Oname)

    Первый подход. Создадим таблицу, в которой вместо 2 строк будет 5.

    Отношение R_O_1

    KodR 

    KodP 

    RName 

    Address 

    RStart 

    RFinish 

    Rent 

    KodO 

    OName 

    R76

    P04

    Саблев 

    Адрес 1

    1.06.94 

    30.08.96 

    350 

    С40 

    Кротова 

    R76

    P16

    Саблев 

    Адрес 2 

    1.09.96 

    1.09.98 

    450 

    С93 

    Зимина 

    R56

    P04

    Рубин 

           

    C40

    Кротова 

    R56

    P36

    Рубин 

           

    C93

    Зимина 

    R56

    P16

    Рубин 

           

    C93

    Зимина 

    Потенциальные ключи – составные. Например, (KodR,KodP) или (KodR,Rstart) (если…). Выберем в качестве первичного — (KodR,KodP). Отношение R_O_1 находится в 1НФ, но здесь мы имеем большую избыточность данных. Для устранения этого ее необходимо преобразовать в 2НФ.

    Второй подход. Повторяющаяся группа удаляется и переносится в другое, добавив копию ключевого атрибута. Из отношения получаем

    Отношение R_O_2

    KodR 

    RName 

    R76

    Саблев 

    R56

    Рубин 

    Отношение R_O_3

    KodR 

    KodP 

    Address 

    RStart 

    Rfinish 

    Rent 

    KodO 

    OName 

    R76

    P04

    Адрес 1 

    1.06.94 

    30.08.96 

    350 

    С40 

    Кротова 

    R76

    P16

    Адрес 2 

    1.09.96 

    1.09.98

    450 

    С93 

    Зимина 

    R56

    P04

           

    C40

    Кротова 

    R56

    P36

           

    C93

    Зимина 

    R56

    P16

           

    C93

    Зимина 

     

     

     

     

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

    6.6. Вторая нормальная форма (2НФ)

    Вторая нормальная форма (2НФ) основана на понятии полной функциональной зависимости.

    6.6.1. Полная функциональная зависимость

    Полная

    функциональная

    зависимость 

    В некотором отношении атрибут В называется полностью функционально зависимым от атрибута (или группы) А, если атрибут В функционально зависит от полного значения атрибута А и не зависит ни от какого подмножества атрибута А.

    Частичная
    функциональная зависимость

    Если в зависимости А®В в группе А есть некий атрибут, при удалении которого эта зависимость сохраняется, то она называется частичной функциональной зависимостью

     

    6.6.2. Определение второй нормальной формы

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

    Вторая нормальная форма (2НФ) 

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

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

    Пример. Вторая нормальная форма (2НФ). На рис. ___ показаны функциональные зависимости (от fl до f6) для отношения R_O_1 с парой атрибутов (KodR, KodP) в качестве первичного ключа.

    f1

    KodR, KodP®RStart, RFinish

    Первичный ключ 

    f2

    KodR®RName

    Частичная зависимость 

    f3 

    KodP® Address, Rent

    Частичная зависимость 

    f4 

    KodO® OName

    Транзитивная зависимость 

    f5 

    KodR, RStart ® KodP, Address, RFinish

    Потенциальный ключ 

    f6

    KodP, RStart ® KodR, RName

    Потенциальный ключ 

     

    110313 2216 3 Нормализация

    Рис. __. Функциональные зависимости отношения R_O_3

    После выявления функциональных зависимостей процесс нормализации отношения продолжается проверкой его принадлежности ко второй нормальной форме. Для этого требуется найти хотя бы один случай частичной зависимости от первичного ключа. Нетрудно заметить, что атрибут имени клиента частично зависит от первичного ключа (зависимость f2). Кроме того, атрибуты объекта недвижимости также частично зависят от первичного ключа
    (зависимость
    f3).

    В свою очередь, атрибуты объектов недвижимости полностью функционально зависят от первичного ключа в целом (зависимость fl).

    На рис. __ показано наличие транзитивной зависимости (зависимость fd4). Хотя транзитивная зависимость также может послужить причиной аномалий обновления, тем не менее, ее присутствие в отношении не нарушает ограничений для 2НФ. Такие зависимости будут устранены при переходе к ЗНФ.

    Обнаружение частичных зависимостей внутри отношения R_O_1 означает, что данное отношение не находится во второй нормальной форме. Для преобразования отношения его в 2НФ
    необходимо создать новые отношения, причем так, чтобы атрибуты, не входящие в первичный ключ, были перемещены в них вместе с копией части первичного ключа, от которой они функционально зависят. Применение этого правила в нашем случае приведет к созданию трех новых отношений — C1, R1 и P1, которые представлены ниже.

    C1

    KodR 

    RName 

    R76

    Саблев 

    R56

    Рубин 

    R1

    KodR 

    KodP 

    RStart 

    RFinish 

    R76

    P04

    1.06.94 

    30.08.96 

    R76

    P16

    1.09.96 

    1.09.98 

    R56

    P04

       

    R56

    P36

       

    R56

    P16

    <
       

    P1

    KodP

    Address 

    Rent 

    KodO 

    OName 

    P04

    Адрес 1 

    350 

    С40 

    Кротова 

    P16

    Адрес 2 

    450 

    С93 

    Зимина 

    P36

       

    C93

    Зимина 

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

    (ЗНФ)

    Хотя 2НФ-отношения в меньшей степени обладают избыточностью данных, чем 1НФ-отношения, они все еще могут страдать от аномалий обновления. Так, при попытке обновления имени владельца недвижимости (например, «Зимина» с номером C93 (атрибут KodO)) потребуется обновить две строки отношения P1. Если обновить только одну из этих двух строк, база данных попадет в противоречивое состояние. Эта аномалия обновления вызывается транзитивной зависимостью, присутствующей в данном отношении. Она может быть устранена путем приведения данного отношения к третьей нормальной форме. В этом разделе транзитивные зависимости рассматриваются вместе с третьей нормальной формой.

    6.7.1. Транзитивная зависимость

    Транзитивная зависимость

    Если для атрибутов A, В и C некоторого отношения существуют зависимости вида A®B и B®C, то говорят, что атрибут C транзитивно зависит от атрибута A через атрибут B (при условии, что атрибут A функционально не зависит ни от атрибута В, ни от атрибута С).

    Например, рассмотрим следующие функциональные зависимости внутри отношения S_B.

    S_B

    KodS 

    Name 

    Dol 

    ZP 

    KodO 

    Address 

    S21 

    Иванов 

    Руководитель 

    500 

    B5

    Тюмень, Береговая, 22 

    S37

    Петрова 

    Агент 

    250 

    B3

    Тюмень, Северная, 34 

    S14

    Сидоров 

    Менеджер 

    400 

    B3

    Тюмень, Северная, 34 

    S09

    Зотова 

    Агент 

    240 

    B7

    Нижневартовск, Новая, 15 

    S05

    Степанова 

    Секретарь 

    200 

    B3

    Тюмень, Северная, 34 

    S41

    Петров 

    Менеджер 

    450 

    B5

    Тюмень, Береговая,22 

     

    KodS®KodO и KodO®Address

    В этом случае транзитивная зависимость KodS®Address осуществляется через атрибут KodO. Данное утверждение справедливо, поскольку атрибут KodS не зависит функционально от атрибутов KodO и Address. Другие примеры транзитивных зависимостей приводятся в следующих разделах.

    6.7.2. Определение третьей нормальной формы

    Третья нормальная форма (3НФ) 

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

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

    Пример 6.5. Третья нормальная форма (3НФ).

    C1

    KodR 

    RName 

    R76

    Саблев 

    R56

    Рубин 

    R1

    KodR

    KodP 

    RStart 

    RFinish 

    R76 

    P04 

    1.06.94 

    30.08.96 

    R76 

    P16 

    1.09.96 

    1.09.98 

    R56 

    P04 

       

    R56 

    P36 

       

    R56 

    P16 

       

    P1

    KodP 

    Address 

    Rent 

    KodO 

    OName 

    P04

    Адрес 1

    350 

    С40 

    Кротова 

    P16

    Адрес 2 

    450 

    С93 

    Зимина 

    P36

       

    C93

    Зимина 

    Рассмотрим функциональные зависимости, существующие в отношениях C1, R1 и P1

    Отношение C1

    f2

    KodR®Rname

    Отношение R1

    f1

    KodR, KodP®Rstart, Rfinish

    f5 

    KodR, RStart®KodP, RFinish

    f6

    KodP, Rstart®KodR, RFinish

    Отношение P1

    f3

    KodP® Address, Rent, KodO, OName

    f4 

    KodO®OName

    Все, не входящие в первичный ключ, атрибуты отношений C1 и R1, функционально зависимы только от их
    первичных ключей. Следовательно, отношения C1 и R1 не имеют транзитивных зависимостей, а потому они уже находятся в третьей нормальной форме (ЗНФ).

    Все, не входящие в первичный ключ атрибуты отношения P1, функционально зависят от первичного ключа, за исключением атрибута OName, который также зависит и
    от атрибута KodO (зависимость fd4).

    Для преобразования отношения P1 в третью нормальную форму необходимо, прежде всего, удалить упомянутую выше транзитивную зависимость путем создания двух новых отношений P2 и O:

    P2

    KodP 

    Address 

    Rent 

    KodO 

    P04 

    Адрес 1 

    350 

    С40 

    P16

    Адрес 2

    450 

    С93 

    P36

       

    C93

    O

    KodO 

    OName 

    С40 

    Кротова 

    С93 

    Зимина 

    C93

    Зимина 

     

    Отношения P1 и O находятся в третьей нормальной форме, поскольку в них нет никаких транзитивных зависимостей от первичного ключа.

    В результате выполнения нормализации исходное отношение R_O, находящееся в 1НФ, было преобразовано в четыре отдельных отношения, каждое из которых находится в третьей нормальной форме.

    KodR 

    KodP 

    RName 

    Address 

    RStart 

    RFinish 

    Rent 

    KodO 

    OName 

    R76

    P04

    Саблев 

    Адрес 1 

    1.06.94 

    30.08.96 

    350 

    С40 

    Кротова 

    R76

    P16

    Саблев

    Адрес 2 

    1.09.96 

    1.09.98 

    450 

    С93 

    Зимина 

    R56

    P04

    Рубин 

           

    C40

    Кротова 

    R56

    P36

    Рубин 

           

    C93

    Зимина 

    R56

    P16

    Рубин 

           

    C93

    Зимина 

    Данная цель достигается за счет использования первичных и внешних ключей.

    Процесс нормализации заключается в декомпозиции исходного отношения посредством последовательного выполнения нескольких операций проекции реляционной алгебры. Полученные в результате декомпозиции отношения обеспечивают выполнение их соединения без потерь, результаты декомпозиции можно обратить посредством операции естественного соединения. (Задание!)

    Окончательный вид отношений, полученных в результате декомпозиции:

    C1

    KodR 

    RName 

    R76

    Саблев 

    R56

    Рубин 

    R1

    KodR

    KodP 

    RStart 

    RFinish 

    R76 

    P04 

    1.06.94 

    30.08.96 

    R76 

    P16 

    1.09.96 

    1.09.98 

    R56 

    P04 

       

    R56 

    P36 

       

    R56 

    P16 

       

    P2

    KodP 

    Address 

    Rent 

    KodO 

    P04 

    Адрес 1 

    350 

    С40 

    P16

    Адрес 2 

    450 

    С93 

    P36

       

    C93 

    O

    KodO 

    OName

    С40 

    Кротова 

    С93 

    Зимина 

    C93

    Зимина 

     

    6.8. Нормальная форма Бойса-Кодда (НфБК)

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

    6.8.1. Определение нормальной формы Бойса-Кодда

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

    Нормальная форма Бойса Кодда 

    Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.

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

    Различие между ЗНФ и НФБК заключается в том, что функциональная зависимость A->В допускается в 3НФ-отношении, если атрибут B является первичным ключом, а атрибут A не обязательно является потенциальным ключом. В НФБК эта зависимость допускается только тогда, когда атрибут A является потенциальным ключом. Следовательно, нормальная форма Бойса-Кодда является жесткой версией формы 3НФ: каждое НФБК-отношение является ЗНФ-отношением, но не всякое 3НФ-отношение является НФБК-отношением.

    Перед тем как обратиться к очередному примеру, еще раз рассмотрим отношения C1, R1, P2 и O. Отношения C1, P2 и O являются НФБК-отношениями, так как каждое из них имеет только один детерминант, который в то же время является потенциальным ключом этого отношения. Отношение R1 содержит три детерминанта (KodR, KodP), (KodR, Rstart) и (KodP, Rstart), которые были выявлены нами в примере выше и
    имеют вид:

    f1 

    KodR, KodP®Rstart, Rfinish

    f5 

    KodR, RStart®KodP, RFinish

    f6 

    KodP, Rstart®KodR, RFinish

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

  • имеются два (или более) составных потенциальных ключа;
  • эти потенциальные ключи перекрываются, т.е. ими совместно используется, по крайней мере, один общий атрибут.

    В следующем примере описывается ситуация, когда отношение нарушает требования НФБК, и представлен метод преобразования этого отношения в НФБК.

    Пример 6.6. Нормальная форма Бойса-Кодда (НФБК)

    В этом примере мы рассмотрим отношение C_I, которое содержит сведения о собеседованиях клиентов с сотрудниками компании «Аренда». Для проведения собеседования в тот день, на который назначена встреча с клиентом, в распоряжение сотрудника предоставляется особая комната (все встречи в этот день он проводит только в ней). Однако, в течение рабочего дня эта комната может использоваться несколькими разными сотрудниками. С клиентом проводится только одно собеседование в день, но он может участвовать в нескольких собеседованиях в разные дни.

    Информация содержится в отношении C_I:

    CN 

    ID 

    IT 

    SN 

    RN

    Код клиента 

    Дата 

    Время 

    Код сотрудника 

    Код комнаты 

    C76

    13.05.98 

    10:30 

    S05 

    G101 

    C56

    13.05.98 

    12:00 

    S05 

    G101 

    C74 

    13.05.98 

    12:00 

    S37 

    G102 

    C56 

    1.06.98 

    10:00 

    S05

    G102

    Отношение имеет три потенциальных ключа: (CN, ID) (SN, ID, IT) и (RN, ID, IT). Следовательно, отношение C_I обладает тремя составными потенциальными ключами, которые перекрываются, т.е. в них используется один общий атрибут ID. В качестве первичного ключа данного отношения выбрана комбинация атрибутов (CN, ID). Это отношение имеет следующий вид:

    C_I(CN, ID, IT, SN, RN)

    Оно содержит следующие функциональные зависимости:

    fd1 

    CN, ID®IT, SN,RN

    fd2 

    SN, ID, IT®CN, RN

    fd3 

    RN, ID, IT® SN, CN

    fd4 

    SN, ID® RN

     

    Рассмотрим эти функциональные зависимости для определения нормальной формы отношения C_I. Поскольку детерминанты функциональных зависимостей fd1, fd2 и fd3 являются потенциальными ключами этого отношения, то они не вызовут никаких проблем. Нам потребуется рассмотреть только функциональную зависимость fd4.

    Даже если комбинация атрибутов (SN, ID) не является потенциальным ключом отношения, эта функциональная зависимость допускается в ЗНФ, потому, что атрибут RN является атрибутом первичного ключа и частью потенциального ключа (RN, ID, IT). Поскольку в этом отношении нет никаких частичных или транзитивных зависимостей от первичного ключа (CN, ID) и допускается наличие функциональной зависимости fd4, можно считать, что отношение C_I находится в ЗНФ.

    Однако это отношение не находится в НФБК, так как в нем присутствует детерминант (SN, ID), который не является потенциальным ключом этого отношения. В НФБК требуется, чтобы все детерминанты отношения были его потенциальными ключами. В противном случае отношение C_I может страдать от аномалий обновления. Например, 13 мая 1998 года при изменении номера комнаты, выделенной сотруднику SG5, потребуется обновить значения в двух строках. Если при этом будет обновлена только одна строка, то база данных будет приведена в противоречивое состояние.

    Для преобразования отношения C_I в форму НФБК необходимо устранить нарушающую ее ограничения функциональную зависимость посредством создания двух новых отношений I и R:

    I (CN, ID, IT, SN)

    R (SN, ID, RN)

    I

    CN 

    ID 

    IT 

    SN 

    C76

    13.05.98 

    10:30 

    S05 

    C56 

    13.05.98 

    12:00 

    S05 

    C74 

    13.05.98 

    12:00 

    S37 

    C56 

    1.06.98 

    10:00 

    S05

    R

    SN 

    ID 

    RN 

    S05

    13.05.98 

    G101 

    S05 

    13.05.98 

    G101 

    S37 

    13.05.98 

    G102 

    S05 

    1.06.98 

    G102

     

    Любое отношение можно декомпозировать с образованием НФБК-отношений, однако делать это не всегда желательно. Например, декомпозиция будет нежелательна, если в результате ее выполнения утрачивается некоторая функциональная зависимость (т.е. детерминант и определяемые им атрибуты помещаются в разные отношения). В этой ситуации будет трудно обеспечить исходную функциональную зависимость отношения и важное ограничение может быть утрачено. Если имеет место упомянутая ситуация, то лучше закончить процесс нормализации на этапе образования ЗНФ-отношений, в которых все требуемые зависимости всегда сохраняются. Обратите внимание на то, что в примере при создании двух новых НФБК-отношений на основе исходного отношения C_I утрачивается функциональная зависимость fd3, поскольку детерминант этой зависимости больше не будет находиться в том же отношении, что и определяемые им атрибуты. Однако следует признать, что если не устранить функциональную зависимость SN, ID®RN (зависимость fd4), то отношение C_I будет обладать избыточностью данных.

    6.10. Четвертая нормальная форма (4НФ)

    Как было сказано выше, НФБК позволяет устранить любые аномалии, вызванные функциональными зависимостями. Однако в ходе исследований был выявлен еще один тип зависимости — многозначная зависимость, которая при проектировании отношений также может вызвать проблемы, связанные с избыточностью данных. В этом разделе кратко описывается многозначная зависимость и, связь этого типа зависимости с четвертой нормальной формой отношений (4НФ).

    6.10.1. Многозначная зависимость

    Возможность существования в отношении многозначных зависимостей возникает вследствие приведения исходных таблиц к 1НФ, для которой не допускается наличие некоторого набора значений на пересечении одной строки и одного столбца. Например, при наличии в отношении двух многозначных атрибутов для достижения непротиворечивого состояния строк необходимо повторить в них каждое значение одного из атрибутов в сочетании с каждым значением другого атрибута. Подобный тип ограничения порождает многозначную зависимость и приводит к избыточности данных. Рассмотрим представленное в табл. ___ отношение B_S_C, в котором содержатся имена сотрудников (SName) и клиентов (CName) отделения компании (BN).

    Отношение B_S_C

    BN 

    Sname 

    CName 

    B3 

    Зимина Анна 

    Петрова Татьяна 

    B3

    Иванов Иван 

    Петрова Татьяна 

    B3

    Зимина Анна

    Степанов Михаил 

    B3

    Иванов Иван 

    Степанов Михаил 

    В этом примере в отделении компании с номером ‘B3’ работают сотрудники с именами Зимина Анна и Иванов Иван. Кроме того, в нем зарегистрированы клиенты с именами Петрова Татьяна и Степанов Михаил. Однако, если в данном отделении компании между сотрудниками и клиентами нет никакой прямой связи, то необходимо создать строку для каждой комбинации сотрудника и клиента — только это позволит иметь гарантии, что отношение находится в непротиворечивом состоянии. Это требование отражает наличие в отношении B_S_C многозначной зависимости. Иначе говоря, в данном отношении существует многозначная зависимость, так как в нем содержится две независимые связи типа 1:М.

    Многозначная зависимость 

    В случае многозначной зависимости, существующей между атрибутами А, В и С некоторого отношения, для каждого значения А имеется набор значений атрибута В и набор значений атрибута С. Однако входящие в эти наборы значения атрибутов В и С не зависят друг от друга.

    Многозначная зависимость между атрибутами А, В и С некоторого отношения

    дальше будет обозначаться следующим образом:

    А®

    А®

    Например, в отношении B_S_C имеются многозначные зависимости:

    BN®>Sname

    BN®>CName

    Многозначная зависимость может быть определена как тривиальная или нетривиальная. Многозначная зависимость А®>В некоторого отношения R определяется как тривиальная, если атрибут В является подмножеством атрибута А или А È В = R.

    И наоборот, многозначная зависимость определяется как нетривиальная, если ни одно, ни другое условие не выполняется. Тривиальная зависимость не накладывает никаких ограничений на данное отношение, а нетривиальная — накладывает.

    Многозначная зависимость в отношении B_S_C является нетривиальной, так как в этом отношении ни одно, ни другое условие не удовлетворяется. Следовательно, на отношение Branch Staff Client по причине наличия нетривиальной МЗЗ накладывается ограничение, которое приводит к появлению повторяющихся строк, необходимых для того, чтобы гарантировать непротиворечивость связи между атрибутами SName и CName.

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

    6.10.2. Определение четвертой нормальной формы

    Четвертая

    нормальная

    форма (4НФ) 

    Отношение в нормальной форме Бойса-Кодда, которое не содержит нетривиальных многозначных зависимостей.

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

    Например, представленное в табл. 6.28 отношение Branch Staff Client не находится в 4НФ, поскольку в нем присутствует нетривиальная, МЗЗ. Это отношение следует декомпозировать на отношения B_S и B_C:

    Отношение B_S

    BN

    Sname 

    B3

    Зимина Анна 

    B3

    Иванов Иван 

    Отношение B_C

    BN 

    CName 

    B3

    Петрова Татьяна

    B3

    Степанов Михаил 

     

    Оба новых отношения находятся в 4НФ, потому что отношения содержат только тривиальную МЗЗ. Заметим, что эти 4НФ-отношения не характеризуются избыточностью данных.

    6.11. Пятая нормальная форма (5Hф)

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

    Однако бывают случаи, когда требуется декомпозировать отношение на более чем два отношения. В таких (достаточно редких) случаях возникает необходимость учитывать зависимость соединения, которая устраняется с помощью пятой нормальной формы (5НФ). В этом разделе мы кратко рассмотрим сущность зависимости соединения и ее связь с пятой нормальной формой (5НФ).

    6.11.1. Зависимость соединения

    Зависимость соединения 

    Свойство декомпозиции, которое вызывает генерацию ложных строк при обратном соединении декомпозированных отношений с помощью операции естественного соединения.

    При разбиении отношений с помощью операции проекции используемый метод декомпозиции определяется совершенно точно. В частности, следует позаботиться о том, чтобы при обратном соединении полученных отношений можно было восстановить исходное отношение. Такая декомпозиция называется декомпозицией с соединением без потерь, поскольку при ее выполнении сохраняются все данные исходного отношения, а также исключается создание дополнительных ложных строк. Например, после декомпозиции с соединением без потерь из отношений B_S и B_C будет получено отношение B_S_C.
    Иначе говоря, исходное отношение B_S_C может быть реконструировано путем выполнения операции естественного соединения для отношений B_S и B_C. В этом примере исходное отношение декомпозировано на два отношения, однако бывают случаи, когда требуется выполнить декомпозицию без потерь с образованием более чем двух отношений. Именно в таких случаях применимы понятия зависимости соединения и пятой нормальной формы (5НФ).

    6.11.2. Определение пятой нормальной формы (5НФ)

    Пятая нормальная форма (5НФ) 

    Отношение без зависимостей соединения. 

    Рассмотрим показанное в табл. ___ отношение P_I_S, которое содержит сведения о поставщиках мебели (атрибут SN), описания мебели (Item), а также информацию об объектах недвижимости (атрибут PN), в которых она установлена.

    Таблица ____. Отношение P_I_S в четвертой нормальной форме.

    PN 

    Item 

    S_N

     

    P4 

    Кровать 

    S1 

    P4 

    Стул 

    S2 

    P16

    Кровать 

    S2 

    P16

    Стол 

    S1 

    P36 

    Стул

    S3 

    Например, для объекта недвижимости с номером P4 поставщиком с номером Sl поставлена кровать, а поставщиком с номером S2 — стул.

    Единственное дополнительное ограничение в данном случае может заключаться в том, чтобы каждый поставщик поставлял только какие-то определенные типы мебели для заданного объекта недвижимости, вопреки тому, что некий поставщик может поставлять все типы мебели для этого объекта недвижимости. Такое ограничение создает в отношении P_I_S зависимость соединения. Однако структура этого отношения не соответствует этому ограничению, поскольку допускается добавление в нее любых строк, включая строки (P16; «Кровать»; Sl ) и (P4; «Кровать»; S2). Однако данное представление не является корректным отражением реальной ситуации.

    Поскольку отношение P_I_S содержит зависимость соединения, значит, оно не находится в пятой нормальной форме. Для удаления этой зависимости соединения следует выполнить его декомпозицию на три 5НФ-отношения: P_I, I_S и P_S (табл. ___, ____ и ____ соответственно).

    Таблица ____. 5HФ-отношение P_I

    PN 

    Item 

    P4

    Кровать 

    P4 

    Стул

    P16

    Кровать

    P16 

    Стол

    P36 

    Стул

    Таблица 6.33. 5НФ-отношение I_S

    Item 

    S_N

     

    Кровать 

    S1

    Стул

    S2 

    Кровать 

    S2

    Стол

    S1 

    Стул

    S3 

    Таблица 6.34. 5HФ-отношение P_S

    PN 

    S_N

     

    P4

    S1

    P4 

    S2 

    P16

    S2

    P16 

    S1 

    P36 

    S3

     

    Следует отметить, что естественное соединение любых двух из этих трех отношений приведет к появлению ложных строк, но естественное соединение этих трех отношений приведет к восстановлению отношения P_I_S.

    Резюме

    Нормализация — это формальный метод создания набора отношений с заданными свойствами на основе их ключей и существующих функциональных зависимостей между их атрибутами.

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

    Одной из основных концепций нормализации является функциональная зависимость, которая описывает связь между атрибутами отношения. Пусть А и В — это атрибуты (или группа атрибутов) некоторого отношения R. Атрибут В функционально зависит от атрибута A (что обозначается как А®В), если каждое значение А связано с одним значением В.

    Детерминантом называется любой атрибут, от которого полностью функционально зависит какой-то другой атрибут. В определении функциональной зависимости термин «детерминант» характеризует один или несколько атрибутов, расположенных с левой стороны от стрелки.

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

    Сначала были предложены только первая (1НФ), вторая (2НФ) и третья (ЗНФ) нормальные формы. Затем было сформулировано более строгое определение третьей нормальной формы, которое получило название нормальной формы Бойса-Кодда (НФБК). Все эти нормальные формы предназначены для устранения различных видов нежелательных функциональных зависимостей между атрибутами отношения.

    Ненормализованной формой (ННФ) называется таблица, которая содержит одну или несколько повторяющихся групп атрибутов.

    Первой нормальной формой (1НФ) называется отношение, в котором на пересечении каждой строки и каждого столбца располагается одно и только одно значение.

    Второй нормальной формой (2НФ) называется отношение, которое находится в первой нормальной форме, а каждый атрибут, не входящий в первичный ключ, полностью функционально зависит от этого первичного ключа. Полная функциональная зависимость для атрибутов А и В некоторого отношения означает следующее: атрибут В полностью функционально зависит от атрибута А, если атрибут В функционально зависит от атрибута А, но не зависит ни от какого подмножества атрибута А.

    Третьей нормальной формой (ЗНФ) называется отношение, которое находится в первой и во второй нормальных формах, причем в нем нет атрибутов, не входящих в первичный ключ, которые транзитивно зависят от этого первичного ключа. Транзитивная зависимость для атрибутов А, В и С некоторого отношения означает следующее: если А®В и В®С, то С транзитивно зависит от атрибута А через атрибут В (при условии, что А функционально не зависит от В или С).

    • Нормальной формой Бойса-Кодда (НФБК) называется отношение, в котором ] каждый детерминант является потенциальным ключом.

    • Четвертой нормальной формой (4НФ) называется отношение, которое находится в нормальной форме Бойса-Кодда и не содержит нетривиальных многозначных зависимостей. Многозначная зависимость представляет такую зависимость между атрибутами А, В и С некоторого отношения, при которой для каждого значения атрибута А существуют соответствующие наборы значений атрибутов В и С, причем оба этих набора не зависят друг от друга.

     

    110313 2216 4 Нормализация

    Рис. ___. Схема процесса нормализации

<

Комментирование закрыто.

MAXCACHE: 1.17MB/0.00158 sec

WordPress: 24.26MB | MySQL:119 | 3,752sec