нормализация БД

структур данных и операций их обработки.

Различают :
иерархическую,
сетевую,

реляционную модели.

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

уровне дерева имеется один узел – корень, на следующем уровне располагаются узлы, связанные с этим корнем, затем узлы, связанные с узлами предыдущего уровня, и т. д. Каждый узел может иметь только одного предка.

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

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

Например, каждый преподаватель может обучать много студентов и каждый студент

может обучаться у многих преподавателей

Сетевая модель

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

Эдгаром Ф. Коддом. В ней информация представляется в виде двумерных

таблиц, а операции сводятся к манипуляциям с таблицами. В 1980-х годах она получила широкое распространение, а реляционные СУБД стали промышленным стандартом.

Причины доминирования РМД обусловлены тем, что имеются:
· развитая теория (реляционная алгебра);
· аппарат сведения других моделей данных к РМД;
·специальные средства ускоренного доступа к информации;
· стандартизированный высокоуровневый язык запросов к БД, позволяющий манипулировать данными без знания физической организации БД.

появлением объектно-ориентированных языков. Такие БД хранят методы классов, что позволяет

интегрировать данные и их обработку в приложениях.

соответствует понятие «отношение» (relation).
Таблица отражает объект реального мира –

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

содержащую некоторые данные. Сущность – объект любой природы, данные о

котором хранятся в БД. Атрибуты – свойства, характеризующие сущность (столбцы). Степень отношения – количество столбцов. Схема отношения – список имен атрибутов, например, СОТРУДНИК (№, ФИО, Год рождения, Должность, Кафедра). Домен – совокупность значений атрибутов отношения (тип данных). Кортеж – строка таблицы. Кардинальность (мощность) – количество строк в таблице.

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

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

и ПРЕДМЕТ (Назв Пр, Часы) связаны отношением СТУДЕНТ_ПРЕДМЕТ (ФИО, Назв

Пр, Оценка), в котором внешние ключи ФИО и Назв_Пр образуют составной ключ.

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

целостности.
СУБД должна контролировать соответствие данных заданным ограничениям при переводе

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

существованию – потенциальный ключ отношения не может иметь пустого значения

(NULL).

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

Целостность реляционных данных (2)

имела эффективный инструментарий – операции реляционной алгебры. Основной единицей обработки

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

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

языке манипулирования данными СУБД (SQL, QBE, другие языки запросов). Язык

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

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

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

способами. При проектировании БД в качестве отправной точки может использоваться

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

 Таблица 13

·     потенциальная противоречивость (аномалии).
Под избыточностью понимают повторение данных в

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

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

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

большим числом пустых атрибутов. Если мы хотим указать, что один

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

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

Нормализация баз данных (2)

видами зависимостей являются:
· функциональные;
· многозначные;
· транзитивные.
Базовым

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

Нормализация баз данных (3)

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

атрибут того же отношения, если для каждого значения первого атрибута

существует множество соответствующих значений второго атрибута. Многозначные зависимости могут быть:
·   один-ко-многим (1:М);
·   многие-к-одному (М:1);
·   многие-ко-многим (М:М).

Нормализация баз данных (4)

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

нормальных форм:
·   первая нормальная форма (1НФ);
·   вторая нормальная форма (2НФ);
·   третья нормальная форма (3НФ);
·   усиленная 3НФ или нормальная форма Бойса-Кодда (БКНФ);
·   четвертая нормальная форма (4НФ);
·  пятая нормальная форма (5НФ).

Нормализация баз данных (5)

содержит только одно значение для каждого атрибута (столбца), то есть

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

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

Нормализация баз данных (6)

в 1НФ, и каждый неключевой атрибут полностью функционально зависит от

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

Нормализация баз данных (7)

на два, в которых все неключевые атрибуты будут полностью функционально

зависеть от ключа: сотрудники (Код сотрудника, ФИО, Должность, Номер отдела, Наименование отдела) и Квалификации_сотрудников (Код сотрудника, Квалификация) (табл. 15–16).
Таблица 15 Таблица 16

Нормализация баз данных (8)

во 2НФ и ни один из его неключевых атрибутов не

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

Нормализация баз данных (8)

содержит промежуточный шаг (зависимость Номер отдела ’ Наименование отдела). Для

приведения в 3НФ необходимо исключить эту транзитивную зависимость, декомпозируя отношение на два: сотрудники (Код сотрудника, ФИО, Должность, Номер отдела) и отделы (Номер отдела, Наименование отдела) (табл. 17–18).
Таблица 17 Таблица 18

Нормализация баз данных (9)

в отношении были только такие функциональные зависимости, левая часть которых

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

Рис. 15. Алгоритм приведения ненормализованных схем в 3НФ

Нормализация баз данных (10)

ключ и ничего, кроме ключа».


Нормальные формы высших порядков

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