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



Алгоритм метода синтеза отношений


В данном разделе приводится лишь некоторый обзор алгоритма синтеза отношений.

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

Е,С \to В
, которая не может быть исключена из множества F-зависимостей, связанных с получаемыми отношениями R1 или R2. Таким образом, суть проблемы сводится к нарушению замкнутости реляционных операций над ФЗ на полученной схеме базы данных. Для того чтобы ее решить, необходимо пополнить минимальное покрытие ФЗ, или, как говорят, усилить минимальное покрытие.

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

Введем определение.

Определение 4. Реляционная база данных называется полной, если:

  • все ФЗ усилены ключами;
  • все отношения находятся в 3НФ;
  • не существует варианта базы данных с меньшим числом схем, удовлетворяющим вышеперечисленным свойствам.

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

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

Пример. Универсальный ключ и ложные соединения

R = ABCD, F = \{A \to B, B,C \to D\}.

Пусть отношение R имеет кортежи:

1 1 1 14 1 2 2

Случай 1.


Содержание  Назад  Вперед