Нормализация отношений

В реляционных базах данных схема содержит как структурную, так и семантическую информацию. Структурная информация связана с объявлением от-

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

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

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

Нормализация - это пошаговый обратимый процесс замены данной схемы (или совокупности отношений) базы данных другой схемой, в которой отноше-

ния имеют более простую и регулярную структуру [4]. В теории нормальных форм определены различные нормальные формы, которые ограничивают типы допустимых функциональных зависимостей отношения. Каждой нормальной форме соответствует некоторый определенный набор ограничений, и отношение находится в некоторой нормальной форме, если удовлетворяет заданному набору ограничений. Коддом первоначально [1] выделено три нормальных формы – первая (1НФ), вторая (2НФ) и третья (3НФ) и описан механизм, позволяющий любое отношение преобразовать к 3НФ. В работе [2] Коддом предложена усиленная третья нормальная форма, или нормальная форма Бойса-Кодда (БКНФ). Четвертая нормальная форма (4НФ) определена Фейджином в работе [7] и в работах [8], [9] определены другие нормальные формы. Рассмотрим три нормальные формы, предложенные Коддом. Эти нормальные формы ограничивают зависимость непервичных атрибутов от ключей.Уровень нормализации отношения зависит от его семантики и не может быть однозначно определен из данных, содержащихся в текущий момент в базе данных. Семантика базы данных должна быть задана с помощью функциональных зависимостей. Понятие функциональной зависимости является фундаментальным в теории реляционных баз данных. Поэтому, прежде чем рассмотреть три первые нормальные формы, дадим несколько определений.

Функциональная зависимость. В отношении R атрибут Y функционально зависит от атрибута X тогда и только тогда, когда в любой момент времени каж-

дому значению Х соответствует в точности одно значение Y.

R.X →R.Y

Пример.

Товар Имя_Поставщика Адр_Постав-

щика

Кол_товара Цена_ то-

вара

Компьютер “Электрон” Нахимова, 47 200 6200000

Ризограф “Протон” Гагарина, 12 12 90000000

Принтер “Электрон” Нахимова, 47 100 1500000

Ксерокс “Сигма” Садовая, 128 50 5000000

Рис.2.10. Пример функциональной зависимости

В примере атрибут Адр_Поставщика функционально зависит от атрибута

Имя_Поставщика.

Имя_Поставщика →Адр_Поставщика

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

R.X →R.Y называется полной, если атрибут Y зависит от всей группы атрибу-

тов Х и не зависит функционально от любой ее части (подмножества).

Транзитивная функциональная зависимость. Функциональная зависи-

мость R.X →R.Y называется транзитивной, если существует такой атрибут Z,

что имеются функциональные зависимости:

R.X →R.Z и R.Z →R.Y

Первая нормальная форма (1НФ).Отношение R называется нормализо-

ванным или приведенным к первой нормальной форме, если значения всех его

атрибутов простые (атомарные), т.е. значение атрибута не должно быть множе-

ством или повторяющейся группой.

Пример.

Отношение S1

Номер_ Дети

сотруд-

ника

ФИО_

Сотрудника

Ауди-

тория

Телефон

Имя Возраст

31 Петров Т.Н. 326 217 Таня

Саша

44 Смирнов Ю.А. 412 258 Игорь 9

51 Павлов И.С. 412 258 Олег

Таня

Рис.2.11. Пример ненормализованного отношения

В отношении S1 первичным ключом является атрибут Но-

мер_сотрудника. Отношение S1 содержит один сложный атрибут – Дети. Для

приведения отношения S1 к 1НФ необходимо разбить сложный атрибут Дети на

два простых атрибута - Имя и Возраст и введем атрибут Имя в состав первич-

ного ключа. В итоге получим нормализованное отношение S2, представленное на

рисунке 2.12.

Отношение S2

Номер_

сотруд-

ника

Имя Возраст ФИО_

сотрудника

Ауди-

тория

Телефон

31 Таня 13 Петров Т.Н. 326 217

31 Саша 6 Петров Т.Н. 326 217

44 Игорь 9 Смирнов Ю.А. 412 258

51 Олег 2 Павлов И.С. 412 258

51 Таня 6 Павлов И.С. 412 258

Рис.2.12. Пример нормализованного отношения (1НФ)

В отношении S2 первичным ключом являются атрибуты Номер_сотрудника и Имя.

Отношение, приведенное к 1НФ, характеризуется как минимум двумя аномалиями – аномалией включения и аномалией модификации. Рассмотрим эти

аномалии на примере отношения S2.

