vhphong_nt
New Member
Download miễn phí Bài tập về Phụ thuộc hàm
MỘT SỐ LƯU Ý
Tiên đề Amstrong. Áp dụng hệ tiên đề amstrong trong các bài toán chứng minh.
Phụ thuộc hàm theo quan hệ và theo tiên đề, bao đóng của tập các thuộc tính và của tập các phụ thuộc hàm.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
2. BµI TËP VÒ phỤ THUỘC HÀMMỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC
Hiểu được tầm quan trọng của lý thuyết của phụ thuộc hàm
Vận dụng các thuật toán tính bao đóng, định nghĩa suy diễn theo tiên đề, theo quan hệ, tìm phủ tối thiểu, bài toán thành viên để giải quyết các bài tập cụ thể.
Áp dụng các thuật toán để giải quyết các bài tập liên quan: Tìm bao đóng, chứng minh một phụ thuộc hàm có dư thừa trong tập các phụ thuộc hàm không,...
A/ NHẮC LẠI LÝ THUYẾT
I. MỘT SỐ ĐỊNH NGHĨA, TÍNH CHẤT
Định nghĩa phụ thuộc hàm
Định nghĩa: cho U là một tập thuộc tính, một phụ thuộc hàm trên U là một phát biểu có dạng XàY, trong đó X,YÍU.
Cho R là quan hệ trên tập thuộc tính U, nói rằng quan hệ R thoả mãn phụ thuộc hàm XàY, nếu với 2 bộ bất kì trong R mà chúng giống nhau trên tập thuộc tính X thì chúng cũng giống nhau trên tập thuộc tính Y, nghĩa là "u,v ÎR, nếu u.X=v.X thì u.Y=v.Y.
Nếu f= XàY là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ thuộc hàm vào tập thuộc tính X (Y functional dependent on X ) hay tập thuộc tính X xác định hàm tập thuộc tính Y (X functional determines Y).
Cho f là một phụ thuộc hàm trên U, nếu quan hệ R thoả mãn phụ thuộc hàm f thì ta ký hiệu R(f), nếu R không thoả mãn phụ thuộc hàm thì ta ký hiệu ùR(f).
Cho F là một tập các phụ thuộc hàm trên U, nói rằng quan hệ R thoả mãn tập phụ thuộc hàm F, ký hiệu là R(F) nếu và chỉ nếu với " f Î F thì R(f) hay nói một cách tương đương quan hệ R thoả mãn tập phụ thuộc hàm F nếu như nó thoả mãn từng phụ thuộc hàm trong tập đó.
Định nghĩa: Lược đồ quan hệ là một cặp a=(U, F) trong đó U là tập hữu hạn các thuộc tính còn F là tập các phụ thuộc hàm trên U.
2. Một số tính chất của phụ thuộc hàm:
1) Tính chất phản xạ: " X, YÍU, YÍX, thì XàY
2) Tính chất bắc cầu: " X, Y, ZÍU, nếu có XàY và YàZ thì XàZ
3) Tính chất gia tăng: " X, YÍU, nếu Xà Y và " ZÍU thì XZàYZ
4) Tính chất tựa bắc cầu: " X, Y, Z, W ÍU, nếu XàY, YZà W thì XZàW
5) Tính chất phản xạ chặt: " XÍU thì XàX
XàY
XàZ
6) Luật tách: " X, Y, Z ÍU, nếu có XàYZ thì có:
7) Luật hợp: " X, Y, Z ÍU, nếu có Xà Y và XàZ thì có XàYZ
Tính chất cộng tính: " X, Y, Z, W ÍU, nếu XàY, Zà W thì XZàYW
3. Hệ tiên đề Amstrong
F1 - Luật phản xạ "X,YÍU, nếu XÍY thì Yà X
F2 - Bắc cầu "X, Y, Z Í U nếu có
XàY
YàZ
thì XàZ
F3 - Luật gia tăng " X, Y, Z Í U, nếu có XàY thì XZàYZ
4. Định nghĩa suy dẫn theo hệ tiên đề
Cho F là tập phụ thuộc hàm trên U, f là một phụ thuộc hàm trên U ( f có thể không thuộc F), nói rằng f suy dẫn được từ F theo hệ tiên đề Amstrong và kí hiệu là F├ f nếu như f có thể nhận được từ tập F sau một số hữu hạn lần áp dụng các luật của hệ tiên đề Amstrong.
Nhận xét:
Với " f Î F thì F├ f
Kí hiệu F+ là tập tất cả các phụ thuộc hàm được suy dẫn từ tập F theo hệ tiên đề Amstrong.
Ta thấy FÍ F+
F+ được gọi là bao đóng của tập phụ thuộc hàm F, nếu F+ =F thì ta nói F là một tập đầy đủ các phụ thuộc hàm, đôi khi ta còn nói F là tập đóng.
5. Định nghĩa suy dẫn theo quan hệ
Cho F là một tập các phụ thuộc hàm trên tập thuộc tính U, f là một phụ thuộc hàm trên U, (f có thể không thuộc F), nói rằng f được suy dẫn từ tập F theo quan hệ và ký hiệu F ╞f, nếu và chỉ nếu với mọi quan hệ R trên U, nếu R thoả mãn F thì R cũng thoả mãn f.
Ký hiệu F* là tập tất cả các phụ thuộc hàm được suy dẫn từ tập F theo quan hệ.
F*={f:XàY | X,YÍU, F╞f}
Tính chất của F*:
Cho F và G là hai tập phụ hàm trên tập thuộc tính U khi đó ta có:
1. Tính phản xạ: Với " f Î F thì F ╞f từ đây ta suy ra F Í F*.
2. Tính đơn điệu: Nếu FÍ G thì F* Í G*.
3. Tính luỹ đẳng: Với mọi tập phụ thuộc hàm F thì ta luôn có (F*)*=F*.
6. Bao đóng của tập thuộc tính
Cho tập phụ thuộc hàm F trên U, XÍU, bao đóng của tập thuộc tính X, kí hiệu là X+ được xác định như sau:
X+= { A | AÎU và XàAÎF+ }
* Thuật toán tìm bao đóng của một tập thuộc tính
Input a = (U,F), XÍU
Output X+ =?
Thuật toán
Ta xác định dãy X(0), X(1), X(2),... theo quy nạp như sau
1. Đặt X(0)=X
2. Giả sử rằng đã xây dựng được đến bước thứ i tức là đã biết X(i) (i>=0)
3. Xây dựng tiếp bước i+1 như sau
Xjà Yj Î F (1)
Xj ÍXi (2)
YJ Ë X(i) (3)
X(i+1)= X(i) È Z(i) trong đó
Z(i) = È Yj với điều kiện :
Vì vậy Z(i) chính là hợp của các vế phải của các phụ thuộc hàm trong tập F mà có vế trái là tập con của tập trước mà có vế phải chưa được thêm vào.
điều kiện (3) chỉ có tác dụng tăng tốc độ tính toán
Nhận xét:
X(0), X(1), X(2),... là một dãy không giảm và bị chặn trên bởi U, do đó tồn tại chỉ số i nào đó để X(i)= X(i+1) (*), gọi i là chỉ số nhỏ nhất khi đó X+ = X(i) hay khi X(i) = U thì X+ = X(i) = U.
7. Phụ thuộc hàm dư thừa
Cho F là một tập các phụ thuộc hàm trên U, f là một phụ thuộc hàm của F tức f ÎF, f được gọi là dư thừa trong F nếu như (F-f)+ =F+
Hay có thể nói tương đương f được gọi là dư thừa trong F nến nó suy dẫn được từ tập F sau khi đã bỏ đi phụ thuộc hàm f.
Thuật toán thành viên
Input
- Tập phụ thuộc hàm F
- f Î F
Output
- True nếu như f là dư thừa trong F
- False nếu như f là không dư thừa trong F
Method
1) tạm xoá f khỏi F, gọi G là tập thu được
G=F-f, nếu G¹f thì chuyển qua bước 2, còn không thì kết thúc thuật toán và kết luận f là không dư thừa trong F
2) Giả sử f=XàY nếu G├ f tức YÍ thì f là dư thừa trong F còn ngược lại f là không dư thừa.
Như vậy, ta chỉ cần tính X+ và so sánh với tập con Y ta có ngay câu trả lời X ® Y có thuộc vào F+ hay không.
8. Phụ thuộc hàm dư thừa
II. CÁC VÍ DỤ
Ví dụ 1:
Cho lược đồ quan hệ a = (U,F) với
U = ABCDEGH
F={ BCà ADE, ACà BDG, BEà ABC, CDà BDH, BCHà ACG}
Hãy tính X+ trong các trường hợp
a) X=BD
b) X=ABE
c) X=CDG
Giải
a) đặt X(0)=BD (=X)
X(1) = X(0) È Z(0) =BD È F=BD
Suy ra X(0)= X(1) vậy X+ =X=BD
b) đặt X(0)=ABE (=X)
X(1) = X(0) È Z(0) =ABE ÈABC=ABCE
X(2) = X(1) È Z(1) =ABCE È (ADE È BDG)=ABCDEG
X(3) = X(2) È Z(2) = ABCDEG È BDH=ABCDEGH=U
Vậy X+=U
Ví dụ 2 : Áp dụng bài toán thành viên
Giả sử có tập F={XàYW, XWàZ, ZàY, XYàZ}
Hãy cho biết XYàZ có dư thừa trong F hay không?
Giải
1) Tạm thời xoá XYàZ ra khỏi F
G:=F-{XYàZ}={XàYW, XWàZ, ZàY}
2) Tính (XY)+G ( bao đóng của XY trong tập G)
ta có (XY)+G= XYWZ thế nên ZÍ(XY)+G hay G├ (XYàZ) thế nên phụ thuộc hàm XYàZ là dư thừa trong F.
III. MỘT SỐ LƯU Ý
Tiên đề Amstrong. Áp dụng hệ tiên đề amstrong trong các bài toán chứng minh.
Phụ thuộc hàm theo quan hệ và theo tiên đề, bao đóng của tập các thuộc tính và của tập các phụ thuộc hàm.
B/ BÀI TẬP MẪU
Bài số 1:
Cho tập thuộc tính U=ABCDEGH
Cho tập phụ thuộc hàm F={ ABàCD, ACEàBG, BCDà AE, CHà DG}
f=BCDH àAG, hỏi rằng F├ f hay không (f Î F+) ?
Hướng dẫn:
Áp dụng hệ tiên đề Amstrong để chứng minh, đầu tiên cần làm xuất hiện vế trái của phụ thuộc hàm cần chứng minh sau đó lần lượt áp dụng 3 tiên đề để suy ra ĐPCM.
Giải
BCDHà BCD (1) ( tính chất phản xạ )
BCDàAE ( gt) (2)
BCDàACE ( gia tăng) (3)
ACEà A (phản xạ) (4)
Suy ra BCDHà A theo tính chất bắc cầu(5)
ACEà BG (6) giả thiết
BGàG (7) phản xạ
Suy ra ACEà G(8) bắc cầu
Suy ra BCDHà G (9) bắc cầu
Từ (5) và (9) theo luật cộng tính ( luật ghép)
Suy ra BCDHà AG Î F+ ( đpcm)
Bài số 2:
Cho a=(U,F); U=ABCDEGH
F={ ABàBCP, EàBGH, ACD àBG, DàAEH}
H...