Bài tập phụ tối thiểu có lời giải

bài tập về phụ thuộc hàm có lời giải-Nguyễn Công Trình

Nội dung chính Show

+ Loại bỏ những thuộc tính dư thừa bên trái
+ Loại bỏ những PTH dư thừa
Kết luận: phủ tối thiểu của tập phụ thuộc hàm F trong quan hệ R là

Hệ quản lý bán hàng có cơ sở dữ liệu quan hệ với tập thuộc tính U và tập phụ thuộc hàm F.

+U = {Số đơn hàng, ngày cung cấp, người cung cấp, địa chỉ người cung cấp, ngày đặt hàng, mã hàng, số lượng, tên hàng, đơn vị tính, đơn giá}

F = {Số đơn hàng ==>(ngày cung cấp, người cung cấp, địa chỉ người cung cấp, ngày đặt hàng), (Số đơn hàng,mã hàng) ==> (tên hàng, đơn vị tính, đơn giá, số lượng), ngày cung cấp ==>(người cung cấp, địa chỉ người cung cấp), mã hàng ==>(tên hàng, đơn vị tính, đơn giá)}.

Tập phụ thuộc hàm F đã phủ tối thiểu chưa ? Vì sao? Nếu chưa tìm một phủ tối thiểu của tập phụ thuộc hàm F trong quan hệ R ?

nguyen cong trinh -Nguyễn Công Trình-nguyễn công trình

GIẢI :

Tập phụ thuộc hàm F chưa tối thiểu vì tồn tại PTH Số đơn hàng ==>(ngày cung cấp, người cung cấp, địa chỉ người cung cấp, ngày đặt hàng) có vế phải gồm 4 thuộc tính

Đặt các thuộc tính của U tương ứng như sau:

Số đơn hàng =A, ngày cung cấp = B, người cung cấp = C, địa chỉ người cung cấp = D,

ngày đặt hàng = E, mã hàng=F, số lượng=G, tên hàng= H, đơn vị tính = I, đơn giá=K

Khi đó F={A==>BCDE ; AF==>HIKG ; B ==> CD;F==>HIK}

+ Tách vế phải của các PTH thành các thuộc tính đơn

F1={A==>B ;A==>C ;A==>D ;A==>E ;AF==>H ; AF==>I ; AF==>K ; AF==>G ; B ==>C ; B ==>D ; F==>H ; F==>I ; F==>K}

+ Loại bỏ những thuộc tính dư thừa bên trái

Xét PTH AF==>H

A+= ABCDE không chứa F nên F không dư thừa

F+= FHIK không chứa A nên A không dư thừa

Xét PTH AF==>I

A+= ABCDE không chứa F nên F không dư thừa

F+=FHIK không chứa A nên A không dư thừa

Xét PTH AF==>K

A+= ABCDE không chứa F nên Fkhông dư thừa

F+=FHIK không chứa A nên Akhông dư thừa

Xét PTH (A,F)àG

A+= ABCDE không chứa F nên F không dư thừa

F+=FHIK không chứa A nên A không dư thừa

Như vậy ta có:

F2={A==>B ;A==>C ;A==>D ;A==>E ;AF==>H ; AF==>I ; AF==>K ; AF==>G ; B ==>C ; B ==>D ; F==>H ; F==>I ; F==>K}

nguyen cong trinh -Nguyễn Công Trình-nguyễn công trình

+ Loại bỏ những PTH dư thừa

Xét các PTH sau :

AF==>H dư thừa vì có {AF}+ = ABCDEFGHIK chứa H

AF==>I dư thừa vì có {AF}+ = ABCDEFGHIK chứa I

AF==>K dư thừa vì có {AF}+ = ABCDEFGHIK chứa K

A==>C dư thừa vì có A+= ABCDE chứa C

A==>D dư thừa vì có A+= ABCDE chứa D

Như vậy ta có F3={A==>B ; A==>E ; AF==>G ; B ==>C ; B ==>D ;F==>H ; F==>I ; F==>K} (1 điểm)

Kết luận: phủ tối thiểu của tập phụ thuộc hàm F trong quan hệ R là

F=F3={A==>B ; A==>E ; AF==>G ; B ==>C ; B ==>D ;F==>H ; F==>I ; F==>K}

Hay F = {Số đơn hàng ==>ngày cung cấp; Số đơn hàng ==>ngày đặt hàng ;(Số đơn hàng, mã hàng) à==>số lượng ; ngày cung cấp ==>người cung cấp; ngày cung cấp ==>địa chỉ người cung cấp ; mã hàng ==>tên hàng ; mã hàng ==> đơn vị tính ; mã hàng ==>đơn giá }

sách hay-nguyen cong trinh Nguyễn Công Trình sưu tầm

Liên hệ :

++facebook của tôi : http://bit.ly/2gbTWGk

+++blog : http://bit.ly/2iEwW3Y

++ pinterest của tôi : http://bit.ly/2yXVriG

+++kênh học tập : http://bit.ly/2zM0S1v

