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

5.3 Аномалии

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

Рассмотрим пример неполного соответствия ограничений целостности концептуальной и логической моделей. Пусть в концептуальной модели имеются данные, которые должны пониматься в четырехзначной логике со значениями истинности "ИСТИННО", "ЛОЖНО", "НЕ ОПРЕДЕЛЕНО" и "НЕ ЗНАЮ". Отображение этих данных в логическую модель сводится к представлению их в трехзначной логике. Два последних значения истинности при этом объединятся в одно. Как бы оно не интерпретировалось, значения "НЕ ОПРЕДЕЛЕНО" и "НЕ ЗНАЮ" окажутся неразделимыми. И тогда тонкая интерпретация ряда запросов окажется невозможной. Как, например, понять результат вычисления среднего дохода группы лиц, у которых в рамках концептуальной схемы атрибут "доход" может быть помечен метками "НЕ ИЗВЕСТЕН" и "НЕ УЧИТЫВАТЬ"? А вот вставке, удалению и обновлению записей здесь ничто не мешает.

Более точно, аномалии - это противоречия между концептуальной и логической схемами базы. Для их выявления следует рассматривать и прямое и обратное отображения между схемами. Аномалия может пониматься еще как несоответствие бизнес-правил правилам работы в модели, логической или, может быть, физической. В главе 12 будет предложен более общий подход, основанный на анализе смыслов данных.

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

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

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

В логической модели записать первое ограничение невозможно. Нет в ней понятия "дерево". Ничто не мешает, например, удалению записи о Петрове, превращающему дерево в лес. Имеем аномалию по удалению. Аномалия по обновлению наблюдается при переподчинении Петрова Иванову. Ничто не мешает изменить в третьей строке значения атрибута ТНН с 1 на 2, но в графе образуется цикл.

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

Ограничения концептуальной модели:

Попытка вставить запись (230, "Сидоров С.С", "2-31") удается, но первое ограничение целостности будет нарушено. Вам пример не кажется странным? Вроде бы номер телефона можно вычислить по номеру комнаты. Строку с номером телефона образуем так: берем первую цифру номера телефона, за ней записываем дефис, а в конце - оставшиеся две цифры номера комнаты. Все верно, только в реляционной модели значения атрибутов атомарные и описанное преобразование просто не допустимо.

Все сказанное в этом разделе может быть полностью перенесено на любые модели данных.

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

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

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

5.4 Определение первой нормальной формы. Правило приведения

Рассмотрим ненормализованную сущность "Подписка" с полями "Подписчик" и "Издание" (таблица 5.3). Таблица, представляющая это отношение, может быть создана вручную, если необходимо узнать, на какие издания вы подписываетесь. Ключевой столбец - "Подписчик". Понятно, если я напишу в первом столбце "Иванов", то во втором можно будет перечислить все издания, разделив их, например, запятой. Такая форма понятна человеку. Можно считать, что это ненормализованная таблица. На самом деле, она находится в, так называемой, непервой нормальной форме. Англоязычные исследователи любят такие "несерьезные" термины. Раз, кроме первой нормальной формы, существует что-то еще, пусть будет называться непервой формой.

Почему ненормализованные отношения неудобны? Вспомните, что значения атрибутов считаются атомарными. Это означает, что их нельзя препарировать, разделяя на составные части. Например, невозможно определить, что Иванов подписывается на Известия, но можно найти тех, кто подписывается сразу на Правду, Известия и Коммерсант (но не на Известия, Правду, и Коммерсант).

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

Использованный способ нормализации до 1НФ называется выравниванием таблицы.

Иногда говорят, что нормализация необходима для минимизации объема базы. Но при переходе к 1НФ мы увеличили избыточность. На самом деле, нормализация нужна для устранения аномалий.

Остается дать определения. Их будет два: 1НФ через атрибуты, 1НФ через ключи.

Определение (1НФа (через атрибуты)). Сущность (отношение) находится в 1НФ, если значения всех ее атрибутов атомарны.

Определение (1НФк (через ключи)). Сущность (отношение) находится в 1НФ, если она имеет ключ.

На самом деле, из определения через атрибуты следует определение через ключи.

Утверждение. Из определения 1НФа следует определение 1НФк.

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

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

