Меню

Если каждый атрибут таблицы содержит только одно значение



ПЭИС : 4.Теоретические основы реляционной модели данных. Фундаментальные свойства отношений. Нормализация схем отношений

Реляционная модель (РМ) основана на понятии «отношения» (Relationship), она наиболее распространена сегодня.

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

Недостатками реляционной модели:

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

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

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

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

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

Схемой отношения называют именованное множество пар (Ai, Di), i=1,k, где Ai — имя атрибута, Di — имя домена, k — ранг отношения. Например: Студенты ((имя, имена людей), (возраст, числа от 17 до 59), (номер паспорта, целые числа)) ранг=3.

Схема реляционной базы данных представляет собой совокупность схем отношений и содержит следующие компоненты:
S= , где A — множество атрибутов, D — множество доменов, R — множество имен отношений, Rel — множество схем отношений, F — множество ограничений.

Кортеж отношения — это множество пар вида «имя атрибута, значение атрибута», причем каждый атрибут отношения один и только один раз входит в кортеж. # (Саша, 19, 222222) или (Катя, 20, 353453) или (Настя, 18, 424242)

Отношение — это множество кортежей, соответствующих одной схеме отношения. Элементами отношений являются кортежи.
# R=

Фундаментальные свойства отношений:

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

Для связи между разными отношениями используется понятие внешнего ключа. Внешним ключом называется атрибут (совокупность атрибутов), который является ключом Ak в другом отношении R1 и его значения принадлежат домену Dk отношения R2, т.е отношение, в котором определен внешний ключ ссылается на другое отношение в котором такой же атрибут является первичным ключом.

Компоненты реляционной модели данных (согласно Дейту модель состоит из 3 частей)

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

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

В модели должны выполняться 2 базовых условия целостности:

  • Любой кортеж любого отношения должен быть отличим от любого другого кортежа этого отношения;
  • Для каждого значения внешнего ключа в отношении Х должен найтись кортеж с таким же значением первичного ключа в отношении У, на которое он ссылается.

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

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

  • Первая нормальная форма (1NF);
  • Вторая нормальная форма (2NF);
  • Третья нормальная форма (3NF);
  • Нормальная форма Бойса — Кодда (BCNF);
  • Четвертая нормальная форма (4NF);
  • Пятая нормальная форма, или форма проекции соединения (5NF или PJ/NF).

Основные свойства нормальных форм:

  • Каждая следующая NF улучшает свойства предыдущей;
  • При переходе к следующей NF свойства предыдущих NF сохраняются.

Дадим некоторые определения:

Функциональная зависимость. В отношении R атрибут Y функционально зависит от атрибута X — если каждому значению X соответствует в точности одно значение Y. Обозначается y:x→y (x функционально определяет y)

Полная функциональная зависимость. Функциональная зависимость y:x→y называется полной, если атрибут Y не зависит функционально от любого точного подмножества X

Транзитивная функциональная зависимость. Функциональная зависимость y:x→y называется транзитивной, если существует такой атрибут Z, что имеются функциональные зависимости x →z и z→y (обратная зависимость отсутствует).

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

Неключевой атрибут — любой атрибут отношения, не входящий в состав первичного ключа.

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

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

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

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

Таблица находится в первой нормальной форме, если каждый её атрибут атомарен. Под выражением «атрибут атомарен» понимается, что атрибут может содержать только одно значение. Таким образом, не существует 1NF таблицы, в полях которых могут храниться списки значений. Для приведения таблицы к 1NF обычно требуется разбить таблицу на несколько отдельных таблиц.

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

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

Таблица находится во второй нормальной форме, если она находится в первой нормальной форме, и при этом любой её атрибут, не входящий в состав первичного ключа, функционально полно зависит от первичного ключа. Функционально полная зависимость означает, что атрибут функционально зависит от всего первичного составного ключа, но при этом не находится в функциональной зависимости от из входящих в него атрибутов (частей). Или другими словами: в 2NF нет неключевых атрибутов, зависящих от части составного ключа (+ выполняются условия 1NF).

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

Таблица находится в третьей нормальной форме (3NF), если она находится во второй нормальной форме 2NF и при этом любой ее неключевой атрибут зависит только от первичного ключа (Primary key, PK) (иначе говоря, один факт хранится в одном месте).

Таким образом, отношение находится в 3NF тогда и только тогда, когда оно находится во 2NF и отсутствуют транзитивные зависимости неключевых атрибутов от ключевых. Транзитивной зависимостью неключевых атрибутов от ключевых называется следующая: A → B и B → C, где A — набор ключевых атрибутов (ключ), B и С — различные множества неключевых атрибутов.

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

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

Это модификация третьей нормальной формы (в некоторых источниках именно 3NF называется формой Бойса — Кодда).

Таблица находится в BCNF, если она находится в 3NF, и при этом отсутствуют функциональные зависимости атрибутов первичного ключа от неключевых атрибутов. Таблица может находиться в 3NF, но не в BCNF, только в одном случае: если она имеет, помимо первичного ключа, ещё по крайней мере один возможный ключ. Все зависимые от первичного ключа атрибуты должны быть потенциальными ключами отношения. Если это условие не выполняется, для них создаётся отдельное отношение. Чтобы сущность соответствовала BCNF, она должна находиться в третьей нормальной форме. Любая сущность с единственным возможным ключом, соответствующая требованиям третьей нормальной формы, автоматически находится в BCNF.

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

Таблица находится в 4NF, если она находится в BCNF и не содержит нетривиальных многозначных зависимостей. Многозначная зависимость не является функциональной, она существует в том случае, когда из факта, что в таблице содержится некоторая строка X, следует, что в таблице обязательно существует некоторая определённая строка Y. То есть, таблица находится в 4NF, если все ее многозначные зависимости являются функциональными.

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

Таблица находится в 5NF, если она находится в 4NF и любая многозначная зависимость соединения в ней является тривиальной. Пятая нормальная форма в большей степени является теоретическим исследованием и практически не применяется при реальном проектировании баз данных. Это связано со сложностью определения самого наличия зависимостей «проекции — соединения», поскольку утверждение о наличии такой зависимости должно быть сделано для всех возможных состояний БД .

нормальная форма (DKNF)

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

Шестая нормальная форма (6NF)

Таблица находится в 6NF, если она находится в 5NF и удовлетворяет требованию отсутствия нетривиальных зависимостей. Зачастую 6NF отождествляют с DKNF.

Источник

Часть 2. Нормализация таблиц

Практическое занятие №3

«Даталогическое проектирование базы данных»

Цель:приобретение практических навыков по проектированию логической модели БД, минимизация избыточности данных на основе принципов нормализации

Время выполнения: 2 часа

Общие теоретические сведения

Часть 1. Построение реляционной схемы

Результатом этапа даталогического (логического) проектирования является логическая схема БД, включающая определение всех информационных единиц и связей, в том числе задание типов, характеристик и имен. Основная задача этого этапа — преобразование ER-диаграммы в реляционную схему.

Получение реляционной схемы из ER-диаграммы:

1.Каждая простая сущность превращается в таблицу (отношение). Имя сущности становится именем таблицы.

2.Каждый атрибут становится возможным столбцом с тем же именем. Столбцы, соответствующие необязательным атрибутам, могут содержать неопределенные значения; столбцы, соответствующие обязательным атрибутам, — не могут. Если атрибут является множественным, то для него строится отдельное отношение.

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

Читайте также:  Программы microsoft office для создание таблица

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

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

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

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

• выполнение текущего учебного плана;

• формирование ведомостей по отдельным дисциплинам для групп студентов;

• формирование листов зачетных книжек студентов;

• формирование сводной ведомости курса;

• расчет среднего балла по дисциплинам и т. п.

Рассмотрим этап построения даталогической модели (реляционной схемы) на основе имеющейся ER-диаграммы) для решения задачи.

ER-диаграмма рассматриваемой задачи представлена на рис.2.

Рис 2. ER-диаграмма предметной области

На данном этапе проектирования необходимо построить даталогическую модель. В рассматриваемом случае задача этого этапа — преобразование ER-диаграммы в реляционную схему.

Первые шаги преобразования состоят в превращении каждой сущности в отношение (таблицу). Связь типа М:М, которую называют «сущность — связь», тоже превращается в отдельное отношение. Каждое свойство становится атрибутом — столбцом соответствующей таблицы.

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

Рис. 3. Реляционная схема после первого шага проектирования

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

Для ликвидации избыточности и потенциальной противоречивости данных добавим в таблицу «Учебный план» столбец ID_План, содержимое которого будет однозначно идентифицировать каждую строку таблицы. Теперь этот новый столбец станет первичным ключом, и одноименный столбец должен быть добавлен в таблицу «Сводная ведомость».

