Bài giảng Cơ sở dữ liệu: Chương 3 - Ths. Lê Ngọc Lãm

Chia sẻ: Hồ Ky | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

163
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 3 Chuẩn hoá cơ sở dữ liệu thuộc bài giảng cơ sở dữ liệu, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu một số nội dung chính sau: một số khái niệm, các dạng chuẩn của lược đồ quan hệ, chuẩn hóa lược đồ cơ sở dữ liệu thông qua phép tách.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu: Chương 3 - Ths. Lê Ngọc Lãm

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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 1
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 2
MỘT SỐ KHÁI NIỆM ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 3
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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 4
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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 5
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) ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 6
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 7
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 8
Dạng chuẫn 1 – ví dụ ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 9
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 10
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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 11
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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 12
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 13
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 14
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. ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 15
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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 16
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: thể chuấ lượ phé 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: lượ thuộ Thuậ chuẩ sau: Bướ Bước 1: Xác định tất cả các phụ thuộc hàm F sao cho: phụ thuộ cho: F:=F \ fF : VT( f) VP( f) = Q+, trong đó (VT: Vế trái, VP: Vế phải) Q+ trá phả Bướ 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: thì quả lượ thú + Nếu F  thì: 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ộ X (nên nhữ hoặ phụ thuộ phận hay từng phần vào khoá chính). phậ phầ khoá chí nh). . Tách quan hệ Q thành hai quan hệ Q1 và Q2 dựa vào PTH f thà Q1 (X,Y) với tập Pth F1 F1= f/ VT( f) VP( F)  XYXY Q2(Q+\ Y) với tập Pth F2: Q2(Q+\ F2 = f/ VT( f) VP( F)  Q+\ Y Q+\ Bướ 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 hoặ phụ thuộ phậ phầ thì tiế 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. thự hiệ bướ thể đượ ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 17
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 ThS. Lê Ngọc Lãm Ngọ Thursday, July 03, 2014 Cơ Sở Dữ Liệu Sở Liệ 18