{BD}+F = {BD}
Duyệt lần 1:
- Từ f1: {BD}+F = {BCA}
- Từ f2: {BD}+F = {BCACE}
- Từ f3: {BD}+F = {BCACEH}
Duyệt lần 2: không thay đổi
Vậy {BD}+F = {BCACEH}
{BCG}+F = {BCG}
Duyệt lần 1:
- Từ f1: {BCG}+F = {BCGA}
- Từ f5: {BCG}+F = {BCGAD}
Duyệt lần 2:
- Từ f2: {BCG}+F = {BCGADE}
- Từ f3: {BCG}+F = {BCGADEH} = U (tập thuộc tính của lược đồ quan hệ Q)
Vậy {BCG}+F = {BCGADEH}
{TX}+F = {TX}
Duyệt lần 1:
- Từ f1: {TX}+F = {TXV}
- Từ f3: {TX}+F = {TXVW}
- Từ f4: {TX}+F = {TXVWZ}
Duyệt lần 2: không thay đổi
Vậy {TX}+F = {TXVWZ}, mà {UV} không thuộc {TXVWZ} nên {TX} -> {UV} không suy dẫn từ F
N = U - ∪∀f∈Fright(f) = {ABCDEG} - {CAGE} = {BD}
N+F = {BD}+F = {BDG} ≠ U
D = ∪∀f∈Fright(f) - ∪∀f∈Fleft(f) = {CAGE} - {AECGBD} = ∅
L = U - N+FD = {ABCDEG} - {BDG} = {ACE}
Các tập con của L là {A}, {C}, {E}, {AC}, {AE}, {EC}, {ACE}
- Xét {BDA}+F = {BDAGEC} = U => {BDA} là khoá của Q. Loại các tập cha của {A} là {AC}, {AE}, {ACE}
- Xét {BDC}+F = {BDCGAE} = U => {BDC} là khoá của Q. Loại các tập cha của {C} là {AC}, {EC}, {ACE}
- Xét {BDE}+F = {DBGE} ≠ U => {BDE} không phải là khoá của Q
Vậy có hai khoá tối thiểu của Q là {BDA} và {BDC}
N = U - ∪∀f∈Fright(f) = {MaGV, HoTen, MaMH, TenMH, Phong, Gio} - {HoTen, TenMH, MaMH, Phong} = {MaGV, Gio}
N+F = {MaGV, Gio}+F = {MaGV, Gio, HoTen, Phong, MaMH, TenMH} = U
Vậy có một khoá tối thiểu của Q là {MaGV, Gio}
N = U - ∪∀f∈Fright(f) = {ABCEG} - {BCAG} = {E}
N+F = {E}+F = {E} ≠ U
D = ∪∀f∈Fright(f) - ∪∀f∈Fleft(f) = {BCAG} - {ABCEG} = ∅
L = U - N+FD = {ABCEG} - {E} = {ABCG}
Các tập con của L là {A}, {B}, {C}, {G}, {AB}, {AC}, {AG}, {BC}, {BG}, {CG}, {ABC}, {ABG}, {ACG}, {BCG}, {ABCG}
- Xét {EA}+F = {EAG} ≠ U => {EA} không phải là khoá của Q
- Xét {EB}+F = {EBAGC} = U => {EB} là khoá của Q. Loại các tập cha của {B} là {AB}, {BC}, {BG}, {ABC}, {ABG}, {BCG}, {ABCG}
- Xét {EC}+F = {ECBAG} = U => {EC} là khoá của Q. Loại các tập cha của {C} là {AC}, {BC}, {CG}, {ABC}, {ACG}, {BCG}, {ABCG}
- Xét {EG}+F = {EG} ≠ U => {EG} không phải là khoá của Q
- Xét {EAG}+F = {EAG} ≠ U => {EAG} không phải là khoá của Q
Vậy có hai khoá tối thiểu của Q là {EB} và {EC}
- f1: ABH -> C
- f2: ABH -> K
- f3: A -> D
- f4: C -> E
- f5: BGH -> F
- f6: F -> A
- f7: F -> D
- f8: E -> F
- f9: BH -> E
- {A}+F-{f1} = {AD} không chứa C
- {B}+F-{f1} = {B} không chứa C
- {H}+F-{f1} = {H} không chứa C
- {AB}+F-{f1} = {ABD} không chứa C
- {AH}+F-{f1} = {AHD} không chứa C
- {BH}+F-{f1} = {BHEFAD} không chứa C, nhưng chứa A, thay thế f1: ABH -> C bằng f1: BH -> C
- {A}+F-{f2} = {AD} không chứa K
- {B}+F-{f2} = {B} không chứa K
- {H}+F-{f2} = {H} không chứa K
- {AB}+F-{f2} = {ABD} không chứa K
- {AH}+F-{f2} = {AHD} không chứa K
- {BH}+F-{f2} = {BHEFAD} không chứa K, nhưng chứa A, thay thế f2: ABH -> K bằng f2: BH -> K
- {B}+F-{f5} = {B} không chứa F
- {G}+F-{f5} = {G} không chứa F
- {H}+F-{f5} = {H} không chứa F
- {BH}+F-{f5} = {BHEFAD} có chứa F => G thừa. Thay thế f5: BGH -> F bằng f5: BH -> F
- {B}+F-{f9} = {B} không chứa E
- {H}+F-{f9} = {H} không chứa E
Vậy ta có:
- f1: BH -> C
- f2: BH -> K
- f3: A -> D
- f4: C -> E
- f5: BH -> F
- f6: F -> A
- f7: F -> D
- f8: E -> F
- f9: BH -> E
- {A}+F-{f3} = {A}
- {C}+F-{f4} = {C}
- {BH}+F-{f5} = {BHCKEF} chứa F => f5 thừa nên loại f5
Vậy ta được:
- f1: BH -> C
- f2: BH -> K
- f3: A -> D
- f4: C -> E
- f5: F -> A
- f6: F -> D
- f7: E -> F
- f8: BH -> E
- {F}+F-{f6} = {FAD} chứa D => f6 thừa nên loại f6
Vậy ta được:
- f1: BH -> C
- f2: BH -> K
- f3: A -> D
- f4: C -> E
- f5: F -> A
- f6: E -> F
- f7: BH -> E
- {BH}+F-{f7} = {BHCKEF} chứa E => f7 thừa nên loại f7
Phủ tối thiểu của tập PTH F là:
- f1: BH -> C
- f2: BH -> K
- f3: A -> D
- f4: C -> E
- f5: F -> A
- f6: E -> F
- f1: A -> B
- f2: A -> C
- f3: BE -> G
- f4: E -> D
- f5: D -> G
- f6: A -> B
- f7: AG -> B
- f8: AG -> C
Ta thấy f6 trùng f1 nên loại bỏ f6: A -> B. Giảm các f7, f8 về 1 bậc
- f1: A -> B
- f2: A -> C
- f3: BE -> G
- f4: E -> D
- f5: D -> G
- f6: AG -> B
- f7: AG -> C
- {B}+F-{f3} = {B} không chứa G
- {E}+F-{f3} = {EDG} không chứa G
Vâỵ f3 không bị loại bỏ
-
{A}+F-{f6} = {ABC} chứa B => G thừa. Thay thế f6: AG -> B bằng f6: A -> B nhưng trùng với f1: A -> B nên loại bỏ f6
-
f1: A -> B
-
f2: A -> C
-
f3: BE -> G
-
f4: E -> D
-
f5: D -> G
-
f6: AG -> C
-
{A}+F-{f6} = {ABC} chứa C => G thừa. Thay thế f6: AG -> C bằng f6: A -> C nhưng trùng với f2: A -> C nên loại bỏ f6
-
f1: A -> B
-
f2: A -> C
-
f3: BE -> G
-
f4: E -> D
-
f5: D -> G
- {B}+F-{f3} = {B} không chứa G
- {D}+F-{f5} = {D} không chứa G
Phụ thuộc hàm tối thiểu là:
- f1: A -> B
- f2: A -> C
- f3: BE -> G
- f4: E -> D
- f5: D -> G
- f1: A -> B
- f2: A -> D
- f3: A -> E
- f4: J -> H
- f5: J -> I
- f6: E -> D
- f7: E -> G
- f8: BC -> G
- f9: BC -> H
- f10: DE -> G
- f11: H -> J
- f12: HG -> J
- {B}+F-{f8} = {B} không chứa G
- {C}+F-{f8} = {C} không chứa G
Vậy f8 không bị loại bỏ
- {B}+F-{f9} = {B} không chứa H
- {C}+F-{f9} = {C} không chứa H
Vậy f9 không bị loại bỏ
-
{D}+F-{f10} = {D} không chứa G
-
{E}+F-{f10} = {EDG} chứa G => D thừa, thay thế f10: DE -> G bằng f10: E -> G nhưng trùng với f7: E -> G nên loại bỏ f10
-
f1: A -> B
-
f2: A -> D
-
f3: A -> E
-
f4: J -> H
-
f5: J -> I
-
f6: E -> D
-
f7: E -> G
-
f8: BC -> G
-
f9: BC -> H
-
f10: H -> J
-
f11: HG -> J
-
{H}+F-{f11} = {HJ} chứa J => G thừa, thay thế f11: HG -> J bằng f11: H -> J nhưng trùng với f10: H -> J nên loại bỏ f11
-
f1: A -> B
-
f2: A -> D
-
f3: A -> E
-
f4: J -> H
-
f5: J -> I
-
f6: E -> D
-
f7: E -> G
-
f8: BC -> G
-
f9: BC -> H
-
f10: H -> J
-
{A}+F-{f2} = {ABDEG} chứa D => f2 thừa nên loại bỏ f2
-
f1: A -> B
-
f3: A -> E
-
f4: J -> H
-
f5: J -> I
-
f6: E -> D
-
f7: E -> G
-
f8: BC -> G
-
f9: BC -> H
-
f10: H -> J
- {J}+F-{f4} = {JI} không chứa H => f4 không bị loại bỏ
- {BC}+F-{f9} = {BCG} không chứa H => f9 không bị loại bỏ
- {E}+F-{f7} = {ED} không chứa G => f7 không bị loại bỏ
- {BC}+F-{f8} = {BCH} không chứa G => f8 không bị loại bỏ
Phủ tối thiểu của tập PTH F là:
- f1: A -> B
- f2: A -> E
- f3: J -> H
- f4: J -> I
- f5: E -> D
- f6: E -> G
- f7: BC -> G
- f8: BC -> H
- f9: H -> J
Q(TUVWXYZ) F = {X -> V; Z -> X; T -> W; {TX} -> Z; {WY} -> {UV}}
Đặt tên:
- f1: X -> V
- f2: Z -> X
- f3: T -> W
- f4: {TX} -> Z
- f5: {WY} -> {UV}
Trước tiên {TX}+F = {TX}
Duyệt lần 1:
- Từ f1: {TX}+F = {TVX}
- Từ f3: {TX}+F = {TVWX}
- Từ f4: {TX}+F = {TVWXZ}
Duyệt lần 2:
- Từ f2: {TX}+F = {TVWXZ} = U (tập thuộc tính của lược đồ quan hệ F)
Vậy {TX}+F = {TVWXZ}
Mà {UV} không thuộc {TVWXZ} nên {TX}
Nên PTH {TX} -> {UV} không suy dẫn từ F
N = U - ∪∀f∈Fright(f) = {TUVWXYZ} - {UVXWZ} = {TY}
N+F = {TY}+F = {TY} ≠ U
D = ∪∀f∈Fright(f) - ∪∀f∈Fleft(f) = {UVXWZ} - {TWXYZ} = {UV}
L = U - N+FD = {TUVWXYZ} - {TUVY} = {XZ}
Các tập con của L là {X}, {Z}, {XZ}
- Xét {TXY}+F = {TUVWXYZ} = U => {TXY} là khoá của Q. Loại các tập cha của {X} là {XZ}
- Xét {TYZ}+F = {TUVWXYZ} = U => {TYZ} là khoá của Q. Loại các tập cha của {Z} là {XZ}
Vậy có hai khoá tối thiểu của Q là {TXY} và {TYZ}
F={AB → CD; AB → C; AB → D}
Vậy ta có:
- f1: AB → C
- f2: AB → D
- f3: B → C
- f4: C → D
Xét f1: AB → C
- {A}+F - f1 = {A} không chứa C
- {B}+F - f1 = {BCD} chứa C. => A thừa. Thay thế f1: AB → C bởi f1 : B → C, nhưng trùng với f3: B → C. → Loại bỏ f1.
Xét f2: AB → D
- {A}+F - f2 = {A} không chứa D
- {B}+F - f2 = {BCD} chứa D. → A thừa. Thay thế f2: AB → D bởi f2: B → D.
Vậy ta có:
- f1: B → D
- f2: B → C
- f3: C → D
Xét f1: B → D
- {B}+F - f1 = {BCD} chứa C. → f1 thừa nên loại f1
Vậy phủ tối thiểu của tập PTH F là:
- f1: B → C
- f2: C → D
N = U - ∪∀f∈Fright(f) = {ABCDEFGHIJKL} - {BCDEFHIJKL} = {AG}
N+F = {AG}+F = {ABCDEFGHIJKL} = U
Vậy Q có khoá duy nhất là {AG}
- f1: AB -> C
- f2: AB -> D
- f3: A -> B
- f4: B -> C
- f5: C -> E
- f6: BD -> A
-
{A}+F-{f1} = {ABCDE} chứa C => B thừa. Thay thế f1: AB -> C bằng f1: A -> C
-
f1: A -> C
-
f2: AB -> D
-
f3: A -> B
-
f4: B -> C
-
f5: C -> E
-
f6: BD -> A
-
{A}+F-{f2} = {ABCE} không chứa D, nhưng chứa B. Thay thế f2: AB -> D bằng f2: A -> D
-
f1: A -> C
-
f2: A -> D
-
f3: A -> B
-
f4: B -> C
-
f5: C -> E
-
f6: BD -> A
- {B}+F-{f6} = {BC} không chứa A
- {D}+F-{f6} = {D} không chứa A
Vậy f6 không bị loại bỏ
- {A}+F-{f1} = {ABCE} chứa C => f1 thừa. Loại bỏ f1
Vậy phủ tối thiểu của tập PTH F là:
- f1: A -> D
- f2: A -> B
- f3: B -> C
- f4: C -> E
- f5: BD -> A
N = U - ∪∀f∈Fright(f) = {ABCDE} - {ABCDE} = ∅
D = ∪∀f∈Fright(f) - ∪∀f∈Fleft(f) = {ABCDE} - {ABCD} = {E}
L = U - N+FD = {ABCDE} - {E} = {ABCD}
Các tập con của L là {A}, {B}, {C}, {D}, {AB}, {AC}, {AD}, {BC}, {BD}, {CD}, {ABC}, {ABD}, {ACD}, {BCD}, {ABCD}
- Xét {A}+F = {ABCDE} = U => {A} là khoá của Q. Loại các tập cha của {A} là {AB}, {AC}, {AD}, {ABC}, {ABD}, {ACD}, {ABCD}
- Xét {B}+F = {BCE} ≠ U, nên {B} không phải là khoá của Q
- Xét {C}+F = {CE} ≠ U, nên {C} không phải là khoá của Q
- Xét {D}+F = {D} ≠ U, nên {D} không phải là khoá của Q
- Xét {BC}+F = {BCE} ≠ U, nên {BC} không phải là khoá của Q
- Xét {BD}+F = {ABDCE} = U => {BD} là khoá của Q. Loại các tập cha của {BD} là {BCD}, {ABD}, {BCD}, {ABCD}
- Xét {CD}+F = {CDE} ≠ U, nên {CD} không phải là khoá của Q
Vậy có hai khoá tối thiểu của Q là {A} và {BD}
Có F = {f1: AB -> C; f2: A -> DE; f3: B -> F; f4: F -> GH; f5: D -> IJ}
N = U - ∪∀f∈Fright(f) = {ABCDEFGHIJ} - {CDEFGHIJ} = {AB}
N+F = {AB}+F = {ABCDEFGHIJ} = U, nên có một khoá tối thiểu của Q là {AB}