Skip to content

Теория проектирования реляционных баз данных

Jump to bottom
Pandas edited this page Jan 9, 2018 · 9 revisions

Часть 1

  1. Дана переменная-отношение R(A, B, C, D) с функциональными зависимостями S={A–>BC, B–>C, A–>B, AB–>C, AC–>D}. Найти неприводимое множество функциональных зависимостей, эквивалентное данному множеству.
1. Перепишем так, чтобы каждая зависимость имела одноэлементную правую часть.
A -> B
A -> C
B -> C
A -> B (можно убрать, т.к. записана выше)
AB -> C
AC -> D  (*)

2. A -> C  ⇒ ( по правилу дополнения) A -> AC  ⇒  (*) ⇒ A -> D 

3. AB -> C м.б. убрана, т.к. дана зависимость A -> C ⇒ ( по правилу дополнения ) AB -> CB ⇒ 
( по правилу декомпозиции) AB -> C, AB -> B 

4. Т.к. A -> B, B -> C, то A -> C можно опустить. 

Ответ: A -> D, A -> B, B -> C
  1. Дано множество функциональных зависимостей S={A–>B, BC–>DE, AEF–>G}, имеющих место для переменной-отношения R(A, B, C, D, E, F, G). Вычислить замыкание {A, C}+ для данного множества функциональных зависимостей. Подразумевается ли зависимость ACF–>DG одной из функциональных зависимостей этого множества?
1) {A, C}+ = {A, B, C, D, E}. 

2) ACF–>DG
𝑆 = {𝐴 → 𝐵(1),𝐵𝐶 → 𝐷𝐸(2),𝐴𝐸𝐹 → 𝐺(3)}
   a. 𝐴→𝐵 => 𝐴𝐶→𝐵𝐶 => (2)𝐴𝐶→𝐷𝐸 => 𝐴𝐶𝐹→𝐷𝐸𝐹 => 𝐴𝐶𝐹→𝐷
   b. 𝐴→𝐵 => 𝐴𝐶→𝐵𝐶 => (2)𝐴𝐶→𝐷𝐸 => 𝐴𝐶→𝐸=>𝐴𝐶𝐹→𝐴𝐸𝐹 => (3)𝐴𝐶𝐹→𝐺 
   c. 𝑎, 𝑏 => 𝐴𝐶𝐹→𝐷𝐺
Ответ: да.
  1. Эквивалентны ли два множества функциональных зависимостей S1={A –>B, AB–>C, D–>AC, D–>E} и S2={A–>BC, D–>AE}, установленных для переменной-отношения R(A, B, С, D, E)?

Они эквивалентны. Пронумеруем функциональные зависимости из 
множества S1 следующим образом.
   1. A–>B
   2. AB–>C 
   3. D–>AC 
   4. D–>E
Тогда строка 3 (по правилу декомпозиции) может быть заменена следующей строкой 
   3. D–>A и D–>C
Затем с помощью строки 1 можно придать строке 2 такой вид. 
   2. A–>C
Но поскольку теперь D–>A и A–>C, то (по правилу транзитивности) 
это подразумевает D–>C, а в результате для строки 3 можно получить следующее выражение.
   3. D–>A
Таким образом, первое множество функциональных зависимостей
 эквивалентно следующему неприводимому множеству.
   {A –>B, A–>C, D–>A, D–>E}
Множество S2={A–>BC, D–>AE} очевидно эквивалентно полученному 
неприводимому множеству. Таким образом, эти множества эквивалентны.
  1. Найдите неприводимое покрытие множества функциональных зависимостей S={AB–>C, C–>А, BC–>D, ACD–>B, BE–>C, CE–>FA, CF–>BD, D–>EF}, заданных для переменной-отношения R(A, B, C, D, E, F).
Аналогично (1)
AB -> C
C -> A
BC -> D
BE -> C
CE -> F
CF -> B 
D -> E 
D -> F
или
AB -> C
C -> A
BC -> D
CD -> B
CE -> F
BE -> C
CF -> D 
D -> E 
D -> F
  1. Пусть дана переменная-отношение R(A, B, C, D, E, F, G, H, I, J), для которой выполняется множество функциональных зависимостей S={ABD–>E, AB–>G, B–>F, C–>J, CJ–>I, G–>H}. Является ли это множество неприводимым? Какие потенциальные ключи существуют для данной переменной-отношения?
   1) 𝐴𝐵𝐷→𝐸, 
   2) 𝐴𝐵→𝐺 
   3) 𝐵→𝐹
   4) 𝐶→𝐽
   5) 𝐶𝐽→𝐼 
   6) 𝐺→𝐻

