Глава 2. Логическое проектирование реляционных баз данных
Будем считать, что проблема логического проектирования реляционной базы данных состоит в обоснованном принятии решений о том:
При этом мы очень коротко коснемся очень важного аспекта проектирования - определения ограничений целостности (за исключением ограничения первичного и внешнего ключа), поскольку при использовании СУБД с развитыми механизмами ограничений целостности (например, SQL-ориентированных систем) трудно предложить какой-либо общий подход к определению ограничений целостности.
2.1. Проектирование реляционных баз данных с использованием аппарата нормализации
Отношения реляционной базы данных содержат как структурную, так и семантическую (смысловую) информацию. Структурная информация задается схемой отношения, а семантическая выражается функциональными связями между атрибутами схемы. Группировка атрибутов должна быть рациональной и удовлетворять следующим требованиям:
Пример.
Отношение: Поставка (Название_фирмы, Адрес, Товар, Кол-во,
Цена)
Избыточность: кортежи отношения многократно дублируют название и адрес фирмы, если она поставляет несколько видов товара, а тем более плохо, если имеется несколько поставок одного вида товара.
Аномалии модификации: вследствие избыточности при обновлении необходимо просматривать все отношение для нахождения и изменения всех подходящих строк; изменение адреса фирмы, выполненное не во всех кортежах, относящихся к некоторой конкретной фирме, ведет к нарушению целостности.
Аномалии удаления: удаление всех кортежей с поставками от некоторого поставщика приведет к потере адреса и других реквизитов фирмы.
Аномалии включения: предположим, что заключен договор, но еще нет поставок от некоторой фирмы: следует ли включать кортежи с пустым (NULL) значением количества? А не забудем ли мы впоследствии удалить строку с неопределенным значением?
Таким образом, основная цель логического проектирования базы данных - сокращение избыточности хранимых данных и устранение возможных потенциальных аномалий работы с базами данных.
Для удовлетворения вышеотмеченных требований Э.Коддом предложен аппарат нормализации отношений. Нормализация отношений - это пошаговый обратимый процесс композиции или декомпозиции исходных отношений в отношения, обладающие лучшими свойствами при включении, изменении и удалении данных, назначение им ключей по определенным правилам нормализации и выявление всех возможных функциональных зависимостей.
В теории реляционных баз данных обычно выделяется следующая последовательность
нормальных форм:
Основные свойства нормальных форм:
Нормальные формы отношений основываются на фундаментальных в теории реляционных баз данных понятиях функциональной и многозначной зависимости.
Определение 1. Функциональная зависимость.
В отношении R атрибут Y функционально зависит от атрибута X (X и Y могут быть
составными) в том и только в том случае, если каждому значению X соответствует
в точности одно значение Y: R.X ->R.Y.
Табельный номер ->Фамилия; Должность ->Зарплата.
Определение 2. Полная функциональная зависимость.
Функциональная зависимость R.X -> R.Y называется полной, если атрибут Y не
зависит функционально от любого точного подмножества X.
Определение 3. Неключевой атрибут.
Неключевым атрибутом называется любой атрибут отношения, не входящий в состав
ключа (в частности, первичного).
Определение 4. Функционально полная и частичная зависимость неключевого
атрибута от составного ключа.
Неключевой атрибут функционально полно зависит от составного ключа, если он
функционально зависит от ключа, но не находится в функциональной зависимости
ни от какой части ключа, в противном случае имеет место частичная зависимость.
Отношение:
Чтение лекций (Таб_номер, Название_курса, Кол-во_часов)
Название_курса ->Кол-во_часов
Зависимость неключевого атрибута Кол-во_часов от части составного ключа говорит о частичной зависимости.
Определение 5. Транзитивная функциональная зависимость.
Функциональная зависимость R.X -> R.Y называется транзитивной, если существует
такой атрибут Z, что имеются функциональные зависимости R.X -> R.Z и R.Z
-> R.Y и отсутствует функциональная зависимость R.Z ->R.X.
Фамилия ->Офис ->Телефон.
Определение 6. Взаимно независимые атрибуты.
Два или более атрибута взаимно независимы, если ни один из этих атрибутов не
является функционально зависимым от других.
В отношении Чтение лекций:
Кол-во_часов ->->Таб_номер;
Таб_номер ->-> Кол-во_часов.
Определение 7. Отношение находится в 1NF тогда и только тогда, когда все входящие в него атрибуты являются атомарными (неделимыми).
Отношение R1
Функциональные зависимости: |
Таб_номер ->ФИО; Таб_номер -> Оклад; Таб_номер ->Офис; Офис ->Телефон; Таб_номер, Имя_ребенка-> Возраст_ребенка. |
Атрибуты ФИО, Оклад, Офис не находятся в полной функциональной зависимости от ключа, поскольку функционально зависят от части ключа (Таб_номер). Следствием это является
Определение 8. Отношение находится в 2NF, если оно находится в 1NF и каждый неключевой атрибут функционально полно зависит от первичного ключа (см. определение 4).
Для приведения отношения во 2NF необходимо:
Если допустить наличие нескольких ключей, то определение 8 примет вид:
Определение 8~. Отношение находится в 2NF, если оно находится в 1NF и каждый неключевой атрибут функционально полно зависит от каждого ключа отношения.
Наличие транзитивной зависимости
Таб_номер->Офис;
Офис ->Телефон
порождает аномалии следующего характера:
Определение 9 (в предположении существования единственного ключа). Отношение находится в 3NF в том и только в том случае, если оно находится в 2NF и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.
Для исключения транзитивной зависимости нужно произвести декомпозицию отношения R4 в два отношения R5 и R6.
В результате преобразований имеем три отношения в 3NF, свободные от отмеченных аномалий:
Отношение R3 | Первичный ключ: | Таб_номер, Имя ребенка |
Функциональные зависимости: | Таб_номер, Имя_ребенка ->Возраст |
|
Отношение R5 | Первичный ключ: | Таб_номер |
Функциональные зависимости: |
Таб_номер -> ФИО Таб_номер -> Оклад Таб_номер -> Офис |
|
Отношение R6 | Первичный ключ: | Офис |
Функциональные зависимости: | Офис -> Телефон |
Если отказаться от того ограничения, что отношение обладает единственным ключом, то определение 3NF примет следующую форму:
Определение 9~. Отношение находится 3NF в том и только в том случае, если оно находится во 2NF, и каждый неключевой атрибут не является транзитивно зависимым от какого-либо ключа отношения.
На практике третья нормальная форма схем отношений достаточна в большинстве случаев, и приведением к третьей нормальной форме процесс проектирования реляционной базы данных обычно заканчивается.
При отсутствии многозначной зависимости, но наличии других зависимостей атрибутов, кроме зависимости от ключа, 3NF не гарантирует отсутствия аномалий операций включения, обновления и удаления. В этом случае применяют усиленную 3NF Бойса-Кодда (BCNF).
Рассмотрим пример отношения:
Курсовой проект (Преподаватель, Предмет, Тема, Студент)
Курсовые проекты ведут несколько преподавателей по различным дисциплинам и каждый студент закреплен за одним из них. Студент выполняет только один проект, а одну и ту же тему проекта могут выполнять несколько студентов, но у разных преподавателей.
Преподаватель | Предмет | Тема | Студент |
Иванов | экономика | Тема_1 | Смирнов |
Зайцев | физика | Тема_2 | Федоров |
Хабаров | математика | Тема_2 | Антонов |
Иванов | экономика | Тема_2 | Егоров |
Григорьев | статистика | Тема_1 | Круглов |
Григорьев | статистика | Тема_3 | Фомин |
Возможные ключи:
Функциональные зависимости:
Преподаватель, Тема ->->Студент (зависимость от ключа);
Предмет, Тема ->->Студент (зависимость от ключа);
Студент -> Тема.
Приведенное отношение находится в 3NF, так как в нем отсутствуют частичные и транзитивные зависимости неключевых атрибутов от ключа. Однако имеется зависимость части составного ключа Тема от неключевого атрибута Студент, что порождает следующие аномалии:
Устранение этих аномалий достигается устранением функциональной зависимости части составного ключа от неключевого атрибута (Студент -> Тема).
Определение 10. Детерминант.
Детерминант - любой атрибут, от которого полностью функционально зависит некоторый
другой атрибут.
Определение 11.
Отношение находится в нормальной форме Бойса-Кодда (BCNF), если оно находится
в 3NF и каждый детерминант является возможным ключом.
Можно дать и другое определение BCNF.
Определение 11~.
Отношение находится в нормальной форме Бойса-Кодда (BCNF), если оно находится
в 3NF и в нем отсутствуют зависимости ключей или их частей от неключевых атрибутов.
Очевидно, что это требование не выполнено для отношения Курсовой проект. Можно произвести его декомпозицию к двум отношениям Руководство (Преподаватель, Предмет) и Выполнение (Студент, Предмет, Тема).
Отношение |
|
Отношение |
|
Соединение полученных отношений Руководство и Выполнение по атрибуту Предмет дает исходное отношение Курсовой проект.
Отношение | Первичный ключ: | Преподаватель |
Руководство | Функциональные зависимости: | Преподаватель -> Предмет |
Отношение | Первичный ключ: | Студент |
Выполнение | Функциональные зависимости: | Студент -> Предмет Студент-> Тема |
Если в отношении присутствуют многозначные зависимости, то устранение возможных аномалий выполняется приведением к 4NF.
Рассмотрим пример следующей схемы отношения:
Проекты (Проект_номер, Таб_номер, Проект_задание)
Отношение Проекты содержит номера проектов, для каждого проекта список сотрудников, которые могут выполнять проект, и список заданий, предусматриваемых проектом. Сотрудники могут участвовать в нескольких проектах, и разные проекты могут включать одинаковые задания.
Каждый кортеж отношения связывает некоторый проект с сотрудником, который может участвовать в этом проекте, и заданием, которое сотрудник выполняет в рамках данного проекта. Предполагается, что любой сотрудник, участвующий в проекте, выполняет все задания, предусмотренные проектом.
Проект_номер (A) | Таб_номер (B) | Проект_задание (C) |
П1
|
C1
|
1
|
П1
|
C1
|
2
|
П1
|
С2
|
1
|
П1
|
С2
|
2
|
П2
|
C1
|
1
|
П2
|
C1
|
3
|
П2
|
C1
|
4
|
П2
|
С3
|
1
|
П2
|
С3
|
3
|
П2
|
С3
|
4
|
По причине сформулированных выше условий единственным возможным ключом отношения является составной атрибут Проект_Номер, Таб_номер, Проект_задание и нет никаких других детерминантов. Следовательно, отношение Проекты находится в BCNF. Но при этом оно обладает недостатками: если, например, некоторый сотрудник присоединяется к данному проекту, необходимо вставить в отношение Проекты столько кортежей, сколько заданий в нем сотрудник будет выполнять. Аналогичная ситуация возникает при появлении нового проекта.
Определение 12. Многозначные зависимости.
В отношении R (A, B, C) существует многозначная зависимость R.A->->R.B в том
и только в том случае, если множество значений B, соответствующее паре значений
A и C, зависит только от A и не зависит от С (то есть если для каждого значения
атрибута R.A существует хорошо определенное множество соответствующих значения
атрибута R.B).
В отношении Проекты существуют следующие две многозначные зависимости:
Проект_номер ->-> Таб_номер;
Проект_номер ->-> Проект_задание
Легко показать, что в общем случае в отношении R (A,B,C) существует многозначная зависимость R.A -> R.B в том и только в том случае, когда существует многозначная зависимость R.A ->R.C.
Определение 13. Полная декомпозиция и проецирование без потерь.
Полной декомпозицией отношения называют такую совокупность произвольного числа ее проекций, соединение которых полностью совпадает с исходным отношением. Под проецированием без потерь понимается такой способ декомпозиции отношения, при котором исходное отношение полностью и без избыточности восстанавливается путем естественного соединения полученных отношений.
Теорема Фейджина.
Отношение R (A, B, C) можно спроецировать без потерь в отношения R1(A,B) и R2(A,C) в том и только в том случае, когда в отношении существуют многозначные зависимости A->->B и A->->С.
Определение 14. Отношение находится в четвертой нормальной форме (4НФ), если оно находится в BCNF и все многозначные зависимости являются функциональными зависимостями с детерминантами - возможными ключами отношения.
В нашем примере можно произвести декомпозицию отношения Проекты в два отношения Проекты-Cотрудники и Проекты-Задания:
|
|
||||||||||||||||||
|
|
Оба эти отношения находятся в 4NF и свободны от отмеченных аномалий. Соединение отношений Проекты-Cотрудники и Проекты-Задания дает отношение Проекты.
Однако не всегда декомпозиция схем отношений гарантирует обратимость. Отношение может быть восстановлено без потерь соединением его проекций, если оно удовлетворяет зависимости по соединению.
Определение 15. Зависимость соединения.
Отношение R(X, Y, . . . ,Z) удовлетворяет зависимости соединения *(X,Y,...,Z)
в том и только в том случае, когда R восстанавливается без потерь путем соединения
своих проекций на X, Y, ..., Z.
В качестве примера рассмотрим отношение
Сотрудники-Отделы-Проекты (Таб_номер, Отд_номер, Проект_номер)
Предположим, что один и тот же сотрудник может работать в нескольких отделах и работать в каждом отделе над несколькими проектами. Первичным ключом этого отношения является полная совокупность его атрибутов, отсутствуют функциональные и многозначные зависимости.
Поэтому отношение находится в 4NF. Однако в нем могут существовать аномалии, которые можно устранить путем декомпозиции в три отношения.
Определение 16. Отношение находится в нормальной форме проекции-соединения PJ/NF в том и только в том случае, когда в каждой ее полной декомпозиции все проекции содержат возможный ключ.
Введем следующие имена составных атрибутов:
Предположим, что в отношении Сотрудники-Отделы-Проекты существует зависимость соединения:
* (СО, СП, ОП)
Возможные аномалии при работе с отношением Сотрудники-Отделы-Проекты можно устранить путем декомпозиции исходного отношения в три новых отношения:
Пятая нормальная форма - это последняя нормальная форма, которую можно получить путем декомпозиции. Ее условия достаточно нетривиальны, и на практике 5NF не используется.
Заметим, что зависимость соединения является обобщением как многозначной, так и функциональной зависимостей.
2.3. Об ограничениях целостности
Целостность (от англ. integrity - нетронутость, неприкосновенность, сохранность, целостность) понимается как правильность данных в любой момент времени. Поддержание целостности базы данных может рассматриваться как защита данных от неверных изменений или разрушений.
Выделяют три группы правил целостности:
Общая мотивировка первых двух правил целостности общих для любых реляционных баз данных, состоит в следующем:
Для любой конкретной базы данных существует ряд дополнительных специфических правил, которые относятся к ней одной и определяются разработчиком. Чаще всего контролируется:
Вопрос 1. Может ли внешний ключ принимать неопределенное значение (NULL-значение)? Значение внешнего ключа должно:
Например, в отношении Поставка, очевидно, поставка, осуществляемая неизвестным поставщиком, или поставка неизвестного продукта, не может иметь NULL-значения, в то время как атрибут Отдел в отношении Сотрудник может иметь NULL-значение, если сотрудник пока еще не зачислен ни в какой отдел.
Вопрос 2. Что должно случиться при попытке УДАЛЕНИЯ экземпляра целевой сущности, на которую ссылается внешний ключ? Например, при удалении поставщика, который осуществил по крайней мере одну поставку.
Существует три возможности:
КАСКАДИРУЕТСЯ | Операция удаления "каскадируется" с тем, чтобы удалить также поставки этого поставщика. |
ОГРАНИЧИВАЕТСЯ | Удаляются лишь те поставщики, которые еще не осуществляли поставок. Иначе операция удаления отвергается. |
УСТАНАВЛИВАЕТСЯ | Для всех поставок удаляемого поставщика внешний ключ устанавливается в неопределенное значение, а затем этот поставщик удаляется. Такая возможность, конечно, неприменима, если данный внешний ключ не должен содержать NULL-значений. |
Вопрос 3. Что должно происходить при попытке ОБНОВЛЕНИЯ первичного ключа экземпляра целевой сущности, на которую ссылается некоторый внешний ключ? Например, может быть предпринята попытка обновить номер такого поставщика, для которого имеется по крайней мере одна соответствующая поставка. Имеются те же три возможности, как и при удалении:
КАСКАДИРУЕТСЯ | Операция обновления "каскадируется" с тем, чтобы обновить также и внешний ключ в поставках этого поставщика. |
ОГРАНИЧИВАЕТСЯ | Обновляются первичные ключи лишь тех поставщиков, которые еще не осуществляли поставок. Иначе операция обновления отвергается. |
УСТАНАВЛИВАЕТСЯ | Для всех поставок такого поставщика внешний ключ устанавливается в неопределенное значение, а затем обновляется первичный ключ поставщика. Такая возможность, конечно, неприменима, если данный внешний ключ не должен содержать NULL-значений. |
2.4. Получение реляционной схемы из ER-модели
Шаг 1. Каждая простая сущность превращается в отношение. Простая сущность - сущность, не являющаяся подтипом и не имеющая подтипов. Имя сущности становится именем отношения.
Шаг 2. Каждый атрибут становится возможным столбцом с тем же именем; может выбираться более точный формат. Столбцы, соответствую-щие необязательным атрибутам, могут содержать неопределенные значения; столбцы, соответствующие обязательным атрибутам, - не могут.
Шаг 3. Компоненты уникального идентификатора сущности превращаются в первичный ключ отношения. Если имеется несколько возможных уникальных идентификаторов, выбирается наиболее используемый.
Шаг 4. Связи "многие к одному" (и "один к одному") становятся внешними ключами. Для этого делается копия уникального идентификатора с конца связи "один", и соответствующие столбцы составляют внешний ключ. Необязательные связи соответствуют столбцам, допускающим неопределенные значения; обязательные связи - столбцам, не допускающим неопределенные значения.
Шаг 5. В таблицах, построенных на основе ассоциаций, внешние ключи используются для идентификации участников ассоциации, а в таблицах, построенных на основе характеристик и обозначений, внешние ключи используются для идентификации сущностей, описываемых этими характеристиками и обозначениями. Специфицировать ограничения, связанные с каждым из этих внешних ключей.
Шаг 6. Если в концептуальной схеме присутствовали подтипы, то возможны два способа:
При применении способа (а) таблица создается для наиболее внешнего супертипа. В таблицу добавляется по крайней мере один столбец, содержащий код ТИПА и он становится частью первичного ключа. Для работы с подтипами могут создаваться представления.
При использовании метода (б) супертип воссоздается с помощью конструкции UNION.
Все в одной таблице | Таблица - на подтип |
Преимущества | |
Все хранится вместе | Более ясны правила подтипов |
Легкий доступ к супертипу и подтипам | Программы работают только с нужными таблицами |
Требуется меньше таблиц | |
Недостатки | |
Слишком общее решение | Слишком много таблиц |
Требуется дополнительная логика работы с разными наборами столбцов и разными ограничениями | Смущающие столбцы в представлении UNION |
Потенциальное узкое место (в связи с блокировками) | Потенциальная потеря производительности при работе через UNION |
Для хранения неопределенных значений требуется дополнительная память | Над супертипом невозможны модификации |
Шаг 7. Выполнить шаги по нормализации полученных отношений, приведя их к желаемой нормальной форме.
Шаг 8. Указать ограничения целостности проектируемой базы данных и дать (если это необходимо) краткое описание полученных таблиц и их полей.
Шаг 9. Создать индексы для первичного ключа (уникальный индекс), внешних ключей и тех атрибутов, на которых предполагается в основном базировать запросы и выполнять соединения.
В заключение приведем пример описания таблиц базы данных Питание, ER-модель которой приводилась в гл. 1 настоящего учебного пособия.
Создать таблицу Блюда (ID_БЛ Целое, Описание Текст 60,
Вид Текст 7) *( Стержневая сущность )
Первичный ключ | (ID_БЛ) |
Ограничения |
|
Создать таблицу Состав ( ID_БЛ Целое, ID_ПР Целое,
Вес Целое ) *( Связывает Блюда и Продукты )
Первичный ключ | (ID_БЛ, ID_ПР) |
Внешний ключ | (ID_БЛ из Блюда NULL-значения НЕ ДОПУСТИМЫ Удаление из Блюда КАСКАДИРУЕТСЯ Обновление Блюда.ID_БЛ КАСКАДИРУЕТСЯ) |
Внешний ключ | (ID_ПР из Продукты NULL-значения НЕ ДОПУСТИМЫ Удаление из Продукты ОГРАНИЧИВАЕТСЯ Обновление Продукты.ID_ПР КАСКАДИРУЕТСЯ) |
Ограничения |
|
Иногда связи между первичными и внешними ключами удобно изображать в виде вертикальной диаграммы. На примере базы данных Питание вертикальная диаграмма будет иметь вид:
В каждом отношении выделены атрибуты, составляющие первичный ключ. Вертикальные стрелки определяют соответствие первичных и внешних ключей.