Полнота системы аксиом вывода

Пусть А — некоторое множество аксиом вывода, Т — множество функциональных зависимостей. Понятие замыкания [Fa множества Т относительно системы аксиом А вводится индуктивно:

• 2) если / выводится из [Fa однократным применением аксиом из Л, то /6 [Та
• 3) других F-зависимостей в [?]а нет.

Если А = {F1,F2,F3,F4,F5,F6}, то индекс А будем опускать и писать [F]. .

Если / 6 [F], то будем говорить, что / выводится из Т.

В предыдущем разделе мы фактически показали, что если / € [F], то Т |= /, т. е. если / выводится из F, то / является логическим следствием F. В этом разделе мы покажем обратное.

Система аксиом вывода А полна, если из Т f= / следует, что.

/ € [Ял;

Теорема 8. Если домен каждого из атрибутов имеет мощность более 1, то система аксиом А = {F1,F2,F3,F4,F5,F6} полна.

Доказательство. Пусть 71 = {А, Лг,…, Л_п} — схема отношения, Т — некоторое множество F-зависимостей над 71, н X С 7Z, Y С 71. Покажем, что если X —? У # [F], то Т И X -> У.

Чтобы показать, что Т X —? У, нам надо найти такое отношение R, которое удовлетворяет всем зависимостям из F, но не удовлетворяет X —> У.

Пусть Х⁺ такое подмножество 7Z, что для любого Z С 71 из того, что X —> Z? [F] следует, что Z С Х⁺, т. е. Х⁺ — это максимальное подмножество, зависящее от X. Понятно, что ХСХ+.

Пусть Qi, bi G dom (Ai), i = 1,2,…, п. Рассмотрим отношение R, состоящее из двух кортежей г = (<�ц, аг,…, а_п) иг', где.

Покажем, что если X —> Y & [F], то отношение F не удовлетворяет X —? Y.

По определению г (Х) = г'(Х). Предположим, что г (У) = г'(У). Тогда У С Х+ и, значит, Х⁺ —? У, но X —> Х⁺ € [V], откуда следует, что X —? У G [F]. Противоречие.

Теперь покажем, что F удовлетворяет всем F-зависимостям из [Т].

Имеет смысл рассматривать только F-зависимости вида W —> Z, где W С Х+, так как если W g Х⁺, то r (W) ф r'(W). Если W С ЛГ+, то Х⁺ — W е [ЯУчитывая X Х+ е [F] н W -> Z е (Я) по транзитивности имеем X —* Z € [ЯОткуда следует, что Z С Х⁺ и, значит, r (Z) = r'(Z). Следовательно, Я удовлетворяет W —? Z.

Значит, R удовлетворяет всем F-зависимостям из [Я" но не удовлетворяет X —? Y. Значит Т ф X —? Y.

Теорема доказана. ?

У пражнения.

• 2.1. Пусть R (A, B, C) и S (D, C_}D) — отношения, а е dom (A) и 6 € dom (B). Какие из следующих выражений правильно составлены:
  • а) RnS
  • б) n_B® тгв (5);
  • в) <7в=ь)(#);
  • г) <7д=а, в=ь)(?);
  • д) Я N5;
  • е) 7гд (Я) М 7 Г?>(?)?
• 2.2. Отношения Я и 5 таковы:

Я (Д В С) S (B С D).

а Ь с V? d

а 6' с' Ь" с' с'.

а 6″ с' 6″ с d

а 6' с Вычислить значения следующих выражений:

• а) Я;
• б) S;
• в) <7_Д=:а)(Я);
• г) все правильно составленные выражения в упр. 2.1.
• 2.3. Пусть Я и S — отношения со схемой TZ и ключом К. Какие из следующих отношений обязательно должны иметь ключ К:
  • а) Я U 5;
  • б) Дп5;
  • в) Д5;
  • г) R_} где R — отношение;
  • д) тгк-(Я);
  • е) ДМ 5?
• 2.4. Пусть X С 7Z, и R, S — отношения со схемой 71. Докажите или опровергните утверждение
• а) 7rx (R П S) = nx® П 7гх (5);
• б) 7гх (Ди 5) = 7гх (Д) U7rx (5);
• в) 7гх (Д5) = 7гх (Д)тгх (5);
• г) 7гх (Д) = 7Гх (Д), где Д — отношение.
• 2.5. Пусть Д и Д' — отношения со схемой 71 и 5 — отношение со схемой 5. Докажите или опровергните утверждение
• а) (ДПД')МД=(Д"Д)П (Д^/М5);
• б) (ДД')М5 = (ДМ5)(Д'М5);
• в) Дм5 = Д1хГ5.
• 2.6. Для данных отношений R (7Z) и 5(5) и Q = Д М 5 определено Д' = 7Гя (ф) и 5' = 7rs (Q). Докажите, что Q = Д' М 5'.
• 2.7. Докажите, что отношение Д удовлетворяет Л" —? У тогда и только тогда, когда X является ключом для тгхиу (Д) —
• 2.8. Пусть Д — отношение со схемой 71, X С 71. Покажите, что если 7Гх (Д) имеет то же число кортежей, что и Д, то Д удовлетворяет X —? У для любого У из 71.
• 2.9. Докажите или опровергните следующие правила вывода для отношения Д со схемой 71, в которых W, X, У и Z — подмножества 71:
  • а) из X -> У и Z — И⁷ следует X U У —? У U И⁷;
  • б) из X U У -? Z и X —? X следует Z —? X;
  • в) изХ-«УиУ-+2 следует X —» У U Z;
  • г) из X —? У, И⁷ —* Z и И⁷ С У следует X — Z.
• 2.10. Докажите, что аксиомы вывода FI, F2 и F6 являются независимыми. Это значит, что ни одна их них не может быть получена из двух других.