Для того, чтобы получить правила приведения к 1НФ рассмотрим пример (рисунок 5.5). Кстати, почему я все время отсылаю вас к примерам? Потому что для человека мышление по образцам более естественно, чем мышление с помощью логики.

Итак, у нас с вами некоторая сущность "Сотрудник". Название отношения или сущности всегда задается в единственном числе, хотя экземпляров сущности может быть много. "Табельный номер" - ключ. Имеются атрибуты: "Фамилия, Имя, Отчество", "Должность", "Специальность1", "Специ-альность2", "Оклад", "Телефон1", "Телефон2", "Телефон3", "Дата зачисления или увольнения". Что в этом отношении не хорошо? А кто сказал, что специальностей не больше двух? А, если их три, что делать? А если телефонов четыре?

Есть еще атрибут "Дата зачисления или увольнения". Как узнать какая дата записана, если она одна? Понятно, можно написать: "1 марта 2010 уволен". Но, наверное, такие вольности приведут к неоправданному усложнению процедурной части программы из-за неатомарных значений.

Давайте сделаем несколько оправданных предположений. Разумнее атрибут "Дата зачисления и увольнения" заменить на два атрибута: "Дата зачисления" и "Дата увольнения" Раз специальностей и телефонов у человека может быть много, давайте считать, что это отдельные сущности. Выделим их, как показано на рисунке 5.2 вверху справа. Число экземпляров у сущностей "Специальность" и "Телефон" может быть любым.

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

Описанный способ приведения к 1НФ называется выделением в отдельные отношения.

Теперь будут понятны следующие правила.

5.4.1 Правила приведения к первой нормальной форме

Для многозначных атрибутов возможны два пути:

Для составных и повторяющихся атрибутов:

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

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

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

5.5 Замечание о непервой нормальной форме (Н1НФ, NFNF, NF)

Определим непервую нормальную форму как первую нормальную форму (1НФ) удовлетворяющую условию 1НФк, но не удовлетворяющую условию 1НФа. Для обозначения непервой нормальной формы используют аббревиатуры Н1НФ, NFNF, и даже NF2.

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

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

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

Оказывается могут существовать зависимости не от всего ключа, а от его части. Посмотрите какое, может быть необычное для вас, отношение "Доходы_совместителей" со столбцами ИНН, ФИО, Организация, Зарплата изображено на рисунке 5.3. Оно описывает доходы совместителей, то есть людей, работающих в двух или более организациях. В первичный ключ входят поля ИНН и Организация, иначе непонятно было бы, где человек с этим ИНН получает зарплату. Имеется одна особенность: поле ФИО, зависящее от всего ключа, кроме того, функционально зависит от части ключа - ИНН - , так как фамилия, имя и отчество однозначно определяются по ИНН.

Теперь можно переходить к определению второй нормальной формы (2НФ, 2NF).

Определение (Полнота функциональной зависимости). Если набор атрибутов $$В=\{B_j\}$$ зависит от всего набора атрибутов $$A=\{A_i\}$$, но не зависит от части этого набора, то говорят, что функциональная зависимость $$A\to B$$ полная.

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

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

Эти определения эквивалентны, в отличие от определений 1НФ.

Замечание. Если единственный ключ отношения в ШФ является простым (не конкатенированным), то отношение находится в 2НФ по той простой причине, что невозможно выделить часть ключа.

Правила приведения, как и в ШФ, сначала рассмотрим на примере. Имеется (рисунок 5.4 вверху) ненормализованная сущность под названием "Проект". Ее ключ образуют два поля "Наименование_проекта" и "Таб_номер_руководителя". Неключевые поля "Дата_начала" (проекта), "Дата завершения" (проекта), "Фамилия", "Имя", "Отчество" и "Должность" (руководителя проекта). Поскольку фамилия, имя, отчество и должность руководителя проекта зависят функционально от табельного номера, предполагаем, что внутри спрятана сущность "Руководитель" и выделяем ее (рисунок 5.7 справа вверху). Что останется в сущности "Проект"? Атрибуты "Наименование_проекта", "Дата начала" и "Дата завершения".