4: 𝐶 → 𝐽 => 𝐶 → 𝐶𝐽 транзитивно с 5 => 𝐶 → 𝐼, заменяем 5 на 𝐶 → 𝐼
   1) 𝐴𝐵𝐷→𝐸,
   2) 𝐴𝐵→𝐺
   3) 𝐵→𝐹
   4) 𝐶→𝐽
   5) 𝐶→𝐼 
   6) 𝐺→𝐻
Атрибуты, встречающиеся только в левой части: 𝐴, 𝐵, 𝐶, 𝐷 – (входят во все потенциальные ключи) 
Атрибуты, встречающиеся только в правой части: 𝐸, 𝐹, 𝐻, 𝐼 (не входят в потенциальные ключи) 
Атрибуты, не вошедшие в первые 2 группы: 𝐺

(A,𝐵,𝐶,𝐷)+ = {𝐴,𝐵,𝐶,𝐷,𝐸,𝐹,𝐺,𝐻,𝐼,𝐽}
Остальные подмножества атрибутов будут содержать в себе потенциальный ключ, то есть сами не будут являться потенциальными ключами.
Потенциальные ключи: (𝐴, B, 𝐶, 𝐷)
  1. Пусть дана переменная-отношение R(A, B, C, D, E), для которой выполняется множество функциональных зависимостей S={A–>B, BC–>E, ED–>A}. Какие потенциальные ключи существуют для данной переменной-отношения? Находится ли переменная-отношение в 3NF? Находится ли переменная-отношение в BCNF? Ответ пояснить.
Атрибуты, встречающиеся только в левой части: C,D – (входят во все потенциальные ключи) Атрибуты, встречающиеся только в правой части: - (не входят в потенциальные ключи) Атрибуты, не вошедшие в первые 2 группы: A, B, E
(𝐶, 𝐷)+ = {𝐶, 𝐷}
(𝐴,𝐶,𝐷)+ = {𝐴,𝐵,𝐶,𝐷,𝐸}
(𝐵,𝐶,𝐷)+ = {𝐴,𝐵,𝐶,𝐷,𝐸}
(𝐶,𝐷,𝐸)+ = {𝐴,𝐵,𝐶,𝐷,𝐸}
Остальные подмножества атрибутов будут содержать в себе потенциальный ключ, то есть сами не будут являться потенциальными ключами.
Потенциальныеключи:(𝐴,𝐶,𝐷), (𝐵,𝐶,𝐷), (𝐶,𝐷,𝐸)
  1. Дана переменная-отношение Homework_Result(Student_ID, Exercise_No, Points, Max_Points), для которой выполняется множество функциональных зависимостей S={{Student_ID, Exercise_No} –>Points, Exercise_No –>Max_Points}. Какие потенциальные ключи существуют для данной переменной-отношения? Находится ли переменная-отношение в 3NF? Находится ли переменная-отношение в BCNF? Ответ пояснить.
Атрибуты, встречающиеся только в левой части: StudentID, ExerciseNo – (входят во все потенциальные ключи)
Атрибуты, встречающиеся только в правой части: Points, MaxPoints (не входят в потенциальные ключи)
Атрибуты, не вошедшие в первые 2 группы: -
(StudentID,ExerciseNo)+ ={StudentID,ExerciseNo,Points,MaxPoints}
Остальные подмножества атрибутов будут содержать в себе потенциальный ключ, то есть сами не будут являться потенциальными ключами.
Потенциальные ключи: (StudentID, ExerciseNo)
  1. Дано множество функциональных зависимостей S={A–>BC, AC–>DE, D–>F, E–>AB}, имеющих место для переменной-отношения R(A, B, C, D, E, F). Вычислить замыкание {А}+ для данного множества функциональных зависимостей. Какие потенциальные ключи существуют для данной переменной-отношения?
Найдем неприводимое множество: 
1) 𝐴→𝐵𝐶
2) 𝐴𝐶→𝐷𝐸
3) 𝐷→𝐹
4) 𝐸→𝐴𝐵

1) 𝐴→𝐵
2) 𝐴→𝐶 
3) 𝐴𝐶→𝐷 
4) 𝐴𝐶→𝐸 
5) 𝐷→𝐹 
6) 𝐸→𝐴 
7) 𝐸→𝐵

Из 2: 𝐴 → 𝐶 => 𝐴 → 𝐴𝐶 транзитивно с 𝐴𝐶 → 𝐷 => 𝐴 → 𝐷 => заменяем 3 на 𝐴 → 𝐷 Из 2: 𝐴 → 𝐶 => 𝐴 → 𝐴𝐶 транзитивно с 𝐴𝐶 → 𝐸 => 𝐴 → 𝐸 => заменяем 4 на 𝐴 → 𝐸

1) 𝐴→𝐵 
2) 𝐴→𝐶
3) 𝐴→𝐷 
4) 𝐴→𝐸
5) 𝐷→𝐹 
6) 𝐸→𝐴 
7) 𝐸→𝐵

из 4 и 7 => 𝐴 → 𝐵, можно удалить 1 

1) 𝐴→𝐶
2) 𝐴→𝐷 
3) 𝐴→𝐸 
4) 𝐷→𝐹 
5) 𝐸→𝐴 
6) 𝐸→𝐵
Атрибуты, встречающиеся только в левой части: - (входят во все потенциальные ключи) 
Атрибуты, встречающиеся только в правой части: 𝐵, 𝐶, 𝐹 (не входят в потенциальные ключи) 
Атрибуты, не вошедшие в первые 2 группы: 𝐴, 𝐷, 𝐸
Так как первая группа пуста, то перебираем все подмножества из третьей группы, начиная с наименее мощных:
(𝐴)+ = {A,B,𝐶,𝐷,𝐸,𝐹} (𝐷)+ = {𝐷, 𝐹}
(𝐸)+ = {𝐴,𝐵,𝐶,𝐷,𝐸,𝐹}
Остальные подмножества атрибутов будут содержать в себе потенциальный ключ, то есть сами не будут являться потенциальными ключами.
Потенциальные ключи: (𝐴), (𝐸)
  1. Дано множество функциональных зависимостей S={AB–>C, CD–>E, C–>A, C–>D, D–>B}, имеющих место для переменной-отношения R(A, B, C, D, E). Какие потенциальные ключи существуют для данной переменной-отношения?
Найдем неприводимое множество: 
1) 𝐴𝐵→𝐶
2) 𝐶𝐷→𝐸 
3) 𝐶→𝐴 
4) 𝐶 → 𝐷 
5) 𝐷 → 𝐵
Из 2 и 4: 𝐶 → 𝐷 => 𝐶 → 𝐶𝐷 транзитивно с 𝐶𝐷 → 𝐸 => 𝐶 → 𝐸
1) 𝐴𝐵→𝐶 
2) 𝐶→𝐸 
3) 𝐶→𝐴 
4) 𝐶→𝐷 
5) 𝐷→𝐵
Атрибуты, встречающиеся только в левой части: - (входят во все потенциальные ключи)
Атрибуты, встречающиеся только в правой части: 𝐸 (не входят в потенциальные ключи) 
Атрибуты, не вошедшие в первые 2 группы: 𝐴, 𝐵, 𝐶, 𝐷,
Так как первая группа пуста, то перебираем все подмножества из третьей группы, начиная с наименее мощных:
(𝐴)+ = {A} (𝐵)+ = {𝐵}
(𝐶)+ = {A,B,𝐶,𝐷,𝐸}
(𝐷)+ ={𝐵,𝐷}
(𝐴,𝐵)+ = {A,B,𝐶,𝐷,𝐸}
(𝐴,𝐷)+ = {A,B,𝐶,𝐷,𝐸}
(𝐵, 𝐷)+ = {B, 𝐷}
Остальные подмножества атрибутов будут содержать в себе потенциальный ключ, то есть сами не будут являться потенциальными ключами.
Потенциальные ключи: (𝐶), (𝐴, 𝐵), (𝐴, 𝐷)
  1. Дана переменная-отношение NADDR (NAME , STREET, CITY, STATE, ZIP), где каждому индексу соответствует только один город и штат, а каждой улице, городу и штату соответствует только один индекс. Найдите неприводимое множество функциональных зависимостей для NADDR. Какие потенциальные ключи существуют для NADDR?
NAME (N) , STREET (R), CITY (C), STATE (T) , ZIP (Z)
1. N -> RCT
2. RCT -> Z
3.Z -> CT

Эквивалентное неприводимое множество:
N -> R 
N -> C
N -> T
RCT -> Z
Z -> C
Z -> T
Атрибуты, встречающиеся только в левой части: N (входят во все потенциальные ключи) 
Атрибуты, встречающиеся только в правой части: − (не входят в потенциальные ключи) 
Атрибуты, не вошедшие в первые 2 группы: 𝑅, 𝐶, 𝑇, 𝑍
(𝑁)+ = {N,𝑅,𝐶,𝑇,𝑍}
Остальные подмножества атрибутов будут содержать в себе потенциальный ключ, то есть сами не будут являться потенциальными ключами.
Потенциальные ключи: (𝑁)
  1. Дано множество функциональных зависимостей S={A–>BC, B–>E, CD–>EF}, имеющих место для переменной-отношения R(A, B, C, D, E, F). Выполняется ли функциональная зависимость AD–>F для переменной-отношения R? Ответ пояснить.
1. A–>BC (дано)
2. A–>C (следует из п. 1 согласно правилу декомпозиции)
3. AD–>CD (следует из п. 2 согласно правилу дополнения)
4. CD–>EF (дано)
5. AD–> EF (следует из п. 3 и 4 согласно правилу транзитивности)
6. AD–> F (следует из п. 5 согласно правилу декомпозиции)
  1. Дано множество функциональных зависимостей S={A->B, CH->A, B->E, BD->C, EG->H, DE->F}, имеющих место для переменной-отношения R(A, B, C, D, E, F, G, H). Выполняются ли функциональные зависимости BFG–>AE, ACG– DH, CEG–>AB для переменной-отношения R? Ответ пояснить.
1. BFG–>AE???
Нет: {BFG}+ = BFGEH, которое содержит E, но не содержит A
2. ACG–>DH???
Нет: {ACG}+ = ACGBE, которое не содержит ни D ни H.
3. CEG–>AB???
Да: {CEG}+ = CEGHAB, которое содержит AB.
  1. Дана переменная-отношение R(A, B, C, D, E), для которой выполняется множество функциональных зависимостей S={AB–>DE, C–>E, D–>C, E–>A}. В результате декомпозиции получена переменная-отношение R1(A, B, C). Какие функциональные зависимости из S будут выполняться для R1? Ответ пояснить.
Необходимо вычислить замыкания всех подмножеств множества {A, B, C}, кроме пустого множества и ABC. Затем, не учитывая функциональные зависимости, которые являются тривиальными и те, которые имеют D или E в правой части, получим искомое множество.
A+ = A
B+ = B
C+ = CEA {C->E, E->A}
AB+ = ABDEC {AB->DE, D->C}
AC+ = ACE {C->E}
BC+ = BCEAD {C->E, E->A, AB->DE}
Не учитываем D и E.
Искомое множество функциональных зависимостей: {C->A, AB->C, BC->A}
(замечание: BC->A можно не учитывать, так как эта функциональная зависимость логически следует из C->A)
  1. Дана переменная-отношение R(A, B, C, D, E, F, G), для которой выполняется множество функциональных зависимостей S={AB–>C, CD–>E, EF–>G, FG–>E, DE–>C, BC–>A}. Будут ли группы атрибутов BDF, ACDF, ABDFG, BDFG потенциальными ключами для R? Ответ пояснить.
1. BDF ???
Нет: BDF+ = BDF
2. ACDF ???
Нет: ACDF+ = ACDFEG (Замыкание не включает B)
3. ABDFG ???
Нет: This choice is a superkey, but it has proper subsets that are also keys (e.g. BDFG+ = BDFGECA) 4. BDFG ???
BDFG+ = ABCDEFG
Check if any subset of BDFG is a key:
Since B, D, F never appear on the RHS of the FDs, they must form part of the key.
BDF+ = BDF <- Not key
So, BDFG is the minimal key, hence the candidate key
  1. Дана переменная-отношение R(A, B, C, D, E, F, G, H), для которой выполняется множество функциональных зависимостей S={CD–>A, EC–>H, GHB–>AB, C–>D, EG–>A, H–>B, BE–>CD, EC–>B}. Найти все потенциальные ключи для R.
