Cho lược đồ R = : 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 = U\P = {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 = , 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 = U\P = {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 = , 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 = U\P = {}
- 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}
Cho lược đồ quan hệ R = , 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 = U\P = {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 = , 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 = U\P = {C}
- Tính thử K + Ta có K+ = {CBA} = U Vì K+ = U, nên K = {C} là một khoá của R.
Câu II: Cho lược đồ quan hệ Q[A,B,C,D,E,G,H] và tập phụ thuộc hàm: F = { E → C; H → E; A→ D; A,E → H; D,G → B; D,G → C }
- Hãy xác đinh tất cả các khóa của Q
- Hãy cho biết Q có đạt 3NF không?
- Tìm phủ tối thiểu của F.
- Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.
HƯỚNG DẪN:
- Tìm khóa? TN = {AG } TG = { DEH } TN+F = { AG }+F = AGDBC ≠ Q+
Xi TN U Xi [TN U Xi]+ Siêu khóa Khóa
ø AG AGDBC
D AGD AGDBC E AGE AGEDBCH = Q+ AGE AGE H AGH AGHDEBC = Q+ AGH AGH DE AGDE AGDEBCH = Q+ AGDE DH AGDH AGDHBCE = Q+ AGDH EH AGEH AGEHDBC = Q+ AGEH DEH AGDEH AGDEHBC = Q+ AGDEHVậy TK = { AGE, AGH }
- 3NF? Xét pth: E → C, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF
- Tìm phủ tối thiểu? Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính F’ = { E → C; H → E; A→ D; A,E → H; D,G → B; D,G → C }
Bước 2: Loại bỏ những thuộc tính dư thừa F’ = { E → C; H → E; A→ D; A,E → H; D,G → B; D,G → C } Bước 3: F’ = { E → C; H → E; TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
A→ D; A,E → H; D,G → B; D,G → C }- Xét E → C: E+ - { E → C } = E, C ∉ E+ ⇔ E → C ∉ F+ ⇒ Không thể bỏ pht này.
- Các pth H → E; A→ D; A,E → H; D,G → B đều không bỏ được vì các thuộc tính E, D, H, B chỉ xuất hiện 1 lần bên vế phải.
- D,G → C: DG+ - { D,G → C } = DGB, C ∉ DG+ ⇔ D,G → C ∉ F+ ⇒ Không thể bỏ pht này.
Vậy F’ = { E → C; H → E; A→ D; A,E → H; D,G → B; D,G → C } Là phủ tối thiếu của F.
- Phân rã? Vậy TK = { AGE, AGH } Bước 1, Bước 2: Không làm Bước 3: Q1[ EC ] với F1 = { E → C } Q2[ HE ] với F2 = { H → E } Q3[ AD ] với F3 = { A→ D } Q4[ AEH ] với F4 = { A,E → H } Q5[ DGB ] với F5 = { D,G → B } Q6[ DGC ] với F6 = { D,G → C } Bước 4: Vì không có LĐQH con nào chứa 1 khóa của Q nên bổ sung 1 khóa của Q vào phân rã: Q7[ AGE ],
F7 = {ø}
\===============================================
ĐỀ SỐ 2
Câu II Cho lược đồ quan hệ Q[ABCDEG] và tập phụ thuộc hàm F= {B → C; DEG → B; A → D; A → E; A → G}
- Hãy xác đinh tất cả các khóa của Q
- Hãy cho biết Q có đạt 3NF không?
- Tìm phủ tối thiểu của F.
- Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.
HƯỚNG DẪN
- Tìm khóa? TN = { A } TG = { BDEG }
TN+F = { A }+F = ADEGBC = Q+ Vậy Q chỉ có 1 khóa duy nhất là A
- 3NF?
Xét pth: B → C, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF
- Tìm phủ tối thiểu?
Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính F’ = { B → C; DEG → B; A → D; TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
G G GB AB AB ADEGBC = Q+ AB AC AC ADEGBC = Q+ AC AD AD ADEGBC = Q+ AD AG AG ADEGBC = Q+ AG BC BC BC BD BD BDEG BG BG BG CD CD CDEGBA = Q+ CD CD CG CG CGABDE = Q+ CG CG DG DG DGBE ABC ABC ADEGBC = Q+ ABC ABD ABD ADEGBC = Q+ ABD ABG ABG ADEGBC = Q+ ABG ACD ACD ADEGBC = Q+ ACD ACG ACG ADEGBC = Q+ ACG ADG ADG ADEGBC = Q+ ADG BCD BCD CDEGBA = Q+ BCD BCG BCG CGABDE = Q+ BCG BDG BDG BDGE CDG CDG CDEGBA = Q+ CDG ABCD ABCD CDEGBA = Q+ ABCD ABCG ABCG CDEGBA = Q+ ABCG ABDG ABDG CDEGBA = Q+ ABDG ACDG ACDG CDEGBA = Q+ ACDG BCDG BCDG CDEGBA = Q+ BCDG ABCDG ABCDG CDEGBA = Q+ ABCDGVậy TK = { A, CD, CG }
- 3NF?
Xét pth: G→B, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF
- Tìm phủ tối thiểu? Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính
F’ = { AB→ C, AC→D, D→E, D→G, G→B, A→D, CG→A }
Bước 2: Loại bỏ những thuộc tính dư thừa F’ = { AB→ C, AC→D, D→E, D→G, G→B, A→D, CG→A }
AB→C: có B dư thừa vì A→D→G→B A→B [ B ẩn trong A] A C→D: có C dư thừa vì A→D
Bước 3: F’ = { A→ C, TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
A→D, D→E, D→G, G→B, A→D, CG→A }A→D: bỏ pth này vì trùng lắp Các pth A→ C; D→E; D→G; G→B; A→D; CG→A đều không bỏ được vì các thuộc tính C, E, G, B, D, A chỉ xuất hiện 1 lần bên vế phải.
Vậy F’ = { A→ C, D→E, D→G, G→B, A→D, CG→A } Là phủ tối thiếu của F.
- Phân rã? Dựa vào phủ tối thiểu F’ TK = { A, CD, CG } Bước 1, Bước 2: Không làm Bước 3: Q1[ AC ] với F1 = { A → C } Q2[ DE ] với F2 = { D→E } Q3[ DG ] với F3 = { D→G } Q4[ GB ] với F4 = { G→B } Q5[ AD ] với F5 = { A→D } Q6[ CGA ] với F6 = { CG→A } Bước 4: Vì có Q1 chứa khóa của Q nên không bổ sung.
\===============================================
ĐỀ SỐ 4
Câu II : Cho quan hệQ[GHIKLM] và tập các phụ thuộc hàm F = {GH→ L, I→M, L→K, HM→G, GK→I, H→L}
- Hãy xác đinh tất cả các khóa của Q
- Hãy cho biết Q có đạt 3NF không?
- Tìm phủ tối thiểu của F.
- Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.
HƯỚNG DẪN
- Tìm khóa? TN = { H } TG = {GIKLM } TN+F = { H }+F = HLK ≠ Q+
Xi TN U Xi [TN U Xi]+ Siêu khóa Khóa
ø H HLK
G HG HGLKIM = Q+ HG HG I HI HILMGK = Q+ HI HI K HK HKL L HL HLK M HM HMLKGI = Q+ HM HM GI HGI HGLKIM = Q+ HGI GK HGK HGLKIM = Q+ HGKGL HGL HGLKIM = Q+ HGL TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
H→L }Bước 2: Loại bỏ những thuộc tính dư thừa F’ = { GH→ L, I→M, L→K, HM→G, GK→I, H→L }
GH→L: có G dư thừa vì có H→L
Bước 3: F’ = { H→ L, I→M, L→K, HM→G, GK→I, H→L }
H→ L: bỏ pth này vì trùng lắp Các pth I→M; L→K; HM→G; GK→I; H→L đều không bỏ được vì các thuộc tính M, K, G, I, L chỉ xuất hiện 1 lần bên vế phải.
Vậy F’ = { I→M, L→K, HM→G, GK→I, H→L } Là phủ tối thiếu của F.
- Phân rã? Dựa vào phủ tối thiểu F’ TK = { HG, HI, HM } Bước 1, Bước 2: Không làm Bước 3: Q1[ IM ] với F1 = { I→M } Q2[ LK ] với F2 = { L→K } Q3[ HMG ] với F3 = { HM→G } Q4[ GKI ] với F4 = { GK→I } Q5[ HL ] với F5 = { H→L }
Bước 4: Vì có Q3 chứa khóa của Q nên không bổ sung.
\===============================================
ĐỀ SỐ 5
Câu II : Cho lược đồ quan hệ Q và tập phụ thuộc hàm F được cho như sau: Q[A,B,C,D,E,G,H,K,L,M,N], F={ C → D,E; G → H,K; A,G → L; M → A,N; A → B,C}
- Hãy xác đinh tất cả các khóa của Q
- Hãy cho biết Q có đạt 3NF không?
- Tìm phủ tối thiểu của F.
- Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.
HƯỚNG DẪN
- Tìm khóa? TN = { GM } TG = { AC } TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
Vậy Q có 1 khóa duy nhất là GM
- 3NF?
Xét pth: C → D,E, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF
- Phủ tối thiểu?
Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính F’ = { C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C }
Bước 2: Loại bỏ những thuộc tính dư thừa F’ = { C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C }
Bước 3: F’ = { C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C }
Các pth C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C đều không bỏ được vì các thuộc tính D, E, H, K, L, A, N, B, C chỉ xuất hiện 1 lần bên vế phải.
Vậy F’ = { C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C } Là phủ tối thiếu của F.
- Phân rã? Dựa vào phủ tối thiểu F’ TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
Bước 2: Loại bỏ những thuộc tính dư thừa F’ = { MAHV → HOTEN, MAHV → NGAYSINH, MAHV → MALOP, MALOP → NGAYKG, MALOP → TENLOP, MAMH → TENMH, MAMH → SOTIET, MAHV,MAMH → DIEMTHI, SOBL → MAHV, SOBL → SOTIEN }
Bước 3: F’ = { MAHV → HOTEN, MAHV → NGAYSINH, MAHV → MALOP, MALOP → NGAYKG, MALOP → TENLOP, MAMH → TENMH, MAMH → SOTIET, MAHV,MAMH → DIEMTHI, SOBL → MAHV, SOBL → SOTIEN }
Các pth MAHV → HOTEN, MAHV → NGAYSINH, MAHV → MALOP, MALOP → NGAYKG, MALOP → TENLOP, MAMH → TENMH, MAMH → SOTIET, MAHV,MAMH → DIEMTHI, SOBL → MAHV, SOBL → SOTIEN đều không bỏ được vì các thuộc tính HOTEN, NGAYSINH, MALOP, NGAYKG, TENLOP, TENMH, SOTIET, DIEMTHI, MAHV, SOTIEN chỉ xuất hiện 1 lần bên vế phải.
Vậy F’ = { MAHV → HOTEN, MAHV → NGAYSINH, MAHV → MALOP, MALOP → NGAYKG, MALOP → TENLOP, MAMH → TENMH, MAMH → SOTIET, MAHV,MAMH → DIEMTHI, SOBL → MAHV, SOBL → SOTIEN } Là phủ tối thiếu của F.
- Phân rã?
Dựa vào phủ tối thiểu F’ TK = { MAMH, SOBL } Bước 1, Bước 2: Không làm Bước 3: Q1[MAHV, HOTEN ] với F1 = { MAHV → HOTEN } Q2[MAHV, NGAYSINH ] với F2 = { MAHV → NGAYSINH } Q3[MAHV, MALOP ] với F3 = { MAHV → MALOP } Q4[MALOP, NGAYKG ] với F4 = { MALOP → NGAYKG } Q5[MALOP, TENLOP ] với F5 = { MALOP → TENLOP } TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate
Q6[MAMH, TENMH ] với F6 = { MAMH → TENMH } Q7[MAMH, SOTIET ] với F7 = { MAMH → SOTIET } Q8[MAHV,MAMH, DIEMTHI ] với F8 = { MAHV,MAMH → DIEMTHI } Q9[SOBL, MAHV ] với F9 = { SOBL → MAHV } Q10[SOBL, SOTIEN ] với F10 = { SOBL → SOTIEN }
Bước 4: Vì không có LĐQH con nào chứa 1 khóa của CSS nên bổ sung 1 khóa của CSS vào phân rã:
Q11[ MAMH, SOBL ], F11 = {ø}
\===============================================
ĐỀ SỐ 8
CÂU II :Cho lược đồ quan hệ HoaDon và tập các phụ thuộc hàm F như sau: HoaDon[SOHD, KHACH, NGAYLAP, MATHANG, DONGIA, SOLUONG] F={SOHD →KHACH, NGAYLAP, SOHD,MATHANG →DONGIA,SOLUONG}
- Tìm khóa cho Hoadon
- Hãy cho biết lược đồ quan hệ HoaDon có đạt dạng chuẩn nào? Tại sao?
- Nếu lược đồ chưa đạt dạng chuẩn 3 hãy phân rã thành các lược đồ con đạt dạng chuẩn 3, xác định khóa chính cho các lược đồ con này.]
HƯỚNG DẪN
- Tìm khóa? TN = { SOHD, MATHANG }
TG = { ø }
Vậy HoaDon có 1 khóa duy nhất là { SOHD, MATHANG }
- Tìm dạng chuẩn? 2NF: Tập thuộc tính không khóa: N = {KHACH, NGAYLAP, DONGIA, SOLUONG} Xét pht SOHD, MATHANG →KHACH Є F: có MATHANG dư thừa vì có SOHD→KHACH SOHD, MATHANG →KHACH là phụ thuộc hàm không đầy đủ. Vậy HoaDon không đạt 2NF. Dạng chuẩn của LĐQH HoaDon là 1NF
- Phân rã?
Phân rã thành các lược đồ con đạt dạng chuẩn 3: Bước 1, Bước 2: Không làm Bước 3: Q1[SOHD, KHACH] với F1 = { SOHD →KHACH }, có K1 = {SOHD} Q2[SOHD, NGAYLAP] với F2 = { SOHD → NGAYLAP }, có K2 = {SOHD} Q3[SOHD,MATHANG, DONGIA] với F3 = {SOHD,MATHANG →DONGIA}, có K3 = {SOHD, MATHANG} Q4[SOHD,MATHANG, SOLUONG] với F4 = {SOHD,MATHANG → SOLUONG}, có K4 = {SOHD, MATHANG} Bước 4: Vì có Q3 chứa khóa của Q nên không bổ sung. TranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslateTranslate