Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/SQL/CelkoJ/01h002.shtml

Глава 2. Нормализация

       Реляционная модель и ее нормальные формы впервые были определены Коддом (Codd, 1970), а затем их концепции были развиты другими исследователями. Термин "нормализованные отношения" был позаимствован им из политического жаргона того времени. Область математики, называемая отношениями, занимается отображениями между множествами, определяемыми с помощью исчисления предикатов, основанного на формальной логике. Точно так же, как и в случае алгебраических выражений, один и тот же реляционный оператор может иметь несколько форм; термин "нормальные формы" относится к некоторым определенным образом описанным конструкциям. Цель создания нормальных форм — избежать аномалий данных, возможных в ненормализованных таблицах. Такие аномалии проще всего объяснить на примере, но сначала введем несколько новых терминов. Предикатом (predicate) называется оператор вида А(Х) — он означает, что X имеет свойство А. Например, оператором предиката является выражение "Джон родом из Индианы". Джон — это субъект, а "родом из Индианы" — предикат. Отношением (relation) называется предикат с двумя или несколькими субъектами. Пример отношения — выражение "Джон и Боб — братья". Распространенным способом визуального представления реляционных операторов является таблица, в которой столбцы представляют собой атрибуты отношения, а каждая строка — конкретный реляционный оператор. Определяя реляционную модель, Кодд создал 13 правил представления отношения в виде таблицы.
       0. Фундаментальное правило. Для того чтобы система имела право называться системой управления реляционными БД, она должна управлять БД исключительно своими реляционными средствами. SQL не слишком строго следует этому правилу, так как часто с данными можно работать процедурными методами.
       1. Правило представления информации. Вся информация должнабыть представлена в БД одним и только одним способом — в виде значений на пересечении столбцов и строк таблицы. SQL следует этому правилу.
       2. Правило гарантированного доступа. Фактически здесь сформулировано фундаментальное требование для первичных ключей. В соответствии с ним каждое индивидуальное скалярное значение в БД должно быть логически адресуемо путем указания имени содержащей таблицы, имени содержащего его столбца и значения первичного ключа содержащей его строки. SQL следует этому правилу в случае таблиц, содержащих первичный ключ, но не требует наличия такого ключа в таблице.
       3. Правило систематической обработки NULL-значений. СУБД должна поддерживать представление отсутствующей и неприемлемой информации таким регулярным способом, чтобы он позволял отличить ее от всех остальных значений и не зависел от типа данных. Необходимо также, чтобы СУБД могла манипулировать таким представлением. В SQL NULL-значение применяется для обозначения и отсутствующей, и неприемлемой информации, хотя Кодд рекомендовал использовать два отдельных обозначения.
       4. Активный каталог, основанный на реляционной модели. Система должна поддерживать интерактивный встроенный реляционный каталог, доступный авторизованным пользователям посредством стандартного языка запросов. SQL соответствует такому правилу.
       5. Правило полного подъязыка данных. Система должна поддерживать хотя бы один реляционный язык, который: а) имеет линейный синтаксис; b) может использоваться как интерактивно, так и в составе прикладных программ; с) поддерживает операции определения данных (в том числе определения представлений), манипулирования данными (не только их чтения, но и изменения), ограничения целостности и безопасности, а также операции управления транзакциями (начала, завершения и отката). SQL прекрасно соответствует этому пункту, так как все указанные операции можно выполнить средствами DML (Data Manipulation Language, язык манипулирования данными).
       6. Правило обновления представлений. Все теоретически обновляемые представления должны обновляться средствами системы. SQL недостаточно хорошо следует этому правилу, в нем реализован самый безопасный сценарий. Обновление представлений — сложная проблема.
       7. Высокоуровневые операции вставки, обновления и удаления. Система должна поддерживать выполнение операторов INSERT, UPDATE и DELETE в режиме последовательной обработки наборов записей.Язык SQL соответствует указанному правилу.
       8. Физическая независимость данных. Это правило понятно без объяснений. Любой реальный продукт характеризуется некоторой физической зависимостью, но SQL соответствует данному правилу лучше большинства языков программирования.
       9. Логическая независимость данных. Это правило также понятно без объяснений, и SQL прекрасно ему соответствует.
       10. Независимость ограничений целостности. Ограничения целостности необходимо определять отдельно от прикладных программ и хранить в каталоге. Должна существовать возможность изменения таких ограничений без воздействия на существующие приложения.SQL поддерживает это правило.
       11. Независимость от распределения данных. Существующие приложения должны продолжать успешно работать: а) при переходе на распределенную версию СУБД; b) при перераспределении уже распределенных данных. Мы лишь приступили к переходу на распределенную версию SQL, так что пока рано говорить, поддерживает SQL это правило или нет.
       12. Правило запрета обходных путей. Если система имеет низкоуровневый интерфейс (с последовательной построчной обработкой), он не может быть использован для отмены или обхода реляционных ограничений безопасности и ссылочной целостности. Стандарт SQL-92 эффективно поддерживает это правило.
       Кодд описал еще девять структурных характеристик, три характеристики целостности и 18 характеристик манипулирования данными, все они также являются обязательными. Во второй версии реляционной модели он расширил первоначальный список из тринадцати правил до 333. Однако их перечисление займет слишком много места, поэтому предлагаю вам ознакомиться с ними самостоятельно.
       Нормальные формы представляют собой попытку гарантировать, что вы не разрушите истинные и не введете ложные данные в БД. Один из способов избежать ошибок — представлять любой факт в БД только один раз; если он появляется более одного раза, один из экземпляров, скорее всего, будет ошибочным. Человек с двумя часами на руке не сможет понять, сколько сейчас времени.
       Такой процесс проектирования таблицы называется нормализацией. Он хорошо понятен, но может быть достаточно сложным. Можно воспользоваться CASE-средством, но для его использования необходимо хотя бы минимальное представление о теоретических основах.

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

       Нормальная форма представляет собой способ классификации таблицы на основе содержащихся в ней функциональных зависимостей (functional dependencies, FD). Функциональная зависимость означает, что, имея значение одного атрибута, я всегда смогу определить значение другого. В реляционной теории FD выражается стрелкой между двумя атрибутами, например зависимость А —> В означает, что А определяет В. Зная номер сотрудника, я смогу определить его имя; зная шифр детали, могу указать ее вес и цвет, и т.д.
       Многозначная зависимость означает, что, имея значение одного атрибута, я всегда могу определить множество значений другого атрибута. В реляционной теории она обозначается стрелкой с двумя остриями между двумя атрибутами. Например, зависимость А —> В означает "А определяет много В". Зная имя преподавателя, я смогу получить список его студентов; зная шифр детали, я смогу определить шифры деталей, входящих в ее состав, и т.д.

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

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