Остается создать связь. Заметим, что экземплярами изолированной сущности "Руководитель_проекта" могут быть любые сотрудники. Но нас интересуют только выбранные из них руководители проектов. Отсюда делаем вывод о том, что сущность "Руководитель_проекта" слабая и потому связь идентифицирующая (рисунок 5.7 слева внизу). В последнем варианте диаграммы (рисунок 5.7 справа внизу) атрибут "Табельный номер" сущности "Проект" заменен на "Табельный_номер_рук" Зачем? В исходной сущности непонятно, чей это табельный номер. А вдруг проекты тоже имеют табельные номера. В сущности "Руководитель" понятно, что "Табельный номер" принадлежит руководителю. Такого рода уточнения не обязательны, но могут быть полезными.

Правила приведения ко второй нормальной форме.

5.7 Третья нормальная форма. Связь третьей и второй нормальных форм

Оказывается, что, кроме функциональной зависимости всех атрибутов от ключа и зависимостей неключевых атрибутов от части ключа, могут еще существовать зависимости неключевых атрибутов от других неключевых атрибутов. Рассмотрим сущность "Сотрудник" с атрибутами "Табельный номер", "Фамилия", "Имя", "Отчество", "Должность", "Оклад", изображенную на рисунке 5.5 слева. Пусть в нашей организации оклад определяется только должностью. Иначе говоря, существует функциональная зависимость, действующая из атрибута "Должность" в атрибут "Оклад". По теореме Хиса атрибуты "Должность" и "Оклад" войдут в новую сущность. Назовем ее "Должность". Из старой сущности "Сотрудник" вычеркнем значение функции "Оклад", а аргумент функции атрибут "Должность" оставим.

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

Предварительно определим две разновидности функциональных зависимостей (ФЗ): транзитивную и прямую.

Определение (транзитивная и прямая ФЗ). Функциональная зависимость $$А\to С$$ называется транзитивной, если найдется атрибут или набор атрибутов $$В$$, отличный от $$А$$ и $$С$$, такой что $$А \to В$$, $$В \to С$$ - функциональные зависимости. Если не существует транзитивной зависимости, то функциональная зависимость называется прямой.

Теперь можно дать два эквивалентных определения третьей нормальной

формы. (3НФ, 3NF).

Определение (3НФк (через ключи)). Отношение в 1НФ находится в 3НФ, если все его атрибуты прямо зависят от ключа.

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

Внимательный читатель должен сразу же спросить: нет ли ошибки в определениях? Не следовало бы начинать определения словами "отношение в 2НФ ..."? Ответ дает следующая теорема.

Теорема 5.1. Если отношение находится в 3НФ, то оно находится во 2НФ.

Доказательство. Предварительно сформулируем два отрицательных высказывания, с которыми будем работать:

Выбор схемы доказательства: Оказывается, достаточно показать, что из частичной зависимости следует транзитивная зависимость. Это будет означать, что из нарушения условия 2НФ следует нарушение условие 3НФ. В самом деле, по определению импликации $$x\Rightarrow y \equiv (\rceil x)\vee y$$. Докажем, что ((3НФ) $$\Rightarrow$$ (2НФ)) $$\equiv\rceil$$ (2НФ) $$\Rightarrow \rceil$$ (3НФ) . В самом деле, в обозначениях $$х$$ и $$у$$:$$(\rceil x \Rightarrow \rceil y) \equiv(\rceil(\rceil x) \vee (\rceil y)) \equiv x \vee(\rceil y) \equiv(\rceil y) \vee x \equiv y \Rightarrow x$$.

Доказательство: Пусть $$\rceil$$2НФ, то есть найдется непервичный атрибут $$А$$, который частично зависит от ключа $$К$$. Это означает, что $$\exists K' \subset K: K'\to A$$. Конечно, не существует зависимости

$$K' \to K$$, иначе $$K'$$ было бы ключом, ведь ключ по определению минимален. Итак, существуют$$f1: K \to K'$$, $$f2: K' \to A$$ то есть цепочка $$f1,f2$$ транзитивная, ч.т.д.

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

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

Правило приведения к третьей нормальной форме.

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

5.8 Сущности с пересекающимися ключами. Нормальная форма Бойса-Кодда. Определение. Правило приведения

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

На рисунке 5.7 приведен пример сущности с несколькими непересекающимися ключами: "Табельный номер", "ИНН", "ФИО", "Дата_рождения", "Паспорт_данные". Как всегда, выбираем один из ключей в качестве первичного, а оставшиеся будут альтернативными ключами.

Сущности с пересекающимися ключами интереснее. Рассмотрим в качестве примера сущность "Поставка" (таблица 5.5).

