2.4Проверка декомпозиции методом табло

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

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

• сохранение всех функциональных зависимостей исходного отношения.

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

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

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

2. На этапе проверки происходит итеративный просмотр всех функциональных зависимостей Х ® Y.

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

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

2.5Нормализация базы данных с использованием модели er-диаграмм

При использовании метода ER-диаграмм (диаграмм сущность-связь: entity – сущность, relationship – связь) сначала строиться сама диаграмма сущностей и связей. На диаграмме обозначаются сущности, связи между сущностями, кардинальности и модальности связей. Существует несколько нотаций метода. В настоящем пособии будем использовать нотацию Баркера. Обозначения объектов в этой нотации приведены в таблице 2.1.

Таблица 2.1. Обозначения в нотации Баркера.

Объект	Обозначение	Примечание
Сущность		Сущность обозначается прямоугольником, разделенным на две области. В верхней указывается имя сущности. В нижней перечисляются атрибуты. Сначала указываются атрибуты, входящие в первичный ключ, они выделяются подчеркиванием, а потом все остальные атрибуты. До нормализации возможно указание только первичного ключа.
Связь		Связь обозначается линией, соединяющей две сущности. Каждая связь имеет два конца и одно или два наименования. Наименование обычно выражается в неопределенной глагольной форме. Если у связи два наименования, их пишут у соответствующих концов. Если у связи одно наименование оно указывается посередине.
Кардинальность связи		Кардинальность связи указывается на каждом конце связи со стороны, противоположной своей сущности. Кардинальность "Один" указыввается прямой линией, кардинальность "Многие" – тройным венчиком.
Модальность связи		Обязательный тип связи обозначается сплошной чертой, необязательный – пунктирной. Связь может иметь разную модальность с разных концов. Модальность указывается со стороны своей сущности.

Строятся ER-диаграммы по описанию предметной области. Например, имеется такой фрагмент предметной области: студент обучается в группе. Ясно, что здесь имеется две сущности – Студент и Группа. Эти сущности связаны связью Обучаться. Определим кардинальность и модальность связи с обоих концов. Что мы знаем о студенте относительно группы? Он обязательно должен обучаться в какой-либо одной группе и только в одной. Со стороны группы мы можем сказать, что в группе может обучаться много студентов, а может не обучаться ни одного студента (например, если группа расформирована или только что создана, и зачисления в нее еще не произошло). ER-диаграмма примера показана на рис. 2.6.

Рис. 2.6.

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

<Каждый экземпляр Сущности1> <Модальность связи> <ИмяСвязи> <Кардинальность Связи> <экземпляр Сущности2>

ER-диаграмма, представленная на рис.2.6, читается следующим образом. Слева направо: каждый студент должен обучаться ровно в одной группе. Справа налево: в каждой группе могут обучаться несколько студентов.

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

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

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

Правило №1. Кардинальность связи один к одному модальность с обоих концов связи "обязательно". Требуется только одно отношение. Первичным ключом этого отношения может быть ключ любой сущности.

Например, известно, что каждый сотрудник (известен табельный номер и ФИО) отдела АСУ обязательно занимает отдельный кабинет (известен номер и площадь) и на этаже нет свободных кабинетов или кабинетов, где бы не работал сотрудник отдела АСУ. Сущности Сотрудники и Кабинеты связаны связью Занимать с кардинальностью "один-к-одному" и модальностью с обоих концов "обязательно". Диаграмма представлена на рис. 2.7.

Рис. 2.7.

После нормализации получим отношение:

СотрудникиВКабинетах(НомСотр, ФИО, НомКаб, Площадь)

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

Правило №2. Кардинальность связи один к одному и модальность с одной из сторон "необязательно". Требуются два отношения по одному на каждую сущность. При этом ключ сущности будет первичным ключом для соответствующего отношения, и ключ сущности, со стороны которой модальность "необязательно", добавляется в качестве атрибута (внешнего ключа) в отношение, выделенное для сущности с модальностью "обязательно".

