lOMoAR cPSD| 45469857 Bài tập CSDLQH Khoa CNTT
BÀI TẬP BUỔI 5 Hệ tiên
đề Amstrong và bao đóng Câu 1:
a. Hãy trình bày các tính chất của hệ tiên đề Amstrong?
Hệ tiên đề Armstrong (Armstrong's axioms) là một tập hợp các tính chất hoặc quy tắc cơ bản
trong lý thuyết cơ sở dữ liệu và hệ thống quản lý cơ sở dữ liệu. Đây là các quy tắc quan trọng để
hiểu về sự phụ thuộc chức năng và chức năng của dữ liệu. Dưới đây là các tính chất cơ bản của hệ tiên đề Amstrong:
1. Tính chất của sự phụ thuộc chức năng (Functional Dependency): •
Tính chất phản xạ (Reflexivity): Nếu Y là một phần của X, thì X phụ thuộc chức năng vào Y. •
Tính chất mở rộng (Augmentation): Nếu X phụ thuộc chức năng vào Y, thì bất
kỳ tập hợp thuộc X nào cũng phụ thuộc chức năng vào Y. •
Tính chất transitiveness (Transitivity): Nếu X phụ thuộc chức năng vào Y và Y
phụ thuộc chức năng vào Z, thì X phụ thuộc chức năng vào Z.
2. Tính chất của sự phụ thuộc hàm (Multivalued Dependency): •
Tính chất phản xạ (Reflexivity): Nếu X phụ thuộc đa giá trị vào Y, thì Y phụ
thuộc đa giá trị vào X. •
Tính chất mở rộng (Augmentation): Nếu X phụ thuộc đa giá trị vào Y, thì bất
kỳ tập hợp thuộc X nào cũng phụ thuộc đa giá trị vào Y. •
Tính chất union (Union): Nếu X phụ thuộc đa giá trị vào Y, thì X phụ thuộc đa
giá trị vào tất cả các phần tử trong tập hợp các giao của Y.
3. Tính chất của sự phụ thuộc chức năng không hoàn toàn (Partial Functional Dependency): •
Tính chất decomposition (Decomposition): Nếu X phụ thuộc chức năng vào Y,
với Z là một phần của Y, nhưng X không phụ thuộc chức năng vào Z, thì Z phụ thuộc chức năng vào Y.
b. Cho U=ABCDEGHK và phụ thuộc hàm
F = {AB--> C, B--> DE, CD--> EK, CE--> GH, G--> AC } - Chứng minh AB-->EG
G --> AC =>> G --> A và G --> C.
CE --> GH =>> C --> GH.
kết hợp hai phụ thuộc trên, ta có C --> GH và G --> A =>> C --> A.
Từ phụ thuộc chức năng AB --> C =>> A --> C.
Do đó, ta có các phụ thuộc sau: • G --> A 1 lOMoAR cPSD| 45469857 Bài tập CSDLQH Khoa CNTT • A --> C C --> E
=>> G --> E bằng tính chất transitiveness. từ AB --> C và G --> E
=>> AB --> EG bằng tính chất augmentation. =>> AB --> EG. Câu 2:
Hãy trình bày thuật toán tìm bao đóng của tập thuộc tính trong lược đồ quan hệ?
a. Cho tập thuộc tính U=ABCDEGH
-bao đóng của tập thuộc tính U=ABCDEGH là U=ABCDEFGHK. 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 hay f có thuộc F+ hay không?
- f không thuộc F+ và không thể suy ra từ F, nên F không phải là một tập hậu tố của f. Câu 3:
Cho quan hệ Q (ABCDEGH) và tập phụ thuộc hàm F thỏa Q
F = { A BG ,D EG ,GB HA , D BA , B HG }
Xác định xem các phụ thuộc hàm sau, phụ thuộc hàm nào được suy ra từ F. + EG BD EG không suy ra BD từ F. + AB CDEGH AB suy ra CDEGH từ F. + D GH D suy ra GH từ F. Câu 4:
Cho lược đồ quan hệ Q và tập phụ thuộc hàm F
A. F={AB E;AG I;BE I;E G;GI H} Chứng minh rằng AB GH. AB không suy ra GH từ F.
B. F={AB C;B D;CD E;CE GH;G A} Chứng minh rằng AB E; AB G
AB không suy ra GH từ F và AB suy ra cả E và G từ F. 2 lOMoAR cPSD| 45469857 Bài tập CSDLQH Khoa CNTT Câu 5:
A.Hãy định nghĩa bao đóng của tập thuộc tính?
Bao đóng của một tập thuộc tính trong lược đồ quan hệ là tập hợp tất cả các thuộc
tính mà chúng ta có thể suy ra từ tập thuộc tính ban đầu, sử dụng các phụ thuộc
chức năng có trong hệ thống. Trong bao đóng, mỗi phần tử phải thỏa mãn một số
phụ thuộc chức năng nào đó từ tập phụ thuộc chức năng ban đầu.
b. Cho lược đồ quan hệ =( U,F), tập thuộc tính U=ABCDEGHI
Và tập phụ thuộc hàm F={AB CE, D BH, CH AD, E GI, CD EA}
Hãy tính X+ trong các trường hợp sau: - X=ABD {ABDCEH}. - X=ABE {ABCEGI}. Câu 6:
Cho quan hệ p=(U,F) trong đó U=ABEGHI và F={AB→E, AG→I, BE→I, E→G, GI→H}.
A. Hãy chứng minh phụ thuộc hàm AB→GH được suy dẫn từ F nhờ các qui tắc suy dẫn của Armstrong 1. AB --> E . (từ F) . 2. E --> G . . (từ F) 3. AG --> I (từ F) 4. GI --> H (từ F) Phụ thuộc chức năng:
AB --> E --> G --> H. AG --> I --> H.
Áp dụng quy tắc Augmentation ta có thêm: AB --> EG --> GH. AG --> IH --> IH.
Áp dụng quy tắc transitivity: AB --> GH.
b) Tìm bao đóng của {AB} bao đóng của {AB} trong
quan hệ p=(U,F) là {ABEG}. Câu 7:
Cho lược đồ quan hệ =( U, F). Trong đó : U=ABCDEGH 3 lOMoAR cPSD| 45469857 Bài tập CSDLQH Khoa CNTT
F={AB C, B D, CD E, CE GH, G A}
a. Chứng tỏ phụ thuộc hàm AB E, AB G được suy diễn từ F nhờ luật Armstrong? b. Tìm bao đóng của AB? Câu 8:
Cho lược đồ quan hệ = (U, F), với:
U = ABCDEGH và F = {B AEG , AE CH , ACD BEG}.
a. Phụ thuộc hàm f = BD CGH có được suy dẫn được từ tập các phụ thuộc hàm F
không? Giải thích vì sao.
b. Tính bao đóng: (BD)+, A+. 4