Tìm khóa tối thiểu của lược đồ quan hệ
Cho lược đồ R = <U,F>, trong đó U là tập thuộc tính, F là tập phụ thuộc hàm. K được gọi là khoá tối thiểu của R nếu như số thuộc tính trong K là ít nhất nhưng vẫn thoả mãn K + =U . Cho lược đồ quan hệ R = ...
Cho lược đồ R = <U,F>, trong đó U là tập thuộc tính, F là tập phụ thuộc hàm. K được gọi là khoá tối thiểu của R nếu như số thuộc tính trong K là ít nhất nhưng vẫn thoả mãn K+ =U .
Cho lược đồ quan hệ R = <U, F>
Hãy tìm một khoá (tối thiểu) của quan hệ R.
Bài tập áp dụng
Cho lược đồ R = <U, F> : U = {ABCDE} , F = {A→B, B→C, B→DE, A→E, A→D}
Hãy tìm một khoá tối thiểu K của lược đồ R ?
- Đặt
T = {AB} (T là tập các thuộc tính xuất hiện phía trái)
P = {BCDE} (P là tập các thuộc tính xuất hiện phía phải)
K = UP = {A}
- Tính thử K+
Ta có K+ = {ABCDE}
Vì K+ = U, nên K = {A} là một khoá của R.
Cho lược đồ quan hệ R = <U, F>, Trong đó : U = {ABCDE} , F = {AB→DE, E→AD, D→C}
Hãy tìm một khoá tối thiểu K của lược đồ R
-
Đặt:
T = {ABED}
P = {DEAC}
K = UP = {B}
-
Tính thử K +
Ta có K+ = {B} U, nên tiếp tục Bước 3
-
Tính K = K (TP)
Ta có K = K (TP) = {ABDE}
-
Thử xóa từng thuộc tính trong TP = {AED} khỏi K
Thử loại bỏ A khỏi K, ta có :
K = {BED} và K + = {BEDAC} vẫn bằng U nên ta loại được A
Thử loại bỏ {E} khỏi K, Ta có:
K = {BD} và K+ = {BDC}
Do K+ U nên không thể loại được {E}. K vẫn là {BDE}
Thử loại bỏ {D} khỏi K ta có
K = {BE} và K+ = {BEADC}= U
Đến đây ta đã thử hết. Vậy khóa tối thiểu tìm được là : K = {BE}
Cho lược đồ quan hệ R = <U, F>, Trong đó :
U = {ABCDEG}
F = {AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD, CE→AG}
Hãy tìm một khoá tối thiểu K của lược đồ R.
- Đặt
- T = {ABCDEG}
- P = {ABCDEG} (P là tập các thuộc tính xuất hiện phía phải)
- K = UP = {}
- Tính thử K
+
Ta có K+ = { } ≠ U, nên tiếp tục bước 3
- Tính K = K
(T
P)
Ta có K = K (T P) = {ABCDEG}
- Thử xoá từng thuộc tính trong T
P = {ABCDEG} khỏi K
- Thử loại bỏ {A} khỏi K, Ta có:
K = {BCDEG} và K+ = {BCDEGA} vẫn bằng U, nên ta loại được A
- Thử loại bỏ {B} khỏi K, Ta có:
K = {CDEG} và K+ = {CDEGAB} vẫn bằng U, nên ta loại được B
- Thử loại bỏ {C} khỏi K, Ta có:
K = {DEG} và K+ = {DEG}
Do K+ ≠ U nên không loại được {C}. K vẫn là {DEGC}
- Thử loại bỏ {D} khỏi K, Ta có:
K = {EGC} và K+ = {EGCABD} vẫn bằng U, nên ta loại được D
- Thử loại bỏ {E} khỏi K, Ta có:
K = {GC} và K+ = {GCABDE} vẫn bằng U, nên ta loại được E
- Thử loại bỏ {G} khỏi K, Ta có:
K = {C} và K+ = {CA}
Do K+ = ≠ U nên không loại được {G}. K vẫn là {CG} → Đã thử hết !
Đến đây ta đã thử hết. Vậy khoá tối thiểu tìm được là : K = {CG}
- Thử loại bỏ {A} khỏi K, Ta có:
Cho lược đồ quan hệ R = <U, F>, Trong đó :
U = {ABCDEGH}
F = {A→C, AB→C, C→DG, CD→G, EC→ABEG,C, H→C}
Hãy tìm một khoá tối thiểu K của lược đồ R
- Đặt
T = {ABCDEH}
P = {ABCDEG}
K = UP = {H}
- Tính thử K
+
Ta có K+ = {HCDG} ≠ U, nên tiếp tục bước 3
- Tính K = K
(T P)
Ta có K = K (T P) = {HABCDE}
- Thử xoá từng thuộc tính trong T
P= {ABCDE} khỏi K
Thử loại bỏ {A} khỏi K, Ta có:
K = {HBCDE} và K+ = {HBCDEGA}
Do K+ ≠ U nên không loại được {A}. K vẫn là {HBCDEA}
Thử loại bỏ {B} khỏi K, Ta có:
K = {HCDEA} và K+ = {HCDEAGB}
Do K+ ≠ U nên không loại được {B}. K vẫn là {HCDEAB}
Thử loại bỏ {C} khỏi K, Ta có:
K = {HDEAB} và K+ = {HDEABCG}
Do K+ ≠ U nên không loại được {C}. K vẫn là {HDEABC}
Thử loại bỏ {D} khỏi K, Ta có:
K = {HEABC} và K+ = {HEABCDG}
Do K+ ≠ U nên không loại được {D}. K vẫn là {HEABCD}
Thử loại bỏ {E} khỏi K, Ta có:
K = {HABCD} và K+ = {HABCDG}
Do K+ ≠ U nên không loại được {E}. K vẫn là {HABCDE}.
Đến đây ta đã thử hết. Vậy khoá tối thiểu tìm được là : K = {HABCDE}
Cho lược đồ quan hệ R = <U, F>, Trong đó :
U = {ABC}
F = {A→B, B→A, C→B}
Hãy tìm một khoá tối thiểu K của lược đồ R
- Đặt
T = {ABC}
P = {AB}
K = UP = {C}
- Tính thử K
+
Ta có K+ = {CBA} = U
Vì K+ = U, nên K = {C} là một khoá của R.