Во-первых, мы замечаем что:
EFG никогда не появляются на RHS никакого FD. Так, EFG должен быть частью ЛЮБОГО ключа R Никогда не появляется на LHS никакого FD, но появляется на RHS некоторого FD. Так, A не часть НИКАКОГО ключа R
Мы теперь видим, является ли EFG самостоятельно ключом ...
EFG + = EFGA? R; Так, один только EFG не ключевой
Проверение добавления единственного признака с EFG (кроме A):
BEFG + = ABCDEFGH = R; это - ключ [BE>CD, EG>A, EC>H]
CEFG + = ABCDEFGH = R; это - ключ [[EG>A, EC>H, H>B, BE>CD]
DEFG + = ADEFG? R; это не ключ [EG>A]
EFGH + = ABCDEFGH = R; это - ключ [EG>A, H>B, BE>CD]
Если мы добавим дальнейший признак (и), то они сформируют суперключ. Поэтому, мы можем прекратить здесь искать возможный ключ (и).
Поэтому, возможные ключи: {BEFG, CEFG, EFGH}
  1. Дана переменная-отношение R(A, B, C, D, E, F, G), для которой выполняется множество функциональных зависимостей S={ABC–>DE, AB–>D, DE–>ABCF, E–>C}. Найти все потенциальные ключи для R.
Во-первых, мы замечаем что:
G никогда не появляется на RHS никакого FD. Так, G должен быть частью ЛЮБОГО ключа R.
F никогда не появляется на LHS никакого FD, но появляется на RHS некоторого FD. Так, F не часть НИКАКОГО ключа R
G+ = G? R Так, G один не ключ!
Теперь мы пытаемся найти ключи, добавляя больше признаков (кроме F) к G
Добавьте LHS FDs, у которых есть только один признак (E in E>C):
GE+ = GEC ? R
Добавьте LHS FDs, у которых есть два признака (AB в AB>D and DE in DE>ABCF):
GAB+ = GABD
GDE+ = ABCDEFG = R; [DE>ABCF] Это - ключ!
Добавьте LHS FDs, у которых есть три признака (ABC в ABC>DE), но не взятие супер набора GDE: GABC + = ABCDEFG = R; [ABC>DE, DE>ABCF] Это - ключ!
GABE + = ABCDEFG = R; [AB>D, DE>ABCF] Это - ключ!
Если мы добавим дальнейший признак (и), то они сформируют суперключ. Поэтому, мы можем остановиться здесь.
Возможный ключ (и) - {GDE, GABC, GABE}
  1. Дана переменная-отношение DB(PatNo, PatName, AppNo, Time, Doctor) с первичным ключом PK={PatNo, AppNo}, для которой выполняется множество функциональных зависимостей S={PatNo–>PatName, {PatNo, AppNo}–>{Time, Doctor}, Time–>AppNo}. Показать этапы преобразования переменной-отношения DB в BCNF.
1.1NF Устраняет повторяющиеся группы. 
Ничего:(None:?) DB(PatNo,PatName,AppNo,Time,Doctor)

2. 2NF Устраняют частичные ключевые зависимости DB(PatNo,AppNo,Time,Doctor)
R1 (PatNo, PatName)

3. 3NF Устраняют переходные зависимости
 Ничего:(None:?) таким образом, так же, как 2NF

4. BCNF Каждый детерминант является возможным ключом DB(PatNo,appNo,Time,Doctor)
R1 (PatNo, PatName)

- Пройдите весь determinates(определенный), где ВСЕ признаки левой руки присутствуют в отношении, 
и ПО КРАЙНЕЙ МЕРЕ ОДИН из правых признаков также присутствуют в отношении.

 - PatNo -> PatName

PatNo присутствует в DB, но не PatName, таким образом, не релевантный.
- PatNo, AppNo -> Time, Doctor
Весь подарок LHS, и время и доктор также представляет, настолько релевантный. 

Действительно ли это - возможный ключ? 
Patno, appNo ЯВЛЯЕТСЯ ключом, таким образом, это - возможный ключ. 
Таким образом это хорошо для соблюдения BCNF.
- Time -> AppNo
Время присутствует, и так является appNo, настолько релевантным. 
Это возможный ключ. 
Если бы это было тогда, то мы могли бы переписать DB как:
DB(PatNo, AppNo, Time, Doctor)
Это не будет работать, поскольку Вам требуются и время и в Patno вместе, чтобы сформировать уникальный ключ. 

Таким образом это определенное не является возможным ключом, 
и поэтому DB не находится в BCNF.
 Мы должны фиксировать это.

- BCNF: перепишите к
DB(PatNo, Time, Doctor) PK = {PatNo, Time} R1(PatNo, PatName) PK = PatNo
R2(Time, AppNo) PK = Time

Времени достаточно, чтобы решить число назначения пациента. 
Теперь BCNF удовлетворен, и заключительные показанные отношения находятся в BCNF.
  1. Дана переменная-отношение GradeReport(StudNo, StudName, (Major, Adviser, (CourseNo, Ctitle, InstrucName, InstructLocn, Grade))), для которой выполняется множество функциональных зависимостей S={StudNo–>StudName, CourseNo–>{Ctitle, InstrucName}, InstrucName–>InstrucLocn, {StudNo, CourseNo, Major}–>Grade, {StudNo, Major}–>Advisor, Advisor–>Major}. Показать этапы преобразования переменной-отношения GradeReport в BCNF.
1. Ненормализованный 
Grade_report(StudNo,StudName,(Major,Advisor,(CourseNo,Ctitle,InstrucName,InstructLocn,Grade)))
2. 1NF Удаляет повторяющиеся группы 
Student(StudNo,StudName)
StudMajor(StudNo,Major,Advisor)
StudCourse(StudNo,Major,CourseNo,Ctitle,InstrucName,InstructLocn,Grade) 
3. 2NF Удаляют частичные ключевые зависимости
Student(StudNo,StudName)
 StudMajor(StudNo,Major,Advisor) 
StudCourse(StudNo,Major,CourseNo,Grade) 
Course(CourseNo,Ctitle,InstrucName,InstructLocn)
4. 3NF Удаляют переходные зависимости 
Student(StudNo,StudName)
StudMajor(StudNo,Major,Advisor) 
StudCourse(StudNo,Major,CourseNo,Grade) 
Course(CourseNo,Ctitle,InstrucName)
 Instructor(InstructName,InstructLocn))
