Батин Н.В. Проектирование баз данных

Подождите немного. Документ загружается.

две даты начала (5.01.2007 и 10.01.2007), две даты окончания (30.01.2007 и

1.03.2007).

Аналогично можно показать, что атрибуты Адрес, Тип объекта и Норма-

тивный документ также находятся в неполной функциональной зависимости

от ключа (Табельный номер, Номер проекта), так как находятся в функцио-

нальной зависимости от части этого ключа – атрибута Номер проекта.

Атрибуты Дата начала и Дата окончания не находятся в функциональной

зависимости ни от одной из частей ключа (Табельный номер, Номер проекта).

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

от атрибута Табельный номер. Они не находятся в функциональной зависимо-

сти и от атрибута Номер проекта: например, номеру проекта 2140 соответст-

вуют две даты начала (15.01.2007 и 10.01.2007) и две даты окончания

(25.02.2007 и 1.03.2007), так как в проекте 2140 заняты два работника (и у каж-

дого из них – своя дата начала и дата окончания работы в данном проекте). Та-

ким образом, атрибуты Дата начала и Дата окончания находятся в полной

функциональной зависимости от ключа (Табельный номер, Номер проекта).

Примечание – В таблице 1.2 имеется еще одна функциональная зависимость: Тип объ-

екта → Нормативный документ. Здесь оба атрибута - неключевые. Эта функциональная за-

висимость будет учтена при приведении к третьей нормальной форме (см. подраздел 1.5).

Наличие неполных функциональных зависимостей – основная причина не-

достатков 1НФ, показанных в подразделе 1.3. Для их устранения таблицы при-

водятся ко второй нормальной форме (2НФ).

Таблица находится во второй нормальной форме (2НФ), если она нахо-

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

ной зависимости от ключа.

Примечание – Если таблица имеет простой (т.е. состоящий из одного атрибута) ключ,

то она всегда находится в 2НФ (по определению 2НФ).

Таблица приводится к 2НФ в следующем порядке:

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

симости от ключа. Эти атрибуты, вместе с ключом, выделяются в отдельную

таблицу;

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

какой-либо из частей ключа. Эти атрибуты вместе с той частью ключа, от кото-

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

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

Приведем к 2НФ таблицу 1.2. Как показано выше, атрибуты Дата начала и

Дата окончания находятся в полной функциональной зависимости от ключа

(Табельный номер, Номер проекта). Поэтому указанные атрибуты вместе с

ключом выделяются в отдельную таблицу (таблица 1.3). Назовем эту таблицу,

например, “Работа над проектами”.

Атрибуты Фамилия, Специальность и Оклад находятся в функциональной

зависимости от части ключа – атрибута Табельный номер. Поэтому эти атрибу-

ты, вместе с атрибутом Табельный номер, выделяются в отдельную таблицу

(таблица 1.4). Присвоим этой таблице имя “Сотрудники”.

Атрибуты Адрес, Тип объекта и Нормативный документ также находятся

в функциональной зависимости от части ключа – атрибута Номер проекта. Эти

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

таблицу (таблица 1.5). Назовем эту таблицу “Проекты”.

Таким образом, БД проектно-строительной организации, приведенная

к 2НФ, состоит из трех таблиц (таблицы 1.3, 1.4, 1.5).

Таблица 1.3 – Работа над проектами

Табельный номер Номер проекта Дата начала Дата окончания

12 2140 15.01.2007 25.02.2007

15 2042 5.01.2007 30.01.2007

15 2140 10.01.2007 1.03.2007

27 2060 10.01.2007 1.03.2007

30 2080 1.02.2007 25.02.2007

Таблица 1.4 – Сотрудники

Табельный номер Фамилия Специальность Оклад

12 Андреев инженер-электрик 500

15 Иванов инженер-строитель 400

27 Мишин архитектор 600

30 Яковлев инженер-строитель 500

Таблица 1.5 – Проекты

Номер проекта Адрес Тип объекта Нормативный документ

2140 ул.Лесная,2 жилой дом СНиП 75

2042 ул.Заводская, 8 склад СНиП 62

2060 ул.Речная, 12 жилой дом СНиП 75

2080 ул.Красная, 7 магазин СНиП 40

БД, приведенные к 2НФ, также могут иметь существенные недостатки.

Так, в рассматриваемом примере таблица 1.5 имеет следующие недостатки:

− избыточность данных: некоторые данные хранятся многократно. На-

пример, данные о том, какой нормативный документ соответствует каждому

типу объекта, хранятся несколько раз (столько, сколько имеется проектов с

данным типом объекта). Так, информация о том, что жилые дома проектируют-

ся согласно документу СНиП 75, приведена в таблице 1.5 дважды;

− аномалия добавления (ввода): невозможность ввода данных о норматив-

ном документе, соответствующем некоторому типу объектов, если в данный

момент в БД нет данных об объектах такого типа. Например, в таблицу 1.5 не-

возможно ввести данные о том, что объекты типа “производственный цех” про-

ектируются, например, согласно СНиП 100 (так как в таблице нет данных об

объектах типа “производственный цех”);

− аномалия удаления: при удалении данных о проекте могут быть потеря-

ны данные о нормативном документе, по которому разрабатывался данный

проект (если в БД нет данных о других проектах с тем же типом объекта). На-

пример, если из таблицы 1.5 удалить данные об объекте 2042, то будет потеря-

на информация о том, что склады проектируются согласно СНиП 62;

− аномалия обновления: если изменяется какой-либо атрибут, то его при-

ходится изменять во многих записях. Например, если изменится нормативный

документ для некоторого типа объекта, то изменение потребуется вносить

столько раз, сколько имеется проектов с данным типом объекта. Кроме того,

при этом в некоторый момент времени одному типу объекта будут соответст-

вовать разные нормативные документы.

Эти недостатки будут устранены при приведении БД к третьей нормальной

форме.

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

Основная причина недостатков БД во второй нормальной форме – наличие

транзитивных зависимостей.

Пусть атрибут B находится в функциональной зависимости от атрибута

или группы атрибутов A (A → B), а атрибут С – в функциональной зависимости

от атрибута B (B → C), причем A - ключ, B и C – неключевые атрибуты. Такая

зависимость (A → B → C) называется транзитивной.

Таблица находится в третьей нормальной форме (3НФ), если она нахо-

дится в 2НФ (а значит, и в 1НФ) и не содержит транзитивных зависимостей.

Примечание – Если таблица содержит только один неключевой атрибут или вообще не

содержит неключевых атрибутов, то она всегда находится в 3НФ, так как в ней не может

быть транзитивных зависимостей.

Чтобы привести к 3НФ таблицу, содержащую транзитивную зависимость

A → B → C, требуется выделить атрибуты B и C в отдельную таблицу, где B

становится ключевым атрибутом. Другими словами, для приведения к 3НФ

таблица разбивается на две: в одну из них помещаются все атрибуты, кроме ат-

рибута C, в другую - атрибуты B и C.

Примечание – Если таблица содержит “длинную” транзитивную зависимость, напри-

мер, A → B → C → D → E (где A – ключ, B, C, D, E – неключевые атрибуты), то сначала в

отдельную таблицу выделяются атрибуты D и E, затем в другую отдельную таблицу – атри-

буты C и D, затем – B и C.

Приведем к 3НФ таблицы, составляющие БД проектно-строительной орга-

низации (таблицы 1.3 – 1.5). Таблицы 1.3 и 1.4 не содержат транзитивных зави-

симостей, т.е. они уже находятся в 3НФ. В таблице 1.5 имеется транзитивная

зависимость Номер проекта → Тип объекта → Нормативный документ.

Именно в этом состоит причина недостатков, указанных в подразделе 1.4. Что-

бы привести ее к 3НФ, разделим ее на две таблицы: таблицу 1.6, содержащую

все атрибуты, кроме атрибута Нормативный документ (присвоим ей имя, на-

пример, “Список проектов”), и таблицу 1.7, содержащую атрибуты Тип объек-

та и Нормативный документ (назовем ее, например, “Нормативные докумен-

ты”).

Таблица 1.6 – Список проектов

Номер проекта Адрес Тип объекта

2140 ул.Лесная,2 жилой дом

2042 ул.Заводская, 8 склад

2060 ул.Речная, 12 жилой дом

2080 ул.Красная, 7 магазин

Таблица 1.7 – Нормативные документы

Тип объекта Нормативный документ

склад СНиП 62

жилой дом СНиП 75

магазин СНиП 40

Таблицы 1.6 и 1.7 находятся в 3НФ. Легко убедиться, что они не имеют не-

достатков, указанных в подразделах 1.3 и 1.4.

Таким образом, вся БД проектно-строительной организации приведена

к 3НФ. Эта БД состоит из четырех таблиц: таблицы 1.3, 1.4, 1.6 и 1.7. Сопоста-

вив эти таблицы с исходными данными, приведенными в подразделе 1.2, легко

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

Таблицы 1.3, 1.4, 1.6 и 1.7 также не имеют недостатков, требующих приве-

дения к нормальным формам более высоких порядков (они будут рассмотрены

в подразделах 1.6 – 1.8). Таким образом, проектирование БД проектно-

