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



tải về 1.86 Mb.
trang11/17
Chuyển đổi dữ liệu17.08.2016
Kích1.86 Mb.
1   ...   7   8   9   10   11   12   13   14   ...   17

F  F1tt={ACDE,ACDB,ACDI,CEA,CED}

Mọi phụ thuộc hàm của F1tt đều có vế trái là siêu khóa  Q đạt dạng chuẩn BC



Ví dụ 8: Q(SV,MH,THAY)F = {SV,MH  THAY;THAY  MH}

Quan hệ trên đạt chuẩn 3 nhưng không đạt chuẩn BC..



Ví dụ 9:

Chẳng hạn cho Q(A,B,C,D) và F={AB  C; D  B; C  ABD}

thì Q là 3NF nhưng không là BCNF

Nếu F={B  D,A  C,C  ABD} là 2 NF nhưng không là 3 NF


Thuật toán kiểm tra dạng chuẩn của một lược đồ quan hệ.

Vào: lược đồ quan hệ Q, tập phụ thuộc hàm F

Ra: khẳng định Q đạt chuẩn gì?

Bước 1: Tìm tất cả khóa của Q

Bước 2: Kiểm tra chuẩn BC nếu đúng thì Q đạt chuẩn BC, kết thúc thuật toán

ngược lại qua bước 3

Bước 3: Kiểm tra chuẩn 3 nếu đúng thì Q đạt chuẩn 3, kết thúc thuật toán

ngược lại qua bước 4

Bước 4: Kiểm tra chuẩn 2 nếu đúng thì Q đạt chuẩn 2, kết thúc thuật toán.

ngược lại Q đạt chuẩn 1
Định nghĩa: Dạng chuẩn của một lược đồ cơ sở dữ liệu là dạng chuẩn thấp nhất trong các dạng chuẩn của các lược đồ quan hệ con.

    1. PHÉP TÁCH KẾT NỐI BẢO TOÀN

      1. Phép tách kết nối bảo toàn thông tin (lossless-join decomposition)

Cho lược đồ quan hệ Q(TENNCC,DIACHI,SANPHAM,DONGIA) có quan hệ tương ứng là r

Đặt r1 là quan hệ có được bằng cách chiếu r lên Q1(TENNCC,SANPHAM,DONGIA),

Đặt r2 là quan hệ có được bằng cách chiếu r lên Q2(TENNCC,DIACHI)

Đặt r’là quan hệ có được bằng cách kết tự nhiên giữa r1 và r2 qua TENNCC.



chẳng hạn:

r










TENNCC

DIACHI

SANPHAM

DONGIA

Hung

12 Nguyễn Kiệm

Gạch ống

200

Hung

12 Nguyễn Kiệm

Gạch thẻ

250

Hung

40 Nguyễn Oanh

Gạch ống

200




r2 = r.Q2+




r1 = r.Q1+

TENNCC

DIACHI




TENNCC

SANPHAM

DONGIA

Hung

12 Nguyễn Kiệm




Hung

Gạch ống

200

Hung

40 Nguyễn Oanh




Hung

Gạch thẻ

250




TENNCC

r’ = r1|><|r2

TENNCC

DIACHI

SANPHAM

DONGIA

Hung

12 Nguyễn Kiệm

Gạch ống

200

Hung

12 Nguyễn Kiệm

Gạch thẻ

250

Hung

40 Nguyễn Oanh

Gạch ống

200

Hung

40 Nguyễn Oanh

Gạch thẻ

250

Kết quả là r  r’ hay r  r.Q1|><|r.Q2.

Với kết quả trên, ta nói phép tách (Q1,Q2) tách Q thành Q1, Q2 là tách-kết nối (phân rã) mất mát thông tin.

Nếu r = r.Q1|><|r.Q2­­ ta nói phép tách (Q1,Q2) là tách-kết nối không mất mát thông tin (tách kết nối bảo toàn thông tin hay phân rã bảo toàn thông tin).

Vậy với điều kiện nào thì phép tách trở thành tách-kết nối không mất mát thông tin?



        1. Định nghĩa phép tách Q thành 2 lược đồ con

Q là lược đồ quan hệ, Q1, Q2 hai lược đồ con có:

Q1+ Q2+ = X

Q1+ Q2+ = Q+

Nói rằng lược đồ quan hệ Q được tách thành hai lược đồ con Q1, Q2 theo phép tách (Q1,Q2) là phép tách kết nối không mất (hay phép tách bảo toàn thông tin) nếu với r là quan hệ bất kỳ của Q ta có:

r = r.Q1r.Q2

Tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên các Q1,Q2



        1. Tính chất

Nếu Q là một lược đồ quan hệ, Q1,Q2­­­ là hai lược đồ quan hệ con có

Q1+  Q2+ = X

Q1+  Q2+ = Q+

X  Q+­

Thì r = r.Q1r.Q2

Chứng minh:

t r t r.Q1r.Q2­­

t  r  t1r1 t1 = t.Q1 t2r2 t2 = t.Q2 t1.X = t2.X = t.X

 t  r.Q1r.Q2­­ (Theo định nghĩa)

t r.Q1r.Q2­­ t r­­

t  r.Q1r.Q2­­  t1r1 t1 = t.Q1 (1)

mà t1  r1=r.Q1 nên theo định nghĩa phép chiếu ta lại có t’r t1 = t’.Q1 (2)

(1) và (2)  t’.Q1 = t.Q1  t’.X = t.X  t’.Q2 = t.Q2­­ (do X  Q2­­)

 t’ = t  t  r

Ví dụ 10: cho Q(SAIP), Q1 =(SA) , Q2 =(SIP) F={SA,SIP}. Hỏi việc tách Q thành Q1 và Q2 có gây ra mất mát thông tin không?

