Pth Va Tach Qh

Bài tập Phụ thuộc hàm và phép tách lược đồ quan hệ

Bài1 • Cho lược đồ quan hệ R={A,B,C,D} và tập phụ thuộc hàm:F= {A->B, BC->D, C->A} . Phụ thuộc hàm nào sau đây được suy diễn từ F • C->D , AC->D AD->C BC->A B->CD

• Phụ thuộc hàm X->Y được gọi là suy diễn từ F khi 1 quan hệ R thoả mãn tất cả các phụ thuộc hàm trong f thì r cũng thoả mãn X->Y • Các qui tắc suy diễn chính: • luật px: • luật thêm vào: • luật bắc cầu:

• +> có A->B • mà BC->D nên AC->B • ( luật giả bắc cầu) • +> có C->A nên BC->A ( luật thêm vào)

Bài 2 • Cho lược đồ quan hệ R= {A,B,C,D,E,G,H} và tập F={AB->C,B->D,CD->E,CE->GH, G->A} • Chứng minh : AB->E, AB->G • LG: • AB->C • B->D  AB->CD (luật hợp) • CD->E •  AB->E (luật bắc cầu)

• Như chứng minh trên có : • AB->E • mà AB->C  AB->CE (luật hợp) • CE->GH •  AB->GH (luật bắc cầu)

Bài 3 • Cho lược đồ quan hệ R ={A,B,C,D,E,G,H} và tập F= {A->D, AB->DE,CE->G, E->H} • Tính (AB)+

Bao đóng của một tập thuộc tính • Định nghĩa: bao đóng của một tập thuộc tính: • X+ = ∪ Ai với X->Ai là phụ thuộc hàm suy diễn từ F nhờ hệ tiên đề amstrong • Thuật toán: • B1 đặt Xo=X • B2 lần lượt xét các phụ thuộc hàm trong F • nếu Y->Z thoả mãn Y Xi thì Xi=Xi ∪Z • B3 nếu b2 không tính được nữa thì Xi là bao đóng. Ngược lại làm b2

• +> đặt Xo= AB • có A->D mà A AB nên X1= ABD • có AB->DE mà AB ABD nên X2=ABDE • E->H mà E ABDE nên • X3= ABDEH • Kết thúc : (AB)+=ABDEH

Bài toán thành viên • Mđích: xác định xem 1 phụ thuộc hàm X->Y có là thành viên của F không( tức là xem X>Y có thuộc F+ hay không) • Thuật toán xác định: • B1 : tính X+(F) • B2 : nếu Y(con) của F+ thì X->Y là thành viên của F ngược lại thì không • (X->Y thuộc F+ khi và chỉ khi Y là con của X+(F))

Bài 4 • Cho lược đồ quan hệ : R ={A,B,C,D,E,G} và tập F= {AB->C, C->A, BC->D, ACD-.B, D->EG, BE->C, CG->BD, CE->AG} • tìm phủ tối thiểu của tập phụ thuộc hàm

• Thuật toán tìm phủ tối thiểu: • B1: loại bỏ các thuộc tính dư thừa ở vế trái các phụ thuộc hàm : +>xét lần lượt các phụ thuộc hàm X->Y trong F • +> với mọi tập con thực sự X’ của X nếu X’->Y thì thay X->Y bởi X’->Y • B2: tách các phụ thuộc hàm thành pthàm có vế phải 1 thuộc tinh

• B3 : loại bỏ các phụ thuộc hàm dư thừa: • +> lần lượt xét các phụ thuộc hàmX->Y • +> tính X+(F-(X->Y)) • +> nếu Y con X+ thì loại được X->Y ngược lại thì không • (bước này sử dụng bài toán thành viên)

