Giáo trình Nhập môn cơ sở dữ liệu - Phạm Thị Thanh

ác cbgd SELECT TênCB,môn dạy, tênKH FROM cbgd, khoa WHERE cbgd.Mah= khoa.MaKH Ánh xạ lồng: Trong câu lệnh tìm kiếm có các khối lồng nhau theo nhiều mức lồng nhau. Tức là trong biểu thức điều kiện của khối này lại chứa một khối khác VD: SELECT * FROM sv WHERE MaL IN (SELECT MaL FROM lop WHERE TenL=’D2 Công nghệ’) Các từ khoá ALL, SOME, ANY trong SQL luôn đi kèm một câu hỏi con mà câu hỏi con này trả ra kết quả chỉ là một cột. VD: Tìm sinh viên nhỏ tuổi hơn mọi sinh viên lớp T13B SELECT TenSV FROM sv WHERE NS>ALL (SELECT NS FROM sv WHERE MaL=’T13B’ (Ánh xạ lồng chỉ lấy được thông tin từ một quan hệ mà điều kiện thuộc về 1 quan hệ khác, chứ không lấy được thông tin ở cả hai quan hệ) Các phép toán tập hợp Trong SQL-92 có các phép UNION, INTERSECT, EXCEPT thao tác trên các quan hệ tương ứng với phép hợp, giao và trừ của đại số quan hệ. Các quan hệ tham gia trong phép toán này phải khả hợp. Các phép toán này tự động loại bỏ các bộ trùng nhau. VD1: Xét CSDL QLDAYHOC nói trên giả sử có thêm quan hệ hoc (MaCB, TenCB, trinhđộ, chuyennganh) chứa thông tin về việc đi học của cbgd. Ta cần MaCB, TenCB của những cán bộ đi học trình độ Tiến sỹ và dạy môn CSDL (SELECT MaCB, TenCB FROM cbgd WHERE Monday=’CSDL’) INTERSECT (SELECT MaCB, TenCB FROM hoc WHERE trinhdo=’Tiến sỹ’) VD2: Cho biết MaCB, TenCB của những cán bộ đi học trình độ Tiến sỹ hoặc dạy môn CSDL (SELECT MaCB, TenCB FROM cbgd WHERE Monday=’CSDL’) UNION (SELECT MaCB, TenCB FROM hoc WHERE trinhdo=’Tiến sỹ’) VD3: Cho biết MaCB, TenCB của những cán bộ đi học trình độ Tiến sỹ nhưng không dạy môn CSDL (SELECT MaCB, TenCB FROM hoc WHERE trinhdo=’Tiến sỹ’) EXCEPT (SELECT MaCB, TenCB FROM cbgd WHERE Monday=’CSDL’) Kết chương Chương II đã giới thiệu một số ngôn ngữ thao tác dữ liệu như đại số quan hệ, ngôn ngữ tân từ và đặc biệt là ngôn ngữ hỏi có cấu trúc SQL có khuôn dạng và ví dụ cụ thể. Câu hỏi và bài tập Câu 1: Nêu các khái niệm cơ bản của mô hình quan hệ: Thuộc tính, Lược đồ quan hệ, Miền trị, Quan hệ, Khóa, Khóa kết nối. Câu 2: Khái niệm khả hợp Bài tập: Bài 1: Cho 3 quan hệ r1(A B C) r2 (D F) r3 (B E D) a1 b1 c1 d1 f1 b1 e1 d1 a2 b2 c2 d2 f2 b2 e2 d2 a1 b1 c3 d3 f3 b3 e3 d1 a2 b3 c1 r4 (A B C D) r5(C D) a b c d c d a b e f e f b c e f e d c d e d e f a b d e Tính các biểu thức sau: a) r1xr2 b)r1*r3 c)dD=d1(r1*r3) d)r1*r2*r3 e) PBC(r1*r2*r3) f) r4:r5 Bài 2: Cho CSDL gồm các lược đồ sau: congty(MaCT, TenCT, DC, DT) mathang(MaMH, TenMH, Mau, TrongLuong) sanpham(MaCT, MaMH, Soluong) Trả lời các câu hỏi sau bằng ngôn ngữ đại số quan hệ Tìm MaCT của những công ty đã cung cấp mặt hàng có mã là P2 Tìm MaCT của những công ty cung ứng ít nhất 1 mặt hàng mầu đỏ Tìm MaMH của những mặt hàng do công ty có tên SamSung cung cấp Tìm MaMH những mặt hàng chưa được công ty nào cung ứng Tìm TenCT đã cung cấp mặt hàng có tên là “Notebook” Bài 3: Cho CSDL gồm các lược đồ sau: nhanvien (ma_nv, ho_ten, ng_sinh, gioi_tinh, ma_dv, luong) phong (ma_dv, ten_phong, ma_tp) dd_dvi(ma_dv, dia_diem) du_an(ma_da, ten_da, dd_du_an, ma_dv) chamcong(ma_nv, ma_da, so_gio) Trả lời các câu hỏi bằng đại số quan hệ Tìm tên dự án có mã số D4 Cho biết họ tên và lương của những nhân viên làm việc ở phòng ‘Nghiên cứu và phát triển’ Với mỗi dự án thực hiện ở Ninh Bình, hãy cho biết mã số dự án đồng thời, cho biết họ tên, ngày sinh của trưởng phòng quản lý dự án này Tìm tên những nhân viên làm việc cho tất cả các dự án do phòng có mã P4 quản lý Tìm mã số những dự án có sự tham gia của một người lãnh đạo phòng trực tiếp quản lý dự án này Bài 4: Cho CSDL về các khách sạn gồm các lược đồ sau: Khach_san(ma_ks, ten_ks, dia_chi) Phong(ma_ph, ma_ks, loai, gia) Dat_phong(ma_ks, ma_khach, tu_ngay, den_ngay, ma_ph) Khach(ma_khach, ho_ten, dia_chi) Hãy viết các biểu thức đại số quan hệ tương ứng với mỗi câu hỏi sau: Cho biết tên tất cả các khách sạn Liệt kê tất cả các phòng có giá dưới 200.000 đ Cho biết giá và loại của tất cả các phòng thuộc khách sạn Sao mai Liệt kê họ tên của tất cả các khách đã đặt thuê phòng ở khách sạn Sao mai Cho biết thông tin chi tiết về các phòng của khách sạn Sao mai với những phòng đang có người đặt thuê thì cho biết cả họ tên và địa chỉ của khách. Bài 5: Xét CSDL gồm các lược đồ quan hệ sau: Nhan_vien (ht_nv, duong_pho, thanh_pho) Lam_viec (ht_nv, ten_cty, luong) Cong_ty(ten_cty, thanh_pho) Quan_ly(ht_nv, ten_thu_truong) Hãy biểu diễn các câu hỏi sau bằng ngôn ngữ đại số quan hệ. Tìm họ tên và thành phố sinh sống của tất cả các nhân viên làm việc cho công ty FBC Tìm họ tên, tên đường phố, thành phố sinh sống của tất cả các nhân viên làm việc cho FBC có lương lớn hơn 2triệu. Tìm tất cả nhân viên trong CSDL sinh sống cùng thành phố của công ty nơi họ làm việc Tìm tất cả nhân viên trong CSDL sống trong cùng thành phố và trong cùng phố với thủ trưởng của họ Tìm tất cả các nhân viên không làm việc cho FBC Tìm tất cả các nhân viên có lương cao hơn mọi nhân viên của công ty FBC Giả sử các công ty được đặt tại nhiều thành phố. Tìm tất cả các công ty đặt tại mọi thành phố nơi có mặt công ty FBC Tìm tất cả các nhân viên có lương cao hơn lương trung bình của mọi nhân viên công ty của họ Tìm công ty có nhiều nhân viên nhất Tìm công ty có quỹ tiền lương nhỏ nhất Tìm các công ty mà nhân viên đều có lương trung bình cao hơn lương trung bình tại FBC Bài 6: Cho csdl gồm các lược đồ quan hệ sau: tacgia(MaTG, TenTG, Dt) nxb(MaNXB, TenNXB, Dc, dt) sach(MaS, TenS, NamXB, Slg, MaTG, MaNXB) Trả lời các câu hỏi sau bằng ngôn ngữ SQL Cho biết tên cuốn sách xuất bản năm 2007 Cho biết Mã sách, tên sách xuất bản năm 2007 và số lượng xuất bản trên 1000 cuốn Tên cuốn sách xuất bản năm 2000 của NXB GD Xoá tác giả “Nguyễn Văn Thành” trong CSDL trên Thêm nhà xuất bản có mã “NB”, tên là “nhà xuất bản Ninh Bình”, Dc là “TP Ninh Bình”, dt là 0303888888) Sửa Dt của tác giả có mã TT07 thành 0983.98.98.98 Bài 7: Cho CSDL gồm các lược đồ quan hệ sau: truong(MaTr, TenT, DC, DT, Hieu truong) khoa(MaTr, MaKh, TenKh, SoSV) sinhvien(MaTr, MaKH, MaSV, TenSV, QQ) Trả lời bằng Ngôn ngữ SQL Cho biết tên trường ĐH có khoa CNTT Tổng số SV khoa CNTT ở tất cả các trường ĐH Khoa nào của trường nào có số SV đông nhất Tên Tr có tổng số SV đông nhất Bài 8: Cho CSDL gồm các lược đồ quan hệ: nhanvien (MaNV, HoTen, NgaySinh, MaPhong) phong (MaPhong, TenPhong, DiaDiem, Sodt) du_an(MaDA, TenDA, NganSach) thamgia(MaNV, MaDA, SoGioThamGia) Biểu diễn các câu tìm kiếm trên bằng Đại số quan hệ và ngôn ngữ SQL Đưa ra danh sách (họ tên, ngày sinh) của các nhân viên tham gia Dự án có tên là đào tạo từ xa hoặc tham gia dự án có tên là QLTC Đưa ra danh sách (tên phòng, địa điểm) của phòng có nhân viên mã số là ‘NV03’ làm việc Cho biết danh sách (họ tên, ngày sinh, mãPh) của các nhân viên tham gia vào dự án Cho biết có bao nhiêu dự án có ngân sách lớn hơn 100.000.000 Bài 9: Xét CSDL gồm các lược đồ quan hệ sau: Nhan_vien (ht_nv, duong_pho, thanh_pho) Lam_viec (ht_nv, ten_cty, luong) Cong_ty(ten_cty, thanh_pho) Quan_ly(ht_nv, ten_thu_truong) Hãy biểu diễn các câu hỏi sau bằng ngôn ngữ SQL. Tìm họ tên và thành phố sinh sống của tất cả các nhân viên làm việc cho công ty FBC Tìm họ tên, tên đường phố, thành phố sinh sống của tất cả các nhân viên làm việc cho FBC có lương lớn hơn 2triệu. Tìm tất cả nhân viên trong CSDL sinh sống cùng thành phố của công ty nơi họ làm việc Tìm tất cả nhân viên trong CSDL sống trong cùng thành phố và trong cùng phố với thủ trưởng của họ Tìm tất cả các nhân viên không làm việc cho FBC Tìm tất cả các nhân viên có lương cao hơn mọi nhân viên của công ty FBC Giả sử các công ty được đặt tại nhiều thành phố. Tìm tất cả các công ty đặt tại mọi thành phố nơi có mặt công ty FBC Tìm tất cả các nhân viên có lương cao hơn lương trung bình của mọi nhân viên công ty của họ Tìm công ty có nhiều nhân viên nhất Tìm công ty có quỹ tiền lương nhỏ nhất Tìm các công ty mà nhân viên đều có lương trung bình cao hơn lương trung bình tại FBC CHƯƠNG III: THIẾT KẾ MỘT CƠ SỞ DỮ LIỆU 1. Mục đích thiết kế CSDL Mục đích chính của thiết kế CSDL là nhóm các thuộc tính vào các bảng sao cho giảm được nhiều nhất sự dư thừa dữ liệu bởi vậy giảm được không gian lưu trữ cần thiết cho các quan hệ cơ sở. Nếu để dư thừa dữ liệu sẽ nảy sinh một số vấn đề. Ta xét ví dụ sau: Để lưu các thông tin về sinh viên trong một khoa với nhiều lớp ta có 2 phương án khác nhau như sau: Phương án a: dùng một lược đồ sinhvien_lop(svid, hoten, ns, qq, diachi, lopid, tenlop, nganhhoc, khoahoc) Phương án b: dùng 2 lược đồ sinhvien(svid, hoten, ns, qq, diachi) và lop(lopid, tenlop, nganhhoc, khoa) Ta nhận thấy ở phương án a các thông tin về lớp bị lặp lại rất nhiều lần khi sinh viên thuộc cùng một lớp. Trong khi ở phương án b thông tin về mỗi lớp được thể hiện là một bộ trong quan hệ lop và trong quan hệ sinhvien chỉ lopid là lặp lại với một số bộ. Khi thao tác dữ liệu sẽ xảy ra một số dị thường sau Ví dụ: quan hệ lop Lopid Tenlop Nganhhoc Khoa 1 T14A Hoá sinh Tự nhiên 2 T14B Tin Công nghệ 3 T14C Văn sử Xã hội Quan hệ sinhvien Svid Hoten Ns Qq Diachi lopid T14A1 Phạm Thị Mai 1/12/1988 Kim Sơn Chính Tâm, KS 1 T14A2 Trần Văn Giang 4/5/1989 Nho quan Gia Sinh, NQ 1 T14B1 Lê Văn Chính 3/3/1988 Yên Khánh Khánh Nhạc, YK 2 T14B2 Phạm Thu Thuỷ 7/4/1989 Hoa Lư Ninh Hoà, HL 2 Quan hệ sinhvien_lop Svid Hoten Ns Qq Diachi lopid Tenlop Nganhhoc khoa T14A1 Phạm Thị Mai 1/12/1988 Kim Sơn Chính Tâm, KS 1 T14A Hoá sinh Tự nhiên T14A2 Trần Văn Giang 4/5/1989 Nho quan Gia Sinh, NQ 1 T14A Hoá sinh Tự nhiên T14B1 Lê Văn Chính 3/3/1988 Yên Khánh Khánh Nhạc, YK 2 T14B Tin Công nghệ T14B2 Phạm Thu Thuỷ 7/4/1989 Hoa Lư Ninh Hoà, HL 2 T14B Tin Công nghệ Dị thường thêm bộ: Có 2 loại dị thường thêm bộ Khi thêm sinh viên mới vào lớp thì tất cả các bộ mới thêm đều phải có thông tin về lớp chẳng hạn thêm sinh viên vào lớp có mã lớp = 2 thì tất cả các bộ thêm vào đều phải có tên lớp = T14B, ngành học Tin, khoá hoc 2007-2010, nếu điều kiện này không thoả mãn thì tính nhất quán bị phá vỡ. Trong trường hợp dùng 2 bảng thì ta chỉ cần lopid mà không phải quan tâm đến vấn đề khác. Khi cần thêm lớp mới mà lớp này chưa có sinh viên nào thì ta phải bỏ trống các trường thông tin về sinh viên, tuy nhiên điều đó là không chấp nhận được vì ít nhất svid là khoá chính không được phép null, nếu dùng 2 bảng thì ta chỉ cần thêm vào bảng lop là xong. Dị thường xoá bộ: Nếu ta xoá một bộ nói về sinh viên duy nhất còn lại của lớp thì toàn bộ thông tin về lớp đó bị mất, khi dùng 2 bảng ta giải quyết được vấn đề đó. Dị thường sửa bộ: Khi ta muốn chuyển lớp sang khoa khác quản lý sẽ phải sửa tất cả các bộ có chứa sinh viên về lớp này, nếu dùng 2 bảng ta chỉ phải sửa một lần Tuy nhiên, việc tách thành nhiều bảng cần phải thoả điều kiện không làm mất thông tin và bảo toàn các ràng buộc quan trọng. 2. Phụ thuộc hàm (Function Defendency-FD) 2.1. Đặt vấn đề Phụ thuộc hàm là một khái niệm dùng để mô tả các ràng buộc dữ liệu trong một cơ sở dữ liệu chẳng hạn để chỉ ràng buộc mỗi giáo viên chỉ dạy một môn học: giáo viên -> môn dạy. 2.2. Định nghĩa phụ thuộc hàm Cho quan hệ R(U). X, Y là các tập con của U. Ta nói rằng Y phụ thuộc hàm vào X (hay X xác định Y), được viết X ® Y. Nếu " t1,t2 ÎR mà t1[X]=t2[X] thì t1[Y]=t2[Y] VD: Cho quan hệ sinhvien như sau: SVID Ho_ten NgaySinh QueQuan LopID C2701 Nguyễn Vân Anh 15/7/89 Hoa Lư T13B C2702 Hoàng Thị Bình 18/9/88 Yên Khánh T13B C2703 Trần Thị Tuyết 8/5/89 Kim Sơn T13B C2704 Lã Thị Vân 9/12/88 TP Ninh Bình T13B Trong ví dụ trên thì các thuộc tính Ho_ten, NgaySinh, QueQuan phụ thuộc hàm vào SVID. 2.3. Hệ tiên đề Amstrong Cho quan hệ R(U). X, Y, Z là tập con của U. Khi đó ta có A1: Tính phản xạ (reflexivity). Nếu YÍX thì X®Y A2: Tính tăng trưởng (Augmentation). Nếu X®Y thì XZ®YZ (XZ=XÈZ) A3: Tính bắc cầu (Transitivity): Nếu X®Y và Y®Z thì X®Z Tính phản xạ phát biểu rằng một tập hợp các thuộc tính luôn luôn xác định chính nó hoặc một tập con bất kỳ của nó. Vì A1 tạo ra các phụ thuộc luôn luôn đúng, những phụ thuộc như vậy được gọi là tầm thường. Một cách hình thức, một phụ thuộc hàm X®Y là tầm thường nếu XÉY, ngược lại, nó được gọi là không tầm thường. Tính tăng trưởng nói rằng việc thêm cùng một tập thuộc tính vào cả hai vế của một phụ thuộc hàm sẽ tạo ra một phụ thuộc hàm đúng đắn. Theo tính A3, các phụ thuộc hàm là bắc cầu. Chứng minh hệ tiên đề Armstrong, ta chứng minh bằng phản chứng dựa trên định nghĩa phụ thuộc hàm. A1: Giả sử X ÉY và 2 bộ t1 và t2 là các thể hiện quan hệ r của R sao cho t1[X]=t2[X]. Khi đó t1[Y] = t2[Y] bởi vì X ÉY, như vậy X®Y phải xảy ra trong r. A2: Giả sử X®Y đúng trong một thể hiện quan hệ r của R nhưng XZ®YZ không đúng. Khi đó có hai bộ t1 và t2 trong r sao cho: t1[X] = t2[X], t1[XZ] = t2[XZ] Þ t1[Z] = t2[Z] t1[Y] = t2[Y] Þt1[YZ] = t2[YZ], mẫu thuẫn với giả thiết. A3: Giả sử X®Y, Y®Z nhưng không có X®Z. t1,t2 là 2 bộ của r, khi đó t1[X] = t2[X] và X®Y nên t1[Y] = t2[Y] vì Y®Z nên t1[Z] = t2[Z], mẫu thuẫn với giả thiết. 2.4. Các luật suy ra từ hệ tiên đề Luật 1: L1: Luật hợp (Union): Nếu X®Y và X®Z thì X®YZ Luật 2: L2: Luật tựa bắc cầu (Pseudotransitivity): Nếu X®Y và YW®Z thì XW®Z Luật 3: L3: Luật tách (Decompisition): Nếu X® Y, ZÍY thì X®Z Sinh viên tự chứng minh các luật dựa theo các tích chất trong hệ tiên đề Amstrong. 2.5. Bao đóng của 1 tập phụ thuộc hàm Định nghĩa 1 phụ thuộc hàm được suy dẫn logic từ một tập phụ thuộc hàm: Cho quan hệ r(U), F là một tập phụ thuộc hàm phát biểu trên U. X, YÍU. X->Y Là một phụ thuộc hàm phát biểu trên U. Khi đó ta nói rằng phụ thuộc hàm X->Y được suy dẫn logic từ F nếu mỗi quan hệ r(U) được xác định trên U thoả F thì r cũng thoả X->Y Ký hiệu Định nghĩa bao đóng của 1 tập phụ thuộc hàm là một tập phụ thuộc hàm ký hiệu F+ = {X->Y | X->Y được suy dẫn logic từ F}. Việc tính toán bao đóng rất khó khăn và mất thời gian nên ta chỉ định nghĩa hình thức. Nếu F+ = F thì F được gọi là họ phụ thuộc hàm đầy đủ. VD Cho lược đồ quan hệ r(U) với U={A,B,C,D,E,F,G,H}. Và tập phụ thuộc hàm F={AB->C, C->DE, E->F, AF->H} + Hỏi phụ thuộc hàm AB->H có được suy dẫn logic từ F không? + Hỏi phụ thuộc hàm AB->GH có được suy dẫn logic từ F không? Trả lời: (Sử dụng các luật và các tính chất từ F để suy ra các phụ thuộc hàm đó. Nếu không suy ra được thì coi như không được suy dẫn logic từ F). + Vậy AB->H được suy dẫn lgic từ F + Trong các phụ thuộc hàm của F không có phụ thuộc hàm nào suy ra G nên AB-> G không được suy dẫn logic từ F 2.6. Bao đóng của 1 tập thuộc tính Cho lược đồ quan hệ R(U, F), XÍU, F là tập phụ thuộc hàm xác định trên U. Ta định nghĩa bao đóng của 1 tập thuộc tính X đối với tập phụ thuộc hàm F là tập thuộc tính được xác định như sau X+={A | (X®A ÎF+} Thuật toán tìm bao đóng của tập thuộc tính X Input: Lược đồ quan hệ R(U), Tập thuộc tính X là con của U Tập phụ thuộc hàm F xác định trên U Output: X+={A | X®A ÎF+} Action: Bước 1: Đặt X(0)=X Bước 2: Nếu $ (Y®Z) ÎF mà AÎZ và YÍXi-1 Nếu ngược lại Bước 3: Nếu Xi=Xi-1 thì dừng, Xi chính là X+ cần tìm VD1: Cho lược đồ quan hệ R(U, F) với U={A,B,C,D,E,F,G,H}. Và tập phụ thuộc hàm F={A®BC, B®E, CE®GH} Cho X=AD. Tìm bao đóng X+ Đặt X0=X=AD X1=ABD vì A®BC nên A®B X2=ABCD vì A®BC nên A®C X3=ABCDE vì B®E X4=ABCDEG vì CE®GH nên CE®G X5=ABCDEGH vì CE®GH nên CE®H X6=X5 dừng. Vậy X+=ABCDEGH VD2: Cho lược đồ quan hệ R(U, F) với U={A,B,C,D,E,G}. Và tập phụ thuộc hàm F= { AB®C, C®A, BC®D, D®EG, BE®C, CG®BD, ACD®B, CE ®AG } Cho X=BD. Tìm bao đóng X+ Đặt X0=X=BD X1=BDEG vì D®EG X2=BCDEG vì BE®C X3=ABCDEG vì C®A X4=X3 Vậy X+=ABCDEG Bổ đề: X®Y thì YÍX+ Sử dụng bổ đề để kiểm tra X®Y hay không Bước 1: Tính X+ Bước 2: Kiểm tra YÍX+ hay không đúng thì X®Y, sai thì X®Y VD3: Cho lược đồ quan hệ R(U, F) với U={A,B,C,D,E,G,H,I}. Và tập phụ thuộc hàm F={A®D, AB®E, BI®E, CD®I, E®C} X=AE ®I không? Tìm bao đóng X+ Đặt X0=X=AE X1=ADE vì A®D X2=ACDE vì E®C X3=ACDEI vì CD®I X4=X3 Vậy X+=ACDEI IÍX+ Vậy X®I 2.7. Định nghĩa khoá và siêu khoá theo ngôn ngữ phụ thuộc hàm Cho lược đồ quan hệ R(U, F), F là tập phụ thuộc hàm xác định trên U. K là một tập con của U (KÍU), Khi đó: + K được gọi là siêu khoá của R nếu K®U + K là khoá của R nếu K® U và "K’ ÍK thì K’®U Thuật toán tìm 1 khoá Input: Lược đồ quan hệ R(U, F), Tập thuộc tính U, Tập phụ thuộc hàm F={Ti®Pi | Ti,Pi ÍU, TiWPi =Æ, i=1n} Output: K là tập con của U sao cho K là khoá của R Action: Đặt P= ÈPi Bước 1: Đặt K0=U \ P (những thuộc tính không nằm trong vế phải FD) Bước 2: Nếu K0+ = U thì chuyển Bước 5 Bước 3: K1:=K0 È (T Ç P) Bước 4: Với mỗi Ai ÎTÇP ta thực hiện Tính Nếu (Ki-1\{Ai})+ = U Ngược lại Bước 5: Kết luận Ki là khoá VD1: Cho lược đồ quan hệ r(U) với U={A,B,C,D,E,F,G,H} F={A®BC,B®E,CE®GH} Tìm 1 khoá của R Đặt: P=BCEGH K0=U \ P = ADF Tính (K0)+ =ABCDEFGH Kết luận ADF là một khoá của R VD2: Cho lược đồ quan hệ R(U) với U={A,B,C,D,E,F,G,H} F={AB®CD, C®D, E®FG, AE®H} Tìm 1 khoá của R Đặt: P=CDFGH Tính :K0=U \ P =ABE, (ABE)+=U Kết luận ABE là khoá của R VD3:Cho lược đồ quan hệ R(U) với U={A,B,C} F={AB ®C, C®B} Tìm 1 khoá của R Đặt P=BC K0=A tính A+=A ¹ U K1=A È BC K2=AÈ B (AB)+ =ABC=U, vậy AB là một khoá của R VD4:Cho lược đồ quan hệ R(U) với U={A,B,C,D,E,G} F={AB ®C, G®A, C®B, ABD®E} Tìm 1 khoá của R Đặt P=ABCE K0=U \ P = DG tính DG+ = ADG ¹ U K1= DG È ABC K2= DGÈ AB, (ABDG)+ =ABCDEG = U vậy bỏ được C K3= DGÈ A, (ADG)+=ADG ¹ U, không bỏ được B, K3=K2 K4=DGÈ B, (BDG)+=ABCDEG=U vậy bỏ được A Kết luận BGD là một khoá của R. Thuật toán tìm mọi khoá của một quan hệ: Input: Lược đồ quan hệ R(U,F) Output: Tập KR tất cả các khoá của lược đồ R Ý tưởng: Thực hiện như thuật toán tìm một khoá nhưng thay đổi thứ tự bớt các thuộc tính Ai Giả mã: 1. Đặt T=ÈTi và P=ÈPi 2. KR:={K | K là khóa của lược đồ R(U,F) và K chứa trong siêu khóa (U\P) È(TÇP)} 3. For each K in KR do 4. For each (Ti®Pi) in F do 5. M:=TiÈ (K\Pi); 6. Test:=true; 7. for each H in KR do 8. if H Í M then test:=false; 9. If test then KR:= KR È {K | K là khóa của R(U,F) và K chứa trong T} 10. end (4) 11. end; (3) 12. Return KR VD1: Xét lại VD3 ở trên Cho lược đồ quan hệ R(U) với U={A,B,C} F={AB ®C, C®B} Tìm mọi khoá của R Đặt P=BC K0=A tính A+=A ¹ U K1=A È BC K2=AÈ B (AB)+ =ABC=U, bỏ được C, vậy AB là một khoá của R, K2’=AÈ C (AC)+=ABC=U, bỏ được B, vậy AC là một khoá của R Kết luận R có 2 khoá là AB và AC VD2: Xét lại VD4 ở trên Cho lược đồ quan hệ R(U) với U={A,B,C,D,E,G} F={AB ®C, G®A, C®B, ABD®E} Tìm mọi khoá của R Đặt P=ABCE K0=U \ P = DG tính DG+ = ADG ¹ U K1= DG È ABC K2= DGÈ AB, (ABDG)+ =ABCDEG = U vậy bỏ được C K3= DGÈ A, (ADG)+=ADG ¹ U, không bỏ được B, K3=K2 K4=DGÈ B, (BDG)+=ABCDEG=U vậy bỏ được A, DGB là một khoá của R K2’= DGÈ BC, (BCDG)+ =ABCDEG = U vậy bỏ được A K3= DGÈ C, (DGC)+=ABCDEG=U vậy bỏ được B, DGC là một khoá của R. Kết luận R có 2 khoá là DGB, DGC Chú ý: Thuật toán tìm mọi khóa cải tiến Input: Lược đồ quan hệ R(U, F), Tập thuộc tính U, Tập phụ thuộc hàm F={Ti->Pi | Ti,Pi ÍU, TiWPi =Æ, i=1n} Output: Mọi Ki là tập con của U sao cho Ki là khoá của R Action: Đặt P= ÈPi Bước 1: Đặt K0=U \ P (những thuộc tính không nằm trong vế phải FD) Bước 2: Nếu K0+ = U thì K0 là khóa duy nhất và kết thúc Bước 3: K1:=K0 Bước 4: Với mỗi Ai ÎTÇP ta thực hiện Tính Nếu (Ki-1)+ = U Ngược lại Bước 5: Kết luận các (Ki )+ là các khoá của lược đồ 2.8. Tập phụ thuộc hàm tối thiểu Các tập phụ thuộc hàm tương đương ? ĐN bao đóng của tập phụ thuộc hàm Hai phụ thuộc hàm gọi là tương đương nếu F+=G+ (nói cách khác F phủ G và G phủ F) Ký hiệu F~G Kiểm tra 2 tập phụ thuộc hàm có tương đương hay không + Lấy mỗi phụ thuộc hàm X®Y ÎF kiểm tra X®YÎG+ không? + Lấy mỗi phụ thuộc hàm X’®Y’ ÎG kiểm tra X’®Y’ÎF+ không? VD: Cho quan hệ r(U) với U={A,B,D,E,F,G} F={A®BC, D®E, AD®F} G={A®B, A®C, D®E, AD®F} Kiểm tra F~G? + Kiểm tra mỗi phụ thuộc hàm ÎG có thuộc F+ hay không Kiểm tra A®B, ta có A®BC nên A®B ÎF vậy A®B ÎF+ Kiểm tra A®C, ta có A®BC nên A®CÎF vậy A®C ÎF+ Kiểm tra D®E và AD®F đều thuộc F Vậy F phủ G + Kiểm tra mỗi phụ thuộc hàm ÎF có thuộc G+ hay không Kiểm tra A®BC, ta có A®B, và A®C nên A®BC ÎF vậy A®BC ÎG+ Kiểm tra D®E và AD®F đều thuộc F Vậy G phủ F Kết luận F~G Tập phụ thuộc hàm tối thiểu: Tập phụ thuộc hàm F được gọi là tối thiểu nếu nó thoả mãn 3 điều kiện sau: F không dư thừa phải ó mỗi phụ thuộc hàm của F đều không dư thừa phải ó mỗi phụ thuộc hàm của F có vế phải chỉ gồm 1 thuộc tính F không dư thừa phụ thuộc hàm ó không tồn tại phụ thuộc hàm dạng X®Y sao cho (F-{X->Y}+=F+ F không dư thừa trái ó mọi phụ thuộc hàm F không dư thừa trái. Dư thừa trái nghĩa là X®Y nếu $ AÎX mà (X-{A})® Y. Định lý: Mỗi tập phụ thuộc hàm F đều tương đương với 1 tập phụ thuộc hàm tối thiểu F’ nào đó. Khi đó F’ gọi là phủ tối thiểu của F Thuật toán: Tìm phủ tối thiểu của 1 tập phụ thuộc hàm Input: Cho lược đồ quan hệ R(U) Tập phụ thuộc hàm F (Li->Ri, i=1m) Output: Phủ tối thiểu F’ của F Action: 1. Xác định tập phụ thuộc hàm F1 ~ F. F1 không dư thừa phải. Nếu tồn tại phụ thuộc hàm dạng X®A1A2..An thì ta tách thành phụ thuộc hàm dạng X ®A1, X®A2,....X,®An 2. Xác định tập phụ thuộc hàm F2 ~ F1. F2 không dư thừa phụ thuộc hàm. Bước 2.0: Đặt F0=F1 nếu Fi-1\Li®Ri~ Fi-1 Bước 2.i: Tính nếu ngược lại Bước 3: Xác định tập phụ thuộc hàm F3~ F2 không dư thừa trái. Bước 3.0: Đặt F0=F2 Bước 3.i: Tính nếu $ZiÌLi sao cho Fi-1\{Li®Ri} È {Zi®Ri} ~Fi-1 Nếu ngược lại VD1: Cho lược đồ quan hệ r(U), U={A,B,C,D,E,F,G} F={A®BC, D®E, AD®F} Tìm phủ tối thiểu của F + Xác định F1~F, F1 không dư thừa phải F1={A®B, A®C, D®E, AD®F} + Xác định F2 ~ F1 không dư thừa phụ thuộc hàm B0: Đặt F0=F1={A®B, A®C, D®E, AD®F} B1: Bỏ A®B, A+=AC, không chứa B ®không bỏ được Bỏ A®C, A+=AB, không chứa C ®không bỏ được Bỏ D®E, không bỏ được Bỏ AD®F, không bỏ được F2=F1 + Xác định F3~F2, F3 không dư thừa trái B0: Đặt F0=F2={A®B, A®C, D®E, AD®F} B1: Chỉ phụ thuộc hàm AD®F là có nhiều hơn 1 thuộc tính ở vế phải của phụ thuộc hàm. Ta bỏ A, kiểm tra D®F, D+ = DE không chứa F, nên không bỏ được Ta bỏ D, kiểm tra A®F, A+=ABC không chứa F, nên không bỏ được Kết luận: F’={A®B, A®C, D®E, AD®F} VD2: Cho lược đồ quan hệ R(U, F), U={A,B,C,D,E,F,G,H} F={A®CD, C®D, EG®F, B®H, E®G}, tìm phủ tối thiểu của F + Xác định F1~F, F1 không dư thừa phải F1={A®C, A®D, C®D, EG®F, B®H, E®G} + Xác định F2 ~ F1 không dư thừa phụ thuộc hàm B0: Đặt F0=F1={A®C, A®D, C®D, EG®F, B®H, E®G} B1: Bỏ A®C, A+=AD, không chứa C -> không bỏ được Bỏ A®D, A+=CD chứa D, nên bỏ được FD A®D Bỏ C®D, không bỏ được Bỏ EG®F, không bỏ được Bỏ B®H, không bỏ được Bỏ E®G, không bỏ được F2={A®C, C®D, EG®F, B®H, E®G} + Xác định F3~F2, F3 không dư thừa trái Xét FD EG®F, bỏ E, G+=G không chứa F nên không bỏ được bỏ G, E+=EGF chứa F nên bỏ được G F3={A®C, C®D, E®F, B®H, E®G} Kết luận F’={A®C, C®D, E®F, B®H, E®G} VD3: Cho lược đồ quan hệ R(U, F), U={A,B,C,D,E,F,G,H} F={AEF®CD, A®GH, EF®B, G®H}, tìm phủ tối thiểu của F + Xác định F1~F, F1 không dư thừa phải F1={AEF®C, AEF®D, A®G, A®H, EF®B,G®H} + Xác định F2 ~ F1 không dư thừa phụ thuộc hàm F2={AEF®C, AEF®D, A®G, EF®B,G®H} + Xác định F3~F2, F3 không dư thừa trái F3=F2={AEF®C, AEF®D, A®G, EF®B,G®H} Kết luận F’={AEF®C, AEF®D, A®G, EF®B,G®H} 3. Phép tách các lược đồ quan hệ 3.1. Khái niệm phép tách + Cho lược đồ quan hệ R(U). Tập các lược đồ r=(R1(U1), R2(U2),, Rn(Un)) được gọi là phép tách của R nếu U1ÈU2ÈÈUn=U Giả sử trên U có tập phụ thuộc hàm F, với ZÍU, hình chiếu F lên Z, ký hiệu ÕZ(F), được xác định như sau: ÕZ(F)={(X®Y)ÎF+ | XYÍZ} khi đó ta ký hiệu phép chiếu F lên mỗi Ui là Fi, khi đó phép tách lược đồ R(U, F) như trên có thể viết là R1(U1, F1), R2(U2,F2),, Rn(Un,Fn)) và ký hiệu Ã=(R1, R2,, Rn) + Mục đích của phép tách là tránh dư thừa dữ liệu, tránh trùng lặp dị thường, nhất quán dữ liệu. + VD Cho lược đồ quan hệ BANHANG (TênNCC, Địa chỉ, Sphẩm, giá) và tập phụ thuộc hàm F={TênNCC®địa chỉ; TênNCC, sphẩm®giá}. Khi đó ta có thể tách lược đồ quan hệ BANHÀNG thành 2 lược đồ quan hệ là NCC (TênNCC,Địa chỉ) tập phụ thuộc hàm FNCC = TênNCC®địa chỉ và SẢNPHẨM (TênNCC,Sphẩm,giá) , Fsanpham={TênNCC, sphẩm®giá} 3.2. Phép tách kết nối không tổn thất + ĐN: Phép tách R thành {R1,R2,Rn} gọi là tách kết nối không tổn thất (tách không mất thông tin - Lossless Join Decomposition – LJ) đối với tập phụ thuộc hàm F, nếu mỗi quan hệ r trên R thoả F, ta đều có r=r1*r2*.*rn, trong đó ri = ÕUi(r) (ri là kết quả phép chiếu r trên Ui) + Tính chất không mất mát thông tin là cần thiết khi ta cần khôi phục quan hệ ban đầu từ các quan hệ đã tách Kiểm tra tính kết nối không tổn thất của 1 phép tách Input: Tập hữu hạn các thuộc tính U={A1, A2,..An}, tập phụ thuộc hàm F trên U và phép tách r={U1, U2,..Uk}, Output: Kết luận r có phải