Декомпозиция с соединением без потерь

Определение ключа

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

Рассмотрим некоторые определения.

Определение

Множество атрибутов Y функционально полно зависит от атрибутов X, если Y функционально зависит от X и не зависит функционально от любого собственного подмножества X.

Другими словами, если есть X à Y, то для любого Z Ì X нет зависимости Z à Y.

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

Например, рассмотрим следующее отношение:

ПОСТАВКА ДЕТАЛЕЙ ( S#, SNAME, CITY, P#, PNAME, PRICE, QTY).

Для данного отношения определена функциональная зависимость (S#, P#) à QTY, и она является функционально полной зависимостью.

С другой стороны, для этого же отношения определена и функциональная зависимость (S#, P#) à CITY, но она не является функционально полной, так как существует функциональная зависимость S# à CITY.

Определение

Если R – схема отношения с атрибутами A1, A2, …, An и множеством функциональных зависимостей F, X Í U – некоторое подмножество атрибутов {A1, A2, …, An}, то X называется ключом R, если:

a) функциональная зависимость X à A1A2…An принадлежит F+,

b) ни для какого собственного подмножества Y Ì X функциональная зависимость Y à A1A2…An не принадлежит F+.

Другими словами, X à A1A2…An есть функционально полная зависимость.

Если X – первичный ключ отношения R, тогда из функциональной зависимости X à A1A2…An в соответствии с правилом 6 следуют функциональные зависимости X à Ai для i = 1, 2, …, n.

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

Определение

Декомпозицией схемы отношения R(A1, A2, …, An) называется замена ее совокупностью подмножеств {Ri} схемы R таких, что R1 È R2 È … È Rk = R. При этом не обязательно, чтобы Ri были не пересекающимися.

Вывод: декомпозиция, по сути, представляет собой совокупность проекций отношения. Так, если есть некоторая реализация отношения r(R), то, используя декомпозицию, получим:

ri = pRi(r), i = 1, 2, …, k.

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

s = r1 r2 … rk

Где гарантия, что s º r? Если такой гарантии нет, получив из ri s, мы не будем знать, достоверна информация или нет.

Рассмотрим пример. Пусть отношение со схемой S(S#, STATUS, CITY) имеет следующую реализацию:

S (S#, STATUS, CITY)
  S1 N1
  S2 N2

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

a) S1 (S#, STATUS)   S2 (S#, CITY)
    S1     S1 N1
    S2     S2 N2

Делаем операцию естественного соединения – восстановление исходного отношения:

s1 s2 = S (S#, STATUS, CITY)
  S1 N1
  S2 N2

Получили отношение, совпадающее с исходным.

b) S1 (S#, STATUS)   S2 (STATUS, CITY)
    S1     N1
    S2     N2

Восстанавливаем:

s1 s2 = S (S#, STATUS, CITY)
  S1 N1
  S1 N2
  S2 N1
  S2 N1

В результате получили лишние строки, отсутствовавшие в исходном отношении.

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

Определение

Пусть R – схема отношения, в результате декомпозиции которой получены схемы R1, R2, …, Rk, и F – множество функциональных зависимостей для R. Говорят, что эта декомпозиция обладает свойством соединения без потерь относительно F, если каждая реализация r(R), удовлетворяющая F, может быть представлена в виде:

r = pR1(r) pR2(r) … pRk(r)

Теорема

Пусть R(A, B, C) – схема отношения с атрибутами (подмножествами атрибутов) A, B и C. Если данная схема отношения удовлетворяет функциональной зависимости A à B, то осуществляется декомпозиция без потери на {R1, R2}, где R1 = {A, B} и R2 = {A, C}.

Вернемся к приведенному выше примеру: S(S#, STATUS, CITY}. Так как S# – первичный ключ отношения, то S# à CITY. Отсюда, декомпозиция без потери осуществляется на подсхемы S1(S#, CITY) и S2(S#, STATUS).

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

S# à CITY

CITY à STATUS

В соответствии с теоремой можно предложить два способа декомпозиции без потери информации:

a) относительно S# à CITY: S11(S#, CITY) и S12(S#, STATUS)

b) относительно CITY à STATUS: S21(CITY, S#) (или S21(S#, CITY) – порядок задания имен атрибутов никакого значения не имеет) и S22(CITY, STATUS)

Какой из этих двух способов лучше?

Чтобы ответить на этот вопрос, введем еще одно определение:

Проекцией множества функциональных зависимостей F на множество атрибутов Z (pZ (F)) называется множество зависимостей X à Y в F+, таких, что XY Í Z.

Рассмотрим все тот же пример.

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

F = {S# à CITY, CITY à STATUS}

Из них по правилам вывода можно вывести следующие зависимости:

S# à STATUS – правило транзитивности;

S# à (CITY, STATUS) – правило объединения.

Отсюда,

F+ = {S# à CITY, CITY à STATUS, S# à STATUS, S# à (CITY, STATUS)}

Для способа a) декомпозиции определены следующие функциональные зависимости:

S# à STATUS, из схемы отношения S11(S#, STATUS)

S# à CITY, из схемы отношения S12(S#, CITY)

Для способа b) декомпозиции определены следующие функциональные зависимости:

S# à CITY, из схемы отношения S21(S#, CITY)

CITY à STATUS, из схемы отношения S22(CITY, STATUS)

Определение

Говорят, что декомпозиция сохраняет множество функциональных зависимостей F, если из объединения всех зависимостей, принадлежащих pRi (F), для i = 1, 2, …, k, логически следуют все зависимости, принадлежащие F.

Из функциональных зависимостей, сохранившихся при способе декомпозиции a), нельзя логически вывести зависимость CITY à STATUS, т.е. данная декомпозиция не сохраняет функциональные зависимости.

Для способа декомпозиции b) все функциональные зависимости из F сохранены.

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

Пусть дана следующая реализация отношения:

S (S#, STATUS, CITY)
  S1 N1
  S2 N2
  S3 N3

Выполним декомпозицию этого отношения способом a):

  S11 (S#, CITY)   S12 (S#, STATUS)
    S1 N1     S1
    S2 N2     S2
    S3 N3     S3

Предположим, что поставщик S2 переехал в город N3. Тогда в отношении S11 появится кортеж <S2, N3>. Но в отношении S12 сохраняется кортеж <S2, 30>, в соответствии с которым город N3 приобретает статус 30, что неправильно. Следовательно, для поддержания достоверного состояния реализаций потребуется изменить не только кортеж в S11, но и кортеж в S12.

Если же выполнить декомпозицию отношения способом b):

  S21 (S#, CITY)   S22 (CITY, STATUS)
    S1 N1     N1
    S2 N2     N2
    S3 N3     N3

Тогда достаточно изменить кортеж в отношении S21: <S2, N3>; статус города N3 определен в отношении S22 независимо от того, какой поставщик в этом городе дислоцирован.