Рубрики

Каноническое покрытие функциональных зависимостей в СУБД

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

Важные определения:

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

  • F логически подразумевает все зависимости в ,
  • логически подразумевает все зависимости в F.
  • Нет функциональной зависимости в содержит посторонний атрибут.
  • Каждая левая сторона функциональной зависимости в уникален То есть нет двух зависимостей и в такой, что ,

В поисках канонической обложки

Алгоритм вычисления канонического покрытия множества F:

repeat
    1. Use the union rule to replace any dependencies in 
        and  with .
    2. Find a functional dependency  with an 
       extraneous attribute either in  or in .
    3. If an extraneous attribute is found, delete it from .
       until F does not change

Example1:

Рассмотрим следующий набор F функциональных зависимостей:

F = {
До нашей эры
В С
В
AB С
}

Шаги, чтобы найти каноническое покрытие:

  1. Есть две функциональные зависимости с одинаковым набором атрибутов слева:
    До нашей эры
    В

    Эти два могут быть объединены, чтобы получить
    ДО НАШЕЙ ЭРЫ.

    Теперь пересмотренный набор F становится:

    F = {
    До нашей эры
    В С
    AB С
    }

  2. В AB есть посторонний атрибут С, потому что даже после удаления AB C из множества F мы получаем такие же замыкания. Это потому что б C уже является частью F.

    Теперь пересмотренный набор F становится:

    F = {
    До нашей эры
    В С
    }

  3. C является посторонним атрибутом в A До н.э., также В логически подразумевается А Б и Б С (по транзитивности).

    F = {
    В
    В С
    }

  4. После этого шага F больше не меняется. Так,
    Следовательно, необходимое каноническое покрытие
    знак равно
    В
    В С
    }

Example2:

Рассмотрим другой набор F функциональных зависимостей:

F = {
До нашей эры
компакт диск Е
В D
Е
}

  1. Левая сторона каждой функциональной зависимости в F уникальна.
  2. Ни один из атрибутов в левой или правой части какой-либо функциональной зависимости не является посторонним (проверяется путем применения определения посторонних атрибутов для каждой функциональной зависимости).
  3. Следовательно, каноническое покрытие равно F.

Примечание: может быть несколько канонических обложек множества F функциональных зависимостей.

Как проверить, может ли набор F в Fd канонически покрывать другой набор G в Fd?

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

F = {
В
AB С
D переменный ток
D Е
}

G = {
До нашей эры
D AB
}

Теперь нам необходимо выяснить, распространяется ли один из этих fd на другой набор fd. Это означает, что нам нужно выяснить, покрывает ли F канонически G, G канонически F или ни одно из двух не охватывает другое.

Чтобы выяснить это, мы следуем следующим шагам:

  • Создайте синглтон с правой стороны. Это означает, что атрибуты справа от стрелки fd должны быть одноэлементными.
    Функциональная зависимость D AC разбивается на две функциональные зависимости, D А и Д C.

    F = {
    В
    AB С
    D
    D С
    D Е
    }

  • Удалить все посторонние атрибуты.

    Рассмотрим любую функциональную зависимость XY Z. Если X сам по себе может определять Z, то атрибут Y является посторонним и может быть удален. Как мы видим, возникновение посторонних атрибутов возможно только в тех функциональных зависимостях, где в LHS имеется более одного атрибута.

    Итак, рассмотрим функциональную зависимость AB C.
    Теперь мы должны найти замыкания A и B, чтобы выяснить, является ли что-то из них посторонним.

    = AB
    = В

    Как мы видим, B можно определить из A. Это означает, что мы можем удалить B из функциональной зависимости AB. C.

    F = {
    В
    С
    D
    D С
    D Е
    }

  • Удалить все избыточные функциональные зависимости.

    Проверьте все fd один за другим, и посмотрите, удалив ли fd X Y, мы все еще можем узнать Y из X с помощью некоторого другого fd. Более формальный способ заявить, что это найти без использования fd мы тестируем и проверяем, является ли Y частью замыкания. Если да, то FD является избыточным.

    Здесь, при проверке на FD D C, мы видим, что даже после того, как он скрыт, замыкание D содержит C. Это потому, что мы можем получить C из D комбинацией двух других FD's D А и А C. Итак, С избыточен.

    F = {
    В
    С
    D
    D Е
    }

Теперь сделайте то же самое для G.

  • Создайте синглтон с правой стороны. Это означает, что атрибуты справа от стрелки fd должны быть одноэлементными.

    G = {
    В
    С
    D
    D В
    }

  • Удалить все посторонние атрибуты.
    Поскольку RHS всех fd содержит только 1 атрибут, посторонний атрибут невозможен.
  • Удалить все избыточные функциональные зависимости.

    Обходя все fd и проверяя закрытие LHS во всех случаях, мы видим, что fd D B является избыточным, так как он может быть получен с помощью комбинации 2 других FD, D А и А B.

    G = {
    В
    С
    D
    }

Теперь, так как все f из G уже покрыты в F, мы заключаем, что F покрывает G.

Эта статья предоставлена Ананней Уберой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Каноническое покрытие функциональных зависимостей в СУБД

0.00 (0%) 0 votes