НОРМАЛИЗАЦИЯ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

Пусть C, Q – два кортежа, т.е. и . Сцепление кортежей C и Q – кортеж . Обозначение: (С, Q) или (С Q).

Пусть наборы атрибутов А и В отношений R и S -сравнимы. Тогда соединение R и S по критерию A B – отношение R[A B]S, кортежи которого получаются сцеплением тех кортежей исходных отношений, для которых на наборах атрибутов А и В критерий сравнения принимает значение ИСТИНА:

R[A B]S = {(r, s) | rÎ R, sÎ S, r.Ai s.Bi = True, i = 1÷k}.

Операция соединения имеет один частный случай. Пусть имеются два отношения:

СЛУЖАЩИЙ_1(Код_сотрудника, Фамилия, Зарплата)

СЛУЖАЩИЙ_2(Код_сотрудника, Вычеты).

Операция соединения этих отношений по очевидному критерию равенства значений в атрибуте Код_сотрудника приведет к отношению вида:

СЛУЖАЩИЙ(Код_сотрудника, Фамилия, Зарплата, Код_сотрудника, Вычеты).

Налицо нарушение свойства 3 реляционных таблиц «Столбцы однозначно именуются». Для устранения данной проблемы введена операция естественного соединения.

Если операция – равенство, то один из двух одинаковых атрибутов (в примере – столбцов “ Код_сотрудника ”) удаляется. Операция обозначается

R*[A=B]*S или R*S.

Естественное соединение по критерию равенства кодов сотрудников

СЛУЖАЩИЙ(Код_сотрудника, Фамилия, Зарплата, Вычеты).

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

Пусть имеются два отношения:

ЗАКАЗ (Код_заказчика, Код_товара, Дата_заказа)

ПОСТАВКА (Код_заказчика, Код_товара, Дата_поставки)

Бизнес-правило: поставка товара осуществляется в срок, не более 7 дней после даты получения заказа.

Задача: найти заказы, по которым отдел поставки не уложился в нормативный срок.

Результирующее отношение будет иметь вид:

ПРОСРОЧЕННАЯ_ПОСТАВКА (Код_заказчика, Код_товара, Дата_заказа, Дата_поставки)

При его получении необходимы операции естественного соединения на наборе атрибутов (Код_заказчика, Код_товара) и соединения на наборе атрибутов (Дата_заказа, Дата_поставки) по критерию Дата_поставки – Дата_заказа > 7

4.2. Функциональные зависимости в отношениях. Возможные ключи. Ключ

Отношения характеризуются внутренними устойчивыми связями, которые определяются семантикой. В частности, в отношениях существуют атрибуты, от которых зависят другие атрибуты. Например, в приведенном выше отношении СЛУЖАЩИЙ от атрибута Код_сотрудника напрямую зависят атрибуты Фамилия, Зарплата, Вычеты. Такие устойчивые отношения называются функциональными зависимостями.

Функциональной зависимостью (ФЗ) набора атрибутов В отношения R от набора атрибутов А того же отношения называется такое соотношение элементов проекций R[A] и R[B], при котором в каждый момент времени любому элементу проекции R[A] соответствует строго один элемент проекции R[B], входящий вместе с ним в некоторый кортеж отношения R.

Наличие ФЗ обозначается R.A R.B

Отсутствие ФЗ обозначается R.A R.B

Такое явление, как ФЗ приводит к понятию возможного ключа (ключа-кандидата). Это набор атрибутов, от которого зависят остальные атрибуты. В одном отношении может быть несколько возможных ключей.

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

1. Каждый атрибут R функционально зависит от К;

2. Ни один атрибут из набора К не может быть удален без нарушения пункта 1.

Математическое определение:

пусть М – полный набор атрибутов R. К является возможным ключом, если:

R.K R.A;

Í M R. R.B

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

Требования основные:

1. Ключ не может иметь значение NULL (не определено, неизвестно);

2. Ключ должен быть уникальным.

Дополнительные требования:

1. Ключ должен быть коротким, компактным.

2. Ключ должен быть по возможности стабильным.

Практически все СУБД по ключу строят индексы. Фактически выбор ключа влияет на физическую организацию данных.

Ключ служит для однозначной идентификации записей. Этим объясняется необходимость соблюдения основных требований. За этим следит СУБД. Если набор атрибутов описан на языке описания данных СУБД как ключевой, СУБД не допустит нарушения основных требований.

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

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

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

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

Допустим, требуется работать с данными, которые можно представить в виде отношения со схемой:

СОТРУДНИК (Табельный_номер, Фамилия, Имя, Отчество, Должность)

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

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

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

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

4.3. Первая нормальная форма

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

Пусть исходная таблица имеет следующий вид:

Здесь столбец “Предмет” является составным. Он содержит повторяющуюся группу данных и сам является таблицей. С такой структурой данных ни одна из классических реляционных СУБД не работает. Необходимо выделять повторяющиеся группы в отдельные таблицы, т.е. приводить отношение к первой нормальной форме.

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

Алгоритм приведения к первой нормальной форме:

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

2. Из корневого отношения удаляются составные атрибуты.

3. Корневое отношение включается в результирующее множество отношений.

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

5. Для каждого из оставшихся отношений повторять с п.1 до тех пор, пока множество не останется пустым.

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

Дальнейшее выполнение алгоритма дает следующие результирующие отношения:

Межтабличная связь осуществляется по ключевому полю.

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

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

4.4. Вторая нормальная форма

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

Определение. Пусть – множество различных атрибутов R, . Зависимость набора атрибутов В от набора атрибутов А (R.A R.B) называе- ся полной, если для любого набора атрибутов С, входящего в А и не принадлежа- щего В, функциональная зависимость В от С отсутствует (R.C R.B, ).

В качестве примера представлена таблица “Расписание”. Для простоты понимания здесь используются некодированные значения атрибутов Предмет и Лектор.

Бизнес-правило: принята кабинетная система обучения, когда за предметом жестко закреплена аудитория.

В этой таблице ключевой является совокупность первых трех столбцов (выделены жирным курсивом). Однако столбец “Аудитория” зависит только от первого столбца “Предмет”. Это приводит к избыточности: сведения о том, что математика читается в 415 аудитории, а физика – в 708 присутствуют столько раз, сколько занятий проводится. Если избыточные данные необходимо скорректировать (например, изменить номер аудитории), возникают также неоправданные затраты времени.

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

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

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

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

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

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

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

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

Пусть исходное отношение “Звери в неволе” имеет вид:

Ключ отношения не указан, т.к. в данном случае это не существенно.

Проекции на наборы атрибутов “Зоопарк, Животное” и “Животное, Зона обитания” будут иметь вид:

Операция естественного соединения по столбцу “Животное” восстановит исходное отношение.

Проекции на наборы атрибутов “Зоопарк, Зона обитания ” и “Животное, Зона обитания” будут иметь вид:

Естественное соединение проекций по зоне обитания даст следующий результат:

Налицо появление лишних кортежей, отсутствующих в исходном отношении.

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

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

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

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

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

Третья нормальная форма связана с так называемыми транзитивными зависимостями. Пусть отношение имеет вид:

Здесь атрибут “Тип организации” зависит от ключа “Преподаватель” не напрямую, а опосредованно через атрибут “Организация”. Налицо транзитивная зависимость.

Это приводит к избыточности, аномалиям удаления и включения. Факт, что Полимер – НИИ, а ЮУрГу – ВУЗ отображается в таблице столько раз, сколько имеется преподавателей из данной организации. Если преподаватели из какой-то организации в некоторый-то момент в таблице не фигурируют, хранить сведения о типе этой организации нельзя (аномалия удаления). Нельзя также включить в таблицу сведения о типе организации до тех пор, пока не будут определены преподаватели из данной организации (аномалии включения.)

Определение. Пусть – множество различных атрибутов R, . Функциональная зависимость набора атрибутов С от набора атрибутов А

(R.A R.С) называется транзитивной, если существует такое, что:

1.

2. С не содержится в В (

3. Существует функциональная зависимость набора атрибутов B от A (R.A R.B)

4. Не существует функциональной зависимости набора атрибутов А от В (R.A R.B)

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

Схема транзитивной зависимости:

Знак? обозначает, что зависимость С от В может иметься (стрелка не перечеркнута) или отсутствовать (стрелка перечеркнута). При отсутствии такой зависимости транзитивная зависимость называется строгой.

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

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

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

Транзитивная зависимость является одним из видов функциональной зависимости. Этот факт отражает определение Бойса-Кодда.

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

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

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

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

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

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

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

Пусть имеются два несвязанных многозначных факта:

Служащий Проекты

Служащий Друзья

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

Один служащий может иметь нескольких друзей, один друг может дружить с несколькими служащими.

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

Расчлененный формат.

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

Смешанный формат возможен в нескольких вариантах:

а) минимум записей с пустыми значениями

б) минимум записей с повторами

в) без ограничений

При рассмотрении таблиц возникают вопросы. Почему в варианте а) пустым является значение в третьей строке, а не в какой-либо другой? Почему в варианте б) повтор сделан для значения «Друг 2», а не «Друг 1»? Почему именно таким образом расположены повторы и пустые значения в варианте в)? Налицо неоднозначность, произвольность в формировании строк таблицы

“Гибрид” всех вариантов.

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

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

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