MÔ HÌnh quan hệ nguyên nhân ra đỜi của mô HÌnh quan hệ

Sửa bảng giá trị để nó thỏa AD Sửa b5,b14 thành a4

Sửa bảng giá trị để nó thỏa DEC sửa b2 thành a3  sửa tất cả b2 thành a3

A

B

C

D

E

A

B

C

D

E

Q1(AD)

a1

b1

b2

a4

b3

Q1(AD)

a1

b1

a3

a4

b3

Q2(AB)

a1

a2

b2

a4

b6

Q2(AB)

a1

a2

a3

a4

b6

Q3(BE)

b7

a2

b2

b9

a5

Q3(BE)

b7

a2

a3

b9

a5

Q4(CDE)

b10

b11

a3

a4

a5

Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1

b12

b2

a4

a5

Q5(AE)

a1

b12

a3

a4

a5

Sửa bảng giá trị để nó thỏa CEA Sửa b7,b10 thành a1.

Lần lượt xét lại các phụ thuộc hàm trong F, nếu bảng giá trị chưa thỏa phụ thuộc hàm nào thì tiếp tục làm cho nó thỏa. Sửa bảng giá trị để nó thỏa AD

A

B

C

D

E

A

B

C

D

E

Q1(AD)

a1

b1

a3

a4

b3

Q1(AD)

a1

b1

a3

a4

b3

Q2(AB)

a1

a2

a3

a4

b6

Q2(AB)

a1

a2

a3

a4

b6

Q3(BE)

a1

a2

a3

b9

a5

Q3(BE)

a1

a2

a3

a4

a5

Q4(CDE)

a1

b11

a3

a4

a5

Q4(CDE)

a1

b11

a3

a4

a5

Q5(AE)

a1

b12

a3

a4

a5

Q5(AE)

a1

b12

a3

a4

a5

Dòng thứ Q₃(BE) của bảng chứa toàn giá trị a_j (j=1..n) nên phép phân rã trên là bảo toàn thông tin.

2. 
   Định lý
   

Ta xây dựng một quan hệ r có các giá trị như bảng kết quả của thuật toán, các hàng là các bộ. Quan hệ r thỏa tập phụ thuộc F vì thuật toán đã sửa các giá trị của r để nó khỏi vi phạm các phụ thuộc hàm trong F  r là một quan hệ của lược đồ Q. Ta tách quan hệ r thành các quan hệ r_i với r_i = r.Q_i và dùng phép kết tự nhiên để kết chúng lại. Nếu:

• 
  k Q_k⁺Q_i⁺ =  i  r₁|><|r₂....|><|r_k không tồn tại  phép tách không bảo toàn thông tin.
  
• 
  i,k Q_i⁺Q_k⁺ = X_ik   mà mỗi r_i đều có một bộ t_i chứa toàn a  các t_i nối được với nhau vì có cùng giá trị trên X_ik  có một bộ tr₁|><|r₂....|><|r_k có toàn giá trị a, bộ này lại không có trong r  r  r₁|><|r₂....|><|r_k  phép tách không bảo toàn thông tin.
  

• 
  Bước 1: chứng minh nếu tr tr₁|><|r₂....|><|r_k. Suy ra rr₁|><|r₂....|><|r_k.
  

• 
  i,k Q_i⁺Q_k⁺ = X_ik    các t_i nối được với nhau vì có cùng giá trị trên X_ik  bộ tr₁|><|r₂....|><|r_k  r  r₁|><|r₂....|><|r_k.
  
• 
  k Q_k⁺Q_i⁺ =  i. Suy ra bảng kiểm tra bảo toàn thông tin ở giai đoạn chưa thỏa các phụ thuộc hàm, có dạng:
  

• 
  Bước 2: chứng minh nếu tr₁|><|r₂....|><|r_k tr. Suy ra r₁|><|r₂....|><|r_kr.
  

(1) và (2)  r = r₁|><|r₂....|><|r_n. Nói cách khác phép tách bảo toàn thông tin.

2. 
   Phép tách bảo toàn phụ thuộc hàm (decompositions that preserve dependencies)
   
   1. 
      Tập phụ thuộc hàm F_i của Q_i
      

• 
  r_i chỉ thỏa các phụ thuộc hàm XYF⁺ với XYQ_i⁺
  

Do r_i được tách từ r mà r thỏa F⁺  r_i thỏa các phụ thuộc hàm XYF⁺ với XYQ_i⁺.Theo định nghĩa phụ thuộc hàm, đương nhiên r_i không thỏa các phụ thuộc hàm XYF⁺ với XYQ_i⁺. Ngoài ra r_i không thỏa bất kỳ một phụ thuộc hàm nào XYF⁺ . Thật vậy nếu có XY như vậy thì r = r₁|><|r₂....|><|r_n cũng phải thỏa XYF⁺. Điều này mâu thuẫn với định nghĩa của tập F⁺ .

2. 
   Định nghĩa:
   

_Qi(F)=F_i⁺={ X  Y| X  Y  F⁺ và XY  Q_i}

Ta nói phân rã  bảo toàn tập phụ thuộc hàm F nếu

F   _Qi(F)  F⁺ = ( _Qi(F))⁺ với i=1..k