Аномалия включения. Невозможно вставить в отношение кортеж, описывающий сотрудника, не имеющего детей, т.к. первичный ключ не может содер-

жать неопределенное значение.

Аномалия модификации. В общем случае одни и те же значения атрибутов ФИО_сотрудника, Аудитория, Телефон неоднократно дублируются в отно-

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

Вторая нормальная форма (2НФ).Отношение R находится во второй нормальной форме, если оно находится в 1НФ, и каждый неключевой атрибут

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

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

Пример. Преобразуем отношение S2 (представленное на рис.2.12.) ко 2НФ путем декомпозиции этого отношения по атрибуту Номер_сотрудника. Получим два

отношения S3 и S4, отвечающих требованиям 2НФ (рис.2.13.).

Отношение S3

Номер_

сотруд-

ника

Имя Возраст

31 Таня 13

31 Саша 6

44 Игорь 9

51 Олег 2

51 Таня 6

Отношение S4

Номер_

сотруд-

ника

ФИО_

сотрудника

Ауди-

тория

Телефон

31 Петров Т.Н. 326 217

44 Смирнов Ю.А. 412 258

51 Павлов И.С. 412 258

Рис.2.13. Пример отношений во 2НФ

Рассмотрим отношение S4. Его атрибуты Номер_сотрудника, Аудитория и Телефон находятся в транзитивной зависимости.

Номер_сотрудника →Аудитория →Телефон Хранение в отношении атрибутов, находящихся в транзитивной зависимости от ключа, порождает ряд трудностей. Рассмотрим их на примере атрибута Телефон [6]. Номер телефона характеризует аудиторию, что приводит к многократному дублированию сведений о телефоне для всех сотрудников, работающих в данной аудитории. Это приведет к аномалии модификации при смене номера телефона.

Третья нормальная форма (3НФ). Отношение R находится в третьей нормальной форме, если оно находится во 2НФ и каждый неключевой атрибут

нетранзитивно зависит от первичного ключа. Для приведения отношения S4 к 3НФ проведем декомпозицию схемы этого отношения.

Декомпозицией схемы отношения R = {A1, A2, …, An} называется замена схемы совокупностью схем = {R1, R2, …, Rk} подмножеств, таких, что

R1∪R2∪…∪Rk = R = {A1, A2, …, An} [11]. При этом не требуется, чтобы схемы Ri были непересекающимися.

Получим два отношения S5 и S6 (рис.2.14), находящихся в 3НФ и свободных от аномалий транзитивной зависимости.

Отношение S5

Номер_

сотруд-

ника

ФИО_

сотрудника

Ауди-

тория

31 Петров Т.Н. 326

44 Смирнов Ю.А. 412

51 Павлов И.С. 412

Отношение S6

Ауди-

тория

Телефон

326 217

412 258

Рис.2.14. Пример отношений в 3НФ

На практике приведение отношений к 3НФ часто оказывается достаточным и процесс нормализации, как правило, заканчивается [5]. В тех случаях, ко-

гда процесс нормализации необходимо продолжить можно использовать источники [3-5, 7-9, 11] для знакомства с механизмами нормализации более высоких

форм.Как видно из примеров, в процессе нормализации число отношений в схеме БД увеличивается. При проектировании промышленных баз данных число

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

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

зованные. Процитируем Д.Васкевича [10]: «Интеллект людей останавливается перед крепостью из 20-30 табличных соединений, а результат создания этих

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

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

Кортеж, соответствующий данной схеме отношения, - это множество пар {имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута, принадлежащего схеме отношения. "Значение" является допустимым значением домена данного атрибута (или типа данных, если понятие домена не поддерживается). Тем самым, степень или "арность" кортежа, т.е. число элементов в нем, совпадает с "арностью" соответствующей схемы отношения. Попросту говоря, кортеж - это набор именованных значений заданного типа.

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

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

Обычным житейским представлением отношения является таблица, заголовком которой является схема отношения, а строками - кортежи отношения-экземпляра; в этом случае имена атрибутов именуют столбцы этой таблицы. Поэтому иногда говорят "столбец таблицы", имея в виду "атрибут отношения". Когда мы перейдем к рассмотрению практических вопросов организации реляционных баз данных и средств управления, мы будем использовать эту житейскую терминологию. Этой терминологии придерживаются в большинстве коммерческих реляционных СУБД.

Реляционная база данных - это набор отношений, имена которых совпадают с именами схем отношений в схеме БД.

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

8. Реляційна модель. Класифікація обмежень цілісності.