Связь «Читает» предполагает добавление в таблицу «Учебный план» столбца ID_Преподаватель. Реляционная схема со связями представлена на рис.4

Рис. 4. Реляционная схема со связями

Часть 2. Нормализация таблиц

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

В качестве примера рассмотрим универсальное отношение сотрудники, содержащее информацию о сотрудниках предприятия (табл. 1). Таблица 1

При использовании универсального отношения возникают две проблемы:

· потенциальная противоречивость (аномалии).

Под избыточностью понимают повторение данных в разных строках одной таблицы или в разных таблицах БД. Так, для каждого сотрудника отдела 128 повторяются данные «128, Отдел проектирования».

Аномалии – это проблемы, возникающие в данных из-за дефектов проектирования БД.

Существуют три вида аномалий: вставки, удаления и модификации.

Аномалии вставки проявляются при вводе данных в дефектную таблицу. Добавляя информацию о новом сотруднике, мы должны добавить номер и название отдела. Если ввести данные, не соответствующие имеющимся в таблице (например, 42, отдел проектирования), будет не ясно, какая из строк БД содержит правильную информацию.

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

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

Решение перечисленных проблем состоит в разделении данных и связей, что обеспечивается процедурой нормализации. Концепции и методы нормализации были разработаны Э. Ф. Коддом.

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

Теория нормализации основана на наличии зависимостей между атрибутами отношения.

Основными видами зависимостей являются:

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

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

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

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

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

· вторая нормальная форма (2НФ);

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

· усиленная 3НФ или нормальная форма Бойса-Кодда (БКНФ);

· четвертая нормальная форма (4НФ);

· пятая нормальная форма (5НФ).

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

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

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

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

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

Таблица Квалификации_сотрудников (табл. 2) находится в 1НФ, но не удовлетворяет 2НФ. Первичный ключ должен уникальным образом идентифицировать каждую строку. Единственным вариантом является использование в качестве первичного ключа комбинации Код сотрудника и Квалификация. Это порождает схему: Квалификации_сотрудников ( Код сотрудника, ФИО, Должность, Номер отдела, Наименование отдела, Квалификация).

Одной из имеющихся здесь функциональных зависимостей будет:

Код сотрудника, Квалификацияà ФИО, Должность, Номер отдела, Наименование отдела.

Но, кроме того, мы также имеем:

Код сотрудникаàФИО, Должность, Номер отдела, Наименование отдела.

Другими словами, можно определить имя, должность и отдел, используя только код сотрудника. Это значит, что указанные атрибуты функционально зависимы только от части первичного ключа, а не от всего первичного ключа. Следовательно, указанная схема не находится в 2НФ.

Для приведения этой схемы в 2НФ необходимо декомпозировать исходное отношение на два, в которых все неключевые атрибуты будут полностью функционально зависеть от ключа: сотрудники (Код сотрудника, ФИО, Должность, Номер отдела, Наименование отдела) и Квалификации_сотрудников (Код сотрудника, Квалификация) (табл. 3-4).

Источник

Нормализация отношений. Первая и вторая нормальные формы

Предисловие

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

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

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

Используемые термины

Атрибут — свойство некоторой сущности. Часто называется полем таблицы.
Домен атрибута — множество допустимых значений, которые может принимать атрибут.
Кортеж — конечное множество взаимосвязанных допустимых значений атрибутов, которые вместе описывают некоторую сущность (строка таблицы).
Отношение — конечное множество кортежей (таблица).
Схема отношения — конечное множество атрибутов, определяющих некоторую сущность. Иными словами, это структура таблицы, состоящей из конкретного набора полей.
Проекция — отношение, полученное из заданного путём удаления и (или) перестановки некоторых атрибутов.
Функциональная зависимость между атрибутами (множествами атрибутов) X и Y означает, что для любого допустимого набора кортежей в данном отношении: если два кортежа совпадают по значению X, то они совпадают по значению Y. Например, если значение атрибута «Название компании» — Canonical Ltd, то значением атрибута «Штаб-квартира» в таком кортеже всегда будет Millbank Tower, London, United Kingdom. Обозначение: -> .

Читайте также:  Калорийность меньше продуктов таблица

Первая нормальная форма

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

Будем называть исходное отношение основным, а значение неатомарного атрибута — подчинённым.

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

Следует пояснить сказанное на примере. Рассмотрим отношение, имеющее атрибуты «Код сотрудника», «ФИО», «Должность», «Проекты». Очевидно, что один сотрудник может работать над несколькими проектами. Предположим, что проект описывается идентификатором, названием и датой сдачи.

