In this tutorial we review Chapter 07.

Question 01

Suppose that we decompose the schema r (A, B, C, D, E) into

R1 (A, B, C)
R2 (A, D, E)

Show that this decomposition is a lossless decomposition if the following set F of functional dependencies holds:

A → BC
CD → E
B → D
E → A

Answer

  1. From F = {
  2.     A - BC        => A-B, A-C
  3.   CD - E        =>    CD - E
  4.   B - D            => A-B-D => A-D
  5.                       => A-E
  6.   E - A
  7. }
  9. A - A,B,C,D,E ( A is candidate key )

:::success Show the decomposition is lossless decomposition
Ans:
A decomposition (R1, R2) is a lossless-join decomposition if

  • R1 ∩ R2 ⇒ R1 or
  • R1 ∩ R2 ⇒ R2.

Let

  • R1 = (A, B, C),
  • R2 = (A, D, E), and
  • R1 ∩ R2 = A.

We need to check if A is a candidate key.
Starting with A > BC, we can conclude: A > B, A > C
A+ = {A, B, C}
Since A > B and B > D => A > D (Decomposition, Transitive)
A+ = {A, B, C, D}
Since A > C and A > D => A > CD (Union, Decomposition)
Since A > CD and CD > E => A > E ( Decomposition, Transitive)
A+ = {A, B, C, D, E}
Since A is a candidate key.

Therefore R1 ∩ R2 ⇒ R1 :::

Knowledge Content

Lossless decomposition 無損分解

如果 R1 ∩ R2 是 R1 或 R2 的超码(Superkey)，则R上的分解（R1，R2）是无损分解。
这是一个充分条件，当所有的约束都是函数依赖时它才是必要条件
（例如多值依赖就是一种非函数依赖的约束），不过这已经足够了。

Lossy decomposition 有損分解

有损分解的举例
employee (ID,name)
employee2 (name,salary,city)
很明显，如果有两个人同名，则合并时无法判断其ID,丢失了信息，因此是有损分解

Dependency 保持依賴

如果 F 上的每一个函数依赖都在其分解后的某一个关系上成立，
则这个分解是保持依赖的（这是一个充分条件）。

Example

设关系模式 R<U, F>其中 U=｛A, B, C, D, E｝，F＝{A → BC，C → D，BC → E，E → A｝，则分解
ρ={R1（ABCE），R2（CD）｝满足 （__） 。
A．具有无损连接性、保持函数依赖
B．不具有无损连接性、保持函数依赖
C．具有无损连接性、不保持函数依赖
D．不具有无损连接性、不保持函数依赖

先做无损链接的判断。R1 ∩ R2={C}，计算C+。
Result = C
由于 C→D，C ∈ result，所以result = result ∪ D = CD
C+ = {C, D}
可见C是R2的超码，该分解是一个无损分解 Lossless Decomposition。
再做保持依赖的判断。
A → BC，BC → E， E → A 都在R1上成立（也就是说每一个函数依赖左右两边的属性都在R1中），
C → D 在R2上成立，因此给分解是保持依赖的。

选A。