5. BCNF Каждый детерминант является возможным ключом
 Student : только детерминант - StudNo
StudCourse: только детерминант - StudNo,Major
StudCourse: только детерминант - CourseNo
Instructor: только детерминант - InstrucName 
StudMajor: детерминанты StudNo,Major, или Adviser
Только StudNo, Major является возможным ключом.
6. BCNF 
Student(StudNo,StudName)
StudCourse(StudNo,Major,CourseNo,Grade) 
Course(CourseNo,Ctitle,InstrucName) 
Instructor(InstructName,InstructLocn) 
StudMajor(StudNo,Advisor) 
Adviser(Adviser,Major)
  1. Дано множество функциональных зависимостей S={AB–>C, BC–>AD, D–>E, CF–>B}, имеющих место для переменной-отношения R(A, B, C, D, E, F). Выполняются ли функциональные зависимости AB–>D и D–>A для переменной-отношения R? Ответ пояснить.
Предположим, что мы хотим проверить ли AB -> D
следует из набора зависимостей.
Да! С тех пор D в {A, B, C, D, E} = {A, B} +.
Повторения:
X = {A, B} Использование: AB -> C
X = {A, B, C} Использование: BC -> AD
X = {A, B, C, D} Использование: D -> E
X = {A, B, C, D, E} больше изменений X не возможно так X = {A, B} +.
С другой стороны, рассмотрите тестирование FD: D -> A
Сначала вычислите {D} +. Первоначально мы имеем X = {D}. Тогда мы можем использовать данный D -> E, и X становится {D, E}. Но здесь мы застреваем, мы достигли закрытия.
Так {D} + = {D, E} и не в {D} +.
Завершая D -> A не следует из данного набора зависимостей.
  1. Дана переменная-отношение R(A, B, C, D), для которой выполняется множество функциональных зависимостей S={AB–>C, C–>D, D–>A}. Найти все потенциальные ключи для R.
Let R be a relational schema R(A, B, C, D). Simple set of FD = {AB -> C, C -> D, D -> A}. Aim to find all keys (minimal superkeys), Calculate singletons
A+, B+, C+, D+,
AB+, AC+, AD+, BC+, BD+, CD+
ABC+, ABD+, BCD+ ABCD+
1.Singletons A+ -> A
B+ -> B
C+ -> CDA D+ -> AD
2.Pairs (note commutative) AB+ -> ABCD
AC+ -> ACD AD+ -> AD BC+ -> ABCD BD+ -> ABCD CD+ -> ACD
3.Triples
ABC+ -> ABCD ABD+ -> ABCD BCD+ -> ABCD
4.Quadruples ABCD+ -> ABCD
Superkeys:
AB, BC, BD, ABC, ABD, BCD, ABCD Minimal superkeys (keys)
AB, BC, BD
  1. Найдите неприводимое покрытие множества функциональных зависимостей S={A–>BC, B–>C, A–>B, AB–>C}, заданных для переменной-отношения R(A, B, C, D, E, F).
Combine A -> BC and A -> B into A -> BC
Set is now {A -> BC, B -> C, AB -> C}
A is extraneous in AB -> C because of B -> C.
Set is now {A -> BC, B -> C}
C is extraneous in A -> BC because of A -> B and B -> C.
 The canonical cover is: A -> B, B -> C
  1. Дана переменная-отношение R(A, B, C, D, E), для которой выполняется множество функциональных зависимостей S={AB–>DE, C–>E, D–>C, E–>A}. В результате декомпозиции получена переменная-отношение R1(A, B, C). Какие функциональные зависимости будут выполняться для R1? Ответ пояснить.