Код сотрудника ФИО Должность Проекты
1 Иванов Иван Иванович Программист ID: 123; Название: Система управления паровым котлом; Дата сдачи: 30.09.2011
ID: 231; Название: ПС для контроля и оповещения о превышениях ПДК различных газов в помещении; Дата сдачи: 30.11.2011
ID: 321; Название: Модуль распознавания лиц для защитной системы; Дата сдачи: 01.12.2011

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

Примечание: с некоторой точки зрения атрибут «ФИО» можно также считать неатомарным и в таком случае его также следует разделить на более простые, как «Фамилия», «Имя», «Отчество».

Теперь настало время рассмотреть алгоритм нормализации отношения до 1НФ.

  1. Создать новое отношение, схема которого будет получена путём слияния основной и подчинённой схем исходного отношения в одну.
  2. Для каждого кортежа исходного отношения включить в новое столько строк, сколько кортежей содержится в подчинённом отношении этого кортежа.
  3. Заполнить значения атрибутов нового отношения, соответствующих атрибутам подчинённого отношения.
  4. Заполнить строки нового отношения значениями атомарных атрибутов исходного.

Применим этот алгоритм к приведённому выше отношению. Схема нового отношения будет состоять из 6 атрибутов: «Код сотрудника», «ФИО», «Должность», «Код проекта», «Название», «Дата сдачи». Для одного единственного кортежа заданного отношения, добавим в новое три строки, по одной для каждого проекта (по количеству кортежей в подчинённом отношении). Теперь можно заполнить значения разделённых атрибутов кортежами из подчинённого отношения. Затем перенесём в каждую из этих строк значения атомарных атрибутов: «Код сотрудника», «ФИО», «Должность» (как Вы уже догадались, все три строки будут содержать одинаковые значения этих атрибутов).

Результат будет выглядеть так:

Код сотрудника ФИО Должность Код проекта Название Дата сдачи
1 Иванов Иван Иванович Программист 123 Система управления паровым котлом 30.09.2011
1 Иванов Иван Иванович Программист 231 ПС для контроля и оповещения о превышениях ПДК различных газов в помещении 30.11.2011
1 Иванов Иван Иванович Программист 321 Модуль распознавания лиц для защитной системы 01.12.2011

Вторая нормальная форма

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

Пусть исходное отношение содержит информацию о поставке некоторых товаров и их поставщиках.

Код поставщика Город Статус города Код товара Количество
1 Москва 20 1 300
1 Москва 20 2 400
1 Москва 20 3 100
2 Ярославль 10 4 200
3 Ставрополь 30 5 300
3 Ставрополь 30 6 400
4 Псков 15 7 100

Заранее известно, что в этом отношении содержатся следующие функциональные зависимости:
< <Код поставщика, Код товара>-> < Количество>,
<Код поставщика>-> <Город>,
<Код поставщика>-> <Статус>,
<Город>-> <Статус>>

Очевидно, что отношение обладает избыточностью: оно описывает две сущности — поставку и поставщика. В связи с этим возникают следующие аномалии:

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

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

Чтобы устранить эти аномалии, необходимо разбить исходное отношение на проекции:

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

В итоге будут получены два отношения:

Код поставщика Код товара Количество
1 1 300
1 2 400
1 3 100
2 4 200
3 5 300
3 6 400
4 7 100

Первому отношению теперь соответствуют следующие функциональные зависимости:
<Код поставщика, Код товара>-><Количество>

Код поставщика Город Статус города
1 Москва 20
2 Ярославль 10
3 Ставрополь 30
4 Псков 15

Второму отношению соответствуют:
< <Код поставщика>-><Город>,
<Код поставщика>-><Статус>,
<Город>-><Статус>>

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

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

Источник

Нормализация отношений. Шесть нормальных форм

В данной теме я затрону 6 нормальных форм и методы приведения таблиц в эти формы.

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

Используемые термины

Атрибут — свойство некоторой сущности. Часто называется полем таблицы.

Домен атрибута — множество допустимых значений, которые может принимать атрибут.

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

Отношение — конечное множество кортежей (таблица).

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

Проекция — отношение, полученное из заданного путём удаления и (или) перестановки некоторых атрибутов.