В нем имеется два пересекающихся ключа: РК1 = {Код_поставщика, Код_товара} и РК2 = {Наим_поставщика, Код_товара}. Поскольку неключевой атрибут "Ед_измерения" связан функционально с атрибутом "Код_то-вара", являющегося частью обоих ключей, то для приведения к 2НФ выделяем сущность "Товар" (таблица 5.6)

Атрибут "Ед_измерения" играет особую роль. Он раскрывает какой-то смысл атрибута "Код_товара". Если не учитывать семантику, то можно, например, посчитать осмысленным вопрос "Какое количество товара поставлено?" относящийся к сущности "Поставка". Но ведь товары в сущности "Поставка" имеют разные единицы измерения. Поэтому осмысленно только суммирование товаров с одной единицей измерения, да и то не всегда. Например, объединение пар носков и пар кроликов не всегда может быть оправданным. Подробнее смыслами мы будем заниматься в главе 12.

Заметим, что выделение сущности "Товар" не имеет никакого отношения к приведению в НФБК. Просто был повод еще раз вспомнить о смыслах данных.

Рассмотрим созданную сущность "Поставка_1" (таблица 5.7). Поскольку неключевой атрибут "Количество" единственный, то не существует зависимостей неключевых атрибутов от других неключевых атрибутов и сущность находится в третьей нормальной форме.

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

Ключи у сущности "Поставка_1" те же, что у сущности "Поставка":

РК1 = {Код_поставщика, Код_товара}

РК2 = {Наим_поставщика, Код_товара} Выпишем сначала все оставшиеся функциональные зависимости:

РК1 $$\to$$ Наим_по став шика, Количество

РК2 $$\to$$ Код_поставщика, Количество

РК1 $$\to$$ Наим_по став шика,

РК2 $$\to$$ Код_поставщика

Код_по ставшика $$\to$$ Наим_поставщика

Наим_поставщика $$\to$$ Код_поставщика

Отмеченная аномалия устраняется выделением отношений "Поставщик" (таблица 5.8) и "Поставка_2" (таблица 5.9).

Перейдем к определениям, чтобы понять, как получать сущности в НФБК.

Любое расширение потенциального ключа есть ключ, но не минимальный ключ. Будем называть его суперключом.

Определение (Тривиальная функциональная зависимость). Функциональная зависимость $$f:A\to B$$ тривиальна тогда и только тогда, когда правая часть функциональной зависимости является подмножеством, не обязательно собственным, левой части, то есть когда $$B \subseteq A$$.

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

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

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

В нашем примере аргумент функции не является суперключом у функций

Код_поставщика $$\to$$ Наим_поставщика

Наим_поставщика $$\to$$ Код_поставщика

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

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

Примем без доказательства простое утверждение: Любое отношение с двумя атрибутами находится в НФБК.

5.9 Нормальная форма схемы. Сходимость нормализации

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

Если, например, говорят, что схема базы находится в 2НФ, это означает, что все сущности преобразованы, по крайней мере, к 2НФ. При этом некоторые могут быть и в 3НФ и в НФБК.

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

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

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

Вот, как видите, при таком нашем несложном подходе мы все-таки были достаточно корректны, хотя, основные рассуждения велись не формально - с примерами и мнемониками.

То, что процесс нормализации по Хису в теории всегда сходится, не означает, что сходится любой процесс проектирования. Когда может случиться такая неприятность? При неточностях в задании (спецификации проекта), когда вы в процессе работы его уточняете. При выяснении подробностей еще раз уточняете, то есть, когда задание, как говорят, "плывет". Утверждение о сходимости нормализации относится только к такому случаю, когда исходное задание не меняется.

5.10 Простой способ получения отношений сразу в третьей нормальной форме и уточнения до НФБК

5.11 Многозначные зависимости. Теорема Фейгина

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

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

Многозначные зависимости (multi-valued dependency) возникают, когда необходимо привести к первой нормальной форме отношение с независимыми многозначными атрибутами, имеющими несколько значений на пересечении строки и столбца. Пусть имеется два таких атрибута $$Y$$ и $$Z$$. Тогда для получения 1НФ необходимо для каждого набора значений остальных атрибутов $$X$$ повторить эту строку для каждого сочетания атомарного значения $$Y$$ с каждым атомарным значением $$Z$$.

Образуется многозначная зависимость, в которой:

Многозначную зависимость принято обозначать $$X\twoheadrightarrow Y|Z$$, хотя можно было бы указать наличие двух существующих одновременно обычных функциональных зависимостей $$X\to Y$$ и $$X\to Z$$. Иногда обозначают многозначную зависимость $$X\twoheadrightarrow Y$$ или $$X\twoheadrightarrow Z$$.

Определение. MV-зависимость $$X\twoheadrightarrow Y$$ называется тривиальной если$$X \supseteq Y$$, либо $$X\cup Y=\{X,Y,Z\}$$.

Рассмотрим еще одно отношение с многозначными зависимостями (рисунок 5.17). Обозначения: 3 - завод, Т - товар, М - магазин. Выполняется условие: каждый товар из группы товаров продается во все магазины из некоторой группы магазинов. При этом и в группе товаров и в группе магазинов может быть один экземпляр. Исходное отношение ЗТМ разлагается на отношения ЗТ и ЗМ. В отличие от первых четырех нормальных форм связи между созданными отношениями (ЗТ и ЗМ) отсутствуют.

$$ЗТМ: \begin{array}{|c|c|c|} \hline З Т М \\ \hline З_1 Т_1 М_1 \\ \hline З_1 Т_1 М_2 \\ \hline З_1 Т_1 М_3 \\ \hline З_1 Т_2 М_1 \\ \hline З_1 Т_2 М_2 \\ \hline З_1 Т_2 М_3 \\ \hline З_2 Т_2 М_2 \\ \hline \end{array}$$

$$ЗТ: \begin{array}{|c|c|} \hline З Т \\ \hline З_1 Т_1 \\ \hline З_1 Т_2 \\ \hline З_2 Т_2 \\ \hline \end{array}$$

$$ЗМ: \begin{array}{|c|c|} \hline З М \\ \hline З_1 М_1 \\ \hline З_1 М_2 \\ \hline З_2 М_3 \\ \hline З_2 М_2 \\ \hline \end{array}$$

Определение (MV-зависимость). Пусть $$r$$ - отношение, а $$X, У, Z$$ - непересекающиеся множества его атрибутов. Атрибуты $$Y$$ и $$Z$$ многозначно зависят от $$X$$ (обозначение $$X\twoheadrightarrow Y|Z$$) если из того, что в отношении $$r$$ содержатся кортежи $$r_1=(x,y,z_1)$$ и $$r_2=(x,y_1,z)$$, следует, что в отношении $$r$$ содержится также кортеж $$r_3=(x,y,z)$$.

По симметрии определения в $$r$$ содержится и кортеж$$r_4=(x,y_1,z_1)$$. Атрибуты $$Y$$ и $$Z$$ как бы симметричны по отношению к $$X$$.

При наличии MV-зависимости кортежи обязаны вставляться и удаляться одновременно целыми наборами.

Теорема Фейгина (R. Fagin) играет для многозначных зависимостей ту же роль, что теорема Хиса для функциональных зависимостей. Примем ее без доказательства.

Теорема Фейгина. Пусть $$X,Y,Z$$ - три непересекающиеся подмножества атрибутов $$R(X, У, Z)$$ отношения $$r$$. Декомпозиция отношения г на проекции на множества атрибутов $$\{X, Y\}$$ и $$\{X, Z\}$$ будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость $$X\twoheadrightarrow Y|Z$$.

Частный случай. Если зависимость $$X\twoheadrightarrow Y|Z$$ является тривиальной, т.е. существует только одна из функциональных зависимостей $$X\to Y$$ или$$X\to Z$$, но не задана независимость $$Y$$ и $$Z$$, то получаем теорему Хиса.

5.12 Четвертая нормальная форма. Правило приведения

Определение (4НФ). Отношение находится в четвертой нормальной форме, если оно находится в нормальной форме Бойса-Кодда и не содержит нетривиальных многозначных зависимостей.

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

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

Полученные после декомпозиции отношения никак не связаны между собой.

Теперь к правилам приведения до НФБК, изложенным в разделе 5.10, можно добавить только что сформулированное правило, может быть, уточнив, что возможен вариант использования не 1НФ а Н1НФ.

На рисунке 5.8 приведена мнемоника для правил приведения к первым пяти нормальным формам. Считалочка для запоминания: "Ключ, весь ключ и ничего кроме ключа". Как присяга - правду, всю правду и ничего кроме правды! Крестом отмечены виды функциональных зависимостей, которые должны быть устранены.