R = {A, B, C, D, E}
F = {AB->DE, C->E, D->C, E->A}
S={A, B, C}
A+ = A
B+ = B
C+ = CEA [C->E, E->A]
AB+ = ABDEC [AB->DE, D->C]
AC+ = ACE [C->E]
BC+ = BCEAD [C->E, E->A, AB->DE]
We ignore D and E.
So, the FDs that hold in S are:
{C->A, AB->C, BC->A}
(Note: BC->A can be ignored because it follows logically from C->A)
Рассмотрите R = {A, B, C, D, E} с рядом FDs F = {AB->DE, C->E, D->C, E->A} И мы хотим спроектировать те FDs на отношение S = {A, B, C}
Дайте FDs, которые держатся в S
Намек:
Мы должны вычислить закрытие всех подмножеств {A, B, C}, кроме пустого набора и ABC. Затем мы игнорируем FD’s, которые тривиальны и те, у которых есть D или E на RHS
Решение
Вычисление F + для подотношения
R = {A, B, C, D, E}
F = {AB->DE, C->E, D->C, E->A}
S={A, B, C}
A+ = A
B+ = B
C+ = CEA [C->E, E->A]
AB+ = ABDEC [AB->DE, D->C]
AC+ = ACE [C->E]
BC+ = BCEAD [C->E, E->A, AB->DE]
Мы игнорируем D и E.
Так, FDs, которые держатся в S:
{C->A, AB->C, BC->A}
(Примечание: BC->A может быть проигнорирован, потому что он следует логически от C->A)
  1. Найдите неприводимое покрытие множества функциональных зависимостей S={AB–>D, B–>C, AE–>B, A–>D, D–>EF}, заданных для переменной-отношения R(A, B, C, D, E, F).

Используя алгоритм минимального покрытия, найдите минимальное покрытие
𝐹 = {𝐴𝐵→𝐷,𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸𝐹}
Шаг 1. Сделайте правые стороны атомными - 𝐺 = {𝐴𝐵 → 𝐷, 𝐵 → 𝐶, 𝐴𝐸 → 𝐵, 𝐴 → 𝐷, 𝐷 → 𝐸, 𝐷 → 𝐹}
Шаг 2. Удалите избыточные функциональные зависимости:
Для 𝐴𝐵 → 𝐷 вычисляют 𝐴𝐵+ исключая из 𝐺 зависимость 𝐴𝐵 → 𝐷
𝐴𝐵+ = ABCDEF
𝐷 входит в 𝐴𝐵+, поэтому удалите 𝐴𝐵 → 𝐷 из 𝐺
𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹}
Для 𝐵 → 𝐶 вычисляют 𝐵+ исключая из 𝐺 зависимость 𝐵 → 𝐶: 𝐵+ = 𝐵
𝐶 не входит в𝐵+ => 𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹}
Для 𝐴𝐸 → 𝐵 вычисляют 𝐴𝐸+ исключая из 𝐺 зависимость 𝐴𝐸 → 𝐵: 𝐴𝐸+ = 𝐴𝐸𝐷𝐹
𝐵 не входит в𝐴𝐸+ => 𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹} Для A→ 𝐷 вычисляют 𝐴+ исключая из 𝐺 зависимость 𝐴 → 𝐷: 𝐴+ = 𝐴
𝐷 не входит в𝐴+ => 𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹} Для D→ 𝐸 вычисляют 𝐷+ исключая из 𝐺 зависимость 𝐷 → 𝐸: 𝐷+ = 𝐷𝐹
𝐸 не входит в𝐷+ => 𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹}
Для D→ 𝐹 вычисляют 𝐷+ исключая из 𝐺 зависимость 𝐷 → 𝐹: 𝐷+ = 𝐷𝐸 𝐹невходит в𝐷+ => 𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹}
Шаг 3. Удалите все избыточные признаки с левой стороны ФЗ
𝐺 = {𝐵→𝐶,𝐴𝐸→𝐵,𝐴→𝐷,𝐷→𝐸,𝐷→𝐹}
Для 𝐴𝐸 → 𝐵
Для 𝐴: вычислите 𝐸+ исключив из 𝐺 𝐴𝐸 → 𝐵 и добавив 𝐸 → 𝐵
𝐸+ with {𝐵 → 𝐶, 𝐸 → 𝐵, 𝐴 → 𝐷, 𝐷 → 𝐸, 𝐷 → 𝐹} = 𝐸𝐵𝐶 => не содержит A, таким образом, А не избыточный атрибут в 𝐴𝐸 → 𝐵
Для 𝐸: вычислите 𝐴+ исключив из 𝐺 𝐴𝐸 → 𝐵 и добавив 𝐴 → 𝐵
𝐴+ with {𝐵 → 𝐶, 𝐴 → 𝐵, 𝐴 → 𝐷, 𝐷 → 𝐸, 𝐷 → 𝐹} = 𝐴𝐵𝐶𝐷𝐸𝐹 => содержит 𝐸, таким образом, 𝐸 избыточный атрибут в 𝐴𝐸 → 𝐵
Минимальное покрытие = {𝐵 → 𝐶,𝐴 → 𝐵,𝐴 → 𝐷,𝐷 → 𝐸,𝐷 → 𝐹}
  1. Дана переменная-отношение R(A, B, C, D, E, G, H, I), для которой выполняется множество функциональных зависимостей S={H–>GD, E–>D, HD–>CE, BD–>A}. Показать этапы преобразования переменной-отношения R в BCNF.

