База данных. ЭУМК Базы данных. Пояснительная записка Теоретический раздел Практический раздел Раздел контроля знаний Вспомогательный раздел Пинск
 Скачать 2.33 Mb.
|
|
Нормализация отношений – это пошаговый обратимый процесс декомпозиции (разложения) исходных отношений базы данных на другие, более мелкие, с целью ликвидации нежелательных функциональных зависимостей. Нормализация отношений позволяет устранить избыточное дублирование данных, обеспечивает их непротиворечивость, уменьшает трудозатраты на ведение (ввод, корректировку, удаление) базы данных. Аппарат нормализации отношений был разработан Е. Коддом. В нем определяются различные нормальные формы. Каждая нормальная форма ограничивает типы допустимых функциональных зависимостей отношения и устраняет некоторые аномалии при выполнении операций над отношениями базы данных. Функциональные зависимости. Дадим определение функциональной зависимости. Функциональная зависимость – один из возможных типов зависимостей между атрибутами. Пусть X и Y – атрибуты отношения R. Атрибут Y отношения R функционально зависит от атрибута X отношения R, если в каждый момент времени каждому значению X соответствует одно и то же значение Y. Функциональная зависимость записывается: X -> Y. Если X -> Y и Y -> X, то между X и Y существует взаимно однозначное соответствие. Атрибуты X и Y могут быть составными, т.е. могут представлять собой группы, состоящие из двух и более атрибутов. С практической точки зрения смысл данного определения состоит в том, что если Y функционально зависит от X, то каждый из кортежей, имеющих одно и то же значение X, должен иметь также одно и то же значение Y. Значения X и Y могут изменяться время от времени, но при этом должны изменяться так, чтобы каждое уникальное значение X имело только одно уникальное значение Y, связанное с ним. В конкретной ситуации функциональные зависимости определяются путем детализации свойств всех атрибутов в отношении, т.е. функциональные зависимости получают исходя из природных свойств самих атрибутов. Нормальные формы. Процесс проектирования БД с использованием метода нормальных форм является итерационным и заключается в последовательном переводе отношений из первой нормальной формы в нормальные формы более высокого порядка по определенным правилам. Каждая следующая нормальная форма ограничивает определенный тип функциональных зависимостей, устраняет соответствующие аномалии при выполнении операций над отношениями БД и сохраняет свойства предшествующих нормальных форм. Выделяют следующие нормальные формы: Первая нормальная форма (1НФ); Вторая нормальная форма (2НФ); Третья нормальная форма (3НФ); Усиленная третья нормальная форма, или нормальная форма Бойса-Кодда (БКНФ); Четвертая нормальная форма (4НФ); Пятая нормальная форма (5НФ). Отношение находится в первой нормальной форме (1НФ) тогда и только тогда, когда все входящие в него атрибуты являются атомарными, т.е. значения атрибутов, образующие соответствующие домены, рассматриваются как неделимые, а не как множества из более элементарных доменов. Неделимость поля означает, что содержащиеся в нем значения не должны делиться на более мелкие или представлять из себя повторяющиеся группы. В общем случае можно считать, что отношение и отношение в первой нормальной форме – это синонимы. Отношение находится во второй нормальной форме (2НФ), если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от первичного (составного) ключа. Таким образом, если в отношении нет частичных функциональных зависимостей, то оно находится в 2НФ. Дадим определение частичной и полной функциональным зависимостям. Если в отношении неключевой атрибут функционально зависит от части составного ключа, то между ключом и неключевым атрибутом имеет место частичная функциональная зависимость. Если в отношении неключевой атрибут функционально зависит от составного ключа и не находится в функциональной зависимости от любых его частей, то неключевой атрибут функционально полно зависит от ключа. Рассмотрим отношение, в котором присутствуют частичные и полные функциональные зависимости: Выдача книг (Шифр книги, Авторы, Название, Год издания, Номер читательского билета, Ф.и.о., Шифр группы, Курс, Специальность, Факультет, Вид обучения, Дата выдачи, Дата возврата). Ключом данного отношения являются поля: Шифр книги, Номер читательского билета. Полная функциональная зависимость: Шифр книги, Номер читательского билета -> Дата выдачи, Дата возврата. Частичные функциональные зависимости: Шифр книги -> Авторы, Название, Год издания. Номер читательского билета -> Ф.и.о., Шифр группы, Курс, Специальность, Факультет, Вид обучения. Частичные функциональные зависимости приводят к аномалиям: избыточно дублируются сведения о книгах (авторы, название, год издания), поскольку одинаковую книгу могут взять несколько читателей; избыточно дублируются сведения о читателях (ф.и.о., шифр группы, курс и т.д.), поскольку читатель может взять несколько книг; существует проблема контроля правильности данных: измененные сведения о книге или читателе приходится вносить более чем в один кортеж; существует проблема добавления записей: включить в таблицу кортеж о новой книге можно только, если эта книга взята; включить в таблицу кортеж о новом читателе можно только, если он взял книгу; существует проблема удаления записей: удаление кортежа может привести к потере сведений о книге или читателе. Перевод отношения в следующую нормальную форму осуществляется методом «декомпозиции без потерь». Такая декомпозиция должна обеспечить то, что запросы (выборка данных по условию) к исходному отношению и к отношениям, получаемым в результате декомпозиции, дадут одинаковый результат. Основной операцией метода является операция проекции. Чтобы устранить частичную зависимость и привести отношение во 2НФ, необходимо разложить его на новые отношения следующим образом: построить проекцию без атрибутов, которые находятся в частичной зависимости от составного ключа; построить проекцию на часть составного ключа и атрибуты, зависящие от этой части. При разложении отношения Выдача книг получают три новых отношения: Выдача книг (Шифр книги, Номер читательского билета, Дата выдачи, Дата возврата); Книги (Шифр книги, Авторы, Название, Год издания); Читатели (Номер читательского билета, Ф.и.о., Шифр группы, Курс, Специальность, Факультет, Вид обучения). В первом отношении ключом являются атрибуты – Шифр книги, Номер читательского билета; во втором – Шифр книги; в третьем – Номер читательского билета. Отношение находится в третьей нормальной форме (3НФ), если оно находится в 2НФ и в нем отсутствуют транзитивные зависимости неключевых атрибутов от ключа. Если в отношении для атрибутов X,Y,Z имеют место функциональные зависимости X -> Y, Y -> Z, но обратная зависимость отсутствует, то атрибут Z транзитивно зависит от атрибута X. Рассмотрим отношение, в котором присутствуют транзитивные зависимости: Сотрудники (Табельный номер, Ф.и.о., Кафедра, Номер корпуса, Номер аудитории, Телефон кафедры, Должность, Категория, Оклад, Надбавка за должность). Ключом данного отношения является Табельный номер. В отношении Сотрудники имеют место следующие функциональные зависимости: Табельный номер -> Ф.и.о., Кафедра, Номер корпуса, Номер аудитории, Телефон кафедры, Должность, Категория, Оклад, Надбавка за должность; Кафедра -> Номер корпуса, Номер аудитории, Телефон кафедры; Должности -> Надбавка за должности; Категория -> Оклад. Три последние зависимости являются транзитивными. Наличие транзитивных зависимостей порождает аномалии следующего характера: избыточно дублируется информация о кафедрах, должностях, категориях; сложное редактирование данных: изменение, например, оклада требует поиска и замены его во всех кортежах для сотрудников, имеющих одинаковую категорию; существует проблема удаления записей: удаление кортежа может привести к потере сведений о кафедре, должности, категории; существует проблема добавления записей: невозможно, например, включить сведения о новой должности, если эту должность никто не занимает. Чтобы устранить транзитивную зависимость и привести отношение в 3НФ, необходимо: построить проекцию без атрибутов, находящихся в транзитивной зависимости от ключа; построить проекцию на неключевые атрибуты, между которыми имеется функциональная зависимость. В нашем примере получим: Сотрудники (Табельный номер, Ф.и.о., Кафедра, Должность, Категория); Кафедры (Кафедра, Номер корпуса, Номер аудитории, Номер телефона); Должности (Должность, Надбавка за должность); Категории (Категория, Оклад). В первом отношении ключ – Табельный номер, во втором – Кафедра, в третьем – Должность, в четвертом – Категория. На практике процесс проектирования схем отношений заканчивается, когда отношения приведены к 3НФ. Усиленная 3НФ или нормальная форма Бойса-Кодда (БКНФ). Если в отношении имеется зависимость атрибутов составного ключа от неключевых атрибутов, то необходимо перейти к усиленной 3НФ. Отношение находится в БКНФ, если оно находится в 3НФ и в нем отсутствуют зависимости ключей (атрибутов составного ключа) от неключевых атрибутов. Можно дать другое определение усиленной 3НФ. Отношение находится в нормальной форме Бойса-Кодда, если оно находится в третьей нормальной форме и каждый детерминант отношения является возможным ключом отношения. Если в отношении существует несколько функциональных зависимостей, то каждый атрибут или набор атрибутов, от которого зависит другой атрибут, называется детерминантом отношения. Рассмотрим отношение, моделирующее сдачу текущих экзаменов. Предположим, что студент может сдавать экзамен по одной дисциплине несколько раз, если он получил неудовлетворительную оценку. Допустим, что студента можно однозначно идентифицировать номером его зачетной книги, в то же время для электронного учета в период обучения каждый студент получает уникальный номер-идентификатор. Отношение, которое моделирует сдачу текущей сессии, имеет следующую структуру: Экзамены(Номер зач_кн, Идентификатор_студента, Дисциплина, Дата, Оценка) Возможными ключами отношения являются Номер зач_кн, Дисциплина, Дата и Идентификатор-студента, Дисциплина, Дата. В данном отношении имеют место следующие функциональные зависимости: Номер зач_кн, Дисциплина, Дата -> Оценка; Идентификатор_студента, Дисциплина, Дата -> Оценка; Номер зач_кн -> Идентификатор_студента; Идентификатор_студента -> Номер зач_кн. Это отношение находится в третьей нормальной форме, потому что в нем отсутствуют частичные и транзитивные зависимости. Для приведения отношения к нормальной форме Бойса-Кодда надо разделить отношение, например, на два со следующими схемами: Экзамен(Идентификатор_студента, Дисциплина, Дата, Оценка) Идентификаторы(Номер зач_кн, Идентификатор_сту-дента) В большинстве случаев достижение третьей нормальной формы или даже формы Бойса-Кодда считается достаточным для реальных проектов баз данных, однако в теории нормализации существуют нормальные формы высших порядков, которые уже связаны не с функциональными зависимостями между атрибутами отношений, а отражают более тонкие вопросы семантики предметной области и связаны с другими видами зависимостей. Дадим несколько определений. В отношении R(A,B,C) существует многозначная зависимость A ->> B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от А и не зависит от С. При рассмотрении функциональных зависимостей каждому значению детерминанта соответствовало только одно значение зависимого от него атрибута. При рассмотрении многозначных зависимостей одному значению некоторого атрибута соответствует устойчиво постоянное множество значений другого атрибута. Пусть дано отношение, которое моделирует предстоящую сдачу экзаменов на сессии. Допустим, оно имеет вид: (Номер зач_кн, Группа, Дисциплина) Перечень дисциплин, которые должен сдавать студент, однозначно определяется не его фамилией, а номером группы (то есть специальностью, на которой он учится). В данном отношении существуют две многозначные зависимости: Группа ->> Дисциплина, Группа ->> Номер зач_кн. Это означает, что каждой группе однозначно соответствует перечень дисциплин по учебному плану и номер группы определяет список студентов, которые в этой группе учатся. Если работать с исходным отношением, то невозможно внести информацию о новой группе и ее учебном плане (перечне дисциплин, которые должна изучить группа) до тех пор, пока в нее не будут зачислены студенты. При изменении перечня дисциплин по учебному плану, например при добавлении новой дисциплины, внести эти изменения в отношение для всех студентов, занимающихся в данной группе, весьма затруднительно. С другой стороны, если мы добавляем студента в уже существующую группу, то мы должны добавить множество кортежей, соответствующих перечню дисциплин для данной группы. Эти аномалии модификации отношения связаны с наличием двух многозначных зависимостей. В теории реляционных баз данных доказывается, что в общем случае в отношении R(A,B,C) существует многозначная зависимость A ->> B в том и только в том случае, когда существует многозначная зависимость A ->> C. Дальнейшая нормализация отношений основывается на теореме Фейджина. Теорема Фейджина. Отношение R(A,B,C) можно спроецировать без потерь в отношения R1(A,B) и R2(A,C) в том и только в том случае, когда существуют многозначные зависимости A ->> B и A ->> C. Под проецированием без потерь понимается такой способ декомпозиции отношения путем применения операции проекции, при котором исходное отношение полностью и без избыточности восстанавливается путем естественного соединения полученных отношений. Практически теорема доказывает наличие эквивалентной схемы для отношения, в котором существует несколько многозначных зависимостей. Отношение R находится в четвертой нормальной форме (4НФ) в том и только в том случае, если в случае существования многозначной зависимости A ->> B все остальные атрибуты R функционально зависят от А. В примере можно произвести декомпозицию исходного отношения в два отношения: (Номер зач_кн, Группа) (Группа, Дисциплина) Оба эти отношения находятся в 4НФ и свободны от отмеченных аномалий. Действительно, обе операции модификации теперь упрощаются: добавление нового студента связано с добавлением всего одного кортежа в первое отношение, а добавление новой дисциплины приводит к добавлению одного кортежа во второе отношение, кроме того, во втором отношении мы можем хранить любое количество групп с определенным перечнем дисциплин, в которые пока еще не зачислены студенты. Следующей нормальной формой является пятая нормальная форма (5НФ), которая связана с анализом нового вида зависимостей, зависимостей «проекции соединения». Этот вид зависимостей является в некотором роде обобщением многозначных зависимостей. Отношение R(X, Y, …, Z) удовлетворяет зависимости соединения (X, Y, …, Z) в том и только в том случае, когда R восстанавливается без потерь путем соединения своих проекций на X, Y,…, Z. Здесь X, Y, …, Z – наборы атрибутов отношения R. Наличие зависимостей «проекции соединения» в отношении делает его в некотором роде избыточным и затрудняет операции модификации. Отношение R находится в пятой нормальной форме (нормальной форме проекции соединения) в том и только в том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R. Рассмотрим отношение R1: R1(Преподаватель, Кафедра, Дисциплина). Предположим, что каждый преподаватель может работать на нескольких кафедрах и на каждой кафедре может вести несколько дисциплин. В этом случае ключом отношения является полный набор из трех атрибутов. В отношении отсутствуют многозначные зависимости, и поэтому отношение находится в 4НФ. Введем следующие обозначения наборов атрибутов: ПК (Преподаватель, Кафедра) ПД (Преподаватель, Дисциплина) КД (Кафедра, Дисциплина) Допустим, что отношение R1 удовлетворяет зависимости проекции соединения (ПК, ПД, КД). Тогда отношение R1 не находится в 5НФ, потому что единственным ключом его является полный набор атрибутов, а наличие зависимости «проекции соединения» связано с набором атрибутов, которые не составляют возможные ключи отношения R1. Для того чтобы привести это отношение в 5НФ, его надо представить в виде трех отношений: R2(Преподаватель, Кафедра) R3(Преподаватель, Дисциплина) R4(Кафедра, Дисциплина) Пятая нормальная форма редко используется на практике. В большей степени она является теоретическим исследованием. Трудно определить само наличие зависимостей «проекции–соединения», потому что утверждение о наличии такой зависимости делается для всех возможных состояний БД, а не только для текущего экземпляра отношения R1. Итак, нормализация отношений выполняется декомпозицией (разложением) их схем. Декомпозиция должна гарантировать обратимость, т.е. получение исходных отношений путем выполнения операций соединения над их проекциями. Процесс нормализации отношений последовательно устраняет частичные зависимости неключевых атрибутов от ключа, транзитивные зависимости неключевых атрибутов от ключа, зависимости ключей от неключевых атрибутов. Можно сформулировать набор правил, соблюдение которых позволит выполнять требования нормализации: каждый информационный объект (реляционная таблица) должен содержать уникальный идентификатор (ключ); ключ является простым, если он состоит из одного реквизита, или составным, если из нескольких; все описательные реквизиты должны быть взаимонезависимы, т.е. между ними не должно быть функциональных зависимостей; все реквизиты, входящие в составной ключ, должны быть также взаимонезависимы; каждый описательный реквизит должен функционально полно зависеть от ключа, т.е. каждому значению ключа должно соответствовать только одно значение описательного реквизита; при составном ключе описательные реквизиты должны зависеть целиком от всей совокупности реквизитов, образующих ключ; каждый описательный реквизит не должен зависеть от ключа транзитивно, т.е. через другой промежуточный реквизит. Выполнение требований нормализации обеспечивает построение реляционной базы данных без дублирования данных и возможность поддержания целостности данных при внесении в них изменений. 2.3. Физическая организация БД Метод сущность-связь называют также методом «ER-диаграмм». Аббревиатура ER происходит от слов Essence (сущность) и Relation (связь). Метод основан на использовании диаграмм, называемых диаграммами ER- экземпляров и диаграммами ER-типа. Основные понятия метода. Основными понятиями метода сущность-связь являются следующие: сущность; атрибут сущности; ключ сущности; связь между сущностями; степень связи; класс принадлежности экземпляров сущности; диаграммы ER-экземпляров; диаграммы ER-типа. |