Даталогическое проектирование для реляционной модели данных

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

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

• Описание концептуальной схемы БД в терминах выбранной СУБД.
• Описание внешних моделей в терминах выбранной СУБД.
• Описание декларативных правил поддержки целостности базы данных.
• Описание процедур поддержки семантической целостности базы данных.

Однако, перед тем как описывать построенную схему в терминах выбранной СУБД, нам надо выстроить эту схему.

ОПРЕДЕЛЕНИЕ 1. Корректной назовем схему БД, в которой отсутствуют нежелательные зависимости между атрибутами отношений.

Процесс разработки корректной схемы реляционной БД называется даталогическим проектированием БД. Проектирование схемы БД может быть выполнено двумя путями:

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

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

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

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

• первая нормальная форма (1NF);
• вторая нормальная форма (2NF);
• третья нормальная форма (3NF);
• нормальная форма Бойса—Кодда (BCNF);
• четвертая нормальная форма (4NF);
• пятая нормальная форма, или форма проекции-соединения (5NF или PJNF).

ОПРЕДЕЛЕНИЕ 2. Схемы БД называются эквивалентными, если содержание исходной БД может быть получено путем естественного соединения отношений, входящих в результирующую схему, и при этом не появляется новых строк в исходной БД.

ОПРЕДЕЛЕНИЕ 3. Функциональной зависимостью набора атрибутов В отношения R от набора атрибутов A того же отношения, обозначаемой как R.A→ R.B или A→ Bназывается такое соотношение проекций R[A] и R[B], при котором в каждый момент времени любому элементу проекции R[A] соответствует только один элемент проекции R[B], входящий вместе с ним в какой-либо кортеж отношения R.

Функциональная зависимость R.A → R.B называется полной, если набор атрибутов B функционально зависит от A и не зависит функционально от любого подмножества A, то есть
R.A→ R.B называется полной, если: ∀ A1 ⊆ A →R.A -/→ R.B, что читается следующим образом: для любого A1, являющегося подмножеством А, R.B функционально не зависит от R.A, в противном случае зависимость R.A→ R.B называется неполной.

Функциональная зависимость R.A→ R.B называется транзитивной, если существует набор атрибутов С такой, что:

1. С не является подмножеством А.

2. С не включает в себя B.

3. Существует функциональная зависимость R.A→ R.C.

4. Не существует функциональной зависимости R.C→ R.A.

5. Существует функциональная зависимость R.C→ R.B.

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

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

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

Взаимно-независимые атрибуты — это такие атрибуты, которые не зависят функционально один от другого.

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

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

ОПРЕДЕЛЕНИЕ 4. Отношение находится в первой нормальной форме тогда и только тогда, когда на пересечении каждого столбца и каждой строки находятся только элементарные значения атрибутов.

ОПРЕДЕЛЕНИЕ 5. Отношение находится во второй нормальной форме тогда и только тогда, когда оно находится в первой нормальной форме и не содержит неполных функциональных зависимостей непервичных атрибутов от атрибутов первичного ключа.

Рассмотрим отношение, моделирующее сдачу студентами текущей сессии:

<ФИО, Номер зач.кн., Группа, Дисциплина, Оценка>

Так как каждый студент сдает набор дисциплин в процессе сессии, то первичным ключом отношения может быть (Номер зач.кн., Дисциплина), который однозначно определяет каждую строку отношения. С другой стороны, атрибуты ФИО и Группа зависят только от части первичного ключа — от значения атрибута Номер зач. кн., поэтому в данном отношении есть неполные функциональные зависимости. Для приведения данного отношения ко второй нормальной форме следует разбить его на проекции, при этом должно быть соблюдено условие восстановления исходного отношения без потерь. Такими проекциями могут быть два отношения:

<ФИО, Номер зач.кн., Группа> и <Номер зач.кн., Дисциплина, Оценка>

Зачем приводить отношения к 2NF? Рассмотрим ситуацию, когда студент переведен из одной группы в другую. Тогда если мы не разбивали исходное отношение на два мы должны найти все записи с данным студентом и в них изменить значение атрибута Группа на новое. В случае приведения к 2NF меняется только один кортеж в первом отношении. Риск нарушения корректности БД в первом случае выше.

ОПРЕДЕЛЕНИЕ 6. Отношение находится в третьей нормальной форме тогда и только тогда, когда оно находится во второй нормальной форме и не содержит транзитивных зависимостей.

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

<ФИО, Номер зач.кн., Группа, Факультет, Специальность, Выпускающая кафедра>

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

1. Номер зач.кн. → ФИО

2. Номер зач.кн. →Группа

3. Номер зач.кн. →Факультет

4. Номер зач.кн. →Специальность

5. Номер зач.кн. →Выпускающая кафедра

6. Группа → Факультет

7. Группа → Специальность

8. Группа → Выпускающая кафедра

9. Выпускающая кафедра → Факультет

Эти зависимости образуют транзитивные группы. Для того чтобы избежать этого, мы можем предложить следующий набор отношений (первичные ключи отношений выделены):

<Номер.зач.кн., ФИО, Специальность, Группа>

<Группа, Выпускающая кафедра>

<Выпускащая кафедра, Факультет>

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

ОПРЕДЕЛЕНИЕ 7. Отношение находится в нормальной форме Бойса—Кодда, если оно находится в третьей нормальной форме и каждый детерминант отношения является возможным ключом отношения.

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

<Номер зач.кн., Идентификатор_студента, Дисциплина, Дата, Оценка>

Возможными ключами отношения являются:

1. Номер_зач.кн, Дисциплина, Дата

2. Идентификатор_студента, Дисциплина, Дата.

Функциональные зависимости:

1. Номер_зач.кн, Дисциплина, Дата → Оценка;

2. Идентификатор_студента, Дисциплина, Дата → Оценка;

3. Номер зач.кн. →Идентификатор_студента;

4. Идентификатор_студента → Номер зач.кн.

Каждому студенту ставится в соответствие один Номер зач.кн. и один Идентификатор_студента, поэтому по значению Номер зач.кн. можно однозначно определить Идентификатор_студента (3-я зависимость) и обратно (4-я зависимость).

Это отношение находится в третьей нормальной форме, потому что неполных функциональных зависимостей непервичных атрибутов от атрибутов возможного ключа здесь не присутствует (в том числе 3-я и 4-я), и нет транзитивных зависимостей. Потому что зависимым не является непервичный атрибут, то есть атрибут, не входящий ни в один возможный ключ. Под нормальную форму Бойса—Кодда наше отношение не подходит, потому что у нас есть два детерминанта Номер зач.кн. и Идентификатор_студента, которые не являются возможными ключами отношения. Для приведения отношения к нормальной форме Бойса—Кодда надо разделить отношение, например, на два со следующими схемами:

<Идентификатор_студента, Дисциплина, Дата, Оценка>

<Идентификатор_студента, Номер зач.кн.>

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

ОПРЕДЕЛЕНИЕ 8. В отношении R (A, B, C) существует многозначная зависимость (multivalue dependence, MVD) R.A ->> R.B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не зависит от С.

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

<Номер зач.кн., Группа, Дисциплина>

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

В данном отношении существуют следующие две многозначные зависимости:

1. Группа ->> Дисциплина

2. Группа ->> Номер зач.кн.

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

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

В теории реляционных баз данных доказывается, что в общем случае в отношении R (A, B, C) существует многозначная зависимость R.A ->> R.B в том и только в том случае, когда существует многозначная зависимость R.A ->> R.C.

ТЕОРЕМА ФЕЙДЖИНА. Отношение R (A, B, C) можно спроецировать без потерь в отношения R1 (A, B) и R2 (A, C) в том и только в том случае, когда существуют MVD A ->> B и A ->> C. Под проецированием без потерь понимается такой способ декомпозиции отношения путем применения операции проекции, при котором исходное отношение полностью и без избыточности восстанавливается путем естественного соединения полученных отношений.

ОПРЕДЕЛЕНИЕ 9. Отношение R находится в четвертой нормальной форме (4NF) в том и только в том случае, если в случае существования многозначной зависимости A ->> B все остальные атрибуты R функционально зависят от A.

В вышеприведенном примере можно произвести декомпозицию исходного отношения в два отношения: <Номер зач.кн., Группа>, <Группа, Дисциплина>.

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

ОПРЕДЕЛЕНИЕ 10. Отношение R (X, Y,…, Z) удовлетворяет зависимости соединения (X, Y,…, Z) в том и только в том случае, когда R восстанавливается без потерь путем соединения своих проекций на X, Y, …, Z. Где X, Y, …, Z — наборы атрибутов отношения R.

Наличие PJ-зависимости («проекции соединения», project-join зависимости) в отношении делает его в некотором роде избыточным и затрудняет операции модификации.

ОПРЕДЕЛЕНИЕ 11. Отношение R находится в пятой нормальной форме (нормальной форме проекции-соединения — PJ/NF) в том и только в том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R.

Рассмотрим отношение R1: <Преподаватель, Кафедра, Дисциплина>

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

ПК (Преподаватель, Кафедра)

ПД (Преподаватель, Дисциплина)

КД (Кафедра, Дисциплина)

Допустим, что отношение R1 удовлетворяет зависимости проекции соединения (ПК, ПД, КД). Тогда отношение R1 не находится в PJNF, потому что единственным ключом его является полный набор атрибутов, а наличие зависимости PJ связано с наборами атрибутов, которые не составляют возможные ключи отношения R1. Для того чтобы привести это отношение к PJNF, его надо представить в виде трех отношений: ПК, ПД, КД.