Classes = RECORD
          course:  ARRAY [1:7] OF CHAR; 
         section:  CHAR; 
            time:  INTEGER; 
            room:  INTEGER;
        roomsize:  INTEGER;
       Professor:  ARRAY [1:25] OF CHAR;
        Students:  ARRAY [1:classsize]
                   OF RECORD
                      student ARRAY [1:25] OF CHAR;
                        major ARRAY [1:10] OF CHAR;
                        grade CHAR;
                   END;
        END;

       Эта таблица не находится в основной нормальной форме реляционных баз данных. Первая нормальная форма (1NF) означает, что таблица не содержит повторяющихся групп. Следовательно, каждый столбец содержит скалярные (или нормальные) значения, а не массивы, списки или другие подобные структуры. Если разработчик SQL не включил в него массивы или другие расширения, все таблицы SQL обязательно будут находиться в 1NF. Приведенную ранее запись можно перевести на язык SQL:

CREATE TABLE Classes
   (course     CHAR(7)  NOT NULL,
    section    CHAR(l) NOT NULL,
    time       INTEGER NOT NULL,
    room       INTEGER NOT NULL,
    roomsize   INTEGER NOT NULL,
    professor  CHAR(25) NOT NULL,
    student    CHAR(25) NOT NULL,
    major      CHAR(10) NOT NULL,
    grade      CHAR(1) NOT NULL);

       Такая таблица уже будет доступна средствами SQL. Строку в ней можно определить по комбинации курса, раздела курса и студента, так что мы получаем ключ. Обратите внимание: мы удалили массив Students, природу которого изменить не удалось. Это способно привести к неприятностям.
       Если профессор Джонс с факультета математики умрет, мы должны будем удалить все его строки из таблицы Classes. При этом будет удалена информация обо всех посещавших этот курс студентах, но, возможно, не все они захотят быть автоматически отчисленными. Таким образом, я удаляю из базы данных больше одного факта, это называется аномалией удаления.
       Если студент Уилсон захочет поменять посещаемый им курс математики у профессора Джонса на курс английского языка, то профессор Джонс появится в списке инструкторов факультетов математики и английского. Таким образом, я не могу по отдельности изменить ни одного факта. Любая такая попытка приведет к вводу ложной информации, это называется аномалией обновления.
       При открытии нового факультета, на котором еще нет студентов, мы не сможем включить в его таблицы данные о только что нанятых профессорах, пока не получим сведений об аудиториях и студентах, необходимых для заполнения строки. Я не могу по отдельности вставить ни одного факта, это называется аномалией включения.
       С такой таблицей связаны и другие проблемы, но достаточно и этих. Существуют способы обойти некоторые из них, не меняя таблиц. Так, в таблицы можно разрешить включать NULL-значения. Можно написать процедуры, проверяющие наличие в них ложных данных. Однако с усложнением данных и связей между ними положение ухудшается. Кардинальное решение заключается в разбиении таблицы на несколько более простых, каждая из которых представляет одну связь или простой факт.

2.2.1. Комментарий относительно повторяющихся групп

       В соответствии с определением 1NF таблица не содержит повторяющихся групп, и все столбцы скалярные. Это означает отсутствие массивов, связанных списков, вложенных таблиц и структур записей, характерных для других языков программирования. Как уже говорилось, в SQL добиться этого очень просто, поскольку массивы и структурированные данные в нем просто не поддерживаются.
       Однако такое правило можно обойти, воспользовавшись группой столбцов, в которой все столбцы имеют одну и ту же семантику, т.е. представляют один и тот же атрибут в таблице. Рассмотрим таблицу сотрудника и его детей:

CREATE TABLE Employees 
   (empno    INTEGER NOT NULL,
    empname  CHAR(30) NOT NULL,
    child1   CHAR(30), birthday1 DATE, sex1 CHAR(1),
    child2   CHAR(30), birthday2 DATE, sex2 CHAR(1),
    child3   CHAR(30), birthday3 DATE, sex3 CHAR(1),
    child4   CHAR(30), birthday4 DATE, sex4 CHAR(1));

       Эта структура напоминает структуру существующих файловых систем в Cobol и других языках третьего поколения. Сведения о дне рождения и поле каждого ребенка входят в состав повторяющейся группы и потому нарушают 1NF — в SQL мы получили массив из четырех элементов. В большинстве книг ничего не говорится о том, плохо это или хорошо, мы же подробно рассмотрим данную проблему в главе 25 "Структуры массивов в SQL".
       Допустим, моя таблица содержит количество продукции, проданной за каждый месяц конкретного года, и первоначально она выглядела так:

CREATE TABLE Abnormal
   (product   CHAR(10) NOT NULL PRIMARY KEY,
    bin_01    INTEGER,
    bin_02    INTEGER,
. . . . .
    bin_12    INTEGER); 

       Теперь я пытаюсь привести ее в более нормализованную форму:

CREATE TABLE Normal
  (product   CHAR(10) NOT NULL,
   bm_nbr    INTEGER NOT NULL,
   qty       INTEGER NOT NULL,
PRIMARY KEY (product,bin_nbr));

Можно использовать оператор:

INSERT INTO Normal
  SELECT product, 1, bm_01
    FROM Abnormal WHERE bin_01 IS NOT NULL
UNION ALL 
  SELECT product, 2, bin_02
    FROM Abnormal WHERE bm_02 IS NOT NULL
