Проектирование реляционных баз данных

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

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

Перечислим этапы концептуального проектирования:

· изучение предметной области для формирования общего представления о ней;

· выделение и анализ функций и задач разрабатываемой ИС;

· определение основных объектов-сущностей предметной области и отношений между ними;

· формализованное представление предметной области.

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

· определение перечня таблиц и связей между ними;

· определение перечня полей, типов полей, ключевых полей каждой таблицы (схемы таблицы), установление связей между таблицами через внешние ключи;

· установление индексирования для полей в таблицах;

· разработка списков (словарей) для полей с перечислительным и данными;

· установление ограничений целостности для таблиц и связей;

· нормализация таблиц, корректировка перечня таблиц и связей.

Проектирование БД осуществляется на физическом и логическом уровнях. Проектирование на физическом уровне реализуется средствами СУБД и зачастую автоматизировано.

Логическое проектирование заключается в определении числа и структуры таблиц, разработке запросов к БД, отчетных документов, создании форм для ввода и редактирования данных в БД и т.д.

Одной из важнейших задач логического проектирования БД является структуризация данных. Выделяют следующие подходы к проектированию структур данных:

· объединение информации об объектах-сущностях в рамках одной таблицы (одного отношения) с последующей декомпозицией на несколько взаимосвязанных таблиц на основе процедуры нормализации отношений;

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

· осуществление системного анализа и разработка структурных моделей.

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

Процесс проектирования начинается с выделения объектов-сущностей, информация о которых будет храниться в БД, и определения их атрибутов. Выделенные атрибуты объединяются в одной таблице (отношении).

Полученное отношение подвергается нормализации.

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

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

· первая нормальная форма (1НФ);

· вторая нормальная форма (2НФ);

· третья нормальная форма (ЗНФ);

· усиленная третья нормальная форма или нормальная форма Бойса-Кодда (БКНФ);

· четвертая нормальная форма (4НФ);

· пятая нормальная форма (5НФ).

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

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

Пример неизбыточного дублирования данных представляет отношение «ТЕЛЕФОНЫ» (рис. 11). Предположим, что в одной комнате установлен только один телефон, тогда номера телефонов сотрудников, находящихся в одном помещении, совпадают. Номер телефона 24212 встречается несколько раз. В этом состоит дублирование. Однако для каждого сотрудника номер уникален и при удалении одного из номеров будет утеряна информация о том, по какому номеру можно дозвониться до того или иного сотрудника. В этом состоит неизбыточность.

ТЕЛЕФОНЫ

Рис. 11 – . Неизбыточное дублирование данных

Избыточное дублирование данных имеет место в отношении «КОМНАТЫ», в которое добавлен атрибут «Номер комнаты» (рис. 12).

Сотрудники Белкин, Синицын и Медведев находятся в одной комнате и, следовательно, имеют одинаковые номера. То есть номер телефона Синицына и Медведева можно узнать из кортежа со сведениями о Белкине. В этом и состоит избыточность дублирования данных.

Избыточное дублирование данных приводит к проблемам обработки кортежей отношения, названным Э. Коддом «аномалиями обновления отношения».

КОМНАТЫ

Рис.12 – Избыточное дублирование данных

Аномалиями называются такие ситуации в таблицах БД, которые приводят к противоречиям в БД, или существенно усложняяют обработку данных.

Выделяют три основных вида аномалий:

· аномалии модификации (редактирования);

· аномалии удаления;

· аномалии добавления.

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

Так изменение номера телефона в комнате 325 (рис. 12) потребует пересмотра всей таблицы «КОМНАТЫ» и изменения значений атрибута «Номер телефона» в записях, в которых встречается этот номер.

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

Так удаление записи о сотруднике Волкове (например, по причине увольнения) приводит к исчезновению информации о номере телефона, установленного в 320-й комнате (см. рис. 12).

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

Например, в таблице «КОМНАТЫ» (см. рис. 12) невозможно отразить информацию о комнате с установленным в ней телефоном до тех пор, пока в нее не помещен ни один сотрудник (при условии, что поле «ФИО» является ключевым).

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

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

На рис. 13 показан пример отношения «ГОРОДА» и приведены два варианта его декомпозиции [18].

ГОРОДА

a)

б)

Puc. 13 – Отношение «ГОРОДА» и два варианта его декомпозиции

В варианте а) информация не утрачивается, поскольку отношения все еще содержат данные о том, что город с кодом К3 имеет статус 30 и называется Париж, а город с номером К5 имеет статус 30 и называется Афины. Таким образом, первая декомпозиция является декомпозицией без потерь.

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

На рис.14 показаны два отношения, полученные путем декомпозиции исходного отношения «КОМНАТЫ».

Рис.14 – Исключение избыточного дублирования данных

Теперь, удаление информации о Волкове из базы данных не приведет к утере информации о номере телефона в 320-й комнате.

Процедура декомпозиции отношения является основной при нормализации отношений. Однако для осуществления «декомпозиции без потерь» необходимо предварительно выявить так называемые функциональные зависимости.

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

Функциональная зависимость (ФЗ) называется тривиальной, если она не может не выполняться. Например:

{А, В}®{B}

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

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

Функциональные зависимости – это особый вид ограничений целостности, поэтому понятие ФЗ является семантическим. Распознавание функциональных зависимостей представляет собой часть процесса выяснения смысла тех или иных данных.

Функциональная взаимозависимость.Если существует функциональная зависимость вида А®В и В®А, то между А и В имеется взаимно однозначное соответствие, или функциональная взаимозависимость. Наличие функциональной взаимозависимости между атрибутами А и В обозначается А↔В.

Например, если в некотором отношении существуют атрибуты «ФИО» и «Номер паспорта», то они являются взаимозависимыми, то есть одному значению атрибута «ФИО» соответствует только одно значение атрибута «Номер паспорта» и наоборот. Правда это возможно, только если исключается полное совпадение фамилий, имен и отчеств двух людей.

Частичной функциональной зависимостьюназывается зависимость неключевого атрибута от части составного ключа.

Полная функциональная зависимость – зависимость неключевого атрибута от всего составного ключа.

Транзитивная зависимость существует, если для атрибутов А, В, С выполняются условия А®В и В®С, но обратная зависимость отсутствует.

Между атрибутами может иметь место многозначная зависимость.

В отношении R атрибут В многозначно зависит от атрибута А, если каждому значению А соответствует множество значений В, не связанных с другими атрибутами из R.

Многозначные зависимости могут быть «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М).

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

Существует 8 основных правил вывода. Они обеспечивают выявление всех ФЗ. Перечислим эти правила.

1. Правило рефлексивности:если множество В является подмножеством множества А, то А ® В.

2. Правило дополнения:если А®В, то АС®ВС.

3. Правило транзитивности: если А®В и В®С, то А®С.

4. Правило самоопределения: А®А.

5. Правило декомпозиции: если А®ВС, то А®В и А®С.

6. Правило объединения: если А®В и А®С, то А®ВС.

7. Правило композиции: если А®В и С®D, то АС®ВD.

8. Общая теорема объединения: если А®В и С®D, то АÈ(С – В)®ВD.

Рассмотрим проектирование БД на примере создания БД, содержащей информацию о преподавателях.

Выделим атрибуты отношения:

«ФИО» – фамилия и инициалы преподавателя. Возможность совпадения фамилий и инициалов исключается.

«Должность» – должность преподавателя.

«Оклад» – оклад преподавателя.

«Стаж» – преподавательский стаж.

«Надбавка» – надбавка за стаж.

«Кафедра» – аббревиатура кафедры, на которой числится преподаватель.

«Дисциплина» – название дисциплины, закрепленной за преподавателем.

«Группа» – код группы, в которой преподаватель проводит занятия.

«Вид занятий» – лекции, практические или лабораторные занятия.

Исходное отношение «ПРЕПОДАВАТЕЛЬ» приведено на рис. 15.

ПРЕПОДАВАТЕЛЬ

Рис. 15 – Исходное отношение «ПРЕПОДАВАТЕЛЬ»

Отношение «ПРЕПОДАВАТЕЛЬ» содержит избыточное дублирование данных.

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

Отношение имеет составной ключ {ФИО, Дисциплина, Группа}. Данное сочетание атрибутов является ключом, при условии, что один и тот же преподаватель не может вести одновременно лекции и практические занятия в одной и той же группе.

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

ФИО®Оклад

ФИО®Должность

ФИО®Стаж

ФИО®Надбавка

ФИО®Кафедра

Стаж®Надбавка

Должность®Оклад

Оклад®Должность

{ФИО, Дисциплина, Группа} ® Вид занятий

Рис. 16 – Функциональные зависимости между атрибутами

Рассмотрим семантический смысл выявленных ФЗ.

Фамилия, имя и отчество у преподавателей уникальны. Каждому преподавателю однозначно соответствует его стаж (ФИО®Стаж). Обратное утверждение неверно, так как одинаковый стаж может быть у разных преподавателей.

Каждый преподаватель имеет определенную надбавку за стаж (ФИО®Надбавка). Обратная функциональная зависимость отсутствует, так как одну и ту же надбавку могут иметь несколько преподавателей.

Каждый преподаватель имеет определенную должность, но одну и ту же должность могут иметь несколько преподавателей (ФИО®Должность).

Каждый преподаватель является сотрудником одной и только одной кафедры (ФИО®Кафедра), вместе с тем на одной кафедре могут работать несколько преподавателей.

Каждому преподавателю соответствует определенный оклад, величина которого одинакова для всех преподавателей с одинаковыми должностями. Поэтому ФИО®Оклад и Должность®Оклад. Одинаковых окладов для разных должностей не существует, поэтому Оклад®Должность.

Один и тот же преподаватель в одной группе по разным предметам может проводить разные виды занятий. Определение вида занятий, которые проводит преподаватель, невозможно без указания предмета и группы, поэтому имеется функциональная зависимость {ФИО, Дисциплина, Группа} ® Вид занятий.

Зависимости между атрибутами «ФИО», «Дисциплина» и «Группа» не выделены, поскольку они образуют составной ключ и не учитываются в процессе нормализации исходного отношения.

Выявленные функциональные зависимости необходимо проверить на согласованность с данными исходного отношения «ПРЕПОДАВАТЕЛЬ» (рис. 15). Например, значение атрибута «Должность» «ассистент» должно соответствовать значению атрибута «Оклад» «1500» во всех кортежах отношения. Если это так, то функциональная взаимозависимость Должность↔Оклад подтверждается. Верификация ФЗ осуществляется с учетом условий (ограничений целостности).

Отношение находится в первой нормальной форме, если оно удовлетворяет принципам реляционной модели.

Рассматриваемое отношение уже находится в 1НФ.

Как было сказано выше, перевод отношения в следующую нормальную форму осуществляется методом «декомпозиции без потерь».

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

Отношение «ПРЕПОДАВАТЕЛЬ» не находится во второй нормальной форме, поскольку можно выделить зависимость атрибутов «Стаж», «Надбавка», «Кафедра», «Должность», «Оклад» от части ключа (атрибута «ФИО»). Эта частичная зависимость приводит к информационной избыточности и возникновению аномалий.

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

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

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

В результате получим два отношения R1 и R2, находящиеся во второй нормальной форме (рис. 17).

R1

R2

Рис. 17 – Отношения во второй нормальной форме

В отношении R1 первичным ключом является совокупность атрибутов {ФИО, Дисциплина, Группа}. В отношении R2 ключом является атрибут «ФИО».

Отношения R1 и R2 находятся во второй нормальной форме.

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

Отношение R1 находится в третьей нормальной форме, а отношение R2 – нет (см. рис.17). В R2 по-прежнему присутствует информационная избыточность, поэтому требуется дополнительное преобразование.

В отношении R2 присутствуют транзитивные зависимости:

ФИО®Должность®Оклад, ФИО®Оклад®Должность,

ФИО®Стаж®Надбавка

Транзитивные зависимости порождают избыточное дублирование данных. Для устранения таких зависимостей можно воспользоваться операцией проекции на атрибуты, являющиеся причиной транзитивных зависимостей. Преобразуем отношение R2, получив отношения R3, R4 и R5 (рис. 18). Полученное преобразование не является единственно верным.

R3

R4

R5

Рис. 18 – Отношения в третьей нормальной форме

Отношения R3, R4, R5 находятся в третьей нормальной форме.

На практике в большинстве случаев приведением отношений к третьей нормальной форме заканчивается процесс проектирования реляционной БД.

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

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

В рассматриваемом примере таких зависимостей нет, поэтому процесс проектирования можно завершить.

Рис. 19 – Реляционная база данных

Результатом проектирования является реляционная БД как набор взаимосвязанных двумерных таблиц Rl, R3, R4, R5. Схема базы данных, реализованной в СУБД Microsoft Access, представлена на рис.19.

В полученной БД имеет место неизбыточное дублирование данных, но отсутствует избыточное.