Bài giảng Chương 3: chuẩn hoá cơ sở dữ liệu

Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 1 CHƯƠNG 3: CHUẨN HOÁ CSDL  MỘT SỐ KHÁI NIỆM  CÁC DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ  CHUẨN HOÁ LƯỢC ĐỒ CSDL THÔNG QUA PHÉP TÁCH Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 2 MỘT SỐ KHÁI NIỆM 1. Lược đồ cơ sở dữ liệu:  Lược đồ cơ sở dữ liệu là một tập các quan hệ con và các phụ thuộc hàm liên quan đến một ứng dụng nào đó.  Có nhiều cách để lưu trữ, tổ chức thông tin đối với một ứng dụng cụ thể( có thể xây dựng một hoặc nhiều quan hệ để mô tả cùng một nội dung). Do đó để quản lý, lưu trữ thông tin không bị dư thừa, dễ dàng truy xuất, thêm, bớt thì việc chuẩn hóa các lược đồ quan hệ là rất cần thiết.  Chuẩn hóa một quan hệ là quá trình biến đổi những dữ liệu cập nhật( thêm, xóa, sửa) gây nên những dị thường cho quan hệ thành các dạng phù hợp. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 3 MỘT SỐ KHÁI NIỆM Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 4 MỘT SỐ KHÁI NIỆM 2. Thuộc tính khóa (primary key) - Thuộc tính không khóa (nonprimary key)  Cho lược đồ quan hệ Q (Q+), K Q+ là khóa chỉ định của Q nếu:  Thuộc tính AK  A là thuộc tính khóa  Thuộc tính A K A là thuộc tính không khóa Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 5 MỘT SỐ KHÁI NIỆM 3. Phụ thuộc hàm đầy đủ (Fully functional dependency)  Cho lược đồ quan hệ Q với tập thuộc tính Q+  X,Y là hai tập con khác nhau của Q+, Y được gọi là phụ thuộc hàm đầy đủ vào X nếu có phụ thuộc hàm không hiển nhiên X Y và Y không phụ thuộc hàm vào bất kỳ tập con nào của X. Ghi chú: Để chứng minh một tập thuộc tính Y là không phụ thuộc đầy đủ vào tập thuộc tính X ta cần chứng minh   X Y hoặc XY nhưng  X'X : X'Y Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 6 MỘT SỐ KHÁI NIỆM 4. Phụ thuộc bắc cầu của một tập thuộc tính vào một tập thuộc tính khác.  Cho lược đồ quan hệ Q với tập thuộc tính Q+  X và Y là hai tập con của Q+,X  Y, ta nói Y phụ thuộc bắt cầu vào tập thuộc tính X nếu tồn tại một tập thuộc tính A  Q+ sao cho X A và A Y nhưng A X (A không xác định X) Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 7 CÁC DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ  Quan hệ được chuẩn hóa là quan hệ trong đó mỗi miền của một thuộc tính chỉ chứa những giá trị nguyên tố (atomic), tức là không phân nhỏ được nữa và do đó, mỗi giá trị trong quan hệ cũng là nguyên tố.  Quan hệ có chứa các miền giá trị là không nguyên tố gọi là quan hệ không chuẩn hóa. Một quan hệ được chuẩn hóa có thể thành một hoặc nhiều quan hệ chuẩn hóa khác và không làm mất mát thông tin.  Để đánh giá chất lượng của lược đồ quan hệ người ta đưa ra các tiêu chuẩn gọi là dạng chuẩn. Lược đồ cơ sở dữ liệu ở dạng chuẩn càng cao thì chất lượng càng tốt. Thông thường khi thiết kế cơ sở dữ liệu ta cố gắng đưa các quan hệ về dạng chuẩn 3 hoặc tốt hơn là dạng chuẩn BC. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 8 Dạng chuẩn 1 – 1NF (First Normal Form)  Một lược đồ quan hệ Q được gọi là đạt dạng chuẩn nếu và chỉ nếu tòan bộ các miền ( thuộc tính) có mặt trong Q đều chỉ chứa các giá trị nguyên tố( thuộc tính đơn)  Định nghĩa trên cho thấy bất kỳ quan hệ chuẩn hóa nào cũng ở dạng chuẩn 1NF nếu quan hệ đó không có thuộc tính gộp. Do đó khi mô tả một bảng chỉ nên giữ giá trị đơn tránh dùng các miền thuộc tính giá trị kép như tên bao gồm họ và tên. Trong trường hợp này khi một quan hệ không thuộc 1NF người ta tách thuộc tính kép ra thành các thuộc tính đơn hoặc tách quan hệ ban đầu ra thành hai hoặc nhiều quan hệ khác. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 9 Dạng chuẫn 1 – ví dụ Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 10 Dạng chuẩn 2 – 2NF (Second Normal Form) Cho lược đồ quan hệ Q với tập thuộc tính Q+, Q được gọi là đạt dạng chuẩn 2 nếu:  Q đạt dạng chuẩn 1 và  Các thuộc tính không khóa phụ thuộc đầy đủ vào khóa.  Một bảng thuộc dạng chuẩn một luôn có thể được tách ra thành các bảng tương đương thuộc dạng chuẩn hai. Vì không có thông tin nào bị mất trong việc tách quan hệ, bất kỳ thông tin nào có thể suy ra được từ cấu trúc ban đầu cũng có thể nhận được từ các quan hệ con theo cấu trúc mới.  Dạng chuẩn hai cho phép loại trừ dư thừa về khóa thuộc tính. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 11 Dạng chuẩn 2 – 2NF (Second Normal Form) Ví dụ: Cho lược đồ quan hệ SINHVIEN(MA_SV, MON_HOC, TEN_SV, DIA_CHI, DIEM) , Với các phụ thuộc hàm sau:  f1: MA_SV  TEN_SV, DIA_CHI  f2: MA_SV, MON_HOC DIEM  Khóa là MA_SV, MON_HOC Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 12 Dạng chuẩn 3 – 3NF (Third Normal Form) Một lược đồ quan hệ được gọi là đạt dạng chuẩn 3 nếu:  Đạt được dạng chuẩn 2 và  Các thuộc tính không khóa không phụ thuộc bắc cầu vào khóa chính. Ví dụ 1:  Cho lược đồ quan hệ HOADON(SO_HD, NGAY_LAP, K_HANG, M_HANG, SO_LG, DON_GIA,THANHTIEN)  HOADON CHƯA ĐẠT DANG CHUẨN 3 Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 13 DẠNG CHUẨN BC (BOYE CODD)  Cho lược đồ quan hệ Q với tập phụ thuộc hàm F, lược đồ quan hệ này được gọi là đạt dạng chuẩn BC nếu với mọi phụ thuộc hàm f: XY xác định trên lược đồ quan hệ (XY là không hiển nhiên) thì X là một khóa của lược đồ quan hệ Q.  Như vậy một lược đồ quan hệ đạt được dạng chuẩn BC thì chỉ có phụ thuộc hàm mà vế trái là khóa. Lược đồ quan hệ này hiển nhiên đạt được dạng chuẩn 3.  Để chứng minh vấn đề trên, giả sử rằng lược đồ quan hệ Q là ở dạng BCNF nhưng không thuộc 3NF. Như vậy sẽ tồn tại ít nhất một phụ thuộc hàm thành phần hoặc phụ thuộc hàm bắt cầu.  f1: XY  f2: YA  Trong đó X là khóa của Q, A X, và A Y,Y XF( không tồn tại phụ thuộc hàm này trong tập phụ thuộc hàm của Q) Do đó Y không phải là khóa của Q, mà Y A  F (là một phụ thuộc hàm) cho nên vi phạm điều kiện của BCNF. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 14 PHỤ THUỘC ĐA TRỊ  Giả sử cho R với các thuộc tính A1, A2 ,… An là một lược đồ quan hệ với các tập thuộc tính X,Y  R, ta nói rằng X  Y (X xác định đa trị Y hay Y phụ thuộc đa trị vào X) nếu cho những giá trị X, có một tập giá trị Y liên quan và tập này độc lập với các thuộc tính Z = R-X-Y. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 15 Dạng chuẩn 4 – 4NF (Fourth Normal Form)  Dạng chuẩn 4 là dạng tổng quát của chuẩn BCNF để tách các quan hệ có phụ thuộc đa trị. Như vậy một quan hệ ở dạng chuẩn 4 khi và chỉ khi những phụ thuộc đa trị cơ sở là phụ thuộc trong đó xác định một thuộc tính tức là nếu có phụ thuộc đa trị thì nó có dạng X  A. Một quan hệ ở dạng chuẩn 4 sẽ thuộc dạng BCNF và 3NF.  Ở ví dụ trên nếu tách quan hệ SINH_VIEN thành SV_M_HOC với các thuộc tính MA_SV và MON_HOC và quan hệ SV_T_THAO bao gồm các thuộc tính MA_SV và THE_THAO thì các quan hệ mới này sẽ đạt dạng chuẩn 4. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 16 Chuẩn hóa lược đồ quan hệ thông qua phép tách Định lý:  Cho lược đồ quan hệ Q với tập thuộc tính Q+ phụ thuôïc hàm không hiển nhiên f: XY xác định trên Q. Phép tách Q thành hai quan hệ con Q1 (X,Y) và Q2 (Q+\Y) là phép tách bảo tòan thông tin nghĩa làQ(Q+) = Q1 Q2 Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 17 Chuẩn hóa lược đồ quan hệ thông qua phép tách Dựa vào định lý trên ta có thể chuấn hóa lược đồ quan hệ thông qua phép tách như sau: Cho lược đồ quan hệ Q(Q+) với tập thuộc tính F xác định trên Q. Thuật tóan chuẩn hóa như sau: Bước 1: Xác định tất cả các phụ thuộc hàm F sao cho: F:=F \ fF : VT( f) VP( f) = Q+, trong đó (VT: Vế trái, VP: Vế phải) Bước 2: + Nếu F =  ( không có PTH) thì kết quả là lược đồ quan hệ Q và kết thúc: + Nếu F  thì: . Lấy một PTH f: X Y trong F (nên lấy những PTH mang tính bắt cầu hoặc phụ thuộc bộ phận hay từng phần vào khoá chính). . Tách quan hệ Q thành hai quan hệ Q1 và Q2 dựa vào PTH f Q1 (X,Y) với tập Pth F1 F1= f/ VT( f) VP( F)  XY Q2(Q+\ Y) với tập Pth F2: F2 = f/ VT( f) VP( F)  Q+\ Y Bước 3: Nếu các quan hệ con vẫn còn các pth bắt cầu hoặc phụ thuộc bộ phận hay từng phần thì tiếp tục thực hiện từ bước 1 cho các quan hệ đó cho đến khi không thể tách được nữa. Thursday, July 03, 2014 ThS. Lê Ngọc Lãm Cơ Sở Dữ Liệu 18 NỘI DUNG CHƯƠNG TRÌNH  NHẬP MÔN CƠ SỞ DỮ LIỆU  CƠ SỞ DỮ LIỆU QUAN HỆ  CHUẨN HOÁ CƠ SỞ DỮ LỊÊU  PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG  CƠ SỞ DỮ LIỆU TÀI NGUYÊN ĐẤT ĐAI  CƠ SỞ DỮ LIỆU KHÔNG GIAN