5.13 Зависимости соединения и пятая нормальная форма. Правило приведения

Бегло рассмотрим дальнейшее обобщение понятия функции до зависимости проекция-соединение. На его основе определим пятую нормальную форму и правила приведения к ней.

4НФ не дает полного решения вопроса о декомпозиции отношений без потерь информации. Причина в том, что рассмотрения декомпозиции только на два отношения недостаточно. Может существовать нетривиальная декомпозиция на три отношения, но не существовать такой декомпозиции на два отношения.

Ниже на рисунке 5.9 приведен пример отношения, которое нельзя восстановить после разложения на две части, но например, соединение, $$r_{12}\ join\ r_3=(r_1 \ join\ r_2)\ join\ r_3 $$ восстанавливает отношение. Оказалось необходимым использование соединения трех проекций.

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

Определение (зависимость соединения). Пусть $$r$$- отношение на множествах атрибутов $$A_1,A_2,\dots,A_n$$, может быть пересекающихся. Отношение $$r$$ удовлетворяет зависимости соединения тогда и только тогда, когда оно равносильно соединению всех своих проекций на подмножества атрибутов $$ A_1,A_2,\dots,A_n$$, то есть

$$R=(proj\{A_1\}r)\ join\ (proj\{A_2\}r)\ join\ \dots\ join\ (proj\{A_n\}r$$.

Обозначение зависимости соединения $$*(A_1,A_2,\dots,A_n)$$.

Зависимость соединения обобщает MV-зависимости. Если в отношении имеется многозначная зависимость, то имеется и зависимость соединения. Обратное неверно.

Связь расширений функциональной зависимости определяет

Теорема 5.2. Отношение $$r$$ со схемой $$R(X, Y, Z)$$ удовлетворяет зависимости соединения $$*(XY,XZ)$$ тогда и только тогда, когда имеется многозначная зависимость $$X\twoheadrightarrow Y|Z$$ .

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

Определение (тривиальная зависимость соединения). Зависимость $$*(A_1,A_2,\dots,A_n)$$ называется тривиальной зависимостью соединения, если выполняется одно из условий:

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

Правило приведения к 5НФ: Если в отношениях обнаружены нетривиальные зависимости соединения, то для их исключения необходимо провести декомпозицию на выделенные подмножества атрибутов $$A_1,A_2,\dots,A_n$$.

5.14 Понятие о нормальной форме домен-ключ

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

Определение (НФДК, DKNF). Отношение находится в нормальной форме домен-ключ, если каждое ограничение отношения есть логическое следствие определений ключей и доменов.

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

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

Домен - это множество допустимых значений. Он содержит:

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

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

5.15 Понятие о денормализации

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

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

Как правило, денормализация ускоряет запросы, но замедляет манипулирование данными и усложняет, может быть существенно, процедурную часть приложения.

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

Пусть обнаружено, что запросы к проблемной таблице TAB₁ обращаются чаще к коротким столбцам 1, 2, 5, 6 шириной, например, по 5 байт, чем к широким столбцам 3 и 4 шириной 12 кбайт и 64 кбайт, соответственно. Ключ образуют столбцы 1 и 2. Понятно, что для извлечения 20-ти байт приходится работать со всей строкой шириной примерно 76 кбайт. Это сильно тормозит процесс.

Проведем денормализацию. Разделим таблицу на две - TAB₁₁, включающую широкие столбцы 3, 4, и TAB₁₂ с узкими столбцами. Ключ у новых таблиц тот же. Скорость запросов возрастет, так как теперь не нужно извлекать "лишних" 76 килобайт на каждую строку. Однако, теперь вместо одной команды вставки, удаления и обновления исходной таблицы необходимо выполнять по две соответствующих команды для TAB₁₁ и TAB₁₂, причем обе команды должны быть выполнены обязательно. В главе 6 станет понятно, что для этого необходимо вставить их в транзакцию.

Если поток запросов изменится, то выполненное преобразование схемы может оказаться бесполезным и даже вредным.

5.16 Основные алгоритмы главы

Алгоритмы нормализации, основанные на теореме Хиса:

1НФ

2НФ

3НФ

НФБК

Алгоритм нормализации, основанный на теореме Фейгина:

4НФ

Связи между образованными сущностями: