Bài giảng môn Cơ sở dữ liệu: Chương 9 - Thiết kế cơ sở dữ liệu quan hệ

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

125
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng môn Cơ sở dữ liệu: Chương 9 - Thiết kế cơ sở dữ liệu quan hệ bao gồm những nội dung về phụ thuộc hàm; bao đóng của tập PTH; kiểm tra PTH suy diễn; xác định khóa của lược đồ; tìm một khóa của lược đồ; xác định khóa cho quan hệ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng môn Cơ sở dữ liệu: Chương 9 - Thiết kế cơ sở dữ liệu quan hệ

THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ 1
Phụ thuộc hàm Định nghĩa 3.1: Xét lược đồ quan hệ gồm n thuộc tính – R(U), U={A1, A2,…, An} PTH giữa hai tập thuộc tính X, Y U – Ký hiệu: X  Y (đọc: X xác định hàm Y hay Y phụ thuộc hàm X) – r(R),  t1, t2  r nếu t1[X] = t2[X] thì t1[Y] = t2[Y]. – X là vế trái và Y là vế phải của PTH. Ví dụ 3.2 r(R) A B 1 4 r không thỏa A  B, nhưng thỏa B  A 1 5 3 7 NHANVIEN_PHONGBAN TenNV MaNV NgSinh Diachi MaPB TenPB TrPhong MaNV  TenNV MaNV  MaPB MaPB  {TenPB, TrPhong} 2
Bao đóng của tập PTH • Định nghĩa: Trên lược đồ quan hệ R; F là tập các PTH, cho XY là một PTH. - Ta nói rằng tập PTH F suy diễn logic X  Y ký hiệu F╞═ X  Y, nếu bất kỳ quan hệ r của R thỏa các phụ thuộc trong F thì cũng thỏa X  Y. • Định nghĩa: Bao đóng của tập PTH (Closure of FD) F là tập các phụ thuộc hàm được suy diễn logic từ F, ký hiệu là F+, nghĩa là: F+ = { X  Y | F ╞═ X  Y} 3
Bao đóng của tập PTH • F là tập PTH trên R – F = (MaNV  TenNV, MaPB  {TenPB, TrPhong}, MaNV  MaPB). – rR thỏa F và MaNV  {TenPB, TrPhong} cũng đúng với r thì MaNV {TenPB, TrPhong} gọi là được suy diễn từ F. • Bao đóng của F, ký hiệu F+, gồm – F và tất cả các PTH được suy diễn từ F. • F gọi là đầy đủ nếu F = F+. 4
Kiểm tra PTH suy diễn Cho F = {AB  C, A  D, D  E, AC  B} Hai PTH AB  E và D  C có được suy diễn từ F hay không? X XF+ AB ABCDE Được suy diễn từ F D DE Không được suy diễn từ F 5
Xác định khóa của lược đồ Thuật toán: Tìm một khóa tối thiểu của quan hệ Nhập: tập PTH F xác định trên lược đồ R(U) U = {A1, …, An}; Xuất: khóa K của R. Phương pháp : – Bước 0 : Đặt K0 = U – Bước i : Tính Ki –1 \ {Ai} nếu Ki-1 \ {Ai}  U Ki = Ki-1 nếu ngược lại – Đặt K = Kn 6
Ví dụ: Tìm khóa của lược đồ Cho R(U), U = {A, B, C, D, E, F, G}. – F = {B  A, D  C, D  BE, DF  G}. Tìm khóa của R – B1: K = ABCDEFG. – B2: • Lặp 1: (BCDEFG)F+ = BCDEFGA  K = BCDEFG. • Lặp 2: (CDEFG)F+ = CDEFGBA  K = CDEFG. • Lặp 3: (DEFG)F+ = DEFGCBA  K = DEFG. • Lặp 4: (EFG)F+ = EFG. • Lặp 5: (DFG)F+ = DFGCBEA  K = DFG. • Lặp 6: (DG)F+ = DGCBEA. • Lặp 7: (DF)F+ = DFCBEAG  K = DF. – B3: Khóa là K = DF. 7
Bài tập 1: Cho lược đồ quan hệ R(ABCDE) và tập phụ thuộc hàm: F = {A -> B; CD -> E; B -> C} - Tìm một khóa của lược đồ. 8
Tìm một khóa Áp dụng các bước tìm bao đóng của tập các thuộc tính: • Lặp 1: (BCDE)F+ = BCDE  K = ABCDE. • Lặp 2: (ACDE)F+ = ABCDE  K = ACDE. • Lặp 3: (ADE)F+ = ADEBC  K = ADE. • Lặp 4: (AE)F+ = AEBC  K = ADE. • Lặp 5: (AD)F+ = ADBCE  K = AD. AD là khoá. 9
Bài tập 2 Cho lược đồ quan hệ R(A,B,C,D,E,G,H,I,J,K) và tập các phụ thuộc hàm: F = {A -> B ; C -> DHI ; IJ -> K ; BC -> A ; HC -> E} Tìm một khóa của lược đồ. 10
Tìm một khóa của lược đồ Áp dụng các bước tìm bao đóng của tập các thuộc tính: • Lặp 1: (BCDEGHIJK)F+ = R  K = BCDEGHIJK • Lặp 2: (CDEGHIJK) F+  R  K = BCDEGHIJK • Lặp 3: (BDEGHIJK) F+  R  K = BCDEGHIJK • Lặp 4: (BCEGHIJK) F+ = R  K = BCEGHIJK. • Lặp 5: (BCGHIJK ) F+ = R  K = BCGHIJK • Lặp 6: (BCHIJK ) F+  R  K = BCGHIJK • Lặp 7: (BCGIJK ) F+= R  K = BCGIJK • Lặp 8: (BCGJK ) F+ = R  K = BCGJK • Lặp 9: (BCGK ) F+  R  K = BCGJK • Lặp 10: (BCGJ ) F+ = R  K = BCGJ 11
Xác định khóa cho quan hệ Bước 1: Xác định - tập thuộc tính nguồn (là thuộc tính chỉ xuất hiện ở vế phải của tất cả các phụ thuộc hàm thuộc F) - tập thuộc tính đích (là thuộc tính chỉ xuất hiện ở vế phải của tất cả các phụ thuộc hàm thuộc F) - tập thuộc tính trung gian (là thuộc tính xuất hiện ở cả 2 vế của tất cả các phụ thuộc hàm thuộc F Bước 2: 12
Xác định khóa cho quan hệ Bước 2: Lập bảng Xi U N (Xi U N)+ Siêu khóa Khóa Các tổ Xác định Xác hợp có xem định thể xây Xi U N khóa dựng từ có phải là (siêu tập siêu khóa khóa trung hay không nhỏ gian Xi nhất) Xi là tập con của tập trung gian (2n phần tử) 13
Ví dụ: Cho lược đồ quan hệ R(A,B,C,D,E) và tập các phụ thuộc hàm: F = { AB -> C; AB -> D; D -> A; BC -> D ; BC -> E} Xác định tất cả các khóa cho quan hệ 14
Xác định khóa cho quan hệ Bước 1: Xác định - tập thuộc tính nguồn {B} (là thuộc tính chỉ xuất hiện ở vế trái của tất cả các phụ thuộc hàm thuộc F) - tập thuộc tính đích {E} (là thuộc tính chỉ xuất hiện ở vế phải của tất cả các phụ thuộc hàm thuộc F) - tập thuộc tính trung gian {A,C,D} (là thuộc tính xuất hiện ở cả 2 vế của tất cả các phụ thuộc hàm thuộc F) Bước 2: 15
Xác định khóa cho quan hệ Bước 2: Lập bảng Xi Xi U N (Xi U N)+ Siêu khóa Khóa  B - - - A BA U SK K C BC U SK K D BD U SK K AC BAC U SK - AD BAD U SK - CD BCD U SK - ACD BACD U SK - Vậy AB, BC, BD là khóa của quan hệ R 16
Bài tập: Cho lược đồ quan hệ R(A,B,C,D,E,G,H,T,V,X,Y,Z) và tập các phụ thuộc hàm: F = { AB -> HXGC; BH -> V; GC -> Y; D -> CGZ ; E -> ABT} a. Tìm một khóa của quan hệ R b. Tìm tất cả các khóa của quan hệ R 17