›
›

Bài giảng Cơ sở dữ liệu và Phần mềm ứng dụng - Chương II: Thiết kế cơ sở dữ liệu quan hệ

pdf 87 trang hapham 2710
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở dữ liệu và Phần mềm ứng dụng - Chương II: Thiết kế cơ sở dữ liệu quan hệ", để 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:

  • pdfbai_giang_co_so_du_lieu_va_phan_mem_ung_dung_chuong_ii_thiet.pdf

Nội dung text: Bài giảng Cơ sở dữ liệu và Phần mềm ứng dụng - Chương II: Thiết kế cơ sở dữ liệu quan hệ

  1. Quản trị Cơ sở dữ liệu và Phần mềm ứng dụng Bộ môn CNTT Khoa Tin học Thương mại 11/3/2008 Bài giảng - CSDL và Phần mềm ứng dụng 1
  2. Chương II: Thiết kế CSDL quan hệ 1. Giới thiệu chung 1.1. Thiết kế CSDL QH và các cách tiếp cận 1.2. Phụ thuộc hàm 2. Chuẩn hóa lược đồ quan hệ 2.1. Các dạng chuẩn 2.2. Tách lược đồ quan hệ theo chuẩn 3. Ràng buộc toàn vẹn trong CSDL quan hệ 3.1. Khái niệm ràng buộc toàn vẹn 3.2. Ràng buộc toàn vẹn trên thuộc tính 3.3. Ràng buộc toàn vẹn trên quan hệ Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 2
  3. 1. Giới thiệu chung 1.1. Thiết kế CSDL QH và các cách tiếp cận Thiết kế cơ sở dữ liệu quan hệ  xây dựng lược đồ CSDL QH gồm một tập các lược đồ quan hệ thỏa mãn hai yêu cầu:  Lưu trữ thông tin không dư thừa  Tìm kiếm thông tin dễ dàng Ví dụ  Lược đồ quan hệ CUNG_UNG(MaNCC, TenNCC, DiaChi, SanPham, Gia) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 3
  4. Dư thừa dữ liệu Quan hệ CUNG_UNG_0 MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà Nội Kẹo mềm 100 1 Hải Hà Hà Nội Kẹo cứng 150 1 Hải Hà Hà Nội Bánh 200 2 Kinh đô Hồ Chí Minh Kẹo 120 2 Kinh đô Hồ Chí Minh Bánh 150  Một nhà cung cấp cung cấp nhiều mặt hàng.  Lặp các thông tin về nhà cung cấp ứng với mỗi một mặt hàng khác nhau của cùng nhà cung cấp đó. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 4
  5. Không nhất quán Quan hệ CUNG_UNG_0 MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Đà Nẵng Kẹo mềm 100 1 Hải Hà Hà Nội Kẹo cứng 150 1 Hải Hà Hà Nội Bánh 200 2 Kinh đô Hồ Chí Minh Kẹo 120 2 Kinh đô Hồ Chí Minh Bánh 150  Dị thường khi cập nhật thông tin về nhà cung cấp như thay đổi địa chỉ. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 5
  6. Dị thường khi thêm bộ Quan hệ CUNG_UNG_0 MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà nội Kẹo mềm 100 1 Hải Hà Hà Nội Kẹo cứng 150 1 Hải Hà Hà Nội Bánh 200 2 Kinh đô Hồ Chí Minh Kẹo 120 2 Kinh đô Hồ Chí Minh Bánh 150 3 Bibica Đà nẵng NULL NULL  Dị thường khi thêm mới thông tin về nhà cung cấp nhưng nhà cung cấp chưa cung cấp mặt hàng nào. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 6
  7. Dị thường khi xóa bộ Quan hệ CUNG_UNG_0 MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà nội Kẹo mềm 100 1 Hải Hà Hà Nội Kẹo cứng 150 1 Hải Hà Hà Nội Bánh 200 2 Kinh đô Hồ Chí Minh Kẹo 120  Tồn tại nhà cung cấp chỉ cung cấp một mặt hàng.  Dị thường khi xóa thông tin về sự cung cấp xóa luôn thông tin về nhà cung cấp. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 7
  8. Tìm kiếm thông tin MaNCC TenNCC DiaChi MaNCC SanPham Gia 1 Hải Hà Hà Nội 1 Kẹo mềm 100 2 Kinh đô Hồ Chí Minh 1 Kẹo cứng 150 CUNG_UNG_11 1 Bánh 200 2 Kẹo 120 2 Bánh 200 CUNG_UNG_12 Quan hệ CUNG_UNG_0 tách thành 2 quan hệ CUNG_UNG_11 và CUNG_UNG_12  Lưu trữ thông tin không dư thừa ???  Tìm kiếm thông tin dễ dàng ??? Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 8
  9. Các cách tiếp cận Từ trên xuống(Topdown):  Xây dựng sơ đồ thực thể liên kết ER từ các đặc tả  Chuyển đổi sơ đồ ER thành lược đồ CSDL quan hệ.  Chuẩn hóa lược đồ CSDL quan hệ (nếu cần) Từ dưới lên (Bottom Up):  Xây dựng lược đồ quan hệ ban đầu từ các đặc tả.  Chuẩn hóa lược đồ quan hệ. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 9
  10. 1.2. Phụ thuộc hàm a. Khái niệm  Cho quan hệ R, thuộc tính B của quan hệ R được gọi là phụ thuộc hàm vào thuộc tính A của quan hệ R nếu với mỗi giá trị của A xác định duy nhất một giá trị của B. A được gọi là xác định hàm của B.  Ký hiệu: A B Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 10
  11. a. Khái niệm (t) Tập các phụ thuộc hàm F của 1 lược đồ quan hệ R là một tập gồm các phụ thuộc hàm xác định trên R. Ví dụ: Tập phụ thuộc hàm F={A B, B C} của R(A,B,C)  Trong quan hệ R, ký hiệu A, B, C dành cho các thuộc tính đơn, X, Y, Z dành cho tập các thuộc tính. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 11
  12. Ví dụ Tập tất cả các thuộc tính của MaNCC TenNCC SoNV DiaChi quan hệ phải phụ thuộc hàm vào S1 Hải Hà 20 Hà Nội khóa. S2 Kinh Đô 10 Hà Nội  MaNCC TenNCC S3 Bibica 30 HCM  MaNCC SoNV  MaNCC DiaChi  MaNCC: Khóa  F={ MaNCC TenNCC, MaNCC SoNV, MaNCC DiaChi} Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 12
  13. Ví dụ Một tập thuộc tính là xác định hàm của các thuộc tính khác thì chưa chắc là một khóa.  TenNCC DiaChi  TenNCC không phải là khóa MaNCC TenNCC SoNV DiaChi S1 Hải Hà 20 Hà Nội S2 Kinh Đô 10 Hà Nội S3 Bibica 30 HCM S4 Hải Hà 10 Hà Nội Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 13
  14. b. Hệ tiên đề Amstrong Giả thiết  Lược đồ quan hệ R.  X,Y,Z: tập các thuộc tính thuộc R.  XY=XUY Hệ 3 tiên đề với các phụ thuộc hàm:  Phản xạ:XY X; XY Y  Tăng trưởng: X Y thì XZ YZ  Bắc cầu:X Y, Y Z thì X Z Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 14
  15. Luật suy ra từ hệ tiên đề Luật hợp  Nếu X Y, X Z thì X YZ Luật tựa bắc cầu  Nếu X Y, WY Z thì XW Z Luật tách  Nếu X Y, Z thuộc Y thì X Z Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 15
  16. c. Phụ thuộc hàm đầy đủ và phụ thuộc bắc cầu Phụ thuộc hàm đầy đủ  Y phụ thuộc hàm đầy đủ vào X nếu Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kỳ một tập con thực sự nào của X.  Ví dụ Lược đồ R(A, B, C, D) F={AB C; AB D; B D} C phụ thuộc hàm đầy đủ vào {A,B} D không phụ thuộc hàm đầy đủ vào {A,B} Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 16
  17. Phụ thuộc bắc cầu Phụ thuộc hàm X A, A được gọi là phụ thuộc bắc cầu vào X nếu tồn tại Y để cho X Y, Y A, Y / X và A XY Ví dụ:  F = {A B, B C}  A C: C phụ thuộc bắc cầu vào A Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 17
  18. d. Bao đóng và phủ của tập các phụ thuộc hàm Cho tập các phụ thuộc hàm F xác định trên R.  Bao đóng F+ của tập các phụ thuộc hàm F là tập tất cả các phụ thuộc hàm được suy diễn logic từ F.  Phủ G của tập các phụ thuộc hàm F (G≈F) là tập các phụ thuộc hàm xác định trên R sao cho G+ = F+. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 18
  19. X+ ? Bao đóng X+ của thuộc tính X đối với tập phụ thuộc hàm F là tất cả các thuộc tính A mà phụ thuộc hàm X A có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong. Một phụ thuộc hàm X Y thuộc F+ nếu Y thuộc X+: Kiểm tra X Y có thuộc F+ Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 19
  20. Ý nghĩa của phụ thuộc hàm Chỉ ra các phụ thuộc dữ liệu/ràng buộc có thể xảy ra giữa tập thuộc tính của một lược đồ quan hệ. Giúp xác định khóa tối thiểu, khóa chính của quan hệ. Giúp chuẩn hóa lược đồ quan hệ Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 20
  21. 2. Chuẩn hóa lược đồ quan hệ Khái niệm  Là quá trình phân tách các lược đồ quan hệ thành các lược đồ quan hệ nhỏ hơn theo một số tiêu chuẩn nhằm loại bỏ việc lưu trữ dư thừa dữ liệu.  Phép tách thành các lược đồ quan hệ đơn giản hơn, nhỏ hơn phải đảm bảo không làm mất mát thông tin. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 21
  22. 2.1. Các dạng chuẩn Dạng chuẩn 1 Dạng chuẩn 2 Dạng chuẩn 3 Dạng chuẩn Boye-Codd Chuẩn 4 và các dạng chuẩn khác Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 22
  23. a. Dạng chuẩn 1(1NF) Định nghĩa  Một lược đồ quan hệ R ở dạng chuẩn 1 nếu và chỉ nếu toàn bộ các miền giá trị của các thuộc tính trong R đều chỉ chứa các giá trị nguyên tố.  Một quan hệ xác định trên lược đồ quan hệ ở dạng chuẩn 1 được gọi là quan hệ ở dạng chuẩn 1. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 23
  24. Dạng chuẩn 1 (t) Một quan hệ thuộc dạng chuẩn 1 là một quan hệ trong đó mỗi miền giá trị của một thuộc tính chỉ chứa những giá trị nguyên tố (không phân chia được nữa). Một quan hệ thuộc dạng chuẩn 1 nếu mỗi một ô trong bảng chỉ chứa duy nhất một giá trị Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 24
  25. Ví dụ Quan hệ CUNG_UNG_0 chưa thuộc dạng chuẩn 1 MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà Nội Kẹo mềm 100 Kẹo cứng 150 Bánh 200 2 Kinh Đô Hồ Chí Kẹo 120 Minh Bánh 200 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 25
  26. Ví dụ(t) Quan hệ CUNG_UNG_1 đã thuộc dạng chuẩn 1 MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà Nội Kẹo mềm 100 1 Hải Hà Hà Nội Kẹo cứng 150 1 Hải Hà Hà Nội Bánh 200 2 Kinh đô Hồ Chí Minh Kẹo 120 2 Kinh đô Hồ Chí Minh Bánh 200 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 26
  27. b. Dạng chuẩn 2 (2NF) Định nghĩa  Một lược đồ quan hệ R được gọi là ở dạng chuẩn 2 nếu nó đã ở dạng chuẩn 1 và mọi thuộc tính không khóa đều phụ thuộc hàm đầy đủ vào khóa chính.  Một quan hệ xác định trên lược đồ quan hệ ở dạng chuẩn 2 được nói là quan hệ ở dạng chuẩn 2. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 27
  28. Ví dụ Quan hệ CUNG_UNG_1 chưa thuộc dạng chuẩn 2. MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà Nội Kẹo mềm 100 Lặp 1 Hải Hà Hà Nội Kẹo cứng 150 1 Hải Hà Hà Nội Bánh 200 Lặp 2 Kinh đô Hồ Chí Minh Kẹo 120 2 Kinh đô Hồ Chí Minh Bánh 200 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 28
  29. Ví dụ(t) R(M, T, D, S, G) = MTDSG= Lược đồ của quan hệ CUNG_UNG_1 Phụ thuộc hàm  M TD, MS G MS: Khóa tối thiểu  M, S: Thuộc tính khóa  T, D, G: Thuộc tính không khóa T, D không phụ thuộc hàm đầy đủ vào MS Lược đồ quan hệ CUNG_UNG_1 không thuộc dạng chuẩn 2. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 29
  30. Ví dụ MaNCC TenNCC DiaChi MaNCC SanPham Gia 1 Hải Hà Hà Nội 1 Kẹo mềm 100 2 Kinh đô Hồ Chí Minh 1 Kẹo cứng 150 CUNG_UNG_11 1 Bánh 200 2 Kẹo 120 2 Bánh 200 CUNG_UNG_12 Ví dụ 2 thành quan hệ CUNG_UNG_11 và CUNG_UNG_12 tách từ quan hệ CUNG_UNG_1 đã thuộc dạng chuẩn 2.  TenNCC, DiaChi phụ thuộc hàm đầy đủ vào MaNCC  Gia phụ thuộc hàm đầy đủ vào {MaNCC, SanPham} Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 30
  31. c. Dạng chuẩn 3 Định nghĩa  Một lược đồ quan hệ R được gọi là ở dạng chuẩn 3 nếu nó đã ở dạng chuẩn 2 và mọi thuộc tính không khóa của R đều chỉ phụ thuộc hàm duy nhất vào khóa chính.  Một quan hệ xác định trên lược đồ quan hệ ở dạng chuẩn ba được nói là quan hệ ở dạng chuẩn 3. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 31
  32. Ví dụ MaNCC TenNCC DiaChi MaNCC SanPham Gia 1 Hải Hà Hà Nội 1 Kẹo mềm 100 2 Kinh đô Hồ Chí Minh 1 Kẹo cứng 150 CUNG_UNG_11 1 Bánh 200 2 Kẹo 120 2 Bánh 200 CUNG_UNG_12 Ví dụ 2 quan hệ CUNG_UNG_11 và CUNG_UNG_12 đã thuộc dạng chuẩn 3. MTDSG tách thành 1 lược đồ con MTD và MSG:  MTD: T, D phụ thuộc chỉ vào khóa M  MSG: G phụ thuộc hàm chỉ vào MS Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 32
  33. Ví dụ Ví dụ  Lược đồ quan hệ: R(Store, Item, Departement, Manager)  R(S,I,D,M)  Tập các phụ thuộc hàm: F={SI D, SD M}  Khóa tối thiểu: SI  Lược đồ thuộc chuẩn 2: D, M phụ thuộc hàm đầy đủ vào SI  Lược đồ không thuộc chuẩn 3: M phụ thuộc bắc cầu vào SI SI D; SI SD;SD M;SI M(*) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 33
  34. d. Dạng chuẩn Boye-Codd (BCNF) Chuẩn 3 không đáp ứng được những lược đồ quan hệ  Có nhiều hơn một khóa tối thiểu  Các khóa tối thiểu là khóa kép  Các khóa tối thiểu giao nhau Định nghĩa  Một lược đồ quan hệ R thuộc dạng chuẩn Boye-Codd khi và chỉ khi mọi xác định hàm đều là một khóa. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 34
  35. Ví dụ Lược đồ quan hệ: R(CITY, STREET, ZIP) Phụ thuộc hàm:  CITY, STREET ZIP, ZIP CITY Khóa tối thiểu:  {CITY, STREET}, {STREET, ZIP} Thuộc tính khóa:  CITY, STREET, ZIP không có thuộc tính không khóa, thuộc dạng chuẩn 3. Xác định hàm ZIP không phải là một khóa lược đồ không thuộc chuẩn Boye- Codd Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 35
  36. Ví dụ CITY STREET ZIP 2 lược đồ con R1(CITY, ZIP) và Hà Nội Láng 0423 R2( STREET, ZIP) Hà Nội Phạm 0425 thuộc dạng Hùng chuẩn Boye- HCM Võ Thị 0811 Sáu Codd. CITY ZIP STREET ZIP Hà Nội 0423 Láng 0423 Hà Nội 0425 Phạm Hùng 0425 HCM 0811 Võ Thị Sáu 0811 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 36
  37. Quan hệ giữa các dạng chuẩn Chuẩn1 Chuẩn 2 Chuẩn 3 Chuẩn Boye-Codd Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 37
  38. 2.2. Tách lược đồ quan hệ theo chuẩn 2.2.1.Tách bảo toàn thông tin và tách bảo toàn tập phụ thuộc hàm 2.2.2.Các thuật toán tách lược đồ quan hệ 2.2.3.Tách lược đồ quan hệ theo từng bước Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 38
  39. 2.2.1.Tách bảo toàn thông tin và tách bảo toàn tập phụ thuộc hàm a. Phép tách bảo toàn thông tin Khái niệm  Phép tách bảo toàn thông tin là phép tách lược đồ quan hệ sao cho khi kết nối tự nhiên các quan hệ xác định trên các lược đồ con, kết quả cho lại quan hệ ban đầu. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 39
  40. Phép kết nối tự nhiên Phép ghép các cặp R(A, B, C) a1 b1 1 bộ của hai quan a2 b2 2 hệ trên các thuộc a3 b3 3 tính bằng nhau S(D, E) của hai quan hệ, 1 e1 một trong hai 2 e2 thuộc tính của 3 e3 phép so sánh “=“ R kết nối tự nhiên với được loại bỏ sau s với C=D a1 b1 1 e1 khi thực hiện phép a2 b2 2 e2 ghép. a3 b3 3 e3 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 40
  41. Ví dụ  Lược đồ quan hệ MTDSG = (MaNCC, TenNCC, DiaChi, SanPham, Gia) (M, T, D, S, G);  Tập phụ thuộc hàm F={M TD, MS G}  Quan hệ xác định trên lược đồ MTDSG: MaNCC TenNCC DiaChi SanPham Gia 1 Hải Hà Hà Nội Kẹo mềm 10 1 Hải Hà Hà Nội Kẹo cứng 15 1 Hải Hà Hà Nội Bánh ngọt 40 1 Hải Hà Hà Nội Bánh mỳ 16 2 Kinh Đô Hồ Chí Minh Kẹo 12 2 Kinh Đô Hồ Chí Minh Bánh quy 45 3 Kinh Đô Đà Nẵng Bánh mỳ 10 Bài giảng - CSDL và Phần mềm 11/3/2008 3 Kinh Đô ứng dụĐngà Nẵng Bánh quy 30 41
  42. Ví dụ(t) MaNCC SanPham Gia 1 Kẹo mềm 10 MaNCC TenNCC DiaChi 1 Kẹo cứng 15 1 Bánh ngọt 40 1 Hải Hà Hà Nội 1 Bánh mỳ 16 2 Kinh Đô Hồ Chí Minh 2 Kẹo 12 3 Kinh Đô Đà Nẵng 2 Bánh quy 45 3 Bánh mỳ 10 3 Bánh quy 30 Phép tách bảo toàn thông tin  Lược đồ con 1: MTD=(M, T, D)  Lược đồ con 2: MSG=(M, S, G) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 42
  43. Ví dụ(t) TenNCC SanPham Gia Hải Hà Kẹo mềm 10 Hải Hà Kẹo cứng 15 MaNCC TenNCC DiaChi Hải Hà Bánh ngọt 40 1 Hải Hà Hà Nội Hải Hà Bánh mỳ 16 2 Kinh Đô Hồ Chí Minh Kinh Đô Kẹo 12 3 Kinh Đô Đà Nẵng Kinh Đô Bánh quy 45 Kinh Đô Bánh mỳ 10 Kinh Đô Bánh quy 30 Phép tách mất mát thông tin  Lược đồ con 1: MTD=(M, T, D)  Lược đồ con 2: MSG=(M, S, G) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 43
  44. Thuật toán kiểm tra Kiểm tra phép tách không mất mát thông tin của một lược đồ quan hệ thành nhiều lược đồ quan hệ con.  Vào Lược đồ quan hệ: R=(A1, A2, An) Tập phụ thuộc hàm F trên R Phép tách ρ=(R1, R2, Rk)  Ra Một khẳng định rằng phép tách ρ có mất mát thông tin hay không? Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 44
  45. Thuật toán kiểm tra (t)  Phương pháp Bước 1: Xây dựng một bảng k hàng, n cột  Hàng i tương ứng với Ri  Cột j tương ứng với thuộc tính Aj  Giá trị tại hàng i, cột j aj: Nếu Aj thuộc Ri bij: Nếu Aj không thuộc Ri Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 45
  46. Ví dụ (bước 1) Lược đồ quan hệ MTDSG Tập phụ thuộc hàm F={M TD, MS G} Tách thành hai lược đồ MTD, MSG M T D S G R1= MTD a1 a2 a3 b14 b15 R2= MSG a1 b22 b23 a4 a5 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 46
  47. Phương pháp  Bước 2: Lặp Áp dụng các phụ thuộc hàm cho bảng vừa được xây dựng: X Y: Nếu tồn tại hai hàng có cùng giá trị trên X thì làm bằng nhau các giá trị trên Y.  Nếu có giá trị một hàng thuộc Y là aj thì các giá trị khác thuộc Y gán bằng aj.  Nếu không gán bằng một trong các giá trị bij.  Dừng khi các giá trị trong bảng không thể thay đổi được nữa Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 47
  48. Ví dụ (bước 2) M T D S G R1= MTD a1 a2 a3 b14 b15 R2= MSG a1 b22 b23 a4 a5 Áp dụng phụ thuộc hàm M TD  Thay b22 = a2  Thay b23 = a3 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 48
  49. Phương pháp Bước 3: Kiểm tra  Nếu trong bảng có một hàng gồm toàn ký hiệu a1, a2, a3, an thì phép tách là không mất mát thông tin.  Ngược lại phép tách là mất mát thông tin. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 49
  50. Ví dụ M T D S G R1= MTD a1 a2 a3 b14 b15 R2= MSG a1 a2 a3 a4 a5 Phép tách trên là không mất mát thông tin. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 50
  51. Định lý kiểm tra Kiểm tra phép tách không mất mát thông tin của một lược đồ quan hệ thành hai lược đồ quan hệ con.  Cho lược đồ quan hệ R Tập phụ thuộc hàm F trên R ρ=(R1, R2)  Phép tách là không mất mát thông tin nếu R1 R2 R1\R2 hoặc R1 R2 R2\R1. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 51
  52. Ví dụ Lược đồ MTDSG tách thành hai lược đồ con MTD và MSG:  MTD MSG = M  MTD\MSG = TD  M TD thuộc F+: Phép tách là bảo toàn thông tin. Lược đồ MTDSG tách thành hai lược đồ con MTD và TSG  MTD TSG = T  MTD\TSG = MD  TSG\MTD = SG  T MD và T SG không thuộc F+: Phép tách là mất mát thông tin. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 52
  53. b. Phép tách bảo toàn tập phụ thuộc hàm Khái niệm  Phép tách lược đồ quan hệ R thành các lược đồ quan hệ con Ri là bảo toàn các tập phụ thuộc hàm nếu hợp của các phụ thuộc hàm là hình chiếu của F trên Ri suy diễn logic được tất cả các phụ thuộc hàm trong F.  Hình chiếu của F lên Ri là các phụ thuộc hàm X Y thỏa mãn: X, Y thuộc Ri X Y thuộc F+ Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 53
  54. Ví dụ Cho  Lược đồ R = ACBCD  Tập phụ thuộc hàm F = { A B, C D}  Phép tách ρ = (R1,R2): R1= AB, R2 = CD Phép tách bảo toàn tập phụ thuộc hàm  Hình chiếu của F lên R1: A B, AB A, AB B  Hình chiếu của F lên R2: C D, CD C, CD D  Các phụ thuộc hàm trong F có thể được suy diễn từ các hình chiếu này Phép tách không bảo toàn thông tin  AB CD = Φ  AB\CD = AB  CD\AB = CD Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 54
  55. Ví dụ Cho  Lược đồ R = CSZ  Tập phụ thuộc hàm F={CS Z, Z C}  Phép tách ρ = (R1,R2): R1= CZ, R2 = SZ Phép tách không bảo toàn tập phụ thuộc hàm  Hình chiếu của F lên R1: Z C, CZ C, CZ Z,  Tập phụ thuộc hàm trong R2: SZ S, SZ Z,  Phụ thuộc hàm CS Z không thể được suy ra từ các hình chiếu này. Phép tách bảo toàn thông tin  CZ SZ CZ\SZ hay Z C Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 55
  56. Ví dụ Cho  Lược đồ R = MTDSG  Tập phụ thuộc hàm F={M TD, MS G}  Phép tách ρ = (R1 ,R2): R1= MTD, R2 = MSG Phép tách bảo toàn tập phụ thuộc hàm  Hình chiếu của F lên R1: M TD,  Hình chiếu của F lên R2: MS G,  Các phụ thuộc hàm trong F có thể được suy diễn logic từ các hình chiếu này. Phép tách bảo toàn thông tin  Đã chứng minh Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 56
  57. 2.2.2. Các thuật toán tách lược đồ quan hệ a.Thuật toán tìm một khóa tối thiểu của lược đồ quan hệ dựa vào tập phụ thuộc hàm b.Thuật toán tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm về dạng chuẩn 3 c.Thuật toán tách không mất mát thông tin về dạng chuẩn Boye- Codd Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 57
  58. a. Thuật toán tìm một khóa tối thiểu của lược đồ quan hệ dựa vào tập phụ thuộc hàm Khóa của lược đồ quan hệ  Giá trị của tập thuộc tính khóa trên mỗi bộ của quan hệ là duy nhất  Mọi thuộc tính của quan hệ phải phụ thuộc hàm vào khóa. Thuật toán tìm một khóa tối thiểu  Loại bỏ dần từng thuộc tính thuộc khóa của quan hệ cho tới khi tập thuộc tính nhỏ nhất còn lại vẫn thỏa mãn là một khóa khóa tối thiểu của quan hệ. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 58
  59. b.Thuật toán tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm về dạng chuẩn 3 Vào:  Lược đồ quan hệ R  Tập phụ thuộc hàm F (phủ tối thiểu) Ra:  Tập sơ đồ con, trong đó mỗi sơ đồ con Thuộc dạng chuẩn 3 Phụ thuộc hàm là hình chiếu của F lên nó Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 59
  60. b.Thuật toán tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm về dạng chuẩn 3 (t) Phương pháp:  Nếu tồn tại một thuộc tính thuộc R không có mặt ở vế trái hay vế phải của bất kỳ phụ thuộc hàm nào thì tách thuộc tính này ra khỏi R.  Nếu tồn một tại phụ thuộc hàm liên quan tới mọi thuộc tính của R thì kết quả là R.  Nếu các phụ thuộc hàm dạng: X A : lược đồ con ở dạng XA. X A1, X An: lược đồ con ở dạng XA1 An Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 60
  61. Ví dụ Cho lược đồ R = ABCDEG Tập phụ thuộc hàm F = {AB C, C A, BC D, ACD B, D EG, BE C, CG BD, CE AG} Tập phụ thuộc hàm tối thiểu F’ = {AB C, C A, BC D, D E, D G, BE C, CG B, CE G} Phép tách ρ = (ABC, CA, BCD, DEG, BEC, CGB, CEG) = (ABC, BCD, DEG, BEC, CGB, CEG) gồm các lược đồ con đã ở dạng chuẩn 3 bảo toàn tập phụ thuộc hàm và bảo toàn thông tin. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 61
  62. c.Thuật toán tách không mất mát thông tin về dạng chuẩn Boye-Codd Vào :  Lược đồ quan hệ R  Tập phụ thuộc hàm F Ra:  Tập sơ đồ con, trong đó mỗi sơ đồ con Thuộc dạng chuẩn Boye-Codd Phụ thuộc hàm là hình chiếu của F lên nó Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 62
  63. c.Thuật toán tách không mất mát thông tin về dạng chuẩn Boye-Codd (t) Phương pháp:  ρ = (R)  Lặp S là một sơ đồ quan hệ trong ρ không ở dạng chuẩn Boye-Codd. Xét một phụ thuộc hàm X A của S. Nếu X không chứa khóa của S, A không thuộc X thì S được tách thành:  S1 = A U{X}  S2 = S\{A}  Dừng cho tới khi mọi sơ đồ con trong ρ đã thuộc dạng chuẩn Boye-Codd Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 63
  64. 2.2.3. Tách lược đồ quan hệ theo từng bước Quy tắc  Quy tắc 1: Loại bỏ các thuộc tính phụ thuộc chỉ một phần vào khóa chính. Chuẩn hóa về 2NF  Quy tắc 2: Loại bỏ các thuộc tính không khóa không phụ thuộc vào khóa chính. Chuẩn hóa về 3NF  Quy tắc 3: Loại bỏ các thuộc tính là giao của các khóa tối thiểu. Chuẩn hóa về BCNF Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 64
  65. Ví dụ Cho quan hệ R(A1, A2, A3, A4, A5, A6, A7, A8, A9) trong đó A1A2A3 là khóa với sơ đồ phụ thuộc hàm: Quan hệ R ở dạng chuẩn nào? Tại sao? Tách R thành các quan hệ ở dạng chuẩn BCNF. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 65
  66. 3. Ràng buộc toàn vẹn trong CSDL quan hệ (Integrity Constraint) 3.1. Khái niệm ràng buộc toàn vẹn Ràng buộc toàn vẹn là điều kiện bất biến không được vi phạm trong một CSDL.  Các điều kiện mà mọi thể hiện của quan hệ phải thỏa mãn  RBTV xuất phát từ các quy tắc quản lý được áp đặt lên thế giới thực Ví dụ:  RBTV1: Mỗi bộ của quan hệ DON_DAT_HANG phải ứng với một đơn đặt hàng với mã đơn đặt hàng (MaDDH) duy nhất.  RBTV2: Mọi chi tiết về đơn đặt hàng phải có mã hàng (MaHang) thuộc về danh mục hàng.  RBTV3: Mã đơn đặt hàng (MaDDH) khác NULL.  RBTV4: Tổng các trị giá của các mặt hàng trong CHI_TIET_DON_HANG có cùng MaDDH phải bằng TongGT ghi trong DON_DAT_HANG Mục đích của RBTV  Đảm bảo tính nhất quán của dữ liệu(RBTV2, RBTV4)  Đảm bảo ngữ nghĩa nghĩa thực tế của dữ liệu(RBTV1, RBTV3) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 66
  67. Khái niệm ràng buộc toàn vẹn RBTV được xác định và mô tả trong quá trình thiết kế csdl. RBTV có 3 yếu tố chính:  Nội dung  Bối cảnh  Tầm ảnh hưởng RBTV được khai báo thông qua ngôn ngữ định nghĩa và thao tác dữ liệu và được hỗ trợ bởi hqt csdl.  Mệnh đề check, arssertion, triger RBTV được kiểm tra và xử lý bởi hqt csdl. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 67
  68. Nội dung của RBTV Được phát biểu  Ngôn ngữ tự nhiên: Đơn giản dễ hiểu  Ngôn ngữ hình thức: khó hiểu Đại số quan hệ, phép tính quan hệ, mã giả Biểu thức toán học Ví dụ:  RBTV5: Mỗi nhân viên có một mã số dùng để phân biệt với những nhân viên khác t1,t2 NHAN _VIEN(t1 t2 t1.MaNV t2.MaNV )  RBTV6: Mỗi nhân viên làm việc trong một phòng ban NHAN _VIENMaPhong PHONG _ BAN[MaPhong]  RBTV7: Mỗi phòng phải có ít nhất một nhân viên s PHONG _ BAN(t NHAN _VIEN(t.MaPhong s.MaPhong)) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 68
  69. Bối cảnh của RBTV Là những quan hệ mà RBTV có hiệu lực: Một hoặc nhiều quan hệ Ví dụ  RBTV5 có bối cảnh là quan hệ NHAN_VIEN  RBTV6, RBTV7 có bối cảnh là quan hệ NHAN_VIEN, PHONG_BAN Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 69
  70. Tầm ảnh hưởng RBTV có thể bị vi phạm khi thực hiện các thao tác cập nhật trên bối cảnh: Thêm, xóa, sửa Bảng tầm ảnh hưởng dùng để xác định thời điểm cần kiểm tra RBTV Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 70
  71. Xây dựng bảng tầm ảnh hưởng cho từng RBTV Nội dung mỗi ô  +: Cần phải kiểm tra RBTV  - : Không cần phải kiểm tra RBTV Tên RBTV Thêm Xóa Sửa Quan hệ 1 + + - Quan hệ k + - - Các quan hệ bối cảnh Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 71
  72. Ví dụ RBTV5 Thêm Xóa Sửa NHAN_VIEN + - - RBTV6 Thêm Xóa Sửa NHAN_VIEN + - + PHONG_BAN - + - RBTV7 Thêm Xóa Sửa NHAN_VIEN - - + PHONG_BAN + - - Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 72
  73. Xây dựng bảng tầm ảnh hưởng tổng hợp Xây dựng trên cơ sở bảng tầm ảnh hưởng của các RBTV Để xác định thời điểm kiểm tra RBTV khi một thao tác cập nhật trên quan hệ nào đó được thực hiện Tên RBTV 1 Tên RBTV r T X S T X S Quan hệ 1 + + - + - + Quan hệ n - - + + + + Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 73
  74. Ví dụ Xây dựng bảng tầm ảnh hưởng cho các ràng buộc toàn vẹn RBTV1 , RBTV7 cho lược đồ CSDL quan hệ siêu thị M ? Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 74
  75. Phân loại RBTV Dựa trên yếu tố bối cảnh của RBTV  RBTV có bối cảnh là một quan hệ/RBTV trên thuộc tính RBTV miền giá trị RBTV liên thuộc tính RBTV liên bộ  RBTV có bối cảnh là nhiều quan hệ/RBTV trên quan hệ RBTV tham chiếu RBTV thuộc tính tổng hợp RBTV liên thuộc tính RBTV liên bộ Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 75
  76. 3.2. Ràng buộc toàn vẹn trên thuộc tính a.Ràng buộc toàn vẹn về miền giá trị của một thuộc tính  RBTV đặc tả tập giá trị có thể kết hợp với một thuộc tính.  Ví dụ: quan hệ NHAN_VIEN RBTV8: Tuổi của nhân viên trong công ty phải lớn hơn 18 và nhỏ hơn 65. RBTV8 T X S t NHAN _VIEN(18 t.Tuoi 65) NHAN_VIEN + - + Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 76
  77. b. RBTV liên thuộc tính RBTV có liên quan tới nhiều thuộc tính của một quan hệ. Thông thường đó là các phụ thuộc tính toán, hoặc một suy diễn từ giá trị của một hay nhiều thuộc tính trong cùng một bộ giá trị. Ví dụ  Quan hệ NHAN_VIEN  RBTV9: Nếu nhân viên có giới tính là nữ tuổi của nhân viên trong công ty phải lớn hơn 18 và nhỏ hơn 55. t NHAN _VIEN (18 t.Tuoi 55(t.GioiTinh Nu)) RBTV9 T X S NHAN_VIEN + - + Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 77
  78. c. RBTV liên bộ, liên thuộc tính RBTV có liên quan tới 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ụ: RBTV5 Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 78
  79. 3.3. Ràng buộc toàn vẹn trên quan hệ a. RBTV tham chiếu/RBTV về phụ thuộc tồn tại (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ản ghi tương ứng trong một quan hệ khác.  Đảm bảo rằng giá trị xuất hiện trong một quan hệ đối với một tập các thuộc tính đã cho cũng xuất hiện đối với một tập các thuộc tính nhất định trong một quan hệ khác. Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 79
  80. a. Ràng buộc toàn vẹn về phụ thuộc tồn tại (phụ thuộc về khóa ngoại) Ví dụ:  RBTV1 : Mỗi bộ của CHI_TIET_DON_HANG phải có một đơn hàng với MaDDH tương ứng t CHI _TIET _ DON _ HANG(u DON _ HANG(t.MaDDH u.MaDDH)) RVTV4 T X S CHI_TIET_DON_HANG + - - DON_HANG - + - Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 80
  81. Ví dụ RBTV2 : Mỗi bộ của CHI_TIET_DON_HANG phải có MaHang thuộc về danh mục hàng trong quan hệ MAT_HANG Biểu diễn hình thức ? Bảng xác định tầm ảnh hưởng? Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 81
  82. b. Ràng buộc toàn vẹn tổng hợp Khi có sự hiện diện của 1 thuộc tính mang tính chất tổng hợp (tức là giá trị của thuộc tính có thể được tính toán từ giá trị của các thuộc tính khác trên một hay nhiều bộ giá trị của các quan hệ trong CSDL) Ví dụ:  DON_DAT_HANG(MaDDH, NgayLap, TenKH, TongGT)  CHI_TIET_DON_HANG(MaDDH, TenSanPham, SoLuong, Giatri).  RBTV4: Tổng các trị giá của các mặt hàng trong CHI_TIET_DON_HANG có cùng MaDDH phải bằng TongGT ghi trong DON_DAT_HANG . Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 82
  83. t DON _ DAT _ HANG(t.TongGT u.GiaTri(u CHI _TIET _ DON _ HANG  u.MaDDH t.MaDDH)) RVTV4 T X S CHI_TIET_DON_HANG + + + DON_DAT_HANG + - + Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 83
  84. c. RBTV liên thuộc tính Mối quan hệ giữa các thuộc tính trong nhiều lược đồ quan hệ Ví dụ  Quan hệ: NHAN_VIEN (TenNV, Luong, NgaySinh TenPhong) PHONG_BAN(TenPhong, MaPhong, NguoiQuanLy, NgayNhanChuc)  RBTV 10: Ngày nhận chức của trưởng phòng phải lớn hơn ngày sinh Biểu diễn hình thức. Bảng xác định tầm ảnh hưởng? Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 84
  85. d.Ràng buộc toàn vẹn liên bộ Mối quan hệ giữa các bộ trên nhiều lược đồ quan hệ Ví dụ  Quan hệ NHAN_VIEN, PHONG_BAN  RBTV11: Lương của nhân viên không được cao hơn lương trưởng phòng Biểu diễn hình thức? Bảng xác định tầm ảnh hưởng? Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 85
  86. Chỉ mục Functional dependency : Phụ thuộc hàm Functional determinant: Xác định hàm Normal Form: Dạng chuẩn Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 86
  87. Phụ lục Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm  Thuật toán 4.2 (128, Nguyên lý của các hệ csdl) Bài giảng - CSDL và Phần mềm 11/3/2008 ứng dụng 87