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

, 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 đó) Chương 4 - Ràng buộc toàn vẹn (RBTV) 5 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 6 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 7 bangtqh@utc2.edu.vn 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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 8 bangtqh@utc2.edu.vn 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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 9 bangtqh@utc2.edu.vn 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đ ∈ CHITIETHD, ∃ hh ∈ DMHANG sao cho: cthđ.MaH=hh.MaH. Chương 4 - Ràng buộc toàn vẹn (RBTV) 10 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 11 bangtqh@utc2.edu.vn 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 đó Chương 4 - Ràng buộc toàn vẹn (RBTV) 12 bangtqh@utc2.edu.vn 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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 13 bangtqh@utc2.edu.vn 4.1.4. Tầm ảnh hưởng của RBTV (tt)
Ví dụ – Bảng tầm ảnh hưởng của R1 – Bảng tầm ảnh hưởng của R2 – Bảng tầm ảnh hưởng của R3 Chương 4 - Ràng buộc toàn vẹn (RBTV) 14 Quan hệ Thêm Sửa Xóa HOADON + (SoHD) - (*) - Quan hệ Thêm Sửa Xóa HOADON + + (SoMatHang) - CHITIETHD + - + Quan hệ Thêm Sửa Xóa HOADON + + (Tongtien) - CHITIETHD + + (Thanhtien) + bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 15 Quan hệ Thêm Sửa Xóa CHITIETHD + (MaH) - (*) - DMHANG - - (*) + bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 16 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 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ô Chương 4 - Ràng buộc toàn vẹn (RBTV) 17 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 18 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 19 bangtqh@utc2.edu.vn 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á Chương 4 - Ràng buộc toàn vẹn (RBTV) 20 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 21 bangtqh@utc2.edu.vn 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ệ Chương 4 - Ràng buộc toàn vẹn (RBTV) 22 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 23 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 24 bangtqh@utc2.edu.vn 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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 25 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 26 bangtqh@utc2.edu.vn 4.2.6. RBTV do có chu trình
Ví dụ – Q1 (MaNV, MaPhong) – Q2 (MaPhong, MaDean) – Q3 (MaDean, TenDean) – Q4 (MaDean, MaNV) Chương 4 - Ràng buộc toàn vẹn (RBTV) 27 MaPhong Q2 Q1 Q4 Q3 MaNV MaDean TenDean bangtqh@utc2.edu.vn 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). con đường ngắn hơn Q4 khi cùng xác định 1 đề án mà 1 nhân viên tham gia vào. – Nếu vẫn muốn giữ lại quan hệ Q4, tức là không hủy bỏ chu trình, thì phải có một RBTV với thuật toán sau: Q1 I><I Q2 [MaNV, MaDean] = Q4 [MaNV, MaDean] Chương 4 - Ràng buộc toàn vẹn (RBTV) 28 bangtqh@utc2.edu.vn 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 vì 1 nhân viên có thể không tham gia vào tất cả các đề án do phòng mình phụ trách. – RBTV được thể hiện bởi thuật toán sau: Q4[MaNV, MaDean] ⊆ Q1 |><| Q2 [MaNV, MaDean] Chương 4 - Ràng buộc toàn vẹn (RBTV) 29 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 30 bangtqh@utc2.edu.vn 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,q2∈Q: Nếu q1.A=q2.A thì q1.B=q2.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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 31 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 32 bangtqh@utc2.edu.vn 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 XY đượ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 XY. Ký hiệu là: F |= XY – 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 33 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 34 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 35 bangtqh@utc2.edu.vn 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 = {ABC, BD, CDE, CEGH, GA}. Hãy áp dụng hệ tiên đề Amstrong tìm chuỗi suy diễn ABE – Giải: 1. ABC (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) Chương 4 - Ràng buộc toàn vẹn (RBTV) 36 bangtqh@utc2.edu.vn 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 = {ABE, AGJ, BEI, EG, GIH}. Hãy áp dụng hệ tiên đề Amstrong tìm chuỗi suy diễn ABGH – Giải: Chương 4 - Ràng buộc toàn vẹn (RBTV) 37 bangtqh@utc2.edu.vn 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à XF+ 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 X0,X1,X2,... theo phương pháp sau: – Bước 1: X0 = 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ì Xi+1 = Xi ∪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 Xi+1 thì Xi chính là bao đóng của X. Ngược lại lặp lại bước 2 Chương 4 - Ràng buộc toàn vẹn (RBTV) 38 bangtqh@utc2.edu.vn 4.3.3. Bao đóng của tập thuộc tính (tt)
Ví dụ1: – Cho F = {ABC, IK, GBH, CGI, BH} 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}, ABC • X(1) = {A, B, C, G}, GBH • X(2) = {A, B, C, G, H}, GCI • X(3) = {A, B, C, G, H, I}, IK • X(4) = {A, B, C, G, H, I, K} Vậy (AG)+ = ABCGHIK Chương 4 - Ràng buộc toàn vẹn (RBTV) 39 bangtqh@utc2.edu.vn 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ên F  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} Chương 4 - Ràng buộc toàn vẹn (RBTV) 40 bangtqh@utc2.edu.vn 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} Chương 4 - Ràng buộc toàn vẹn (RBTV) 41 bangtqh@utc2.edu.vn 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 XY có được suy dẫn từ tập phụ thuộc hàm F cho trước ? – Nếu XY 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 42 bangtqh@utc2.edu.vn 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 XY của F xác định xem XY có là thành viên của G không? – Bước 2: Với mỗi phụ thuộc hàm XY 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 43 bangtqh@utc2.edu.vn 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? Chương 4 - Ràng buộc toàn vẹn (RBTV) 44 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 45 bangtqh@utc2.edu.vn 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} Chương 4 - Ràng buộc toàn vẹn (RBTV) 46 bangtqh@utc2.edu.vn 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 ABD được suy diễn từ {ABC, BC, AD} Cụ thể: ABC, AD ⇒ 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} Chương 4 - Ràng buộc toàn vẹn (RBTV) 47 bangtqh@utc2.edu.vn 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} Chương 4 - Ràng buộc toàn vẹn (RBTV) 48 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 49 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 50 bangtqh@utc2.edu.vn 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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 51 bangtqh@utc2.edu.vn 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} = F1tt – Bước 3: Loại bỏ các PTH dư thừa Chương 4 - Ràng buộc toàn vẹn (RBTV) 52 bangtqh@utc2.edu.vn 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 = F1tt – {B→C} = {B→D, C→D} – Tính BG+ = BD ⇒ B→C ∉ G+ ⇒ B→C không dư thừa • Kiểm tra B→D có dư thừa không? – Đặt G = F1tt - {B→D} = {B→C, C→D} – Tính BG+ = BCD ⇒ B→D ∈ G + ⇒ B→D dư thừa • Kiểm tra C→D có dư thừa không? – Đặt G = F1tt - {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} Chương 4 - Ràng buộc toàn vẹn (RBTV) 53 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 54 bangtqh@utc2.edu.vn 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+ Chương 4 - Ràng buộc toàn vẹn (RBTV) 55 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 56 bangtqh@utc2.edu.vn 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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 57 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 58 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 59 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 60 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 61 Nút gốc A B C E D H f1 f2 f3 f4 f5 bangtqh@utc2.edu.vn 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
CD+ = CDEHBA Vậy CD là khóa của R Chương 4 - Ràng buộc toàn vẹn (RBTV) 62 A B C E D H f1 f2 f3 f4 f5 bangtqh@utc2.edu.vn 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, X2, ,X2n-1 }
Bước 2: – Tìm bao đóng của các Xi
Bước 3: – Siêu khóa là các Xi có Xi+= Q+ – Giả sử ta đã có các siêu khóa là S = {S1,S2,,Sm}
Bước 4: – xét mọi Si, Sj con của S (i ≠ j), nếu Si ⊂ Sj thì loại Sj(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. Chương 4 - Ràng buộc toàn vẹn (RBTV) 63 bangtqh@utc2.edu.vn 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: Chương 4 - Ràng buộc toàn vẹn (RBTV) 64 bangtqh@utc2.edu.vn 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 Chương 4 - Ràng buộc toàn vẹn (RBTV) 65 bangtqh@utc2.edu.vn 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ỏ