Например, известно, что каждый сотрудник отдела АСУ обязательно занимает отдельный кабинет, но есть служебные помещения, например комната отдыха или столовая, которые не являются ничьим рабочим кабинетом. Сущности Сотрудники и Кабинеты связаны связью Занимать с кардинальностью "один-к-одному", модальность со стороны сущности Сотрудники "обязательно", со стороны сущности Кабинеты "необязательно". Диаграмма представлена на рис. 2.8.

Рис. 2.8.

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

После нормализации получим отношения:

Сотрудники(НомСотр, ФИО, НомКаб)

Кабинеты(НомКаб, Площадь)

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

Правило №3. Кардинальность связи один к одному и модальность с обеих сторон "необязательно". Требуются три отношения по одному для каждой сущности и одно для связи. При этом ключ сущности будет первичным ключом для соответствующего отношения, и ключ каждой сущности войдет в состав отношения, выделенного для связи, как внешний ключ. Первичный ключ отношения-связи будет состоять из ключей каждой сущности.

Например, известно, что сотрудник фирмы может занимать отдельный кабинет (только один). Есть служебные помещения, например комната отдыха или столовая, которые не являются ничьим рабочим кабинетом. Кроме того, в фирме работают сотрудники, которые не занимают кабинеты, например, охранники, которые патрулируют коридоры и дежурят в холле. Сущности Сотрудники и Кабинеты связаны связью Занимать с кардинальностью "один-к-одному", модальность с обоих сторон "необязательно". Диаграмма представлена на рис. 2.9.

Рис. 2.9.

Рассмотрим ситуацию на уровне функциональных зависимостей. Имеем следующие ФЗ: НомСотр  ФИО, НомКаб  Площадь и есть еще один составной атрибут НомСотр, НомКаб, показывающий что определенный сотрудник работает в кабинете. Заметьте, что ФЗ НомСотр  НомКаб в данном случае отсутствует, так как по номеру сотрудника не всегда возможно определить номер кабинета. Видно, что этот набор ФЗ не удовлетворяет требованиям 2НФ (присутствует зависимость неключевых атрибутов от части первичного ключа).

После нормализации получим отношения:

Сотрудники(НомСотр, ФИО)

Кабинеты(НомКаб, Площадь)

СотрудникиВКабинетах(НомСотр, НомКаб)

Если бы мы добавили атрибут НомСотр в отношение Кабинеты, или НомКаб в отношение Сотрудники, то получили бы, что эти атрибуты мог бы принимать значение NULL, поэтому здесь не обойтись без третьего отношения. И уж тем более нельзя объединять эти сущности.

Правило №4. Кардинальность связи один ко многим и модальность со стороны М-связной сущности "обязательно". Требуются два отношения по одному для каждой сущности. При этом ключ сущности будет первичным ключом для соответствующего отношения, и ключ односвязной сущности должен быть добавлен как атрибут (внешний ключ) в отношение, отводимое для М-связной сущности.

Например, известно, что поставщик товара проживает в некотором городе. Сущности Города и Поставщики связаны связью Проживать. Кардинальность "один-ко-многим", модальность со стороны М-связной сущности Поставщики "обязательно". Диаграмма представлена на рис. 2.10.

Рис. 2.10.

Рассмотрим ситуацию на уровне функциональных зависимостей. Имеем следующие ФЗ: КодПост  НаимПост, КодПост  КодГор, КодГор  НаимГор. Видно, что этот набор ФЗ не удовлетворяет требованиям 3НФ (присутствует транзитивная зависимость названия города от кода поставщика).

После нормализации получим отношения:

Города (КодГор, НаимГор)

Поставщики(КодПост, НаимПост, КодГор)

Правило №5. Кардинальность связи один ко многим и модальность со стороны М-связной сущности "необязательно". Требуются три отношения по одному для каждой сущности и одно для связи. При этом ключ сущности будет первичным ключом для соответствующего отношения, и ключ каждой сущности войдет в состав отношения, выделенного для связи, как внешний ключ. Первичный ключ отношения-связи будет состоять из ключей каждой сущности.