. . . . .
UNION ALL
  SELECT product, 12, bm_12
    FROM Abnormal WHERE bin_12 IS NOT NULL;

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

2.3. Вторая нормальная форма (2NF)

       Таблица находится во второй нормальной форме (2NF), если она не содержит частичных функциональных зависимостей. Если для столбцов X и Y первый является ключом, a Z представляет собой правильное подмножество X, то ситуация, когда Z —> Y, невозможна. Неформально можно сказать, что такая таблица находится в 1NF и содержит ключ, определяющий в ней все неключевые атрибуты.
       Допустим, наши пользователи говорят, что знать студента и курс достаточно, чтобы определить раздел (так как студент не может записаться более чем на один раздел курса) и оценку. Это означает следующее: (student, course) —> (section, grade).
       Проведя дополнительный анализ, мы обнаруживаем, что (student —> major) — студенты имеют только одну специализацию. Поскольку студент входит в состав ключа (student, course), мы обнаруживаем, что получили частичную зависимость. Таким образом, необходимо сделать следующее разложение:

CREATE TABLE Classes (course, section, room, roomsize, time, professor, 
PRIMARY KEY (course, section));
CREATE TABLE Enrollment (student, course, section, grade)
PRIMARY KEY (student, course));
CREATE TABLE Students (student, major) PRIMARY KEY (student));

       На этом этапе мы получили 2NF. Все атрибуты зависят от полного ключа в таблице. При любом изменении обновление следует внести только в одном месте. Более того, студент не может записаться на несколько разделов одного курса, так как мы изменили ключ в таблице Enrollment. К сожалению, проблемы все еще сохраняются.
       Обратите внимание: значение столбца roomsize зависит не только от ключа таблицы Classes, но и от аудитории. При перемене аудитории для занятий, возможно, понадобится изменить ее размер. То же самое относится и к ремонту аудитории.

2.4. Третья нормальная форма (3NF)

       Эти проблемы решает следующая нормальная форма. Таблица находится в третьей нормальной форме (3NF), если для всех зависимостей X —> Y (где X и Y — столбцы таблицы) X является ключом или Y входит в состав возможного ключа. Возможный ключ (candidate key) — это уникальный набор столбцов, идентифицирующих каждую строку таблицы; вы не можете удалить столбец из возможного ключа таблицы, не нарушив его уникальности. Поскольку частичная зависимость является типом транзитивной зависимости, это означает, что таблица также находится и в 2NF. Неформально можно сказать, что все неключевые столбцы определяются ключом, полным ключом и ничем, кроме ключа.
       Форма 3NF характеризуется отсутствием транзитивных зависимостей. Последняя представляет собой такую ситуацию: если в таблице со столбцами А, В и С имеют место зависимости (А —> В) и (В —> С), то верно утверждение (А —> С). В нашем примере мы видим зависимости (course, section) —> room и room —> roomsize. Это не простая транзитивная зависимость, так как в ней участвует только часть ключа, но основные принципы выполняются и в ней. Чтобы перевести наши таблицы в 3NF и решить проблему размера комнаты, следует осуществить показанное ниже разложение:

CREATE TABLE Rooms (room, roomsize, PRIMARY KEY (room));
CREATE TABLE Classes (course, section, room, time,
PRIMARY KEY (course,   section));
CREATE TABLE Enrollment (student, course, section, grade, 
PRIMARY KEY (student, course));
CREATE TABLE Students (student, major,PRIMARY KEY (student));

       Тем не менее утверждение, что форма 3NF не содержит транзитивных зависимостей, ошибочно. Как уже упоминалось, если X —> Y, то X не может быть ключом, если Y входит в состав возможного ключа. В нашем примере транзитивная зависимость сохраняется — (room, time) —> (course, section), но поскольку правая ее часть представляет собой ключ, технически это 3NF. Нежелательное поведение такой структуры заключается в том, что в одной аудитории можно назначить проведение нескольких курсов одновременно.

2.5. CASE-средства для нормализации

       Большинство CASE-средств могут генерировать схему, все таблицы которой находятся в 3NF. Исходные данные они получают из ER-диаграммы (диаграммы "сущность-связь") или в результате статистического анализа имеющихся данных, а затем соединяют их в таблицы и проверяют на нормализацию. Часто на основании одного набора FD можно составить несколько схем 3NF. Хорошее CASE-средство способно построить не одну такую схему и в идеале найти самую высокую нормальную форму (существуют и другие нормальные формы, о которых мы еще не говорили). Некоторые утверждают, что для повышения эффективности схемы ее можно несколько денормализовать. Например, чтобы получить список всех студентов и их специализаций для данного курса, необходимо соединить оператором JOIN таблицы Enrollment и Students. Однако нормализация ослабляет требования к программе. При денормализации формы мы либо вынуждены будем отказаться от некоторых требуемых пользователями ограничений, либо для их реализации должны будем написать дополнительный код.
       Первое из этих решений неприемлемо. Во втором случае нам придется дублировать дополнительный код во всех программах, работающих с СУБД. Нормализация избавляет от такой необходимости.

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

       Таблица находится в нормальной форме Бойса-Кодда (Boyce-Codd normal form, BCNF), если для всех нетривиальных FD (X —> А) X представляет собой суперключ (superkey) всей схемы. Суперключ — это уникальный набор столбцов, идентифицирующих все строки таблицы, но вы можете удалить некоторые из них, а он все равно останется ключом. Неформально можно сказать, что суперключ составлен с избытком.
       BCNF представляет собой нормальную форму, в которой действительно отсутствуют все транзитивные зависимости. Таблица находится в BCNF, если для всех зависимостей (X —> Y) X — это ключ. Чтобы перейти к такой форме, в таблицу Classes необходимо добавить еще один ключ с предложением ограничения UNIQUE(room, time). Имеется еще несколько полезных нормальных форм более высокого порядка, но они не являются темой нашего обсуждения. В данном примере, создав BCNF, мы устранили все существенные аномалии.
       Третья нормальная форма касается связей между ключевыми и неключевыми столбцами. Однако часто столбец может выполнять обе функции. Рассмотрим таблицу подсчета подарков, выдаваемых торговым агентам. Она содержит базовую зарплату агента, объем выполненных им продаж и премиальные, основанные на комбинации базовой зарплаты и объема продаж. Например, начинающему агенту с базовой зарплатой в диапазоне от $15.000 до $20.000, продавшему 100 пунктов, мы можем подарить перьевую авторучку, а опытный агент с базовой зарплатой от $30.000 до $60.000, продавший 200 пунктов, может рассчитывать на автомобиль. Таким образом, у нас есть следующие функциональные зависимости:

(paystep, points) —> gift gift —> points

       Начнем с таблицы, содержащей все данные, а затем нормализуем ее.

Gifts
salary     points   gift
$15.000    100      Pencil
$17.000    100      Pen
$30.000    200      Car
$31.000    200      Car
$32.000    200      Car

       Эта схема находится в 3NF, но с ней связаны определенные проблемы. В нашу таблицу нельзя включить новый подарок, не указав также и зарплату. При удалении данных об объемах продаж вы теряете информацию о подарках и зарплатах (автомобиль могут получить только сотрудники с зарплатой в диапазоне $30.000). И, наконец, изменение подарка для конкретного объема продаж повлияет на все строки для того же диапазона зарплаты. Таким образом, нашу таблицу надо разбить на две:

PayGifts
salary gift
$15.000 Pencil $17.000 Pen $30.000 Car $31.000 Car $32.000 Car GiftPoints gift Points Pencil 100 Pen 100 Car 200

 

2.7. Четвертая нормальная форма (4NF)

       В четвертой нормальной форме (4NF) используются многозначные зависимости (multivalued dependencies, MVD). Она решает проблему слишком большого их количества в таблице. Рассмотрим таблицу, содержащую отделы, их проектные задания и хранимые ими детали. Для нее MVD выглядят следующим образом:

department —> projects department —> parts

       Предположим, что отдел d1 работает над заданиями j1 и j2, используя детали p1 и р2; отдел d2 — над заданиями j3, j4 и j5 с деталями р2 и р4, а отдел d3 — над заданием j2, используя детали р5 и р6. Таблица будет выглядеть так:

department    job    part
d1            j1     P1
d1            j1     P2
d1            J2     P1
d1            J2     P2
d2            J3     P2
d2            J3     P4
d2            J4     P2
d2            J4     P4
d2            J5     P2
d2            J5     P4
d3            J2     P5
d3            J2     P6

       Чтобы добавить в отдел новую деталь, необходимо создать несколько строк. Аналогично этому, удаление из строки детали или задания может разрушить всю информацию. Изменение названия детали или задания также потребует модификации нескольких строк.
       Чтобы решить проблему, таблицу надо разделить на две, одну с названиями отделов и заданий, а другую — департаментов и деталей. В соответствии с определением таблица находится в 4NF, если в ней есть не больше одной MVD. Если таблица находится в 4NF, она также находится и в BCNF.

2.8. Пятая нормальная форма (5NF)

       В основе пятой нормальной формы (5NF), называемой также нормальной формой проекции-соединения или соединения-проекции (JPNF), лежит попытка избавиться от аномалий соединения и проекции. Такая проблема возникает при наличии n-арной связи, где n > 2. Таблица находится в 5NF, если она находится в 3NF и все возможные ключи представляют собой простые одиночные столбцы.
       В качестве примера проблем, решаемых формой 5NF, рассмотрим таблицу с информацией о покупке домов, регистрирующую покупателя, продавца и выдавшего заем банка.
       В таблице представлена тройная связь, но, поскольку многие CASE-средства допускают только бинарные связи, она должна быть показана на ER-диаграмме в виде трех бинарных связей, и в результате будут сгенерированы операторы CREATE TABLE для трех таблиц:

HouseNotes
buyer     seller    lender        .
Smith     Jones     National Bank
Smith     Wilson    Home Bank
Nelson    Jones     Home Bank
BuyerLender
buyer     lender           .
Smith     National Bank
Smith     Home Bank
Nelson    Home Bank
SellerLender
seller    lender           .
Jones     National Bank
Wilson    Home Bank
Jones     Home Bank
BuyerSeller

buyer seller
Smith Jones Smith Wilson Nelson Jones

       Проблема возникнет, когда вы пытаетесь собрать первоначальную информацию, соединив попарно эти три таблицы:

SELECT BS.buyer, SL.seller, BL.lender 
  FROM BuyerLender AS BL, 
       SellerLender AS SL, 
       BuyerSeller AS BS 
 WHERE BL.buyer = BS.buyer
   AND BL.lender = SL.lender
   AND SL.seller = BS.seller;

       Вы действительно получите нужные строки первоначальной таблицы (например строку 'Smith', 'Jones', 'National. Bank'), но, кроме того, здесь будут и ложные строки, не входившие в ее состав (например Smith', Jones', 'Home Bank'). Это и называется аномалией соединения-проекции.
       Существуют так называемые сильные (strong) и очень сильные (overst-rong) JPNF, использующие зависимости соединения (join dependencies, JD). К сожалению, систематического способа получения JPNF из 4NF не существует, поскольку эта задача относится к категории NP-полных.