B1 : loại bỏ các thuộc tính dư thừa ở vế trái các phụ thuộc hàm • +> với những phụ thuộc hàm có vế trái 1 thuộc tính ta không xét • +>lần lượt xét với các phụ thuộc hàm còn lại • Vd: xét AB->C : có (A)+(F)=A ,(B)+(F)=B  AB>C không dư thừa • xét BC->D: có (B)+(F)=B, (C)+(F) = C  BC>D không dư thừa • Tương tự làm xét hết các phụ thuộc hàm còn lại : cuối cùng ta được không có phụ thuộc hàm nào có vế trái dư thừa

B2 : tách thành vế phải một thuộc tính • F={AB->C, C->A, BC->D, ACD-.B, D->EG, BE->C, CG->BD, CE->AG} • Tách được: • F1={AB->C, C->A, BC->D,ACD-.B, D->E, D->G, BE-> C, CG-> B, CG->D , CE->A, CE->G}

B3 : loại bỏ phụ thuộc hàm dư thừa • • • • • • • •

+>xét AB->C có : F1=F- {AB->C} (AB)+(F1)=AB không loại BC->C +> xét C->A có : F2=F- {C->A} (C)+(F2)=C  không loại C->A +> xét BC->D có: F3=F-{BC->D} (BC)+(F3)=ABC  không loại BC->D +> xét ACD->B có F4=F- {ACD->B} (ACD)+(F4)=ACDEGB  loại ACD->B

• • • • • • • • •

+>xét CG->B có F5=F4-{CG->B} ( CG)+(F5)=CGADBE  loại CG->B +> xét CG->D có F6=F5- {CG->D} (CG)+(F6)=CGA không loại CG->D +> xét CE->A có F7=F6-{CE->A} (CE)+(F7)=CEAG loại CE->A +> xét CE->G có F8=F7-{CE->G} (CE)+(F8)=CEA  không loại CE->G Tương tự ta không loại các phụ thuộc hàm: D->E , D->G, BE->C

• Kết luận : vậy phủ tối thiểu là tập các phụ thuộc hàm không loại bỏ • Ftt={AB->C, C->A, BC->D, D->E, D->G, BE-> C, CG->D ,CE->G}

Bài 5 • Cho lược đồ quan hệ R ={S,I,D,M} và tập F= {SI->D,SD->M,D->M} • tìm tất cả các khoá của R • Tìm phủ tối thiểu của F

Thuật toán tìm khoá ldqh • Thuật toán tìm khoá (tất cả các khoá)

Tìm tất cả các khoá của R Có F={ SI → DM, SD → M,D → M TN=( S,I) TG=(D)

Xi

D

Xi TN

(Xi TN)+

SK

K

SI

SIDM

SI

SI

SID

SIDM

SID

Tìm phủ tối thiểu của F b1) Loại bỏ các thuộc tính dư thừa (D → M) có vế trái 1 tt nên không dư thừa (SI → DM) không dư thừa (vì SI là khoá) (SD → M) dư thừa vì: (D → SD) và (D → M) ⇒ SD → M dư thừa S Vậy F1 ={ SI → DM, D → M}

b2) Tách các phụ thuộc hàm có vế phải hơn một thuộc tính thành vế phải 1 thuộc tính: F1 = { SI → DM, D → M} F2 = { SI → D, SI → M, D → M}

b3) loại bỏ các phụ thuộc hàm dư thừa: Xét SI → D: F2’= { SI → M, D → M} Có SI+ F2’ = (SIM) D+F2 = (SIM) Nên không thể loại bỏ SI → D khỏi F2

b3) loại bỏ các phụ thuộc hàm dư thừa: Xét SI → D: Có

F2’= { SI → M, D → M} SI+ F2’ = (SIM)

Nên không thể loại bỏ SI → D khỏi F2

Xét (SI → M) có

F3’= { SI → D, D → M} SI+ (F3’) = {SIDM}

Vậy có thể loại được (SI → M) khỏi F2 Khi đó F2 ={ SI → D, D → M}

Tương tự xét (D → M) ta có F4’ = F2\ {D → M}= { SI → D} có