++ instagram của tôi : http://bit.ly/2iFqGsW

+++ Tumblr : http://bit.ly/2zUrIp3

++ reddit : http://bit.ly/2zKuA7h

+++ google+ : http://bit.ly/2iCRIkz

736 KB

140

Nhấn vào bên dưới để tải tài liệu

Để tải xuống xem đầy đủ hãy nhấn vào bên trên

1 Phủ tối thiểu – Minimal cover 2  Phủ tối thiểu Fc của F là tập FD nhỏ nhất sao cho 𝐅 + = 𝑭+ 𝒄  Minimal Cover for a given set of FDs is not unique. Phủ tối thiểu – Minimal cover  3 Tập phụ thuộc hàm Fc được gọi là tối thiểu (minimal) nếu thỏa mãn các tính chất sau: Vế phải của mọi FD đều là thuộc tính đơn  Nếu giảm bất kỳ thuộc tính nào bên vế trái của mỗi FD, tập phụ thuộc mới sẽ không tương đương với phụ thuộc hàm ban đầu.  Không thể loại bỏ bất kỳ FD nào khỏi Fc vẫn được tập phụ thuộc hàm tương đương với tập Fc ban đầu.  Giải thuật tìm phủ tối thiểu 4 Input: tập phụ thuộc hàm F  Output: Fc là 1 phủ tối thiểu của F 1. Fc:=F 2. Biến đổi tất cả FD thành thuộc tính đơn bên phía phải 3. for each X A in Fc  For each attribute B that is an element of X  If { {Fc- {XA}} U { (X- {B}) A }}  Fc then replace X A with (X-{B})  A in Fc  4. For each X A in Fc if {Fc- {XA}}  Fc then remove X A from Fc Return Fc Ví dụ    5 Cho F={ BA, DA, AB D}. Tìm phủ tối thiểu của F Bước 2: tất cả FD đều có vế phải là thuộc tính đơn Bước 3:  Với ABD có thuộc tính dư thừa vế trái không? Có thể thay thế bởi AD hay BD F’= (F – {ABD})  {AD} = ={ BA, DA, B D}.  Cần chứng minh F  F’ B A ⟹ B AB  Từ F ta có ⟹ B  D  F  F’ AB  D  Từ F’ ta có B  D  AB  D  F’  F  Kết luận A là thuộc tính dư thừa của AB D  F’ ={ BA, DA, B  D}   F  F’ Ví dụ   Bước 4:  F’= { BA, DA, B  D}  Vì B  D và DA  BA. FD BA là dư thừa 𝐾ế𝑡 𝑙𝑢ậ𝑛 𝐹𝑐" = {𝐷 → 𝐴, 𝐵 → 𝐷} là phủ tối thiểu 6 Lược đồ tổng hợp thành 3NF  7 Input R(U,F) 1. Tìm phủ tối thiểu G 2. Đối với FD có vế trái X trong G, tạo 1 lược đồ quan hệ với thuộc tính {X {A1} {A2}…{Ak}, với XA1, X A2,…, XAk 3. Nếu không có lược đồ nào trong D chứa khóa của R, tạo thêm 1 lược đồ trong D chứa các thuộc tính của khóa 4. Loại bỏ quan hệ dư thừa khỏi D. Một quan hệ được gọi là dư thừa nếu nó là phép chiếu của 1 quan hệ khác trong D Ví dụ 8 Cho phủ tối thiểu G sau, hãy tổng hợp thành các lược đồ quan hệ : {Emp  Esal, Ephone, Dno; Pno  Pname, Plocation}. Khóa chính của lược đồ là Emp, Pno.  Áp dụng giải thuật, sau bước 2 có 2 lược đồ:  R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  Bước 3: tạo thêm 1 quan hệ mới tương đương với khóa của R {Emp_ssn, Pno}  Kết quả là có 3 lược đồ  R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  R3(Emp_ssn, Pno}  

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Mình giải thế này!
Bước 1: (Giống bạn) Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. F={AB->C, AB->D, B->C, C->D}
Bước 2: Loại bỏ cái phụ thuộc hàm không đầy đủ: - Ta có AB->C mà B->C => Loại bỏ PTH không đầy đủ AB->C

Bây giờ

F={AB->D, B->C, C->D}
Bước 3: Loại bỏ cái PTH hàm dư thừa
- Nếu bỏ PTH: AB->D thì F={B->C, C->D} =>F+={BCD} # Q+={ABCD} => Không thể bỏ
- Nếu bỏ PTH: B->C thì F={AB->D,C->D} F+={ABDC} = Q+={ABCD} => Bỏ
- Viết lại F={AB->D,C->D}
- Xét tiếp C->D nếu bỏ thìF={AB->D} => F+={ABD} # Q+={ABCD} => Không thể bỏ
- Vậy PTT(F) = {AB->D, C->D}
=> Đáp án của mình khác với bạn.

=> Theo như đáp án của bạn thì PTH(F)={B->C, C->D} ??Làm cách nào suy ra A