строительной организации завершено.

1.6 Нормальная форма Бойса-Кодда

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

обработку БД, устраняются в процессе приведения к 3НФ. Однако в некоторых

случаях таблицы, приведенные к 3НФ, тем не менее, обладают недостатками,

аналогичными рассмотренным в подразделах 1.3, 1.4. В этом случае требуется

приведение таблиц к нормальным формам более высоких порядков.

Приведем некоторые определения, необходимые для рассмотрения нор-

мальной формы Бойса-Кодда.

Атрибут (или группа атрибутов) называется детерминантом, если от него

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

имеется функциональная зависимость A → B, то A – детерминант.

Атрибут (или группа атрибутов) называется возможным ключом, если он

может использоваться в качестве ключа.

Таблица находится в нормальной форме Бойса-Кодда (НФБК), если она

находится в 3НФ, и при этом каждый детерминант в таблице является возмож-

ным ключом.

Таблица, не находящаяся в НФБК, может иметь ряд аномалий.

Пример – Разрабатывается БД о поставках деталей внутри предприятия.

На предприятии имеются цехи-поставщики (выпускающие детали, используе-

мые другими цехами) и цехи-потребители (использующие детали, выпущенные

цехами-поставщиками, и выпуска выпускающие готовую продукцию). Извест-

но следующее:

− каждый цех-поставщик выпускает (и поставляет цехам-потребителям)

детали только одного вида;

− каждый цех-потребитель получает детали каждого вида только от одно-

го цеха-поставщика (например, если цех-потребитель Ц22 получает гайки от

цеха-поставщика Ц17, то он не получает гайки от каких-либо других цехов);

− цех-поставщик может поставлять детали (одного вида) нескольким це-

хам-потребителям;

− один вид деталей может выпускаться несколькими цехами-

поставщиками.

Фрагмент БД приведен в таблице 1.8.

Таблица 1.8 – БД о поставках деталей внутри предприятия

Цех-потребитель Деталь Цех-поставщик

Ц21 планка Ц10

Ц21 гайка Ц12

Ц21 этикетка Ц15

Ц22 гайка Ц17

Ц22 штепсель Ц11

Ц23 планка Ц10

Ц23 штепсель Ц11

Здесь ни один из атрибутов в отдельности не является ключом, так как

значение любого атрибута в БД может встречаться несколько раз. В качестве

ключей могут использоваться комбинации атрибутов (Цех-потребитель, Де-

таль) или (Цех-потребитель, Цех-поставщик), так как, согласно постановке

задачи, любая комбинация значений этих атрибутов может встречаться в БД

(структура которой показана в таблице 1.8) только один раз. Например, любая

комбинация значений (Цех-потребитель, Деталь) встречается в БД только

один раз, так как цех-потребитель получает детали любого определенного вида

только от одного цеха-поставщика. Комбинация значений (Цех-потребитель,

Цех-поставщик) встречается в БД только один раз, так как цех-потребитель и

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

разом, комбинации атрибутов (Цех-потребитель, Деталь) и (Цех-потребитель,

Цех-поставщик) – возможные ключи.

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

(Цех-потребитель, Деталь) → Цех-поставщик, (Цех-потребитель, Цех-

поставщик) → Деталь, Цех-поставщик → Деталь. Таким образом, атрибут

Цех-поставщик является детерминантом, но не является возможным ключом.

Будем использовать в качестве ключа комбинацию атрибутов (Цех-

потребитель, Деталь). Тогда таблица 1.8 находится в 2НФ (так как нет функ-

циональных зависимостей от частей ключа) и в 3НФ (так как отсутствуют тран-

зитивные зависимости вида A → B → C). Однако таблица не находится в

НФБК, так как имеется детерминант (Цех-поставщик), не являющийся возмож-

ным ключом. Это является причиной следующих недостатков:

− избыточность данных: некоторые данные хранятся многократно. На-

пример, данные о том, какая деталь выпускается цехом-поставщиком, хранятся

несколько раз (столько, сколько имеется цехов-потребителей, получающих у

цеха-поставщика данную деталь). Так, информация о том, что цех Ц10 выпус-

кает планки, приведена в таблице 1.8 дважды;

− аномалия добавления (ввода): невозможность ввода данных о цехе-

поставщике, пока он не начал выпуск какой-либо детали;

− аномалия удаления: например, если цех Ц22 прекратит получать гайки

от цеха Ц17, то информация о цехе Ц17 будет потеряна;

− аномалия обновления: если цех-поставщик перейдет на выпуск другой

детали, то потребуется вносить изменения в несколько записей. Кроме того,

