Информационные системы

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

Определение 1. Под реляционной базой данных принято понимать совокупность экземпляров конечных отношений. Совокупность схем отношений образует схему реляционной базы данных.

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

Как уже было сказано в лекции 2 - "Предметная область базы данных и ее модели", - на основе информационной модели в процессе проектирования создаются логическая и физическая модели данных. Информационная модель данных отражает потребности системы в данных и связи между данными с точки зрения их потребителей - пользователей; логическая модель данных является независимым логическим представлением данных; физическая модель данных содержит определения всех реализуемых объектов в конкретной базе данных для конкретной СУБД.

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

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

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

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

Нормализация отношений

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

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

· группировка атрибутов в отношении предметной области;

· распределение атрибутов по отношениям базы данных.

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

Перечень наиболее важных требований приведен ниже.

1.     Первичные ключи отношений должны быть минимальными (требование минимальности первичных ключей).

2.     Число отношений базы данных должно по возможности давать наименьшую избыточность данных (требование надежности данных).

3.     Число отношений базы данных не должно приводить к потере производительности системы (требование производительности системы).

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

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

6.     Разброс времени реакции на различные запросы к базе данных не должен быть большим (требование производительности системы).

7.     Данные должны правильно отражать состояние предметной области базы данных в каждый конкретный момент времени (требование актуальности данных).

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

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

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

Пример. Аномалии операций над базой данных

ПОСТАВКИ (Поставщик, Адрес, Товар, Количество, Стоимость)

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

Удаление. Если Поставщик прекращает поставку товаров на некоторое время, то кортежи со всеми его поставками удаляются. При этом происходит потеря реквизитов поставщика - Адреса и Наименования.

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

Подобные аномалии в данных лишь отчасти дают ответ на вопрос, почему логическая структура реляционной БД может быть неудовлетворительной. Некоторые проблемы избыточности данных можно разрешить, заменив, например, исходное отношение ПОСТАВКИ на два новых отношения - отношение ПОСТАВЩИК (Поставщик, Адрес) и отношение ПОСТАВКА (Поставщик, Товар, Количество, Стоимость). Однако в целом остается ряд вопросов, на которые теория реляционных баз данных не дает удовлетворительных ответов: quot;Как найти хорошую замену для плохой схемы отношений? Как определить, является ли выбранная замена выгодной? Как создать схему, обеспечивающую наилучшую производительность?quot;

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

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

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

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

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

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

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

Примечание. Глагол quot;ограничиваетquot; в терминологии баз данных означает набор процедур, направленных на достижение определенных свойств объекта путем сужения области его действия.

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

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

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

Пример. Приведение отношения к 1НФ

На рис. 6.1 представлено ненормализованное отношение SHIPMENT (ОТГРУЗКА). Оно содержит повторяющиеся группы, представляющие массив значений, 1st Consignments, 2st Consignments, 3st Consignments (партии грузов). Атрибуты, характеризующие партию грузов (показаны на следующем рисунке), - Consignee (грузополучатель), Insured Value (застрахованная стоимость) и Declared Value (объявленная стоимость), - повторяются для каждой такой партии. Отметим, что для такого отношения следует ввести бизнес-правило, требующее, чтобы груз состоял не более чем из трех партий, поскольку четвертую партию вставить в этом отношении некуда.

Рис. 6.1.  Ненормализованное отношение

Использование отношения, представленного не в 1НФ, может породить следующие проблемы:

· если груз аннулируется и строка, связанная с грузом, удаляется из отношения, то вместе с ней удаляются все сведения о партиях груза на борту судна;

· если на склад прибывает новая партия груза, и она еще не включена в состав груза, подлежащего отправке, то сведения о партии заносить некуда;

· необходимо вводить ограничение: в грузе не может быть более трех партий.

 Приведение отношения SHIPMENT к 1НФ заключается в изъятии данных о партиях груза из отношения SHIPMENT и создании для них связанного подчиненного отношения CONSIGNMENT (ПАРТИЯ_ГРУЗА). Результат приведения отношения SHIPMENT к 1НФ представлен на рис. 6.2. Для такого представления сущности SHIPMENT не требуется вводить ограничительное бизнес-правило, о котором упоминалось выше.

Рис. 6.2.  Отношение в 1НФ

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

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

Будем считать атрибут отношения ключевым, если он является элементом какого-либо ключа отношения. В противном случае атрибут будет считаться неключевым атрибутом. Так в отношении (Город, Адрес, Почтовый_индекс) все атрибуты являются ключевыми, поскольку при заданных ФЗ город, адрес почтовый_индекс и почтовый_индекс \to город ключами являются пары город, адрес и адрес, почтовый_индекс.

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

Пример. Приведение отношения ко 2НФ

Вновь обратимся к рассмотрению отношения SHIPMENT, представленного на рис. 6.2. Оно содержит частичную ФЗ: неключевой атрибут Ship Capacity (грузоподъемность корабля) не зависит от ключевого атрибута Departure Date (даты убытия), а зависит от ключевого атрибута Ship Registration Number (регистрационный номер корабля).

Использование отношения, представленного не во 2НФ, может породить следующие проблемы:

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

· если удалить кортеж из отношения Shipment после отправки груза, то потеряются все данные о кораблях, для которых в настоящее время нет груза;

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

Приведение отношения SHIPMENT ко 2НФ заключается в изъятии атрибутов частичной ФЗ из отношения SHIPMENT и создании для нее связанного подчиненного отношения SHIP. Результат приведения отношения SHIPMENT ко 2НФ представлен на рис. 6.3.

Рис. 6.3.  Отношения во 2НФ

Таким образом, процедура приведения отношения ко 2НФ состоит в выполнении двух проекций: проекции без атрибутов частичной ФЗ и проекции на часть составного ключа и те атрибуты, которые от него зависят.

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

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

Формально это требование можно сформулировать следующим образом: схема отношения R находится в 3НФ, если не существует ключа Х для R, множества атрибутов и неключевого атрибута А из R, не принадлежащего Х или Y, таких, что: 1) имеет место в R, 2) имеет место в R, но 3) не имеет места в R.

ФЗ представляют не только ограничения целостности, налагаемые на отношения, но и связи между атрибутами, если они (связи) сохраняются в базе данных. Если отношение содержит частичную зависимость - ключ отношения и , то в каждом кортеже, используемом для хранения связи значений Х со значениями какого-либо другого атрибута, кроме А и Х, должна появиться связь между Y и A. Так, например, адрес поставщика дублируется для каждого поставляемого товара в отношении ПОСТАВКИ. Использование 3НФ исключает возможность возникновения такой ситуации (см. условие 3 в формальном определении 3НФ).

Наличие транзитивной зависимости не позволяет связать значения Y и Х, если не существует значения А, связанного со значением Y. Это затрудняет вставку и обновление данных, которые необходимо выполнить сразу для пары связей, а в случае удаления данных приводит к потере связи.

Пример. Приведение отношения к 3НФ

Вновь обратимся к рассмотрению отношения SHIPMENT, представленного на рис. 6.3. Оно содержит транзитивную ФЗ: атрибут Customs Declaration (таможенная декларация) является по своей сути свойством атрибутов Origin (пункт отправления) и Destination (пункт назначения). Результат приведения отношения SHIPMENT к 3НФ представлен на рис. 6.4.

Рис. 6.4.  Отношение в 3НФ

Таким образом, процедура приведения отношения к 3НФ состоит в выполнении двух проекций: проекции по правой части транзитивной ФЗ и проекции по левой части транзитивной ФЗ.

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

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

Отношение находится в нормальной форме Бойса-Кодда (НФБК), если оно находится в 3НФ, и в нем отсутствовали зависимости ключевых атрибутов от неключевых атрибутов. Иными словами, НФБК допускает наличие только таких нетривиальных ФЗ.

Таким образом, схема отношения в НФБК обладает теми же достоинствами, что и схема в 3НФ, но устраняет некоторые дополнительные аномалии, не устраняемые 3НФ. Например, в отношение (Город, Адрес, Почтовый_индекс), находящееся в 3НФ, невозможно записать кортеж для города с известным почтовым индексом, если не известен адрес с этим почтовым индексом. Данное отношение не находится в НФБК, так как имеет место ФЗ Почтовый_индекс Город, а атрибут почтовый_индекс не является ключом этого отношения.

Замечание. В отличие от 3НФ, исходные отношения не всегда могут быть приведены в НФБК.

 Пример. Приведение отношения к НФБК

Продолжим рассмотрение примеров из области судоходства.

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

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

Заметим, что в предыдущих случаях разбиение отношений происходило без создания избыточности данных из-за обратной зависимости атрибута на часть ключа. Приведение отношения к НФБК заключается в создании дополнительного отношения, содержащего сведения о руководителях команд (таблица 6.2).

Результат приведения отношения КОМАНДА к НФБК представлен на рис. 6.5.

Рис. 6.6.  Отношение с многозначными зависимостями

Отношение находится в НФБК и содержит только многозначные ФЗ. Однако имеет место аномалия удаления: если капитан Петров уйдет в отставку и все кортежи о нем будут удалены, то будут потеряны сведения о том, что корабль Жучка совершает рейсы Санкт-Петербург - Марсель. Если добавить новый рейс, то, возможно, придется ввести несколько кортежей в наше отношение.

Приведение отношения к 4НФ заключается в выделении для каждой многозначной ФЗ своего отношения, как показано на рис. 6.7.

Рис. 6.7.  Отношение в 4НФ

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

Пятая нормальная форма

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

Декомпозиция схем отношений не всегда гарантирует обратимость. Это обстоятельство связано с существованием класса ФЗ по соединению. Если отношение удовлетворяет ФЗ по соединению, то оно может быть восстановлено по своим проекциям. Отношения, содержащие более трех МФЗ, требуют особого внимания при построении логической модели реляционной базы данных. Также 4НФ не устраняет избыточность данных полностью, поэтому требуется дальнейшая декомпозиция схем отношений.

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

Приведение отношения к 5НФ заключается во введении еще одного отношения, связывающего три исходных отношения, как показано на рис. 6.9.

Рис. 6.9.  Отношение в 5НФ

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

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

· 1НФ - все атрибуты отношения простые;

· 2НФ - отношение находится в 1НФ и не содержит частичных ФЗ;

· 3НФ - отношение находится во 2НФ и не содержит транзитивных ФЗ от ключа;

· НФБК - отношение находится в 3НФ и не содержит ФЗ ключей от неключевых атрибутов;

· 4НФ, применяется при наличии более чем одной многозначной ФЗ - отношение находится в НФБК или 3НФ и не содержит независимых многозначных ФЗ;

· 5НФ - отношение находится в 4НФ и не содержит ФЗ по соединению.