«Базы данных»

1. Проектирование баз данных с использованием декомпозиционного метода. Аномалии, присущие универсальному отношению. Функциональные зависимости. Нормализация отношений. Нормальная форма Бойса-Кодда.

Универсальное отношение. Основные аномалии, присущие универсальному отношению.

Рассматриваемый метод проектирования называют декомпозиционным методом.

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

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

Для малых БД (включающих не более 20 атрибутов) универсальное отношение может использоваться в качестве отправной точки при проектировании БД.

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

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

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

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

1. проблема, связанная с обновлением (модификацией) данных в БД;

2. проблема, обусловленная необходимостью удаления кортежей;

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

(кортежи - строки таблицы или записи в файле)

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

Проблема вставки.

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

Проблема обновления.

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

Проблема удаления.

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

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

Первая нормальная форма. Функциональные зависимости. Нормальная форма Бойса-Кодда.

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

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

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

Функциональная зависимость (ФЗ) определяется следующим образом:

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

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

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

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

Введем необходимые понятия.

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

2. Детерминант. Если А→В есть ФЗ и В не зависит функционально от любого подмножества А, то говорят, что А представляет собой детерминант В.

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

отношение находится в НФБК, если и только если каждый детерминант отношения является возможным ключом.

Хотя существуют нормальные формы более высокого уровня, которые накладывают даже более сильные ограничения на разрабатываемые отношения, на практике большинство проектировщиков стараются получить отношения в НФБК.

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

Избыточные функциональные зависимости. Транзитивные ФЗ. Приемы удаления избыточных зависимостей использованием объединения, декомпозиции и добавления.

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

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

Приемы удаления избыточных ФЗ

Транзитивные зависимости. Одним из вариантов появления в наборе ФЗ избыточных зависимостей является наличие ФЗ, представляющих транзитивные зависимости, которые опре-деляются следующим образом:

Если A -> B и B -> C, то A -> C - транзитивная зависимость.

Здесь следует подчеркнуть два момента:

1. Транзитивная зависимость A -> C, приведенная в определении выше, является вполне корректной зависимостью.

2. Если A -> B, B -> C и A -> C входят в набор ФЗ, то A -> C является избыточной и ее использование в процессе проектирования не требуется.

Действительно, транзитивная зависимость A -> C причинит больше вреда, чем пользы при проектировании, и ее следует исключить из набора перед началом проектирования.

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

Вид первый формулируется следующим образом: Если А -> В, то А,Z -> В является корректной, но избыточной ФЗ.

Атрибут Z был добавлен к детерминанту А без привнесения какой-либо новой информации в процесс проектирования. (Здесь А,В и Z - атрибуты, каждый из которых может быть составным).

Второй вид возникает в случае добавления к обоим частям данной ФЗ одного и того же атрибута с целью формирования новой зависимости:

Если А -> В, то А,Z -> B,Z является корректной, но избыточной ФЗ.

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

Рассмотрим вкратце еще три приема удаления избыточных ФЗ.

Два наиболее простых для понимания приема удаления связаны с объединением и декомпозицией ФЗ, которые определяются следующим образом:

Объединение ФЗ: если А -> В и А -> С, то А -> В,С.

Декомпозиция ФЗ: если А -> В,С, то А -> В и А -> С.

Пятая разновидность избыточности называется псевдотранзитивностью.

Если X -> Y и Y,W -> Z, то X,W -> Z является избыточной в силу псевдотранзитивности. Этот тип избыточности возникает в тех случаях, когда в получаемых ФЗ обнаруживаются детерминанты. При обнаружении псевдотранзитивной зависимости ее необходимо удалить.