при этом в некоторый момент времени одному цеху-поставщику будут соответ-

ствовать разные детали.

Чтобы привести таблицу к НФБК, требуется выделить детерминант, не яв-

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

висимости от него, в отдельную таблицу. Другими словами, если в таблице

имеется функциональная зависимость A → B, где A не является возможным

ключом, то для приведения к НФБК таблица разбивается на две: в одну из них

помещаются все атрибуты, кроме атрибута B, в другую - атрибуты A и B (атри-

бут A в ней становится ключом).

В рассматриваемом примере таблица 1.8 не находится в НФБК из-за функ-

циональной зависимости Цех-поставщик → Деталь. Значит, требуется выде-

лить их в отдельную таблицу (таблица 1.9). Атрибут Цех-поставщик в этой

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

кроме атрибута Деталь (таблица 1.10). Таким образом, БД о внутренних по-

ставках деталей, приведенная к НФБК, будет состоять из двух таблиц: 1.9

и 1.10.

Таблица 1.9 – Цехи-поставщики

Деталь Цех-поставщик

планка Ц10

гайка Ц12

этикетка Ц15

гайка Ц17

штепсель Ц11

Таблица 1.10 – Поставки

Цех-потребитель Цех-поставщик

Ц21 Ц10

Ц21 Ц12

Ц21 Ц15

Ц22 Ц17

Ц22 Ц11

Ц23 Ц10

Ц23 Ц11

В таблицах 1.9 и 1.10 отсутствуют недостатки, указанные выше. Таким об-

разом, проектирование БД о поставках деталей внутри предприятия завершено.

Примечание – Как было показано выше, в данном примере имелось два возможных

ключа. (Цех-потребитель, Деталь) и (Цех-потребитель, Цех-поставщик). В рассматривае-

мом примере в качестве ключа использовалась комбинация атрибутов (Цех-потребитель,

Деталь). Если бы в качестве ключа была выбрана комбинация (Цех-потребитель, Цех-

поставщик), то потребовалось бы приведение таблицы к 2НФ из-за наличия неполной функ-

циональной зависимости: атрибут Деталь зависел бы от части ключа Цех-поставщик. Ре-

зультатом приведения к 2НФ (см. подраздел 1.4) были бы таблицы 1.9 и 1.10.

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

Недостатки (аномалии) таблиц в нормальных формах, рассмотренных ра-

нее (1НФ, 2НФ, 3НФ) были связаны с условиями, когда некоторые атрибуты

зависят не от ключа, а от части ключа (1НФ) или от неключевого атрибута

(2НФ, 3НФ). Другой причиной аномалий могут быть многозначные зависимо-

сти. Атрибут A многозначно определяет атрибут B (обозначается как

A —>> B), если одному значению атрибута A всегда соответствует определен-

ный набор значений атрибута B. Аномалии возникают, если в одной таблице

имеется несколько многозначных зависимостей.

Пример – Разрабатывается БД о преподавателях вуза. Пусть требуется

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

фамилия; преподаваемые курсы; иностранные языки, которыми владеет препо-

даватель.

В таблице 1.11 приведен фрагмент БД с данными об одном преподавателе

(табельный номер – 115, фамилия – Иванов, преподает курсы “Теория вероят-

ностей”, “Численные методы” и “Дискретная математика”, знает английский и

французский языки).

Таблица 1.11 – БД о преподавателях вуза

Табельный номер Фамилия Преподаваемый курс Иностранный язык

115 Иванов Теория вероятностей английский

115 Иванов Численные методы английский

115 Иванов Дискретная математика английский

115 Иванов Теория вероятностей французский

115 Иванов Численные методы французский

115 Иванов Дискретная математика французский

Таблица 1.11 приведена к 1НФ. Она явно имеет недостатки, например,

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

ти таблицу к 1НФ (т.е. обеспечить, чтобы в каждом поле таблицы содержалось

одно значение) невозможно.

Ключ в таблице 1.11 – комбинация атрибутов (Табельный номер, Препода-

ваемый курс, Иностранный язык). Таблица не находится в 2НФ, так как атри-

бут Фамилия зависит от части ключа (от табельного номера). Результатом при-

ведения к 2НФ (см. подраздел 1.4) являются таблицы 1.12 и 1.13.

Таблица 1.12 – Фамилии

Табельный номер Фамилия

115 Иванов

Таблица 1.13 – Сведения о преподавателях

Табельный номер Преподаваемый курс Иностранный язык

115 Теория вероятностей английский

115 Численные методы английский

115 Дискретная математика английский

115 Теория вероятностей французский

115 Численные методы французский

115 Дискретная математика французский