2.9. Нормальная форма "домен-ключ" (DKNF)

       Функциональные зависимости характеризуются определенным набором аксиом, которые могут быть использованы для решения проблем нормализации. Эти шесть аксиом называются аксиомами Армстронга, они представлены ниже:
       Рефлексивность: X —> X
       Пополнение: если X —> Y, то XZ —> Y
       Объединение: если (X —> Y и X —> Z), то X —> YZ
       Декомпозиция: если X —> Y и Z представляет собой подмножество Y, то X—>Z
       Транзитивность: если (X —>Y и Y —> Z), то X —> Z
       Псевдотранзитивность: если (X —> Y и YZ —> W), то XZ —> W
       Чтобы их понять, достаточно просто взглянуть на них, а это и требуется от аксиом. В реальном мире FD — это те бизнес-правила, которые мы и пытаемся моделировать.
       В разработанном Бернштейном алгоритме нормализации для 3NF (Bernstein, 1976) с помощью указанных аксиом удается избавиться от избыточных FD. Например, мы имеем следующие зависимости:
       А —> В
       А —> С
       В —> С
       DB —> Е
       DAF —> Е
       Зависимость А —> С избыточна, поскольку ее можно получить с помощью аксиомы транзитивности из зависимостей А —> В и В —> С. Зависимость DAF —> Е также избыточна, так как ее можно получить из зависимостей DB —> Е и А —> В с помощью аксиомы псевдотранзитивности (которая дает зависимость DA —> Е) и затем пополнения (мы получим как раз DAF —> Е). Нам требуется найти минимальный набор FD, из которого можно вывести все наши правила. Этот набор называется неизбыточным покрытием (nonredundant cover). Для приведенных выше FD одним из таких наборов будет:
       А —> В
       В —> С
       DB —> E
       Далее Бернштейн показывает, что мы можем создать таблицу для каждой из FD, где А, В и DB — соответствующие ключи. Перейдем к более сложному примеру.
       В качестве примера схемы, содержащей более одной третьей нормальной формы, компания DBStar Corporation предлагает следующую ситуацию (она используется в демонстрации, сопровождающей ее CASE-средство).
       Рассмотрим воображаемую авиакомпанию, БД которой содержит планы полетов и информацию о пилотах. Большая часть связей очевидна. Каждая запись полета содержит только одно время отправления и одно время прибытия. Тем не менее в каждый день недели полет может обслуживаться различными пилотами, а посадка может проводиться через различные шлюзы. Далее представлены функциональные зависимости БД:
       1. light —> destination
       2. flight —> hour
       3. (day, flight) —> gate
       4. (day, flight) —> pilot
       5. (day, hour, pilot) —> gate
       6. (day, hour, pilot) —> flight
       7. (day, hour, pilot) —> destination
       8. (day, hour, gate) —> pilot
       9. (day, hour, gate) —> flight
       10. (day, hour, gate) —> destination
       Наша задача состоит в том, чтобы среди этих FD найти схемы БД в 3NF. Будьте очень внимательны! Очевидно, ваш ответ должен содержать все нужные столбцы и, кроме того, игнорировать некоторые FD. Например, следующий вариант решения работать не будет:

CREATE TABLE PlannedSchedule
   (flight, destination, hour, PRIMARY KEY (flight)),
CREATE TABLE Actual Schedule
(day, flight, gate, pilot, PRIMARY KEY (day, flight));

Применив к некоторым FD аксиому объединения, получим:

(day, hour, gate) —> (destination, flight, pilot)
(day, hour, pilot) —> (destination, flight, gate)

       Это означает, что, получив информацию о дне, часе и шлюзе, мы должны иметь возможность определить уникальный номер полета. Та же возможность должна быть при наличии информации о дне, часе и пилоте.
       На основании таблиц PlannedSchedule и ActualSchedule создать представления с двумя указанными ограничениями не удается. Если на вопрос: "Какой рейс пилотирует пилот X в день Y и час Z?" — вы получите больше одного ответа, это будет нарушением FD. Ниже приводится пример, допустимый в соответствии с предложенной схемой, но нежелательный с учетом наших ограничений.

Таблица PlannedSchedule
flight     hour        destination
118        17:00       Dallas
123        13:00       Omaha
155        17:00       Los Angeles
171        13:00       New York
666        13:00       Hades
Таблица ActualSchedule
day    flight    pilot   gate
Wed    118       Tom     12A
Wed    155       Tom     13B
Wed    171       Tom     12A
Thu    123       John    12A
Thu    155       John    12A
Thu    171       John    13B

       Ограничения требуют возможности найти уникальный ответ на каждый из следующих вопросов, а также сохранности информации при вводе и удалении данных.
       1. Какой самолет отбывает от шлюза 12А по четвергам в 13:00? На первый взгляд кажется, что найти ответ просто, но затем обнаруживается отсутствие соответствующей информации о рейсе 666 в таблице ActualSchedule. Аналогичным образом можно добавить в этутаблицу описание рейса, информация о котором отсутствует в таблице PlannedSchedule.
       2. Какой пилот обслуживает рейс, отбывающий от шлюза 12А по четвергам в 13:00? Здесь возникает аналогичная проблема.
       3. Каково место прибытия самолета из запросов 1 и 2? И здесь возникает аналогичная проблема.
       4. От какого шлюза отбывает самолет, управляемый пилотом Джоном, по четвергам в 13:00?
       5. Куда летит управляемый Томом самолет по четвергам в 17:00?
       6. Каким самолетом управляет Том по средам в 17:00?
       Рассмотрим, как можно получить одну из функциональных зависимостей в описанной нами задаче с помощью аксиом их вычисления (это напоминает решение задачи на доказательство по геометрии).

Дано:
       1. (day, hour, gate) —> pilot
       2. (day, hour, pilot) —> flight

Доказать:
       (day, hour, gate) —> flight

Доказательство:
       3. (day, hour) —> (day, hour);                        рефлексивность
       4. (day, hour, gate) —> (day, hour);               пополнение пункта З
       5. (day, hour, gate) —> (day, hour pilot);       объединение пунктов 1 и 4
       6. (day, hour, gate) —> flight;                         транзитивность пунктов 2 и 5
       Что и требовалось доказать.

       Для решения задачи надо попытаться получить все функциональные зависимости из остального набора. В результате мы получаем несколько коротких доказательств, каждое из которых требует своих начальных зависимостей; все вместе они позволяют получить требуемую FD.
       Ниже приводится список доказательств, позволяющих получить десять различных FD для данной задачи. Приведены все этапы доказательств, а также необходимые для их осуществления операции. Обратите внимание на одну операцию, не включенную в состав рассматривавшихся ранее аксиом, — редукцию слева (left reduction). Она определяет: если XX —> Y, то X —> Y. Ранее она не приводилась, поскольку фактически представляет собой теорему, а не одну из базисных аксиом (задание: попробуйте доказать ее).

       Доказать: (day, hour, pilot) —> gate
       a. day —> day;                                       рефлексивность
       b. (day, hour, pilot) —> day;                  пополнение (а)
       c. (day, hour, pilot) —> (day, flight);      объединение (6,b)
       d. (day, hour, pilot) —> gate;                транзитивность (с, 3)
       Что и требовалось доказать.

       Доказать: (day, hour, gate) —> pilot
       a. day —> day;                                    рефлексивность
       b. (day, hour, gate) —> day;                 пополнение (а)
       c. (day, hour, gate) —> (day, flight);    объединение (9,b)
       d. (day, hour, gate) —> pilot;                транзитивность (с,4)
       Что и требовалось доказать.

       Доказать: (day, flight) —> gate
       a. (day, flight, pilot) —> gate;    псевдотранзитивность (2,5)
       b. (day, flight, day, flight) —> gate;    псевдотранзитивность (а,4)
       c. (day, flight) —> gate;    редукция слева (b)
       Что и требовалось доказать.

       Доказать: (day, flight) —> pilot
       a. (day, flight, gate) —> pilot;    псевдотранзитивность (2,8)
       b. (day, flight, day, flight) —> pilot;    псевдотранзитивность (а,3)
       c. (day, flight) —> pilot;    редукция слева (b)
       Что и требовалось доказать.

       Доказать: (day, hour, gate) —>    flight
       a. (day, hour) —> (day, hour);    рефлексивность
       b. (day, hour, gate) —> (day, hour);пополнение (а)
       c. (day, hour, gate) —> (day, hour, pilot);    объединение (b,8)
       d. (day, hour, gate) —> flight;    транзитивность (с, 6)
       Что и требовалось доказать.    

       Доказать: (day, hour, pilot) —> flight
       a. (day, hour) —> (day, hour);    рефлексивность
       b. (day, hour, pilot) —> (day, hour);    пополнение (а)
       c. (day, hour, pilot) —> day, hour, gate;    объединение (b,5)
       d. (day, hour, pilot) —> flight;    транзитивность (с, 9)
       Что и требовалось доказать.

       Доказать: (day, hour, gate) —> destination
       a. (day, hour, gate) —> destination;    транзитивность (9, 1)
       Что и требовалось доказать.    
       Доказать: (day, hour, pilot) —> destination    
       a. (day, hour, pilot) —> destination;    транзитивность(6, 1)
       Что и требовалось доказать.

       Теперь, поняв, как можно вывести восемь из десяти функциональных зависимостей из остальных зависимостей, вы можете объединять их в наборы, каждый из которых соответствует следующим критериям:
       1. Каждый атрибут должен быть представлен либо с левой, либо с правой стороны по крайней мере одной FD в наборе.
       2. Если данная FD входит в набор, необязательно включать все FD,требуемые для ее вывода.
       3. Если данная FD не входит в набор, включать все требуемые для еевывода FD обязательно.
       Теперь можно создать набор неизбыточных покрытий, сделав это с помощью метода проб и ошибок, а также здравого смысла. Например, исключив зависимость (day, hour, gate) —> flight, следует включить (day, hour, gate) —” pilot и наоборот, поскольку каждая из них применяется при выводе другой. Чтобы гарантировать создание исчерпывающего набора, воспользуйтесь более механическим подходом, реализуемым CASE-средствами.
       Алгоритм решения этой задачи состоит в генерации всех комбинаций наборов FD. Зависимости (flight —> destination) и (flight —> hour) из данного процесса исключаются, так как они не могут быть выведены. В результате мы получаем 28 = 256 комбинаций FD, каждая из которых затем проверяется на соответствие критерию.
       К счастью, вся утомительная работа может быть выполнена в простой электронной таблице. В нашем случае критерий 1 уничтожает только 15 наборов. Критерий 2 приводит к удалению 152 наборов, а критерий 3 — еще 67. В результате мы получим 22 возможных покрытия, пять из которых представляют собой ответы на интересующие нас вопросы (остальные 17 будут описаны далее). Эти пять неизбыточных покрытий представлены в следующем списке:

Set I
       flight —> destination
       flight —> hour
       (day, hour, gate) —> flight
       (day, hour, gate) —> pilot
       (day, hour, pilot) —> gate

Set II
       flight —> destination
       flight —> hour
       (day, hour, gate) —> pilot
       (day, hour, pilot) —> flight
       (day, hour, pilot) —> gate

Set III
       flight —> destination
       flight —> hour
       (day, flight) —> gate
       (day, flight) —> pilot
       (day, hour, gate) —> flight

Set IV
       flight —> destination
       flight —> hour
       (day, flight) —> gate
       (day, hour, gate) —> pilot
       (day, hour, pilot) —> flight

Set V
       flight —> destination
       flight —> hour
       (day, flight) —> pilot
       (day, hour, gate) —> flight
       (day, hour, pilot) —> gate
       (day, hour, pilot) —> flight

       Теперь надо выполнить объединение FD с одной и той же левой частью и для каждой группы создать таблицы, причем левая часть будет ключом. Можно также избавиться от симметричных FD (определяемых как X —> Y и Y —> X и записываемых с помощью двусторонней стрелки — X <—> Y), сведя их в одной таблице.
       Пять описанных неизбыточных покрытий преобразуются таким способом в пять следующих наборов реляционных схем 3NF. Они представлены в сокращенной форме SQL DDL (Data Declaration Language, язык определения данных) без определений типов данных:

Решение 1

CREATE TABLE R1 (flight, destination, hour, PRIMARY KEY (flight)),
CREATE TABLE R2 (day, hour, gate, flight, pilot, PRIMARY KEY (day, hour, gate));

Решение 2

CREATE TABLE R1 (flight, destination, hour, PRIMARY KEY (flight)); 
CREATE TABLE R2 (day, hour, gate, flight, pilot, PRIMARY KEY (day, hour, pilot));

Решение 3