D+ (F4’) = {D}

vậy không thể loại bỏ (D → M) Kết luận: phủ tối thiểu của F là: Ftt = {SI → D, D → M}

các dạng chuẩn của R • +>chuẩn 1: toàn bộ các thuộc tính của mọi bộ đều mang giá trị đơn • +> chuẩn 2: là dạng chuẩn 1 và mọi thuộc tính không khoá đều phụ thuộc hoàn toàn vào khoá • +> chuẩn 3: mọi X->A thuộc F+ với Akhông thuộc X thì đều có hoặc X là siêu khoá hoặc A là thuộc tính khoá • +> chuẩn BC: mọi X->A thuộc F+ với Akhông thuộc X thì đều có hoặc X là siêu khoá

Thuật toán xác định chuẩn của R • B1: tìm tất cả các khoá của R • B2: kiểm tra chuẩn bc nếu đúng thì R đạt chuẩn BC ngược lại thì qua bước 3 • B3: kiểm tra chuẩn 3 nếu đúng thì R đạt chuẩn 3 ngược lại thì qua bước 4 • B4: kiểm tra chuẩn 2 nếu đúng thì R đạt chuẩn 2 ngược lại thì R đạt chuẩn 1 • Dạng chuẩn của một lược đồ quan hệ là dạng chuẩn thấp nhất trong các dạng chuẩn của các ldqh con

Xác định chuẩn cao nhất của R Lược đồ quan hệ R {S,I,D,M} F={ SI → DM, SD → M, D → M} khoá {SI} Xét (SD → M) và (D → M) có SD, D không là siêu khoá ⇒ không đạt chuẩn BC (SD → M) và (D → M) có M không phải tt khoá ⇒ không đạt chuẩn 3 Có (SI → DM) nên mọi thuộc tính không khoá đều phụ thuộc đầy đủ vào khoá SI ⇒ R đạt chuẩn 2

Phân rã R thành các lược đồ chuẩn 3 bảo toàn dữ liệu và phụ thuộc hàm

Thuật toán • Tìm phủ tối thiểu của tập phụ thuộc hàm F • Nếu có một phụ thuộc hàm nào đó của phủ tối thiểu liên quan đến tất cả các thuộc tính của R thì phép tách chính là R luôn • Nếu có những thuộc tính không xuất hiên cả 2 phía các pth thì chúng tạo thành 1 lược đồ con cần tìm • Ngược lại cứ mỗi phụ thuộc hàm X->A sẽ tạo ra 1 lược đồ quan hệ con cần tìm • Nếu 1 lược đồ con chứa khoá K của R thì kết thúc thuật toán . Ngược lại thì tạo ra 1 ldqh con K của R

F = { SI → D,SI → M,SD → M, D → M} Khoá lược đồ quan hệ K={SI} Ta có Ftt = {SI → D, D → M} Tách R thành 2 lược đồ con: R1 {SID} R2 {DM} Nhận thấy R1 chứa khoá {SI} nên R1, R2 là kết quả của phân rã thành chuẩn 3 bảo toàn phụ thuộc hàm và dữ liệu

Phân rã R thành chuẩn BC bảo toàn thông tin

Thuật toán • Ý tưởng: tách các phụ thuộc hàm làm cho R không đạt chuẩn BC ra thành 1 ldqh con • Thuật toán: • B1 :Đặt S=R • B2: nếu S là lược đồ trong phép tách và chưa đạt chuẩn BC (tồn tại X->A thuộc F+ và A không thuộc X mà X khônglà siêu khoá): • +> chọn X->A và nhận XhợpAlà 1 lược đồ con trong kết quả tách • +>chuyển sang bước 3 • B3: xét phần còn lại S=S- { A } lặp lại bước 2

