Bài giảng môn Cơ sở dữ liệu - Chương 4: Ràng buộc toàn vẹn (RBTV)

37 trang ngocly 3240

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Cơ sở dữ liệu - Chương 4: Ràng buộc toàn vẹn (RBTV)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_mon_co_so_du_lieu_chuong_4_rang_buoc_toan_ven_rbtv.pdf

Nội dung text: Bài giảng môn Cơ sở dữ liệu - Chương 4: Ràng buộc toàn vẹn (RBTV)

CƠ SỞ DỮ LIỆU ( Databases ) Ch ươ ng 4: Ràng bu ộc toàn v ẹn (RBTV) bangtqh@utc2.edu.vn Nội dung 1. Các v ấn đề liên quan đế n RBTV 2. Các lo ại RBTV 3. Ph ụ thu ộc hàm 4. Khóa 5. Bài t ập bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 2
4.1.1. Đị nh nghĩa RBTV Ràng bu ộc toàn vẹn (RBTV ) là điều ki ện không đượ c vi ph ạm trong CSDL. RBTV còn đượ c gọi là các quy tắc qu ản lý (Rules ) đượ c áp đặ t lên các đố i tượ ng của th ế gi ới th ực. Trong 1 CSDL, các RBTV đượ c xem nh ư 1 công cụ để di ễn đạ t ng ữ ngh ĩa của CSDL đó. Trong quá trình khai thác CSDL, các RBTV ph ải đượ c th ỏa mãn nh ằm đả m bảo cho CSDL luôn ở tr ạng thái an toàn và nh ất quán. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 3 4.1.1. Đị nh nghĩa RBTV (tt) Đị nh ngh ĩa: – RBTV là m ột quy t ắc đị nh ngh ĩa trên m ột ho ặc nhi ều quan hệ do môi tr ườ ng ứng d ụng quy đị nh Đó chính là quy t ắc để đả m b ảo tính nh ất quán c ủa d ữ li ệu –Mỗi RBTV đượ c đị nh ngh ĩa b ằng 1 thu ật toán trong CSDL. Ví d ụ: – R1: M ỗi Nhân viên có 1 mã s ố duy nh ất để phân bi ệt v ới nhân viên khác – R2: M ỗi đề án ph ải do 1 Phòng/Ban nào đó ch ủ trì – R3: M ỗi nhân viên có th ể tham gia nhi ều đề án khác nhau – R4: M ỗi nhân viên có nhi ều ho ặc không có thân nhân nào bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 4
4.1.1. Đị nh nghĩa RBTV (tt) Khóa nội, Khóa ngo ại, NOT NULL là nh ững RBTV về mi ền giá tr ị của thu ộc tính trong quan hệ Hệ qu ản tr ị CSDL có cơ ch ế tự độ ng ki ểm tra các RBTV về mi ền tr ị của Khóa nội, Khóa ngo ại, NOT NULL qua khai báo cấu trúc của bảng. Các RBTV đượ c ki ểm tra ngay khi th ực hi ện 1 thao tác cập nh ật CSDL (Thêm, Sửa, Xóa ) Thao tác c ập nh ật CSDL ch ỉ đượ c xem là h ợp l ệ n ếu nó không vi ph ạm RBTV nào. Nếu vi ph ạm RBTV, h ệ th ống s ẽ h ủy b ỏ thao tác c ập nh ật (ho ặc h ệ th ống s ẽ có 1 x ử lý thích h ợp nào đó) bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 5 4.1.1. Đị nh nghĩa RBTV (tt) Nh ư v ậy: Ph ươ ng pháp ki ểm tra RBTV – Ki ểm tra t ự độ ng (qua khai báo c ủa c ấu trúc b ảng) – Thông qua nh ững th ủ t ục ki ểm tra và x ử lý vi ph ạm RBTV (do ng ườ i phân tích thi ết k ế cài đặ t) Th ời điểm ki ểm tra RBTV – Ngay sau khi th ực hi ện thao tác c ập nh ật CSDL – Ki ểm tra đị nh k ỳ ho ặc độ t xu ất bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 6
4.1.2. Điều ki ện c ủa RBTV Là s ự mô t ả và bi ểu di ễn hình th ức n ội dung c ủa nó Có th ể đượ c bi ểu di ễn b ằng: – Ngôn ng ữ t ự nhiên – Thu ật gi ải (b ằng mã gi ả - Pseudo Code, ngôn ng ữ t ựa Pascal) – Ngôn ng ữ đạ i s ố t ập h ợp, đạ i s ố quan h ệ – Các ph ụ thu ộc hàm bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 7 4.1.2. Điều ki ện c ủa RBTV (tt) Ví d ụ: Cho CSDL qu ản lý hóa đơ n bán hàng g ồm các b ảng: HOADON(SoHD, SoMatHang, Tongtien) DMHANG(MaH, TenH, DvTinh) CHITIETHD(SoHD, MaH, SL, Dongia, Thanhtien) R1 : Mỗi hóa đơ n có 1 s ố hóa đơ n riêng bi ệt, không trùng v ới hóa đơ n khác R2 : S ố m ặt hàng b ằng s ố b ộ c ủa c ủa chi ti ết hóa đơ n có cùng số hóa đơ n R3:Tổng các thành ti ền của các mặt hàng trong CHITIETHD có cùng số hóa đơ n ph ảib ằng Tổng ti ền ghi trong HOADON R4:Mỗi bộ của chi ti ết hóa đơ n ph ải có Mã Hàng thu ộc về Danh mục hàng. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 8
4.1.2. Điều ki ện c ủa RBTV (tt) Ví d ụ - Bi ểu di ễn b ằng đạ i s ố t ập h ợp R1: ∀ hđ1, h đ2 ∈ HOADON , hđ1 ≠ hđ2 ⇒ hđ1.SoHD ≠ h đ2.SoHD. R2: ∀ hđ ∈ HOADON thì: ⇒ hđ.SoMatHang = COUNT (cth đ ∈ CHITIETHD , cth đ.SoHD = h đ.SoHD) R3: ∀ hđ ∈ HOADON thì: hđ.Tongtien = SUM (cth đ.Thanhtien) đố i v ới các cth đ ∈ CHITIETHD sao cho: cth đ.SoHD= h đ.SoHD. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 9 4.1.2. Điều ki ện c ủa RBTV (tt) Ví d ụ - Bi ểu di ễn b ằng đạ i s ố t ập hợp (tt) R4: CHITIETHD [MaH] ∈ DMHANG [MaH] ho ặc bi ểu di ễn b ằng cách khác ∀ cth đ ∈ CHITIETH D, ∃ hh ∈ DMHANG sao cho: cth đ.MaH=hh.MaH. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 10
4.1.3. Bối c ảnh c ủa RBTV Bối c ảnh có th ể đị nh ngh ĩa trên một quan h ệ c ơ s ở hay nhi ều quan h ệ c ơ s ở. Đó là nh ững quan h ệ mà RBTV áp d ụng trên đó Ví d ụ: – R1: có bối cảnh là 1 quan hệ HOADON – R2, R3: có bối cảnh là 2 quan hệ HOADON và CHITIEHD – R4: có bối cảnh là 2 quan hệ CHITIETHD và DMHANG bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 11 4.1.4. Tầm ảnh hưởng c ủa RBTV Một RBTV có th ể liên quan đế n m ột s ố quan h ệ, chi khi có thao tác c ập nh ật (Thêm, S ửa, Xóa) m ới xu ất hi ện nguy c ơ vi ph ạm RBTV Cần ph ải xác đị nh rõ khi nào d ẫn đế n vi ệc ki ểm tra RBTV Trong quá trình phân tích, thi ết k ế m ột CSDL, ng ườ i phân tích ph ải lập b ảng xác đị nh t ầm ảnh h ưở ng cho mỗi RBTV nh ằm xác đị nh khi nào ph ải ti ến hành ki ểm tra các RBTV đó bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 12
4.1.4. T ầm ảnh h ưởng c ủa RBTV (tt) Bảng xác đị nh t ầm ảnh hưở ng –Gồm 4 c ột: •Cột 1: Tên các b ảng (quan h ệ) có liên quan đế n RBTV •Cột 2, 3, 4: Ứng v ới các thao tác Thêm/S ửa/Xóa 1 b ộ – Đánh d ấu (+) tại ô mà RBTV có nguy c ơ b ị vi ph ạm. Có th ể ghi thêm các thu ộc tính nào n ếu đượ c c ập nh ật m ới sẽ d ẫn đế n vi ph ạm RBTV b ằng cách li ệt kê chúng dướ i d ấu (+) – Đánh d ấu (-) tại ô không có nguy c ơ b ị vi ph ạm. – Đánh d ấu (- (*) ) nếu không b ị vi ph ạm vì không đượ c phép s ửa đổ i. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 13 4.1.4. T ầm ảnh h ưởng c ủa RBTV (tt) Ví d ụ –Bảng t ầm ảnh h ưở ng c ủa R1 Quan h ệ Thêm Sửa Xóa HOADON + (SoHD) - (*) - –Bảng t ầm ảnh h ưở ng c ủa R2 Quan h ệ Thêm Sửa Xóa HOADON + + (SoMatHang) - CHITIETHD + - + –Bảng t ầm ảnh h ưở ng c ủa R3 Quan h ệ Thêm Sửa Xóa HOADON + + (Tongtien) - CHITIETHD + + (Thanhtien) + bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 14
4.1.4. T ầm ảnh h ưởng c ủa RBTV (tt) Ví dụ (tt) –Bảng t ầm ảnh h ưở ng c ủa R4 Quan h ệ Thêm Sửa Xóa CHITIETHD + (MaH) - (*) - DMHANG - - (*) + bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 15 4.1.4. T ầm ảnh h ưởng c ủa RBTV (tt) Bảng t ầm ảnh h ưở ng t ổng h ợp c ủa R1, R2, R3, R4 Q.H ệ HOADON CHITIETHD DMHANG RBTV Thêm Sửa Xóa Thêm Sửa Xóa Thêm Sửa Xóa + R1 - (*) - (SoHD) + R2 + - + - + (SoMatHang) + + R3 + - + + (Tongtien) (Thanhtien) + R4 -(*) - - -(*) + (MaH) bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 16
4.1.5. Hành độ ng khi RBTV b ị vi ph ạm Khi RBTV b ị vi ph ạm, c ần có hành độ ng thích h ợp (g ồm 2 ph ần): – Thông báo : báo cho ng ườ i dùng bi ết d ữ li ệu b ị vi ph ạm RBTV nào và c ần s ửa l ại nh ư th ế nào. –Xử lý : Đư a ra ph ươ ng án x ử lý khi RBTV b ị vi ph ạm. Có th ể t ừ ch ối ho ặc ti ếp t ục cho hi ệu ch ỉnh d ữ li ệu Thông th ườ ng có 2 gi ải pháp: – (1) Đư a ra thông báo và yêu cầu sửa ch ữa dữ li ệu cho phù hợp với RBTV. TB này ph ải đầ y đủ và dễ hi ểu với ng ườ i dùng gi ải pháp này phù hợp cho vi ệc xử lý th ời gian th ực – (2) Từ ch ối thao tác cập nh ật gi ải pháp này phù hợp với vi ệc xử lý theo lô bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 17 4.2. Các loại RBTV RBTV có b ối c ảnh là 1 b ảng – RBTV v ề mi ền tr ị c ủa thu ộc tính – RBTV liên thu ộc tính – RBTV liên b ộ RBTV có b ối c ảnh là nhi ều b ảng – RBTV v ề ph ụ thu ộc t ồn t ại – RBTV v ề liên thu ộc tính – liên quan h ệ – RBTV v ề liên b ộ - liên quan h ệ – RBTV có tính chu trình bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 18
4.2.1. RBTV v ề mi ền tr ị Rất ph ổ bi ến trong các CSDL quan h ệ. Mỗi thu ộc tính không ch ỉ đặ c tr ưng bởi ki ểu giá tr ị mà còn bị gi ới hạn bởi mi ền giá tr ị trong ki ểu dữ li ệu đó Khi c ập nh ật (thêm/s ửa/xóa) giá tr ị cho 1 b ộ trong quan h ệ, ph ải ki ểm tra RBTV này Ví d ụ: DIEMTHI(MaSV, Lanthi, Diemthi) – R1: ∀kq ∈ DIEMTHI thì 0 ≤ kq.Diemthi ≤ 10 – R2: ∀kq ∈ DIEMTHI thì 0 ≤ kq.Lanthi ≤ 2 bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 19 4.2.2. RBTV Liên thuộc tính Là lo ại RBTV liên quan đế n nhi ều thu ộc tính c ủa quan hệ Thông th ườ ng đó là các thu ộc tính suy di ễn t ừ 1 ho ặc nhi ều thu ộc tính trong cùng m ột b ộ giá tr ị Ví d ụ: – Trong quan h ệ: CHITIETHD(SoHD, MaH, SL, Dongia, Thanhtien) – Có RBTV liên thu ộc tính: ∀ cth đ ∈ CHITIETHD thì cth đ.Thanhtien = cth đ.SL* cth đ.Đơ n-giá bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 20
4.2.3. RBTV liên b ộ, liên thu ộc tính Là lo ại RBTV có liên quan đế n nhi ều b ộ và có th ể t ới nhi ều thu ộc tính c ủa các b ộ giá tr ị trong m ột quan h ệ Ví d ụ: – Mã s ố sinh viên không đượ c trùng nhau ∀sv1, sv2 ∈ SINHVIEN thì sv1.MaSV ≠ sv2.MaSV – Điểm thi c ủa sinh viên l ần sau ph ải l ớn h ơn l ần tr ướ c: ∀kq ∈ DIEMTHI •Nếu kq.Lanthi = 1 thì 0 ≤ kq. Điểm ≤ 10 ho ặc: •Nếu kq.Lanthi > 1 thì ∃ kq’ ∈ DIEMTHI , sao cho kq’.Lanthi = kq.Lanthi - 1 và kq.Diem ≥ kq’.Diem bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 21 4.2.4. RBTV v ề phụ thuộc t ồn t ại Đây là lo ại RBTV ph ổ bi ến trong các CSDL quan h ệ. Còn đượ c g ọi là RBTV ph ụ thu ộc v ề khóa ngo ại Bộ giá tr ị của quan hệ này đượ c thêm vào một cách hợp lệ nếu tồn tại một bộ tươ ng ứng trên một quan hệ khác RBTV ph ụ thu ộc tồn tại xảy ra nếu có một trong hai tr ườ ng hợp sau: – Có sự hi ện di ện của khóa ngo ại – Có sự lồng khóa gi ữa các quan hệ bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 22
4.2.4. RBTV v ề ph ụ thu ộc t ồn tại (tt) Ví d ụ: –Mỗi sinh viên ph ải thu ộc 1 l ớp –Mỗi l ớp ph ải thu ộc 1 khoa –Mỗi Điểm ph ải c ủa 1 sinh viên, 1 môn –Mỗi nhân viên ph ải thu ộc 1 Phòng –Mỗi Mã hàng trong CHITIETHD ph ải t ồn t ại trong DMHANG –Mỗi S ố Hóa đơ n trong CHITIETHD ph ải t ồn t ại trong HOADON bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 23 4.2.5. RBTV liên thu ộc tính - liên quan h ệ Một thu ộc tính trong quan h ệ này c ố m ối liên h ệ v ới một thu ộc tính trong quan h ệ khác Ví d ụ: – Ngày giao hàng ph ải sau ngày đặ t HOADON.Ngaygiao ≥ CHITIETHD.Ngaydat – Tr ưở ng phòng ph ải có tu ổi trên 40 YEAR(PHONGBAN.NgayBD) – YEAR(NHANVIEN.Ngaysinh) ≥ 40 bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 24
4.2.5. RBTV liên bộ - liên quan hệ Một thu ộc tính c ủa quan h ệ này có m ối liên h ệ v ới các bộ c ủa quan h ệ khác. Ví d ụ: –Mỗi GV ph ải d ạy ít nh ất 1 l ớp – HOADON.SoMatHang = S ố b ộ c ủa CHITIETHD có cùng s ố hóa đơ n –Mỗi phi ếu m ượ n ch ỉ m ượ n đượ c t ối đa 3 cu ốn sách. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 25 4.2.6. RBTV do có chu trình Bi ểu di ễn cấu trúc CSDL dướ i dạng đồ th ị nh ư sau: mỗi nút của đồ th ị bi ểu di ễn 1quan hệ ho ặc 1 thu ộc tính – Quan hệ đượ c bi ểu di ễn bằng nút tròn tr ắng – Thu ộc tính đượ c bi ểu di ễn bằng nút tròn đen Các nút đượ c ch ỉ rõ bằng tên của quan hệ ho ặc thu ộc tính. Thu ộc tính thu ộc một quan hệ đượ c bi ểu di ễn bằng 1 cung nối gi ữa nút tròn tr ắng và nút tròn đen đó Nếu trên đồ th ị xu ất hi ện 1 đườ ng kép kín thì ta nói trong lượ c đồ CSLD có sự hi ện di ện của chu trình bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 26
4.2.6. RBTV do có chu trình Ví d ụ – Q1 (MaNV, MaPhong) – Q2 (MaPhong, MaDean) – Q3 (MaDean, TenDean) – Q4 (MaDean, MaNV) MaPhong Q1 MaNV Q2 MaDean TenDean Q4 Q3 bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 27 4.2.6. RBTV do có chu trình (tt) Gi ả thi ết 1: Mỗi nhân viên đượ c phân công vào tất c ả các đề án do phòng đóph ụ trách. – 2 con đườ ng mang ý ngh ĩa gi ống nhau. Đườ ng dài hơn Q1 kết nối với Q2 (ký hi ệu là Q1 I> <I Q2 [MaNV, MaDean] = Q4 [MaNV, MaDean] bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 28
4.2.6. RBTV do có chu trình (tt) Gi ả thi ết 2: Mỗi nhân viên đượ c phân công vào 1 s ố đề án do phòng ph ụ trách – Con đườ ng ng ắn Q4 ph ụ thu ộc vào con đườ ng dài Q1 |> <| Q2 [MaNV, MaDean] bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 29 4.2.6. RBTV do có chu trình (tt) Gi ả thi ết 3: Mỗi nhân viên đượ c phân công vào 1 s ố đề án bất k ỳ – Lúc này 2 con đườ ng hoàn toàn độ c l ập nhau, mang ý ngh ĩa khác nhau. – Không có RBTV bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 30
4.3. Phụ thuộc hàm Cho quan h ệ Q(A, B, C). Ph ụ thu ộc hàm A xác đị nh B. Ký hi ệu là A → B n ếu: ∀q1,q 2∈Q: N ếu q 1.A=q 2.A thì q1.B=q 2.B (Ngh ĩa là: ứng v ới 1 giá tr ị c ủa A thì có duy nh ất m ột giá tr ị c ủa B) – A → B đượ c g ọi là ph ụ thu ộc hàm hi ển nhiên nếu B ⊆A – A → B đượ c g ọi là ph ụ thu ộc hàm nguyên tố hay B ph ụ thu ộc hàm đầ y đủ vào A nếu ∀A’ ⊂ A đề u không có A’→ B bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 31 4.3.1. Đị nh nghĩa Phụ thuộc hàm Ví d ụ: HOADON(SoHD, SoMatHang, Tongtien) DMHANG(MaH, TenH, DvTinh) CHITIETHD(SoHD, MaH, SL, Dongia, Thanhtien) Trong quan h ệ DMHANG Có các ph ụ thu ộc hàm: – f1: MaH TenH – f2: MaH DvTinh Trong quan h ệ CHITIETHD có các ph ụ thu ộc hàm – f1: SoHD, MaH SL – f2: SoHD, MaH Dongia – f3: SoHD, MaH Thanhtien – f4: SL, Dongia Thanhtien – f5: MaH Dongia bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 32
4.3.2. Bao đóng t ập ph ụ thu ộc hàm và h ệ lu ật dẫn Amstrong Bao đóng c ủa t ập ph ụ thu ộc hàm – Trên l ượ c đồ quan h ệ R v ới t ập thu ộc tính U; F là t ập các ph ụ thu ộc hàm; cho X Y là m ột ph ụ thu ộc hàm; X, Y ⊆ U. – Ta nói X Y đượ c suy di ễn lôgic t ừ F n ếu R th ỏa mãn các ph ụ thu ộc hàm c ủa F thì c ũng th ỏa X Y. Ký hi ệu là: F |= X Y – Bao đóng (closure) c ủa F (ký hi ệu là F +) là t ập các ph ụ thu ộc hàm đượ c suy di ễn logic t ừ F. –Nếu F=F + thì ta nói F là h ọ đầ y đủ (Full family) c ủa các ph ụ thu ộc hàm bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 33 4.3.2. Bao đóng t ập ph ụ thu ộc hàm và hệ lu ật dẫn Amstrong (tt) Hệ lu ật dẫn Amstrong – Cho quan hệ hệ R với tập thu ộc tính U; – Cho X, Y, Z, W ⊆ U Ba lu ật của tiên đề Amstrong: 1. Lu ật ph ản x ạ (reflexive rule): Nếu Y ⊂ X thì X → Y 2. Lu ật t ăng tr ưở ng (augmentation rule): Nếu Z ⊂ U và X → Y thì XZ → YZ 3. Lu ật b ắc c ầu (Transivity Rule) Nếu X → Y và Y → Z thì X → Z bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 34
Hệ luật dẫn Amstrong Ba h ệ qu ả c ủa tiên đề Amstrong: 1. Lu ật h ợp (Union Rule) Nếu X → Y và X → Z thì X → YZ 2. Lu ật b ắc c ầu gi ả (Pseudotransivity Rule) Nếu X → Y và WY → Z thì XW → Z 3. Lu ật phân rã (Decomposition Rule) Nếu X → Y và Z ⊂ Y thì X → Z bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 35 Hệ luật dẫn Amstrong Ví d ụ 1: – Cho l ượ c đồ quan h ệ R(U), U=ABCDEGH và t ập các ph ụ thu ộc hàm: F = {AB C, B D, CD E, CE GH, GA}. Hãy áp d ụng h ệ tiên đề Amstrong tìm chu ỗi suy di ễn AB E – Gi ải: 1. AB C (ph ụ thu ộc hàm f1) 2. AB AB (lu ật ph ản x ạ vì AB ) 3. AB B (lu ật phân rã) 4. B D (ph ụ thu ộc hàm f2) 5. AB D (lu ật b ắc c ầu t ừ 3, 4) 6. AB CD (lu ật h ợp t ừ 1 và 5) 7. CD E (ph ụ thu ộc hàm f3) 8. AB E (lu ật b ắc c ầu t ừ 6, 7) bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 36
Hệ luật dẫn Amstrong (tt) Ví d ụ 2: – Cho l ượ c đồ quan h ệ R(U), U=ABCDEGHIJ và t ập các ph ụ thu ộc hàm: F = {AB E, AG J, BE I, E G, GI H}. Hãy áp d ụng h ệ tiên đề Amstrong tìm chu ỗi suy di ễn AB GH – Gi ải: bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 37 4.3.3. Bao đóng c ủa t ập thu ộc tính Đị nh ngh ĩa: – Bao đóng c ủa t ập thu ộc tính X đố i v ới t ập các ph ụ + + thu ộc hàm F (ký hi ệu là X F ho ặc X ) l ầ t ập các thu ộc tính A có th ể duy d ẫn t ừ X nh ờ t ập bao đóng c ủa các ph ụ thu ộc hàm F + Thu ật toán tìm bao đóng c ủa X – Tính liên ti ếp t ập các t ập thu ộc tính X 0,X 1,X 2, theo ph ươ ng pháp sau: – Bướ c 1 : X 0 = X – Bướ c 2 : l ần l ượ t xét các ph ụ thu ộc hàm c ủa F • Nếu Y →Z có Y ⊆ Xi thì X i+1 = X i ∪Z • Lo ại ph ụ thu ộc hàm Y → Z kh ỏi F – Bướ c 3 : N ếu ở b ướ c 2 không tính đượ c X i+1 thì X i chính là bao đóng c ủa X. Ng ượ c lại l ặp l ại b ướ c 2 bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 38
4.3.3. Bao đóng c ủa t ập thu ộc tính (tt) Ví d ụ1: – Cho F = {A BC, I K, GB H, CG I, B H} c ủa quan h ệ R(A, B, C, D, E, G, H, I, K) – Hãy tìm bao đóng c ủa t ập thu ộc tính X = {A, G} Gi ải: •X(0) = {A, G}, A BC •X(1) = {A, B, C, G}, GB H •X(2) = {A, B, C, G, H}, GC I •X(3) = {A, B, C, G, H, I}, I K •X(4) = {A, B, C, G, H, I, K} Vậy (AG) + = ABCGHIK bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 39 4.3.3. Bao đóng c ủa t ập thu ộc tính (tt) Ví dụ2: – Cho lượ c đồ quan hệ R(A,B,C,D,E,G,H) và tập ph ụ thu ộc hàm F={B →A; DA →CE; D→H; GH → C; AC →D}. Tìm bao đóng của X={AC}trênF ° X(0) = {A,C} , AC →D ° X(1) = {A,C,D}, AD →CE ° X(2) = {A,C,D,E}, D →H ° X(3) = { A,C,D,E,H } Vậy X += X (3) = ACDEH Ví d ụ3: Tìm bao đóng c ủa t ập thu ộc tính X = {B, D} bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 40
4.3.3. Bao đóng c ủa t ập thu ộc tính (tt) Ví du 4: cho l ượ c đồ quan h ệ: R(A,B,C,D,E,G) F = { f1: A → C; f2: A → EG; f3: B → D; f4: G → E } – Tìm bao đóng c ủa X + và Y + của X = {A,B}; Y = {C,G,D} bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 41 Sử d ụng bao đóng c ủa t ập thu ộc tính Ki ểm tra siêu khóa –Nếu t ập X có X + ch ứa t ất c ả các thu ộc tính c ủa quan h ệ R thì X là siêu khóa – X là khóa d ự tuy ển n ếu không có t ập con nào c ủa X là khóa Ki ểm tra ph ụ thu ộc hàm X Y có đượ c suy d ẫn t ừ t ập ph ụ thu ộc hàm F cho tr ướ c ? –Nếu X Y thu ộc F + ⇔ Y ⊆ X+ Ki ểm tra 2 t ập ph ụ thu ộc hàm t ươ ng đươ ng F + = G + + – ∀ ph ụ thu ộc hàm X Y trong G, n ếu Y ⊆ XF thì F ph ủ G và ng ượ c l ại + – ∀ ph ụ thu ộc hàm X Y trong F, nếu Y ⊆ XG thì G ph ủ F bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 42
4.3.4. Phủ và t ương đương Đị nh ngh ĩa – Hai t ập ph ụ thu ộc hàm F và G trên quan h ệ Q đượ c g ọi là t ươ ng đươ ng (ký hi ệu F ≡G) n ếu F + = G + –F≡G thì F đượ c g ọi là 1 ph ủ c ủa G ho ặc G là m ột ph ủ của F Thu ật toán: Ki ểm tra F và G có t ươ ng đươ ng không? – Bướ c 1: Với m ỗi ph ụ thu ộc hàm X Y c ủa F xác đị nh xem X Y có là thành viên c ủa G không? – Bướ c 2: Với m ỗi ph ụ thu ộc hàm X Y c ủa G xác đị nh xem X Y có là thành viên c ủa F không? – Bướ c 3: Nếu c ả 2 b ướ c trên đề u đúng thì F ≡ G bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 43 4.3.4. Phủ và t ương đương (tt) Ví dụ: Cho l ượ c đồ quan h ệ Q(ABCE) hai t ập ph ụ thu ộc hàm: F = {A→BC, A →D, C →E} G = {A →BCE, A →ABD, C →E} a) F có t ươ ng đươ ng v ới G không? b) F có t ươ ng đươ ng v ới G’={A →BCE} không? bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 44
4.3.4. Phủ và t ương đương (tt) Gi ải: a) – Tính A + dựa trên G + ⇒ + •AG =ABCDE trong G có A →BC và A →D ⇒ F ⊆ G+ ⇒ F+ ⊆ G+ (1). – Tính A + dựa trên t ập F + ⇒ •AF =ABCDE trong F+ có A →BCE và A →ABD ⇒ F+ ⊇ G ⇒ F+ ⊇ G+ (2) • (1) và (2) ⇒ F+ = G + ⇒ F ≡ G. b) + ⇒ + –AG’ = ABCE A → D ∉ G’ Vậy F và G’ không t ươ ng đươ ng bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 45 Ph ụ thu ộc hàm có v ế trái d ư th ừa F là tập các ph ụ thu ộc hàm trên lượ c đồ quan hệ Q. Z→Y ∈ F Phụ thu ộc hàm Z → Y có vế trái dư th ừa nếu có A ∈ Z sao cho: F ≡ F- {Z → Y} ∪ { (Z-A) → Y} Ví dụ 1 : Q (A, B, C), F= { AB →C; B →C} F ≡ F- {AB →C} ∪ { (AB-A) →C}={B →C} bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 46
Ph ụ thu ộc hàm có v ế trái d ư th ừa Ví d ụ 2: Cho tập ph ụ thu ộc hàm F = { A→BC , B → C, AB → D}. Ph ụ thu ộc hàm AB → D có v ế trái d ư th ừa B vì PTH AB D đượ c suy di ễn t ừ {A BC, B C, A D} Cụ th ể: ABC, A D ⇒ A BCD (lu ật h ợp) ABCD ⇒ A D (lu ật phân rã) Nói cách khác: F = F – {AB → D} ∪ {A → D} = {A → BC, B → C, A → D} bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 47 Loại bỏ PTH có v ế trái dư thừa Thu ật toán – Xét l ần l ượ t các PTH có d ạng X → Y (v ế trái có nhi ều hơn 1 thu ộc tính) – ∀ X’ ⊂ X và X’ ≠ ∅, N ếu X’ → Y ∈ F+ thì thay th ế X →Y bằng X’ → Y Ví d ụ: F = {A →BC, B → C, AB → D}, Xét Ph ụ thu ộc hàm AB → D + Tính B + = BC (không ch ứa A) nên A không d ư th ừa + Tính A + = ABC (ch ứa B) nên B là d ư th ừa Vậy: F = {A →BC, B →C, A →D} bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 48
Phụ thuộc hàm dư thừa F là tập ph ụ thu ộc hàm không dư th ừa nếu không tồn tại F’ ⊂ F sao cho F’ ≡ F. Ng ượ c lại F là tập ph ụ thu ộc hàm dư th ừa. Ví dụ: Cho F = {A → BC, B → D, AB → D} thì F dư th ừa vì F ≡ F’= {A →BC, B→D} Ch ứng minh: B → D ⇒ AB → AD (lu ật tăng tr ưở ng) AB → AD ⇒ AB → D (lu ật phân rã) Nh ư vậy AB → D đượ c suy di ễn từ B→D nên nó dư th ừa bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 49 Phủ t ối thi ểu (Minimal cover) Tập F đượ c g ọi là t ập ph ụ thu ộc hàm t ối thi ểu (hay ph ủ t ối thi ểu) n ếu nó th ỏa mãn đồ ng th ời 3 điều ki ện – F là t ập ph ụ thu ộc hàm có v ế trái không d ư th ừa – Các PTH trong F có v ế ph ải ch ỉ g ồm 1 thu ộc tính – F là t ập ph ụ thu ộc hàm không d ư th ừa bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 50
Phủ t ối thi ểu (tt) Thu ật toán tìm ph ủ tối thi ểu của một tập ph ụ thu ộc hàm – Bướ c 1: Loại bỏ các ph ụ thu ộc hàm có vế trái dư th ừa. – Bướ c 2: Tách các ph ụ thu ộc hàm có vế ph ải nhi ều hơn một thu ộc tính thành các ph ụ thu ộc hàm có vế ph ải một thu ộc tính. – Bướ c 3: Loại bỏ các ph ụ thu ộc hàm dư th ừa. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 51 Phủ t ối thi ểu (Minimal cover) Ví d ụ1: Cho l ượ c đồ quan h ệ Q(A, B, C, D) và t ập ph ụ thu ộc hàm F = {AB →CD, B →C, C →D}. Hãy tìm ph ủ t ối thi ểu c ủa F Gi ải: – Bướ c 1: Lo ại b ỏ các ph ụ thu ộc hàm có v ế trái d ư th ừa • Xét ph ụ thu ộc hàm AB → CD. Tính B + = BCD v ậy B → CD ∈ F+ •Vậy ta thay AB →CD b ởi B →CD t ức là F = {B →CD, B →C, C →D} – Bướ c 2: Tách các ph ụ thu ộc hàm có v ế ph ải nhi ều h ơn 1 thu ộc tính thành các PTH có v ế ph ải là 1 thu ộc tính • F = {B →C, B →D, C →D} = F 1tt – Bướ c 3 : Lo ại b ỏ các PTH d ư th ừa bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 52
Phủ t ối thi ểu (tt) – Bướ c 3: Lo ại b ỏ các PTH d ư th ừa • Ki ểm tra B→C có d ư th ừa không? – Đặ t G = F 1tt – {B→C} = {B→D, C →D} + ⇒ + ⇒ – Tính B G = BD B→C ∉ G B→C không d ư th ừa • Ki ểm tra B →D có d ư th ừa không? – Đặ t G = F 1tt - {B →D} = {B →C, C→D} + ⇒ + ⇒ – Tính B G = BCD B→D ∈ G B→D d ư th ừa • Ki ểm tra C→D có d ư th ừa không? – Đặ t G = F 1tt - {C →D} = {B →C, B→D} + ⇒ + ⇒ – Tính CG = C C→D ∉ G C→D Không d ư th ừa –Kết qu ả: Ph ủ t ối thi ểu c ủa t ập ph ụ thu ộc hàm là Fc = {B →C, C→D} bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 53 Phủ t ối thi ểu (tt) Ví d ụ 2: – Cho l ượ c đồ quan h ệ Q(A,B,C,D) và t ập ph ụ thu ộc F nh ư sau: F = {A →C; C → A; CB → D; AD → B; CD → B; AB → D} – Hãy tìm ph ủ t ối thi ểu c ủa F bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 54
4.4. Khóa c ủa l ược đồ quan hệ Đị nh ngh ĩa: – Cho lượ c đồ quan hệ R (A1,A2, ,An) •Q+ là t ập thu ộc tính c ủa R. • F là t ập ph ụ thu ộc hàm trên Q. • K là t ập con c ủa Q + K là m ột khóa c ủa Q nếu: •K+ = Q + (Bao đóng c ủa t ập thu ộc tính K = Q+) • Không tồn t ại K' ⊂ K sao cho K’+= Q+ bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 55 4.4. Khóa (tt) Tập thu ộc tính S đượ c gọi là siêu khóa nếu S ⊇ K Thu ộc tính A đượ c gọi là thu ộc tính khóa nếu A∈K với K là khóa bất kỳ của Q. Ng ượ c lại A đượ c gọi là thu ộc tính không khóa . Một lượ c đồ quan hệ có th ể có nhi ều khóa và tập thu ộc tính không khóa cũng có th ể bằng rỗng bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 56
4.4.2. Thuật toán tìm 1 khóa Bướ c 1: – gán K = Q+ Bướ c 2: – A là một thu ộc tính của K, đặ t K’ = K - A. Nếu K’+= Q+ thì gán K = K' th ực hi ện lại bướ c 2 •Nếu mu ốn tìm các khóa khác (n ếu có) của lượ c đồ quan hệ, ta có th ể thay đổ i th ứ tự lo ại bỏ các ph ần tử của K. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 57 4.4.2. Thuật toán tìm 1 khóa (tt) Ví dụ 1 : cho l ượ c đồ quan h ệ Q và t ập ph ụ thu ộc hàm F nh ư sau: – Q (A,B,C,D,E) – F={AB →C, AC → B, BC → DE} – Tìm khóa K Gi ải: B1: K=Q+ ⇒ K=ABCDE B2:(K\A) + ⇒(BCDE) +=BCDE ≠ Q+ ⇒ K=ABCDE B3:(K\B) + ⇒(ACDE) += ABCDE = Q + ⇒ K=ACDE B4: (K\C) + ⇒(ADE) + = ADE ≠ Q+ ⇒ K=ACDE B5: (K\D) + ⇒ (ACE) + = ACEBD=Q + ⇒ K=ACE B6: (K\E) + ⇒(AC )+ = ACBDE =Q + ⇒ K=AC bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 58
4.4.2. Thuật toán tìm 1 khóa (tt) Ví dụ 2 : cho l ượ c đồ quan hệ Q(ABCDEGHI) và tập ph ụ thu ộc hàm – F={ AC → B; BI → AC; ABC → D; H → I; ACE → BCG; CG → AE} – Tìm Khóa K bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 59 4.4.2. Thuật toán tìm 1 khóa (tt) Thu ật toán 2: Bi ểu di ễn l ượ c đồ quan h ệ b ằng đồ th ị có hướ ng nh ư sau: –Mỗi đỉ nh c ủa đồ th ị là 1 thu ộc tính trong l ượ c đồ quan h ệ –Mỗi ph ụ thu ộc hàm A →B đượ c bi ểu di ễn b ằng 1 cung có hướ ng t ừ đỉ nh A đế n đỉ nh B • Đỉ nh (thu ộc tính) ch ỉ có m ũi tên đi ra đượ c g ọi là nút g ốc • Đỉ nh (thu ộc tính) ch ỉ có m ũi tên đi vào đượ c g ọi là nút lá – Khóa c ủa l ượ c đồ quan h ệ phai bao ph ủ t ập các nút g ốc đồ ng th ời không ch ứa b ất k ỳ nút lá nào. – Thu ật toán: • Bướ c 1 : Xu ất phát t ừ t ập các nút g ốc (X) • Bướ c 2 : Tính bao đóng c ủa t ập thu ộc tính X (X +) • Bướ c 3: Nếu X + = U thi X là khóa. Ng ượ c l ại, b ổ sung 1 thu ộc tính không thu ộc nút lá vào X r ồi l ặp l ại B ướ c 2 bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 60
4.4.2. Thuật toán tìm 1 khóa (tt) Ví d ụ: – Cho R(U) v ới U = {A,B,C,D,E,H} v ới t ập ph ụ thu ộc hàm F = {AB →C, CD →E, EC →A, CD →H, H →B} – Hãy tìm khóa c ủa R H f5 B f4 C f1 f2 A D f3 E Nút g ốc bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 61 4.4.2. Thuật toán tìm 1 khóa (tt) Tính D + = ∅ Do CD có m ặt trong v ế trái c ủa 2 ph ụ thu ộc hàm (CD →H, CD →E) nên ta ghép C vào t ập nút g ốc và tính bao đóng H f5 CD + = CDEHBA B f4 C f1 Vậy CD là khóa c ủa R f2 A D f3 E bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 62
4.4.3. Thuật toán tìm mọi khóa Bướ c 1 : – Xác đị nh t ất c ả các t ập con khác r ỗng c ủa Q+={X1, n X2, ,X 2 -1 } Bướ c 2: – Tìm bao đóng c ủa các X i Bướ c 3: + – Siêu khóa là các X i có X i = Q+ – Gi ả sử ta đã có các siêu khóa là S = {S 1,S 2, ,S m} Bướ c 4 : – xét mọi S i, S j con c ủa S (i ≠ j), n ếu S i ⊂ Sj thì lo ại S j (i,j=1 n), k ết qu ả còn l ại c ủa S chính là t ập t ất c ả các khóa c ần tìm. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 63 4.4.3. Thu ật toán tìm mọi khóa (tt) Ví d ụ: – Tìm tất c ả các khóa c ủa l ượ c đồ quan h ệ và t ập ph ụ thu ộc hàm nh ư sau: bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 64
4.4.3. Thu ật toán tìm mọi khóa (tt) Thu ật toán c ải ti ến – Bướ c1: tạo tập thu ộc tính ngu ồn TN, tập thu ộc tính trung gian TG – Bướ c2: •Nếu TG = ∅ thì lượ c đồ quan hệ ch ỉ có một khóa K = TN kết thúc • Ng ượ c lại Qua bướ c 3 – Bướ c3: tìm tất cả các tập con Xi của tập trung gian TG bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 65 4.4.3. Thu ật toán tìm mọi khóa (tt) – Bướ c 4: tìm các siêu khóa Si bằng cách ∀Xi + + • if (TN ∪ Xi) = Q then •Si = TN ∪Xi – Bướ c 5: Lo ại bỏ các siêu khóa không tối thiểu • ∀ Si,Sj ∈ S • if Si ⊂ Sj then – Lo ại Sj ra kh ỏi Tập siêu khóa S • S còn lại chính là tập khóa cần tìm. bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 66
4.4.3. Thu ật toán tìm mọi khóa (tt) Ví d ụ 1: – Cho lượ c đồ quan h ệ Q(CSZ) và t ập ph ụ thu ộc hàm F={CS →Z; Z → C}. Áp d ụng thu ật toán c ải ti ến, hãy tìm các khóa c ủa Q Gi ải: – TN = {S}; TG = {C,Z} –Gọi X i là các t ập con c ủa t ập TG: bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 67 4.4.3. Thu ật toán tìm mọi khóa (tt) Ví d ụ 2: – Cho quan h ệ R (U), U = {A,B,C,D,G} và các ph ụ thu ộc hàm F = {B →C, C→B, A →GD} hãy tìm t ất c ả các khóa của R Gi ải: –Tập ngu ồn TN = {A}; Tập trung gian: TG = {B, C} + Siêu khóa Xi TN ∪ Xi (TN ∪ Xi) Khóa Si ∅ A AGD B AB ABCGD AB AB C AC ACGDB AC AC BC ABC ABCGD ABC bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 68
bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 69 Tổng k ết chương Hệ lu ật d ẫn Amstrong và h ệ qu ả c ủa nó Thu ật toán tìm bao đóng c ủa t ập thu ộc tính Thu ật toán tìm ph ủ t ối thi ểu của t ập ph ụ thu ộc hàm Thu ật toán tìm 1 khóa quan h ệ. Thu ật toán tìm t ất c ả các khóa của quan h ệ Cho ph ụ thu ộc hàm X →Y và t ập Ph ụ thu ộc hàm F, làm cách nào xác đị nh đượ c X →Y ∈ F+ hay không ? Cho 2 t ập ph ụ thu ộc F và G, làm th ế nào xác đị nh đượ c F và G là tươ ng đươ ng ? bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 70
4.5. Bài t ập bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 71 4.5. Bài t ập (tt) bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 72
4.5. Bài t ập (tt) bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 73 4.5. Bài t ập (tt) bangtqh@utc2.edu.vn Ch ươ ng 4 - Ràng bu ộc toàn v ẹn (RBTV) 74