CREATE TABLE R1 (flight, destination, hour, PRIMARY KEY (flight));
CREATE TABLE R2 (day, flight, gate, pilot, PRIMARY KEY (day, flight));
CREATE TABLE R3 (day, hour, gate, flight, PRIMARY KEY (day, hour, gate));
CREATE TABLE R4 (day, hour, pilot, flight, PRIMARY KEY (day, hour, pilot));

Решение 4

CREATE TABLE R1 (flight, destination, hour, PRIMARY KEY (flight));
CREATE TABLE R2 (day, flight, gate, PRIMARY KEY (day, flight));
CREATE TABLE R3 (day, hour, gate, pilot, PRIMARY KEY (day, hour, gate)); 
CREATE TABLE R4 (day, hour, pilot, flight,PRIMARY KEY (day, hour, pilot));

Решение 5

CREATE TABLE R1 (flight, destination, hour, PRIMARY KEY (flight));
CREATE TABLE R2 (day, flight, pilot, PRIMARY KEY (day, flight)); 
CREATE TABLE R3 (day, hour, gate, flight, PRIMARY KEY (day, hour, gate)); 
CREATE TABLE R4 (day, hour, pilot, gate, PRIMARY KEY (day, hour, pilot));

       Сравнив эти решения с минимальными сгенерировавшими их покрытиями, вы, вероятно, заметите, что первые два содержат транзитивные зависимости. Однако они все равно находятся в 3NF. Большинство аналитиков не слишком хорошо понимают эту особенность. Отношение находится в 3NF, если для каждой FD X —> Y X является суперключом или Y входит в состав возможного ключа. Первые два решения соответствуют подобному критерию.
       Обратите внимание также, что в таблицах не определены дополнительные возможные ключи. В принципе, такой подход мог бы иметь смысл в первых двух решениях, но он не был реализован (и поэтому они находятся в 3NF, а не BCNF). Именно этот метод реализован в CASE-средствах, потому что стандарт SQL-89 позволяет создавать только ограничения PRIMARY KEY. Стандарт SQL-92 разрешает дополнительно накладывать на один или несколько столбцов еще и ограничения UNIQUE. Большинство реализаций SQL также позволяет определять уникальные индексы применительно к подмножеству столбцов.
       Все пять решений находятся в 3NF, но первые два из них не включают две FD. На первый взгляд может показаться, что данный автоматизированный нормализатор считает подобные решения, в которых не указаны все ограничения, допустимыми. Однако в таблицах необходимые возможные ключи можно определить с помощью ограничений UNIQUE. Используемый для получения этих решений нормализатор может оставить некоторые из ограничений, но все равно генерировать схемы 3NF. Будьте внимательны, так как он предполагает, что вы решите этот вопрос вне схемы или захотите преобразовать FD в какие-либо ограничения.
       Если вы имеете право удалять FD (что делает наш анализатор), то можете получить 22 решения (большая их часть не может быть сгенерирована данным нормализатором). Их получают путем удаления из показанных выше решений атрибутов или целых таблиц (имейте в виду, что каждый атрибут все-таки должен быть представлен хотя бы в одной таблице). Некоторые из оставшихся 17 решений можно получить следующим образом:
       1. Удалив любую (или обе) из последних двух таблиц в последних трех решениях.
       2. Удалив комбинацию шлюза (gate), рейса (полета, flight) и пилота втех случаях, если они не являются ключами (не забудьте оставить хотя бы один неключевой атрибут в каждой таблице и следите, чтобы удаляемый из таблицы атрибут присутствовал где-либо еще).
       3. Добавив к первым двум решениям ограничения UNIQUE или индексы.
       Обратите внимание, что в последних трех из пяти приведенных выше решений все-таки имеют место некоторые аномальные состояния. Так, в третьем решении последние две таблицы могут содержать комбинацию дня и рейса, не входящую в состав допустимых комбинаций из списка второй таблицы. Другие решения содержат сходные проблемы целостности.
       Такую проблему решает нормальная форма "домен-ключ" (DKNF), введенная Рональдом Фейджином в 1981 г. Пока не найден общий алгоритм генерации DKNF для заданного набора ограничений. Однако во многих конкретных случаях DKNF определить можно. Взгляните, например, на решение DKNF для нашей задачи.

Решение 6

CREATE TABLE R1 (flight, hour, destination,
         UNIQUE (flight, hour, destination),
         UNIQUE (flight, hour),
         UNIQUE (flight));
CREATE TABLE R2 (day, flight, hour, gate, pilot,
         UNIQUE (day, flight, hour, gate, pilot),
         UNIQUE (day, flight, pilot),
         UNIQUE (day, flight, gate),
FOREIGN KEY (flight, hour) REFERENCES R1(flight, hour));

       Заметьте, что при подобной нормализации удаляется таблица и добавляются ограничения UNIQUE. Поскольку рейс описан как возможный ключ в таблице R1, возможный ключ (flight, hour) не кажется необходимым. Внешний ключ в таблице R2 содержит комбинацию рейса и часа (flight, hour), а не просто рейс. В результате второе отношение уже не может содержать недопустимую комбинацию рейса и часа.
       Однако, добавив внешние ключи к решениям 3, 4 и 5, мы не устраняем все аномалии. Единственным решением, удаляющим их полностью, является создание DKNF, а для этого лучше объединить все таблицы, кроме самой первой, в одну. Это гарантирует невозможность возникновения несогласованных комбинаций шлюза, пилота, дня, часа и рейса. Действительно, поскольку подобная комбинация содержится только в одной таблице, между атрибутами несоответствие невозможно; именно это и является целью DKNF.