Áp dụng tính chất trên, ta có

Q1+  Q2+ = S

Q1+  Q2+ = SAIP = Q+

S  SA = Q1+ ­­

Theo tính chất trên, với mọi quan hệ r của Q ta luôn có r = r.Q1r.Q2. Suy ra phép tách trên là phép tách kết nối bảo toàn thông tin.



        1. Phép tách Q thành n lược đồ con

Q là một lược đồ quan hệ, F là tập phụ thuộc hàm. Q được tách thành các lược đồ con Q1, Q2, Q3...,Qn theo từng bước mà ở mỗi bước một lược đồ được tách thành hai lược đồ con và thỏa mãn điều kiện của tính chất bảo toàn thông tin thì với r là quan hệ bất kỳ của Q ta luôn có:

r = r.Q1|><|r.Q2|><|r.Q3..... |><|r.Qn

Chứng minh:

Ta chứng minh bằng phương pháp qui nạp.

Ở bước i = 1 thì r = r.Q1|><|r.Q1m đúng theo định lý bảo toàn thông tin

Giả sử biểu thức trên đúng ở bước i = k nghĩa là ta có:

r = r.Q1|><|r.Q2|><|r.Q3..... |><|r.Qk |><|r.Qkm (1)

ta phải chứng minh r = r.Q1|><|r.Q2|><|r.Q3.....|><|r.Qk|><|r.Qk+1|><|r.Qk+1m

Với Qkm được tách thành hai lược đồ con Qk+1 và Qk+1m theo đúng điều kiện của tính chất bảo toàn thông tin nghĩa nếu s là quan hệ của Qkm thì s = s.Qk+1|><|s.Qk+1m

r.Qkm = (r.Qkm).Qk+1|><|(r.Qkm).Qk+1m = r.Qk+1|><|r.Qk+1m

r = r.Q1|><|r.Q2|><|r.Q3.....|><|r.Qk|><|r.Qk+1|><|r.Qk+1m


        1. Thuật toán kiểm tra phép tách kết nối bảo toàn thông tin

          1. Thuật toán

Dữ liệu vào: lược đồ quan hệ Q(A1,A2,…An), tập phụ thuộc hàm F, phép tách =(Q1,Q2,…,Qk).

Dữ liệu ra: kết luận phép tách  có phải là phép tách bảo toàn thông tin ?


  1. Thiết lập bảng với k+1 dòng, n+1 cột . Cột j ứng với thuộc tính Aj (j=1...n), hàng i ứng với lược đồ quan hệ Qi(i=1…k). Tại ví trí hàng i, cột j ta điền ký hiệu Aj nếu Aj  Qi, nếu không ta đặt ký hiệu bt vào vị trí đó. (với t đầu tiên bằng 1) và sau đó tăng t lên một đơn vị.

  2. Xét lần lượt các phụ thuộc hàm trong F, áp dụng cho bảng vừa mới thành lập ở trên. Giả sử xét (X  Y)  F, chúng ta tìm những hàng giống nhau ở tất cả các thuộc tính của X, nếu thấy những hàng như vậy ta sẽ làm cho các ký hiệu của hai hàng này bằng nhau ở tất cả các thuộc tính của Y. Khi làm cho 2 ký hiệu này bằng nhau, nếu một trong hai ký hiệu là aj thì cho ký hiệu kia trở thành aj, nếu hai ký hiệu là bk hoặc bl thì có thể cho chúng trở thành bt hoặc bt (với t = min (k,l)). Bước này được tiếp tục cho các phụ thuộc hàm còn lại của F cho đến khi không còn áp dụng được nữa.

  3. Xét bảng kết quả, nếu thấy trong bảng này có một hàng chứa toàn aj (i=1..n) thì kết luận đó là phép kết nối bảo toàn thông tin, ngược lại là phép kết nối mất mát thông tin.


Chú ý: một điều quan trọng cần phải nhớ là khi cho hai ký hiệu bằng nhau thì phải cho bằng nhau ở tất cả các xuất hiện của chúng trong bảng chứ không phải chỉ cho bằng nhau ở những ký hiệu trong phạm vi các phụ thuộc X  Y  F.
Ví dụ 11: Với Q(ABCDE)

Q1 = (AD),Q2 =(AB), Q3 =(BE), Q4 =(CDE), Q5 =(AE)

F = {AC,BC,AD,DEC,CEA}

Kiểm tra tính bảo toàn thông tin của phép phân rã Q thành Q1,Q2,Q3,Q4,Q5.




Bước 1:

a1

a2

a3

a4

a5




Bước 2:

Điền b1,b2,b3, ...




A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1







a4







Q1(AD)

a1

b1

b2

a4

b3

Q2(AB)

a1

a2













Q2(AB)

a1

a2

b4

b5

b6

Q3(BE)




a2







a5




Q3(BE)

b7

a2

b8

b9

a5

Q4(CDE)







a3

a4

a5




Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1










a5




Q5(AE)

a1

b12

b13

b14

a5




Sửa bảng giá trị để nó thỏa AC

Sửa b4,b13 thành b2






Sửa bảng giá trị để nó thỏa BC

Sửa b8 thành b2






A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1

b1

b2

a4

b3




Q1(AD)

a1

b1

b2

a4

b3

Q2(AB)

a1

a2

b2

b5

b6




Q2(AB)

a1

a2

b2

b5

b6

Q3(BE)

b7

a2

b8

b9

a5




Q3(BE)

b7

a2

b2

b9

a5

Q4(CDE)

b10

b11

a3

a4

a5




Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1

b12

b2

b14

a5




Q5(AE)

a1

b12

b2

b14

a5
1   ...   7   8   9   10   11   12   13   14   ...   17


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương