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

Упражнение 1

Рассмотрим схему отношения \(R(A,B,C,D)\), имеющую следующий набор ФЗ:

• \({A, B} \to C\)
• \(C \to D\)
• \(D \to A\)

1. Каковы все нетривиальные ФЗ, которые следуют из заданных?
2. Какие потенциальные ключи есть в \(R\)?
3. Каковы суперключи \(R\), не являющиеся потенциальными ключами?

Решение:

Построим замыкания для всех подмножеств атрибутов \(R\):

• \(A^+ = A\)
• \(B^+ = B\)
• \(C^+ = C, D, A\)
• \(D^+ = D, A\)
• \({A,B}^+ = {A,B,C,D}\)
• \({A,C}^+ = {A,C,D}\)
• \({A,D}^+ = {A,D}\)
• \({B,C}^+ = {B,C,D,A}\)
• \({B,D}^+ = {B,D,A,C}\)
• \({C,D}^+ = {C,D,A}\)
• \({A,B,C}^+ = {A,B,C,D}\)
• \({A,B,D}^+ = {A,B,C,D}\)
• \({A,C,D}^+ = {A,C,D}\)
• \({B,C,D}^+ = {B,C,D,A}\)
• \({A,B,C,D}^+ = {A,B,C,D}\)

Последнее замыкание является тривиальным по очевидным причинам.

Тогда, список суперключей:

• \({A,B}\)
• \({B,C}\)
• \({B,D}\)
• \({A,B,C}\)
• \({A,B,D}\)
• \({B,C,D}\)
• \({A,B,C,D}\)

Из них потенциальными ключами (по признаку минимальности) являются:

• \({A,B}\)
• \({B,C}\)
• \({B,D}\)

Таким образом, получены ответы на вопросы (2, 3)

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

• \(A \to A\)
• \(B \to B\)
• \(C \to (C, D, A)\)
• \(D \to (D, A)\)
• \((A,B) \to (A,B,C,D)\)
• \((A,C) \to (A,C,D)\)
• \((A,D) \to (A,D)\)
• \((B,C) \to (B,C,D,A)\)
• \((B,D) \to (B,D,A,C)\)
• \((C,D) \to (C,D,A)\)
• \((A,B,C) \to (A,B,C,D)\)
• \((A,B,D) \to (A,B,C,D)\)
• \((A,C,D) \to (A,C,D)\)
• \((B,C,D) \to (B,C,D,A)\)
• \((A,B,C,D) \to (A,B,C,D)\)

Их можно раскыть по правилам декомпозиции.

Упражнение 2.

Выполнить задание упражнения 1 для отношений:

1. \(S(A,B,C,D)\) с ФЗ \(A\to B\); \(B\to C\); \(B\to D\)
2. \(T(A,B,C,D)\) с ФЗ \(A B\to C\); \(B C\to D\); \(C D\to A\); \(A D \to B\)
3. \(U(A,B,C,D)\) с ФЗ \(A \to B\); \(B C\to C\); \(C \to D\); \(D \to A\)

Решение аналогично решению упражнения 1.

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

Упражнение 3.

Для каждого из следующих отношений:

1. \(R(A,B,C,D)\) c ФЗ \(A B \to C\); \(C \to D\); \(D\to A\)
2. \(R(A,B,C,D)\) c ФЗ \(B \to C\); \(B \to D\)
3. \(R(A,B,C,D)\) c ФЗ \(A B \to C\); \(B C \to D\); \(C D \to A\); \(A D \to B\)
4. \(R(A,B,C,D)\) c ФЗ \(A \to B\); \(B \to C\); \(C \to D\); \(D \to A\)
5. \(R(A,B,C,D,E)\) c ФЗ \(A B \to C\); \(D E \to C\); \(B \to D\)
6. \(R(A,B,C,D,E)\) c ФЗ \(A B \to C\); \(C \to D\); \(D \to B\); \(B \to E\)

проведите нормализацию до НФЭК или НФБК (если возможно).

Решение 1:

Как в упражнении 1, найдем замыкание ФЗ, но исключим тривиальные:

• \(C \to (D, A)\)
• \(D \to A\)
• \((A,B) \to (C,D)\)
• \((A,C) \to D\)
• \((B,C) \to (D,A)\)
• \((B,D) \to (A,C)\)
• \((C,D) \to A\)
• \((A,B,C) \to D\)
• \((A,B,D) \to C\)
• \((B,C,D) \to A\)

Суперключи:

• \({A,B}\)
• \({B,C}\)
• \({B,D}\)
• \({A,B,C}\)
• \({A,B,D}\)
• \({B,C,D}\)
• \({A,B,C,D}\)

Потенциальные ключи:

• \({A,B}\)
• \({B,C}\)
• \({B,D}\)

ФЗ, не удовлетворяющие условиям НФБК:

• \((A, C) \to D\)
• \(C \to (A, D)\)
• \((C, D) \to A\)
• \(D \to A\)

Или, минимизируя:

• \(C \to (D, A)\)
• \(D \to A\)

Проведем декомпозицию в НФЭК по алгоритму Берштейна. Исходное множество ФЗ является, как несложно заметить, минимальным, поэтому шаги (1) и (2) не меняют его.

3. Группировка
   • Группа 1: \(A B \to C\);
   • Группа 2: \(C \to D\);
   • Группа 3: \(D\to A\)
4. Объединение. Не меняет группировку, поскольку нет взаимных ФЗ.
5. Выделяем отношения. Ключи обозначены жирным:
   • \((\mathbf A, \mathbf B, C)\)
   • \((\mathbf C, D)\)
   • \((\mathbf D, A)\)

Или, построив диаграмму атрибутов по исходным ФЗ:

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

Минимальные множества ФЗ в новых отношениях несложно получить, проецируя замыкание ФЗ на соответствующие наборы атрибутов:

S(A, B, C):

• (A, B) -> C
• C -> A

T(C, D):

• C -> D

U(A, D):

• D -> A

Следует заметить, что отношение S не находится в НФБК, поскольку содержит ФЗ \(C\to A\). Оно, однако, находится в НФЭК. Его нормализация до НФБК оказывается невозможной без потерь ФЗ.

Решение 2:

Очевидно, что суперключом и единственным потенциальным ключом будет \(B\). Отношение не удовлетворяет 2НФ, поскольку атрибут \(A\) не зависит от потенциального ключа. Он может быть вынесен в отдельное отношение:

• S(A)
• T(B, C,D)

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

К аналогичным выводам можно прийти по диаграмме атрибутов:

Решение 5:

• \(A B \to C\)
• \(D E \to C\)
• \(B \to D\)

Аналогично упражнению 1, найдем все ФЗ (исключая тривиальные):

• \((A, B) \to (C, D)\)
• \((A, B, C) \to D\)
• \((A, B, C, E) \to D\)
• \((A, B, D) \to C\)
• \((A, B, D, E) \to C\)
• \((A, B, E) \to (C, D)\)
• \((A, D, E) \to C\)
• \(B \to D\)
• \((B, C) \to D\)
• \((B, C, E) \to D\)
• \((B, D, E) \to C\)
• \((B, E) \to (C, D)\)
• \((D, E) \to C\)

Потенциальные ключи:

• \((A, B, E)\)

ФЗ, не удовлетворяющие НФБК:

• \((A, B) \to (C, D)\)
• \((A, B, C) \to D\)
• \((A, B, D) \to C\)
• \((A, D, E) \to C\)
• \(B \to D\)
• \((B, C) \to D\)
• \((B, C, E) \to D\)
• \((B, D, E) \to C\)
• \((B, E) \to (C, D)\)
• \((D, E) \to C\)

или, минимизируя:

• \((A, B) \to C\)
• \(B \to D\)
• \((D, E) \to C\)

Можно заметить, что эти ФЗ так же не удовлетворяют 3НФ (что понятно, поскольку существует единственный потенциальный ключ, значит 3НФ эквивалентна НФБК)

Пользуясь алгоритмом Берштейна, получаем следуюшие отношения:

• \(S(\mathbf A,\mathbf B,C)\)
• \(T(\mathbf B,D)\)
• \(U(\mathbf D,\mathbf E,C)\)

Несложно заметить, каждое из них находится в НФБК.

Или, построив диаграмму атрибутов по исходным ФЗ:

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