2.10. Практические советы по нормализации

       CASE-средства реализуют формальные методы нормализации. В особенности для этого полезны ER-диаграммы. Однако приводимые далее неформальные советы позволят вам ускорить процесс и сделать хороший старт.
       В широком смысле таблицы представляют либо сущности, либо связи, именно поэтому ER-диаграммы являются столь хорошим средством проектирования. Если таблицы представляют сущности, они должны иметь простое имя, понятное из их содержания. Например, таблица Students должна содержать данные только о студентах, а не о студентах и счет игры в боулинг. Неплохо в качестве имен использовать существительные во множественном числе — это будет напоминать, что таблица представляет множество экземпляров сущности, а строка содержит один ее экземпляр.
       Если таблицы представляют связи "многие-ко-многим", то их имена должны определяться содержанием и должны быть минимальными. Например, таблица Students связана с таблицей Classes с помощью третьей таблицы (связи), в которой отражена их посещаемость. Эти таблицы могут представлять связи в чистом виде или содержать атрибуты связей, например оценку по данному курсу. Поскольку единственным способом получения оценки является посещение курса, таблица будет содержать столбец под названием ReportCards (табель успеваемости) или Grades (оценки).
       Старайтесь избегать NULL-значений. Если таблица содержит слишком много столбцов с такими значениями, ее, вполне возможно, не удастся правильно нормализовать. Вводите NULL только для значений, которых пока нет, но затем они появятся. Еще лучше включить отсутствующие значения в схему кодирования для данного столбца, как описано в соответствующем разделе этой книги.
       Нормализованная БД имеет тенденцию к большому количеству таблиц с малым числом столбцов в каждой. Не пугайтесь, обнаружив это. Программисты, ранее работавшие с файловыми системами (особенно на компьютерах с магнитными лентами), могут попытаться создать один огромный файл для приложения и всю работу выполнять в нем. Раньше такой подход имел смысл, поскольку не было способа объединить большое количество файлов, не заставляя оператора монтировать и демонтировать различные ленты. Однако привычка подобного проектирования перешла и на дисковые системы, потому что процедурные языки программирования остались прежними.
       Проблемой нормализации является наличие одного и того же неключевого атрибута в более чем одной таблице. Рекомендую ключ, определяющий этот атрибут, поместить лишь в одной таблице, тогда атрибут также окажется только в ней.
       Скорее всего один и тот же атрибут появится в вашей БД несколько раз под различными именами, так что советую унифицировать имена в базе данных. Например, вполне возможно, что столбцы под,названием date_of_birth, birthdate, birthday и dob содержат один и тот же атрибут сотрудника.

2.11. Практические советы по денормализации

       Говорите о денормализации с осторожностью — это может послужить началом почти что "религиозной" войны. С одной стороны, вы найдете "реляционных пуристов", считающих, что сама мысль о проектировании БД хотя бы не в 3NF является преступлением против природы. С другой стороны, есть люди, просто добавляющие в базу данных столбцы и удаляющие их с помощью операторов ALTER, не пытаясь обеспечить стабильность схемы.
       Причиной денормализации является производительность. Для конструирования общих представлений данных из отдельных компонентов полностью нормализованная база данных требует применения большого числа операторов JOIN. Это продолжительная ресурсоемкая операция, поэтому предварительное конструирование соединения в денормализованной таблице может сэкономить много времени.
       Рассмотрим реальную задачу, впервые описанную на форуме по Oracle в сети CompuServe. В ней рассматриваются инвентарная таблица и таблица изменений цен фармацевтической компании, которые выглядят следующим образом:

CREATE TABLE Drugs
   (drugno     INTEGER PRIMARY KEY,
    drugname   CHAR(30) NOT NULL,
    quantity   INTEGER  NOT NULL
CONSTRAINT positive_quantity CHECK(quantity > 0),
. . . . .);
CREATE TABLE Prices 
   (drugno INTEGER NOT NULL,
    startdate DATE NOT NULL,
    enddate     DATE NOT NULL
CONSTRAINT started_before_ended
           CHECK(startdate <= enddate),
    price DECIMAL(6,2) NOT NULL,
PRIMARY KEY (drugno, startdate));

       Чтобы узнать цену на момент размещения заказа, необходимо использовать его дату. Текущая цена будет иметь значение "бесконечность" (фиктивная дата устанавливается столь большой, чтобы она никогда не достигалась, например '9999-12-31'). Значение (enddate + INTERVAL1 DAY) одной цены равно значению startdate следующей цены для того же лекарства.
       Эта схема нормализована, но ее производительность невысока. Каждый отчет, счет или запрос должен выполнить оператор JOIN между таблицами Drugs и Prices. В таком случае к первой из них можно добавить дополнительные столбцы, например:

CREATE TABLE Drugs
   (drugno            INTEGER PRIMARY KEY,
    drugname          CHAR(3O) NOT NULL,
    quantity          INTEGER NOT NULL
CONSTRAINT positive_quantity CHECK(quantity > 0),
    currentstartdate  DATE NOT NULL,
    currentenddate    DATE NOT NULL,
CONSTRAINT current_start_before_ended
           CHECK(currentstartdate <= currentenddate),
    currentpnce       DECIMAL(8,2) NOT NULL,
    pnorstartdate     DATE NOT NULL,
    pnorenddate       DATE NOT NULL,
CONSTRAINT pnor_start_before_ended
           CHECK(priorstartdate <= pnorenddate),
            AND (currentstartdate = pnorenddate + INTERVAL1  DAY),
    pnorprice         DECIMAL(8,2) NOT NULL,
. . .);

       Это справедливо для более чем 95% всех заказов реальной компании, поскольку цены меняются более чем 2 раза только для очень небольшого количества заказов. Отдельные исключения из этого правила обрабатываются специальной процедурой.
       Еще один удобный прием — сохранение ограничений, наложенных на первоначальные таблицы, и перемещение их в предложения СНЕСК(). Рассмотрим две таблицы из примеров, описанных в начале этой главы:

CREATE TABLE Enrollment (student, course, section, grade, PRIMARY KEY (student, course));
CREATE TABLE Students (student, major, PRIMARY KEY (student));

       Чтобы объединить их в одну денормализованную таблицу, можно выполнить оператор:

CREATE TABLE StudentEnrollment (student, major, course, section, grade),

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

CHECK (NOT EXISTS (SELECT student, COUNT(DISTINCT major)
                     FROM StudentEnrollment
                    GROUP BY student
                   HAVING COUNT(DISTINCT major) <> 1);

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




<<< Пред. Оглавление
 
След. >>>

Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:55 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/SQL/CelkoJ/01h002.shtml