Введение в системы управления базами данных


Пример 18



Пример 18


X Y Z
1 1 2
1 1 1
1 2 2
1 2 1
2 1 1

Таблица 18 R1 JOIN R2

Серым цветом выделен лишний кортеж, отсутствующий в отношении

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

Однако отношение

восстанавливается соединением всех трех проекций:

.

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

Определение 5. Пусть

является отношением, а
,
, -,
- произвольными (возможно пересекающимися) подмножествами множества атрибутов отношения
. Тогда отношение
удовлетворяет зависимости соединения

тогда и только тогда, когда оно равносильно соединению всех своих проекций с подмножествами атрибутов

,
, -,
, т.е.

.

Можно предположить, что отношение

в примере 3 удовлетворяет следующей зависимости соединения:

.

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

, а не только для состояния, приведенного в примере.

Покажем, что зависимость соединения является обобщением понятия многозначной зависимости. Действительно, согласно теореме Фейджина, отношение

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

Теорема Фейджина (другая формулировка). Отношение

удовлетворяет зависимости соединения
тогда и только тогда, когда имеется многозначная зависимость
.

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

Определение 6. Зависимость соединения

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

  • Одно из множеств атрибутов
  • не содержит потенциального ключа отношения
    .

  • Ни одно из множеств атрибутов не совпадает со всем множеством атрибутов
  • отношения
    .

    Для удобства работы сформулируем это определение так же и в отрицательной форме:

    Определение 7. Зависимость соединения

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

    Определение 8. Отношение

    находится в пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.

    Определения 5НФ может стать более понятным, если сформулировать его в отрицательной форме:

    Определение 9. Отношение

    не находится в 5НФ, если в отношении найдется нетривиальная зависимость соединения.

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

    :

    (i) Отношение

    является полностью ключевым (т.е. потенциальным ключом отношения является все множество атрибутов).

    (ii) Имеется следующая зависимость (довольно странная, с практической точки зрения): если в отношении

    содержатся кортежи
    ,
    и
    , то отсюда следует, что в отношении
    содержится также и кортеж
    .

    Утверждение. Докажем, что при наличии ограничений (i) и (ii), отношение находится в 4НФ, но не в 5НФ.

    Доказательство. Покажем, что отношение

    находится в 4НФ. Согласно определению 4НФ, необходимо показать, что отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей. Т.к. отношение является полностью ключевым, то оно автоматически находится в НФБК. Если бы в отношении имелась многозначная зависимость (необязательно нетривиальная), то, согласно теореме Фейджина, отношение можно было бы декомпозировать без потерь на две проекции. Но пример 3 показывает, что таких декомпозиций нет (здесь мы воспользовались тем, что для доказательства возможности декомпозиции необходимо доказать ее для всех возможных состояний отношения, а для доказательства невозможности достаточно привести один контрпример). Поэтому в отношении нет никаких многозначных зависимостей.

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

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

    Но является ли такая декомпозиция именно зависимостью соединения? Для этого нужно показать, что декомпозиция на три проекции

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

    Как и в предыдущих доказательствах, нужно доказать, что

    для любого состояния отношения
    .

    Включение

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

    Докажем включение

    .

    Пусть кортеж

    . Это означает, что в проекции
    содержится кортеж
    , в проекции
    содержится кортеж
    , а в проекции
    содержится кортеж
    . По определению проекции, найдутся такие значения
    ,
    ,
    атрибутов
    ,
    и
    соответственно, что отношение
    содержит кортежи
    ,
    и
    . Но тогда по условию (ii) в отношении
    содержится также и кортеж
    . Этим доказано необходимое включение. Утверждение доказано.









    Начало  Назад  Вперед