Функциональная зависимость между атрибутами (множествами атрибутов) X и Y означает, что для любого допустимого набора кортежей в данном отношении: если два кортежа совпадают по значению X, то они совпадают по значению Y. Например, если значение атрибута «Название компании» — Canonical Ltd, то значением атрибута «Штаб-квартира» в таком кортеже всегда будет Millbank Tower, London, United Kingdom. Обозначение: -> .

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

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

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

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

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

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

Аномалии-добавления возникают, когда информацию в таблицу нельзя поместить, пока она не полная, либо вставка записи требует дополнительного просмотра таблицы.

Первая нормальная форма

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

Например, есть таблица «Автомобили»:

Фирма Модели
BMW M5, X5M, M1
Nissan GT-R
Фирма Модели
BMW M5
BMW X5M
BMW M1
Nissan GT-R

Вторая нормальная форма

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

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

Например, дана таблица:

Модель Фирма Цена Скидка
M5 BMW 5500000 5%
X5M BMW 6000000 5%
M1 BMW 2500000 5%
GT-R Nissan 5000000 10%

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

Модель Фирма Цена
M5 BMW 5500000
X5M BMW 6000000
M1 BMW 2500000
GT-R Nissan 5000000
Фирма Скидка
BMW 5%
Nissan 10%

Третья нормальная форма

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

Модель Магазин Телефон
BMW Риал-авто 87-33-98
Audi Риал-авто 87-33-98
Nissan Некст-Авто 94-54-12

Таблица находится во 2НФ, но не в 3НФ.
В отношении атрибут «Модель» является первичным ключом. Личных телефонов у автомобилей нет, и телефон зависит исключительно от магазина.
Таким образом, в отношении существуют следующие функциональные зависимости: Модель → Магазин, Магазин → Телефон, Модель → Телефон.
Зависимость Модель → Телефон является транзитивной, следовательно, отношение не находится в 3НФ.
В результате разделения исходного отношения получаются два отношения, находящиеся в 3НФ:

Магазин Телефон
Риал-авто 87-33-98
Некст-Авто 94-54-12
Модель Магазин
BMW Риал-авто
Audi Риал-авто
Nissan Некст-Авто

Нормальная форма Бойса-Кодда (НФБК) (частная форма третьей нормальной формы)

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

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

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

Предположим, рассматривается отношение, представляющее данные о бронировании стоянки на день:

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

  • «Бережливый»: стоянка 1 для льготников
  • «Стандарт»: стоянка 1 для не льготников
  • «Премиум-А»: стоянка 2 для льготников
  • «Премиум-B»: стоянка 2 для не льготников.

Таким образом, возможны следующие составные первичные ключи: <Номер стоянки, Время начала>, <Номер стоянки, Время окончания>, <Тариф, Время начала>, <Тариф, Время окончания>.

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

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

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

Тариф Номер стоянки Имеет льготы
Бережливый 1 Да
Стандарт 1 Нет
Премиум-А 2 Да
Премиум-В 2 Нет
Тариф Время начала Время окончания
Бережливый 09:30 10:30
Бережливый 11:00 12:00
Стандарт 14:00 15:30
Премиум-В 10:00 12:00
Премиум-В 12:00 14:00
Премиум-А 15:00 18:00

Четвертая нормальная форма

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

В отношении R (A, B, C) существует многозначная зависимость R.A -> -> R.B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не зависит от С.

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

Такая переменная отношения не соответствует 4НФ, так как существует следующая многозначная зависимость:
<Ресторан>→ <Вид пиццы>
<Ресторан>→

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

Для предотвращения аномалии нужно декомпозировать отношение, разместив независимые факты в разных отношениях. В данном примере следует выполнить декомпозицию на <Ресторан, Вид пиццы>и <Ресторан, Район доставки>.

Однако, если к исходной переменной отношения добавить атрибут, функционально зависящий от потенциального ключа, например цену с учётом стоимости доставки ( <Ресторан, Вид пиццы, Район доставки>→ Цена), то полученное отношение будет находиться в 4НФ и его уже нельзя подвергнуть декомпозиции без потерь.

Пятая нормальная форма

Отношения находятся в 5НФ, если оно находится в 4НФ и отсутствуют сложные зависимые соединения между атрибутами.
Если «Атрибут_1» зависит от «Атрибута_2», а «Атрибут_2» в свою очередь зависит от «Атрибута_3», а «Атрибут_3» зависит от «Атрибута_1», то все три атрибута обязательно входят в один кортеж.

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