Рассмотрим предметную область: фирма торгует некоторыми товарами со складов, а некоторыми только из магазина. Каждый вид товара может храниться только на одном складе. Сущности Склады и Товары связаны связью Продаваться. Кардинальность "один-ко-многим", модальность со стороны М-связной сущности Товары "необязательно", так как какой-то товар может продаваться только из магазина. Диаграмма представлена на рис. 2.11.

Рис. 2.11.

Рассмотрим ситуацию на уровне функциональных зависимостей. Имеем следующие ФЗ: КодТов  НаимТов, НомСкл  АдресСкл и есть еще один составной атрибут, показывающий, с какого склада какой товар продается КодТов, НомСкл. Видно, что этот набор ФЗ не удовлетворяет требованиям 2НФ (присутствует зависимость неключевых атрибутов от первичного ключа).

После нормализации получим отношения:

Товары(КодТов, НаимТов)

Склады(НомСкл, АдресСкл)

ТоварыНаСкладах(КодТов, НомСКл)

На самом деле, если мы добавим атрибут НомСкл в отношение Товары, то получим, что этот атрибут может принимать неопределенные значения.

Правило №6. Кардинальность связи многие ко многим. Требуются три отношения по одному для каждой сущности и одно для связи. При этом ключ сущности будет первичным ключом для соответствующего отношения, и ключ каждой сущности войдет в состав отношения, выделенного для связи, как внешний ключ. Первичный ключ отношения-связи будет состоять из ключей каждой сущности.

Например, известно, что поставщик делает несколько поставок товара. Известна дата поставки и количество поставляемого товара. Сущности Поставщики и Товары связаны связью Поставлять. Кардинальность "многие-ко-многим", модальность с обоих концов "обязательно" (если есть поставщик в нашей базе данных, то он уже сделал поставку, и если есть товар, то его кто-то поставил). Диаграмма представлена на рис. 2.12.

Рис. 2.12.

Рассмотрим ситуацию на уровне функциональных зависимостей. Имеем следующие ФЗ: КодПост  НаимПост; КодТов  НаимТов; КодПост, КодТов, ДатаПоставки  КолвоПоставки. Видно, что этот набор ФЗ не удовлетворяет требованиям 2НФ (присутствует зависимость неключевых атрибутов от первичного ключа).

После нормализации получим отношения:

Товары (КодТов, НаимТов)

Поставщики(КодПост, НаимПост)

Поставки(КодТов, КодПост, ДатаПоставки, КолвоПоставки)

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

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

Например, известно, что поставщик делает несколько поставок товара. Каждая поставка отправляется на определенный склад (разрывать поставку по разным складам нельзя). Известна дата поставки и количество поставляемого товара. Сущности Поставщики, Товары и Склады связаны связью Поставлять. Получим диаграмму как на рис. 2.13.

Рис. 2.13.

Определим кардинальность и модальность. Модальность со сторон сущностей Поставщики и Товары "обязательно" (см. рассуждения в примере к правилу №6), модальность со стороны сущности Склады "необязательно" (некоторые склады могут пустовать и быть зарезервированы). Со стороны сущности Поставщики кардинальность "многие" (один и тот же товар на складе может быть поставлен разными поставщиками). Со стороны сущности Товары кардинальность "многие" (один и тот же поставщик на один склад может поставить много различных товаров). Со стороны сущности Склады кардинальность "один" (определенный поставщик делает определенную поставку товара только на один склад). Окончательная ER-диаграмма представлена на рис. 2.14.

Рис. 2.14.

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

Товары (КодТов, НаимТов)

Поставщики(КодПост, НаимПост)

Склады(НомСкл, АдресСкл)

Поставки(КодТов, КодПост, ДатаПоставки, НомСкл, КолвоПоставки)

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

Есть другой вариант построения ER-диаграммы предметной области примера. Попробуем вместо трехарной связи использовать промежуточную сущность. В нашем примере такая сущность находится легко – Поставки. Однако интуитивно найти промежуточную сущность не всегда просто, это является одной из причин, почему рекомендуется сначала строить n-арные связи. С промежуточной сущностью схема будет выглядеть как на рис. 2.15.

Кардинальность и модальность для каждой связи рассматривается отдельно.

Рис. 2.15.

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

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