• Khoá lược đồ quan hệ: k=(SI) • F= { SI → D,SD → M, D → M} • Nhận thấy : SD->M có SD không là siêu khoá nên SD->M làm cho R không đạt chuẩn BC nên tách thành 2 lược đồ con: • R1={ S,D,M} • R2={ S,I,D}

• Ta đi tìm tập F1,K1 của R1 và F2,K2 của R2: với R1: F1={ SD->M} K1=(SD) Với R2: có: I+=I, ID+=IDM S+=S, SID+=SIDM D+=DM, (SI)+(F)=SIDM SD+=SDM  F2= { SI->D} khoá K2= (SI)

• • • • •

Kết luận : R được tách thành 2 lược đồ con đạt chuẩn BC R1= (S,D,M) R2= (SID) F1= { SD->M } F2= { SI->D } K1= (SD) K2=(SI)

• Cũng có thể tách như sau( nếu xét D->M trước): • R1= { D,M } R2= { S,I,D } • F1= { D->M } F2= { SI->D } • K1= (D) K2=(SI)

Kiểm tra phép tách R thành R1(SID) va R2(SIM) có bảo toàn thông tin hay không?

• Thuật toán1:(dùng bảng) • Thuật toán 2:phép tách D tách R thành R1 và R2 là bảo toàn thông tin khi va chi khi • R1 giao R2->(R1\R2) • Hoặc R1 giao R2->(R2\R1)

Phân rã R thành R1=(SID) , R2=(SIM) Hỏi có bảo toàn thông tin không? phương pháp dung bảng kiểm tra

a1 S

a2 I

a3 D

a4 M

R1

a1

a2

a3

b1

R2

a1

a2

b2

a4

Sửa bảng để thoả mãn (SI → D) Chuyển b2 thành a3 ở cột D

a1

a2

a3

a4

S

I

D

M

R1

a1

a2

a3

b1

R2

a1

a2

a3

a4

Sửa bảng để thoả mãn (SI → M) Chuyển b1 thành a4 ở cột M

R1 R2

a1

a2

a3

a4

S a1 a1

I a2 a2

D a3 a3

M a4 a4

Nhận thấy ngay các phụ thuộc hàm (SD → M, D → M) cũng đã được thoả mãn Trên bảng thấy có 2 hàng đều chứa các giá trị {Ai} Vậy phép phân rã trên thoả mản bảo toàn dữ liệu

• Phương pháp dùng mệnh đề tương đương: • Có R1=(SID) R2=(SIM) • R1 giao R2= { SI} • R1\R2 = { D} • Mà SI->D (do SI là khoá của R) • =phép tách trên là bảo toàn thông tin

Phân rã R thành R1=(SID) , R2=(SIM) Hỏi có bảo toàn phụ thuộc hàm không?

Thuật toán • Ta đi xét xem mỗi phụ thuộc hàm trong F có phải là thành viên của bao đóng của hợp các hình chiếu của F lên các lược đồ quan hệ con • B1: xác định hình chiếu của F lên các lược đồ quan hệ con • B2: xác định hợp của các hinh chiếu đó(Fh) • B2: lần lượt xét các phụ thuộc hàm trong F nếu mọi phụ thuộc hàm đều là thành viên của Fh thì kết luận là phép tách bảo toàn phụ thuộc hàm ngược lại thì không bảo toàn phụ thuộc hàm

B1:xác định các hình chiếu của F • • • • • • • •

Tìm hình chiếu của F lên R1: S+=S I+=I D+=DM SI+=SIDM SD+=SDM ID+=IDM SID+=SIDM  F1= { SI->D} Tương tự tìm hình chiếu của F lên R2 F2= { SI->M}

B2 : kiểm tra các fd của F • • • • • •

Gọi G= ( F1 F2)+ Xét xem các fd trong F có được bảo toàn ? +> có D+(G)=D  không có D->M +> có SD+(G)=SD  không có SD->M (chỉ cần chỉ ra 1 trong 2 ý trên ) kết luận : phép tách trên không bảo toàn phụ thuộc hàm