Например, некоторая таблица содержит три атрибута «Поставщик», «Товар» и «Покупатель». Покупатель_1 приобретает несколько Товаров у Поставщика_1. Покупатель_1 приобрел новый Товар у Поставщика_2. Тогда в силу изложенного выше требования Поставщик_1 обязан поставлять Покупателю_1 тот же самый новый Товар, а Поставщик_2 должен поставлять Покупателю_1, кроме нового Товара, всю номенклатуру Товаров Поставщика_1. Этого на практике не бывает. Покупатель свободен в своем выборе товаров. Поэтому для устранения отмеченного затруднения все три атрибута разносят по разным отношениям (таблицам). После выделения трех новых отношений (Поставщик, Товар и Покупатель) необходимо помнить, что при извлечении информации (например, о покупателях и товарах) необходимо в запросе соединить все три отношения. Любая комбинация соединения двух отношений из трех неминуемо приведет к извлечению неверной (некорректной) информации. Некоторые СУБД снабжены специальными механизмами, устраняющими извлечение недостоверной информации. Тем не менее, следует придерживаться общей рекомендации: структуру базы данных строить таким образом, чтобы избежать применения 4НФ и 5НФ.

Пятая нормальная форма ориентирована на работу с зависимыми соединениями. Указанные зависимые соединения между тремя атрибутами встречаются очень редко. Зависимые соединения между четырьмя, пятью и более атрибутами указать практически невозможно.

Доменно-ключевая нормальная форма

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

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

Любая переменная отношения, находящаяся в ДКНФ, обязательно находится в 5НФ. Однако не любую переменную отношения можно привести к ДКНФ.

Шестая нормальная форма

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

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

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

Таб.№ Время Должность Домашний адрес
6575 01-01-2000:10-02-2003 слесарь ул.Ленина,10
6575 11-02-2003:15-06-2006 слесарь ул.Советская,22
6575 16-06-2006:05-03-2009 бригадир ул.Советская,22

Переменная отношения «Работники» не находится в 6НФ и может быть подвергнута декомпозиции на переменные отношения «Должности работников» и «Домашние адреса работников».

Источник

Если каждый атрибут таблицы содержит только одно значение

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

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

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

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

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

Вначале определим ненормализованную таблицу StudentCourses, которая содержит всю эту информацию:

Для каждого студента определен уникальный идентификатор StudentId, а также атрибут Name (имя), Emails (все электронные адреса), Course1 /Course2(курс), Date1/Date2 (дата поступления), Teacher1/Teacher2 (преподаватель). Также чтобы различать преподавателей (так как теоретически могут быть преподаватели с одной и той же фамилией), добавлен атрибут TeacherId1/TeacherId2. Для курсов такой идентификатор не требуется, так как в нашем случае название курса уникально.

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

Эта таблица представляет прекрасный пример отклонения от первой нормальной формы. В первую очередь мы видим группу повторяющихся атрибутов, которые представляют данные по одному курсу: Course, Date, TeacherId, Teacher. Эти атрибуты представляют повторяющуюся группу, которую можно условно назвать StudentCourse.

StudentCourse = (Course, Date, TeacherId, Teacher)

Вторая проблема — атрибут Emails содержит набор электронных адресов. Фактически этот атрибут также образует повторяющуюся группу.

Для избавления от первой повторяющейся группы атрибутов применим первый подход: создадим для каждой повторяющейся группы отдельную строку.

StudentId Name Emails CourseId Course Date TeacherId Teacher
1 Том 1 Математика 11/06/2017 1 Смит
1 Том 2 JavaScript 14/06/2017 2 Адамс
2 Сэм sam@gmail.com sam@hotmail.com 3 Алгоритмы 12/06/2017 2 Адамс
3 Боб 1 Математика 13/06/2017 1 Смит

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

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

Email StudentId
sam@gmail.com 2
sam@hotmail.com 2

Так как электронный адрес в принципе уникален, то его можно сделать первичным ключом.

Таким образом, таблицы Emails с таблицей StudentCourses будет связана связью один ко многим (один студент — много электронных адресов). И в этом случае таблица StudentCourses сократится следующим образом:

StudentId Name CourseId Course Date TeacherId Teacher
1 Том 1 Математика 11/06/2017 1 Смит
1 Том 2 JavaScript 14/06/2017 2 Адамс
2 Сэм 3 Алгоритмы 12/06/2017 2 Адамс
3 Боб 1 Математика 13/06/2017 1 Смит

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

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

Источник

Adblock
detector