Consider R(ABCDEGHI) and the following set F of functional dependencies: H->GD, E->D, HD->CE, BD- >A
(a) Find a join loss-less, dependency preserving and 3NF decomposition of R.
(b) Indicate whether your database schema is in BCNF with respect to F. Explain. [10]
Solution:
(a) We first find a minimal cover of the FDs, as shown below. Right reduced Left Reduced Minimal Cover
H !G
H !D
E !D 
HD ! C 
HD ! E 
BD ! A
H !G
 H !D 
E !D 
H !C 
H !E 
BD ! A
H !G
 E !D 
H !C 
H !E 
BD ! A
Then construct a database D0(HGCE;ED;BDA).
Now, we need to check if D0 contains any candidate key.
Since no FD in the minimal cover above contains H, B, or I in its right side, any candidate key shall contain these three attributes.
Further, it is not dificult to check that HBI is indeed a candidate key. Therefore, HBI is the only candidate key of R, and shall be added to D0.
Hence,
D(HGCE;ED;BDA;HBI)
is a join loss-less, dependency preserving and 3NF decomposition of R.
(b) D is in BCNF since all the non-trivial FDs X ! A in held in any relation Ri 2 D, X is a key of Ri.
  1. Эквивалентны ли два множества функциональных зависимостей F={A->C, AC->D, E->AD, E->H} и G={A->CD, E->AH}, установленных для переменной-отношения R(A, С, D, E, H)?
Они эквивалентны. Пронумеруем функциональные зависимости из множества F следующим образом.
   1. A–>C
   2. AC–>D 
   3. E–>AD 
   4. E->H
Из строчки 3 следует: E->A, E->D.
Из строчек 1,2 следует: A->D (через A->AC в 1 строчке)
Т.к. E->A и E->H (4 строчка), то E->AH
Т.к. A->D и A->C (1 строчка), то A->CD
  1. Рассматривается универсальное отношение R=(A, B, C, D, E, F, G, H, I, J) и множество функциональных зависимостей F={AB->C, A->DE, B->F, F->GH, D->IJ}. Какие потенциальные ключи существуют для данного отношения? Декомпозируйте R в 2NF, а затем в 3NF.
1. AB->C
2. A->DE
3. B->F
4. F->GH
5. D->IJ

Из строчки 2 следует: A->D (=> (5) A->I, A->J), A->E.
Из строчек 3,4 следует: B->GH => B->G, B->H

1. AB->C
2. A->E
3. B->G
4. B->H
5. A->I
6. A->J
Потенциальные ключи: (A, B)
  1. Рассматривается универсальное отношение R=(A, B, C, D, E, F, G, H, I, J} и множество функциональных зависимостей F={AB->C, BD->EF, AD->GH, A->I, H->J}. Какие потенциальные ключи существуют для данного отношения? Декомпозируйте R в 2NF, а затем в 3NF.
1. AB->C
2. BD->EF
3. AD->GH
4. A->I
5. H->J

Из строчки 2: BD->E, BD->F
Из строчки 3: AD->G, AD->H (=> (5) AD->J

1. AB->C
2. BD->E
3. BD->F
4. AВ->G
5. AB->J

Первичные ключи:

  1. Найдите каноническое покрытие для множества функциональных зависимостей S={A->BC, B->C, AB->D, AC->D}, заданных для переменной-отношения R(A, B, C, D).

  2. Найдите каноническое покрытие для множества функциональных зависимостей S={A->B, ABCD->E, EF->GH, ACDF->EG}, заданных для переменной-отношения R(A, B, C, D, E, F, G, H).

  3. Рассматривается переменная-отношение R(A, B, C, D, E) и множество функциональных зависимостей F = {A->BC, BC->A, BCD->E, E->C}. Является ли множество F минимальным покрытием самого себя? Найдите 3NF декомпозицию переменной-отношения R и ответьте на вопрос: является ли эта декомпозиция одновременно и BCNF декомпозицией?

2017

  1. Найдите неприводимое покрытие множества функциональных зависимостей E={B->A, D->A, AB->D}, заданных для переменной-отношения R(A, B, C, D).
1. B->A
2. D->A
3. AB->D

Дополняем (2) до BD -> AB.
Из (3) BD->D => B->D.
Из (1) B->A  

Минимальное покрытие: E' = {B->D, D->A}

Конспект лекций

Clone this wiki locally