Таблицы 1.12 и 1.13 находятся в 2НФ, 3НФ и НФБК. В то же время оче-

видно, что таблица 1.13 имеет ряд взаимосвязанных недостатков:

− избыточность данных: информация о преподаваемых курсах и ино-

странных языках хранится многократно. Если преподаватель преподает M кур-

сов и знает N иностранных языков, то для хранения данных об этом требуется

M⋅N записей;

− аномалия добавления (ввода): например, если преподаватель, знающий N

языков, начнет преподавать новый курс, то потребуется добавить N строк;

− аномалия удаления: если преподаватель, знающий N языков, перестанет

преподавать некоторый курс, то потребуется удалить N строк;

− аномалия обновления: если изменится название курса, то его потребуется

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

будет называться по-разному.

Причина этих недостатков – наличие в таблице 1.13 двух многозначных

зависимостей: Табельный номер —>> Преподаваемый курс, Табельный но-

мер —>> Иностранный язык.

Таблица находится в четвертой нормальной форме (4НФ), если она на-

ходится в НФБК и содержит не более одной многозначной зависимости.

Если таблица содержит несколько многозначных зависимостей (A —>> B),

то требуется выделить каждую из них в отдельную таблицу.

Для рассматриваемого примера, чтобы привести таблицу 1.13 к 4НФ, тре-

буется выделить в отдельные таблицы многозначные зависимости Табельный

номер —>> Преподаваемый курс, Табельный номер —>> Иностранный язык.

Результатом будут таблицы 1.14 и 1.15.

Таблица 1.14 – Преподаваемые курсы

Табельный номер Преподаваемый курс

115 Теория вероятностей

115 Численные методы

115 Дискретная математика

Таблица 1.15 – Знание языков

Табельный номер Иностранный язык

115 английский

115 французский

Таким образом, БД о преподавателях вуза, приведенная к 4НФ, состоит из

трех таблиц: 1.12, 1.14, 1.15.

1.8 Другие нормальные формы

В настоящее время в теории баз данных известны также пятая, шестая и

седьмая нормальные формы. Однако недостатки, для устранения которых тре-

бовалось бы приведение к этим нормальным формам, на практике встречаются

крайне редко. Подробности о нормальных формах более высоких порядков

имеются, например, в [6].

2 ПРОЕКТИРОВАНИЕ БАЗ ДАННЫХ НА ОСНОВЕ ER-МОДЕЛЕЙ

2.1 Понятие ER-модели

ER-модель, или ER-диаграмма (Entity – Relation; в русском переводе - мо-

дель “объект - отношение” или “сущность - связь”) предназначена для форма-

лизованного описания предметной области на этапе инфологического проекти-

рования БД. Модель представляет собой графическое описание предметной об-

ласти с использованием стандартизированного набора обозначений. На основе

ER-модели по определенным правилам строится даталогическая модель для

реализации в конкретной СУБД (для реляционных БД – набор таблиц и связей

между ними). БД, построенная на основе ER-модели, обычно (но не всегда) на-

ходится в 4НФ. Тем не менее, необходимо проверять построенную БД на со-

блюдение правил нормализации.

Основные достоинства ER-моделей:

− наглядность;

− удобство для проектирования БД с большим количеством объектов

(сущностей) и атрибутов;

− широкое применение в CASE-системах - системах автоматизированного

проектирования БД (ERWin, Design/IDEF, Prokit*WORKBENCH и т.д.).

Основные элементы, входящие в состав ER-моделей:

− объекты (сущности);

− атрибуты (свойства) объектов;

− связи между объектами.

Правила построения ER-моделей и наборы обозначений, используемые в

различных CASE-системах и приводимые в различных литературных источни-

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

обозначений, близкая к применяемой в CASE-системе Prokit*WORKBENCH

[8], как наиболее наглядная (хотя наиболее распространенной в настоящее вре-

мя, по-видимому, является система ERWin, рассматриваемая в разделе 3).

2.2 ER-модель объекта

Как уже отмечалось выше, под объектом (сущностью) понимается некото-

рый объект предметной области, имеющий свойства (атрибуты). Иногда ис-

пользуются понятия экземпляра объекта (экземпляр – конкретный объект, на-

пример, сотрудник, предприятие, изделие и т.д.) и класса объектов (класс

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

все предприятия отрасли или региона, все выпускаемые предприятием изделия

и т.д.). Обычно под термином “объект” понимается экземпляр объекта.

Основные элементы ER-модели объекта рассмотрим на следующем приме-

ре. Пусть проектируется БД вуза. На рисунке 2.1 приведена ER-модель объекта

“преподаватель”.