Đại Học Bách Khoa Hà Nội
Khoa Điện Tử - Viễn Thông10/2006
Ch??ng III:
C? S? D? LI?U3.3. Chu?n hóa
Nội dung
3.3.1. Giới thiệu.
1. M?c đích & Các khái niệm.
2. Các mức (dạng) chuẩn hóa.
3.3.2. Khái niệm phụ thuộc hàm.
1. Định nghĩa.
2. Hệ tiên đề Amstrong và các bổ đề.
3. Khái niệm bao đóng.
4. Phụ thuộc hàm đầy đủ.
Nội dung
3.3.3. Các mức (dạng) chuẩn hóa.
1. Mức ch?a chu?n hóa.
2. Mức 1NF.
3. Mức 2NF.
4. Mức 3NF.
5. Mức BCNF.
3.3.4. Phép tách sơ đồ quan hệ.
1. Phép tách bảo toàn thông tin.
2. Phép tách bảo toàn tập phụ thuộc hàm.
3.3.5. Kết luận.
1. Các bước đưa về các dạng chuẩn hóa.
2. Kết luận.
3.3.1. Giới thiệu.
1. Mục đích & Các khái niệm.
Mục đích
Mục đích của chuẩn hóa
Khái niệm
Các vấn đề với dữ liệu
Redundancy
Inconsistency
Các dị thường (anomalies)
Update
Insert
Delete
3.3.1. Giới thiệu.
2. Các mức chuẩn hoá.

Hình 3.1. Các mức của chuẩn hoá
3.3.2. Phụ thuộc hàm.
1. Định nghĩa
Cho trước quan hệ R với tập thuộc tính U={A1, A2, ...An}, ta có X, Y ? U là tập các thuộc tính con của U. Ta nói Y là phụ thuộc hàm vào X (hay X suy ra Y) nếu và chỉ nếu với mọi quan hệ r xác định trên R và với mọi 2 bộ t1, t2 bất kỳ, nếu t1[X] = t2[X] thì suy ra t1[Y] = t2[Y] tại bất kỳ thời điểm nào.
Ký hiệu:
X ? Y
Lưu ý:
Có thể không có t1[X] = t2[X] nhưng vẫn tồn tại phụ thuộc hàm.
Yếu tố: tại bất kỳ thời điểm nào.
3.3.2. Phụ thuộc hàm.
2. Hệ tiên đề Amstrong và bổ đề
Hệ tiên đề
Phản xạ (reflexivity): nếu Y ? X ? U thì X ? Y
Tăng trưởng (augmentation): nếu X ? Y, Z ? U thì XZ ? YZ
Bắc cầu (transitivity): nếu X ? Y, Y ? Z thì Y ? Z
Bổ đề
nếu X ? Y, X ? Z thì X ? YZ
nếu X ? Y, WY ? Z thì XW ? Z
nếu X ? Y, Z ? Y thì X ? Z


3.3.2. Phụ thuộc hàm.
3. Khái niệm bao đóng
Bao đóng của tập phụ thuộc hàm F+
Tập hợp tất cả các phụ thuộc hàm được suy ra từ F
Tập phụ thuộc hàm F tối thiểu
Nếu không tồn tại một phụ thuộc hàm X ? Y ? F sao cho: F {X ? Y} tương đương với F
Cách tìm:
vế phải của các phụ thuộc hàm chỉ để 1 thuộc tính
vế trái của các phụ thuộc hàm không bỏ được thuộc tính nào
không có phụ thuộc hàm nào bỏ được
Bao đóng của tập các thuộc tính X+
Tập hợp tất cả các các thuộc tính phụ thuộc hàm vào X
X+ = {A | A là thuộc tính sao cho X ? A ? F+}
3.3.2. Phụ thuộc hàm.
4. Phụ thuộc hàm đầy đủ
Định nghĩa
Tập thuộc tính Y được gọi là phụ thuộc hàm đầy đủ vào tập thuộc tính X nếu nó là phụ thuộc hàm vào X và không phụ thuộc hàm vào bất kỳ một tập con nào của các thuộc tính của X.
Khoá tối thiểu
X ? U ? F+
Với mọi X' là tập con thực sự của X, không tồn tại: X' ? U
Lưu ý
Sau đây chúng ta sẽ nói "phụ thuộc hàm" với ý nghĩa phụ thuộc hàm đẩy đủ trừ khi có giải thích tường minh .
3.3.3. Các mức chuẩn hóa.
1. Mức 0NF
Ví dụ
Mức 1NF
Định nghĩa
Quan hệ R được gọi là ở dạng chuẩn thứ nhất (1NF) nếu và chỉ nếu tất cả các miền đều chỉ chứa các giá trị nguyên tố.
3.3.3. Các mức chuẩn hóa.
3. Mức 2NF
Định nghĩa
Quan hệ R được gọi là ở dạng chuẩn thứ hai (2NF) nếu và chỉ nếu nó ở dạng chuẩn thứ nhất và mọi thuộc tính không khoá đều phụ thuộc hàm đầy đủ vào khoá chính.
Một thuộc tính được gọi là thuộc tính không khoá nếu nó không tham dự vào thành phần của khoá chính hoặc khóa ứng cử.
ý nghĩa
Giảm vấn đề dư thừa và không nhất quán của dữ liệu.
3.3.3. Các mức chuẩn hóa.

Nhận xét
Nếu mức 1NF có khóa là khoá đơn: 1NF => 2NF
Nếu mức 1NF không có thuộc tính không khóa: 1NF => 2NF
Chuyển từ 1NF sang 2NF: phép tách sơ đồ quan hệ
Thay thế các quan hệ mức 1NF bằng tập các quan hệ ở mức 2NF thông qua các ánh xạ
Các vấn đề cần giải quyết khi thực hiện phép tách
Bảo toàn thông tin khi chuyển đổi.
Bảo toàn tập phụ thuộc hàm.
Ví dụ
3.3.3. Các mức chuẩn hóa.

Các vấn đề còn tồn tại với mức 2NF
Phụ thuộc hàm bắc cầu vẫn tồn tại và tạo ra sự dư thừa dữ liệu.
Ví dụ: giả sử City ? Status (Status phụ thuộc hàm gián tiếp vào khoá S#) hoặc ví dụ quan hệ (S#, ITEM, PRICE) có S# là khoá và ITEM ? PRICE
Các phụ thuộc hàm bắc cầu này gây ra những khó khăn khi thực hiện các phép toán:
Insert
Delete
Update
3.3.3. Các mức chuẩn hóa.
4. Mức 3NF
Định nghĩa
Quan hệ R được gọi là ở dạng chuẩn thứ ba (3NF) nếu và chỉ nếu nó ở dạng chuẩn thứ 2 (2NF) và mọi thuộc tính không khoá đều không phụ thuộc hàm bắc cầu vào khoá chính thông qua các thuộc tính không khoá.
Y gọi là phụ thuộc hàm bắc cầu vào X thông qua Z nếu Y phụ thuộc hàm vào Z (Z?Y) và Z lại phụ thuộc hàm vào X (X?Z) (với điều kiện X không phụ thuộc hàm vào Z hoặc Y).
ý nghĩa
Làm biến mất các phụ thuộc hàm bắc cầu của các thuộc tính không khoá.
Giảm vấn đề dư thừa và không nhất quán của dữ liệu.

3.3.3. Các mức chuẩn hóa.

Cách nhận biết mức 3NF
Quan hệ R mức 1NF là 3NF nếu mọi phụ thuộc hàm tối thiểu X?A (A là thuộc tính đơn, A ? X) đều có dạng:
hoặc X là khoá
hoặc A là thuộc tính khoá
Chuyển sang 3NF: phép tách sơ đồ quan hệ
Thay thế các quan hệ mức 2NF bằng tập các quan hệ ở mức 3NF thông qua các ánh xạ
Các vấn đề cần giải quyết khi thực hiện phép tách
Bảo toàn thông tin khi chuyển đổi.
Bảo toàn tập phụ thuộc hàm.
Ví dụ
Định lý: quan hệ mức 1NF luôn có thể tách thành các sơ đồ quan hệ con mức 3NF mà vẫn bảo toàn thông tin.
3.3.3. Các mức chuẩn hóa.

Lưu ý:
mức độ chuẩn hoá đối với một lược đồ quan hệ đã cho được xác định bởi ngữ nghĩa (semantic) chứ không phải bởi các giá trị đã có mặt trong quan hệ tương ứng tại một thời điểm cụ thể nào đó
phải biết ý nghĩa của dữ liệu rồi mới có thể đưa ra nhận định hiện tại lược đồ tương ứng của quan hệ đó ở dạng chuẩn nào
HQTCSDL không thể khẳng định rằng một lược đồ quan hệ đã ở dạng chuẩn tốt nhất (3NF chẳng hạn) nếu như chưa nhận đầy đủ thông tin về các phụ thuộc dữ liệu tương ứng
3.3.3. Các mức chuẩn hóa.

Các vấn đề còn tồn tại với mức 3NF
Phụ thuộc hàm bắc cầu của các thuộc tính khoá vẫn có thể tồn tại và tạo ra sự dư thừa dữ liệu.
Ví dụ:

3.3.3. Các mức chuẩn hóa.
5. Mức BCNF (Boyce ? Codd Normal Form)
Định nghĩa
Một thuộc tính (có thể là thuộc tính ghép) được gọi là thuộc tính quyết định (determinant) nếu một thuộc tính khác nào đó là phụ thuộc hàm đầy đủ vào nó.
Quan hệ đã được chuẩn hoá R được gọi là ở dạng chuẩn BCNF nếu mọi thuộc tính quyết định đều là khoá ứng cử (candidate key).
ý nghĩa
Làm biến mất các phụ thuộc hàm bắc cầu.
Sơ đồ quan hệ sẽ không còn vấn đề dư thừa và không nhất quán của dữ liệu.
3.3.3. Các mức chuẩn hóa.
Nhận xét
Boyce và Codd xem xét các phụ thuộc hàm của cả các khoá ứng cử trong quan hệ.
Đối với quan hệ chỉ có một khoá ứng cử thì các định nghĩa 3NF và BCNF là tương đương.
BCNF không nêu lên điều kiện đầu tiên quan hệ đã cho phải ở dạng chuẩn 3NF và sau đó mới thoả mãn thêm điều kiện nữa. Như vậy:
cần lưu ý là định nghĩa BCNF không hoàn toàn tương đương với định nghĩa 3NF.
định nghĩa 3NF không hoàn toàn phù hợp với trường hợp của một quan hệ có hai khoá ứng cử phủ nhau như sẽ xem xét sau này.
Hai khoá ứng cử là tập phủ nếu mỗi khoá gồm hơn một thuộc tính và có thuộc tính chung
Tuy nhiên, điều sau đây vẫn còn đúng:
Bất kỳ một quan hệ nào không ở dạng chuẩn 3NF (hay BCNF) đều có thể được tách thành một tập tương đương ở dạng chuẩn 3NF (hay BCNF)
Nếu quan hệ ở mức BCNF thì cũng đã đạt mức 3NF.
3.3.3. Các mức chuẩn hóa.

Cách nhận biết mức BCNF
Quan hệ R mức 1NF là BCNF nếu mọi phụ thuộc hàm tối thiểu X?A (A là thuộc tính đơn, A ? X) đều có dạng X là khoá.
Là 1NF và không có bất cứ một phụ thuộc hàm bắc cầu nào.

3.3.3. Các mức chuẩn hóa.

Xét các trường hợp cụ thể
Trường hợp 1:
Đối với quan hệ chỉ có một khoá ứng cử thì các định nghĩa 3NF và BCNF là tương đương
Ví dụ
Trường hợp 2:
Quan hệ là 3NF và BCNF vì có hai khoá ứng cử không phủ nhau (non-overlapping)
Ví dụ
Xét ví dụ trong đó quan hệ S là 3NF và cũng là BCNF vì có hai khoá ứng cử không phủ nhau: S(S#, SNAME, STATUS, CITY)

3.3.3. Các mức chuẩn hóa.

Xét các trường hợp cụ thể
Trường hợp 3:
Quan hệ là 3NF nhưng không là BCNF vì khoá ứng cử là tập phủ
Ví dụ 1: Xét quan hệ SSP(S#, SNAME, P#, QTY)
Ví dụ 2: Xét quan hệ SJT với các thuộc tính S (Student), J (Subject), T (Teacher)
ý nghĩa của một bộ trong quan hệ SJT là một sinh viên được chỉ định được học một môn được chỉ định là do một giáo viên được chỉ định dạy
Mỗi môn học cho mỗi sinh viên học môn đó chỉ do một giáo viên dạy
Mỗi giáo viên chỉ dạy một môn học
Mỗi môn học có thể do một vài giáo viên dạy
Hình 3.11. Bảng dữ liệu mẫu cho quan hệ SJT
3.3.3. Các mức chuẩn hóa.

Xét các trường hợp cụ thể
Trường hợp 4:
Quan hệ là 3NF và cũng là BCNF mặc dù có khoá ứng cử là tập phủ
Ví dụ: quan hệ EXAM với các thuộc tính S (Student), J (Subject), P (Position)
ý nghĩa của một bộ của quan hệ EXAM là một sinh viên được chỉ định đã thi một môn học được chỉ định sẽ đạt được một vị trí đã chỉ định trong danh sách lớp
Với mục đích của bài toán, đưa ra một giả thiết không thể có hai sinh viên cùng nhận một vị trí trong một môn học nào đó
RELATION EXAM (S, J, P)
(S, J) ? P
(J, P) ? S
KEY (S, J)
UNIQUE (J, P)

3.3.4. Phép tách sơ đồ quan hệ.
1. Phép tách bảo toàn thông tin.
Xét ví dụ cụ thể
R(A, B, C)
3.3.4. Phép tách sơ đồ quan hệ.
1. Phép tách bảo toàn thông tin.
Xét ví dụ cụ thể
Phép tách mất thông tin: tách theo cột B
R(A, B, C) R1(A, B) R2(B,C) R'(A,B,C)
3.3.4. Phép tách sơ đồ quan hệ.
1. Phép tách bảo toàn thông tin.
Xét ví dụ cụ thể
Phép tách bảo toàn thông tin: tách theo cột C
R(A, B, C) R1(A, C) R2(B,C) R''(A,B,C)
3.3.4. Phép tách sơ đồ quan hệ.
1. Phép tách bảo toàn thông tin.
Định lý:
Phép tách bảo toàn thông tin quan hệ R (với tập phụ thuộc hàm F) thành (R1, R2) khi và chỉ khi:
(R1 ? R2) ? (R1R2) ? F+ hoặc
(R1 ? R2) ? (R2R1) ? F+
Cách nhận dạng:
Xét ví dụ: R(S, A, I, P), F(S?A, SI?P, P?S), tách: SA, SI, IP, PS
Lập bảng giá trị
Xét dòng i, cột j
viết a nếu Aj ? Ri
bi nếu Aj ? Ri
Thông qua phụ thuộc hàm để sửa giá trị
Cuối cùng nếu nhận được dòng toàn a => phép tách bảo toàn thông tin
2. Phép tách bảo toàn tập phụ thuộc hàm.
Xét ví dụ cụ thể
R(City, Street, PostalCode)
F(CS?P, P?C) tách thành (SP, CP), dễ thấy đây là phép tách bảo toàn thông tin.









Khi hợp lại, dễ dàng nhận thấy phụ thuộc hàm CS?P đã không còn tác dụng.
3.3.4. Phép tách sơ đồ quan hệ.
3.3.4. Phép tách sơ đồ quan hệ.
2. Phép tách bảo toàn tập phụ thuộc hàm.
Kết luận
Phép tách quan hệ có thể dẫn tới các trường hợp sau:
Bảo toàn thông tin + Bảo toàn tập phụ thuộc hàm
Không bảo toàn thông tin + Bảo toàn tập phụ thuộc hàm
Bảo toàn thông tin + Không bảo toàn tập phụ thuộc hàm
Không bảo toàn thông tin + Không bảo toàn tập phụ thuộc hàm
Việc kiểm tra tính bảo toàn tập phụ thuộc hàm là rất khó khăn và tốn nhiều thời gian
Định lý:
Mọi quan hệ luôn có thể tách thành các sơ đồ quan hệ con mức 3NF mà vẫn bảo toàn thông tin và bảo toàn tập phụ thuộc hàm.
Mọi quan hệ ít nhất mức 1NF luôn có thể tách thành các sơ đồ quan hệ con mức BCNF mà vẫn bảo toàn thông tin.
Việc chứng minh các định lý trên sẽ đưa ra phương pháp tách sơ đồ quan hệ.
3.3.4. Phép tách sơ đồ quan hệ.

một cách tách thành 3NF:
R(A1, A2, ..., An),
Tập phụ thuộc hàm tối thiểu: F(X1?A1, X2?A2, ..., Xn?An)
K là 1 khoá của R
Phép tách {X1A1, X2A2, ..., XnAn} U {K} sẽ đảm bảo các tính chất bảo toàn và đưa ra mức 3NF
Nhận xét:
{X1A1, X2A2, ..., XnAn} đảm bảo tính bảo toàn tập phụ thuộc hàm và 3NF
thêm khóa K => đảm bảo tính bảo toàn thông tin, nhưng nếu 1 trong n quan hệ con đã có chứa K thì quan hệ con K không cần xét đến
Có thể tách 1 quan hệ thành BCNF, bảo toàn thông tin nhưng chưa chắc đã bảo toàn tập phụ thuộc hàm, đồng thời việc kiểm tra tính bảo toàn tập phụ thuộc hàm là rất khó và tốn nhiều thời gian => trong thực tế nhà thiết kế thường dừng ở mức 3NF (Xem slide 28)
R(City, Street, PostalCode)
F(CS?P, P?C) tách thành (SP, CP) là những quan hệ BCNF nhưng phép tách không bảo toàn tập phụ thuộc hàm
3.3.5. Kết luận.
1. Các bước đưa về các dạng 4NF.
B??c 1: Chuyển quan hệ chưa chuẩn hóa thành 1 tập quan hệ tương đương ở dạng 1NF.
2 phương pháp:
Cách 1: Loại bỏ các nhóm lặp bằng cách đưa dữ liệu thích hợp vào các cột trống của các hàng chứa dữ liệu lặp
Cách này thường được gọi là ?làm phẳng? (flattening)
Bằng cách này sữ dư thừa đã được đưa vào quan hệ kết quả, tuy nhiên sự dư thừa này sẽ được loại bỏ trong quá trình chuẩn hóa
Cách 2:
Chỉ định một hoặc một nhóm các thuộc tính làm khóa chính cho bảng chưa chuẩn hóa
Loại bỏ các nhóm lặp bằng cách mang nhóm các thuộc tính lặp lại cùng bản copy của khóa chính sang một quan hệ tách biệt
Nhận diện các khóa chính của các quan hệ mới
Nếu bảng chưa chuẩn hóa có chưa hơn một nhóm lặp lại hay các nhóm lặp lại lồng nhau thì cách này được lặp đi lặp lại cho đến khi không còn nhóm lặp nữa.

3.3.5. Kết luận.
Ví dụ: Xét hoạt động của một công ty cho thuê văn phòng.
Với giả thiết:
Mỗi khách hàng chỉ được thuê một văn phòng 1 lần
Mỗi khách hàng chỉ được thuê tối đa 1 văn phòng tại 1 thời điểm,

3.3.5. Kết luận.
Giả sử có 2 khách hàng, thông tin về 2 khách hàng thuê được biểu diễn dưới dạng bảng Customer_Rental:

3.3.5. Kết luận.
Thuộc tính khóa chính được nhận diện cho bảng chưa chuẩn hóa Customer_Rental là Customer_No.
Nhóm lặp lại: (Property_No, PAddress, RentStart, RentFinish, Rent, Owner_ No, OName).
Để chuyển thành 1NF, phải đảm bảo chỉ có một giá trị tại mỗi ô của bảng.
2 Cách chuyển thành 1NF:
Cách 1: Loại bỏ nhóm lặp bằng cách đưa dữ liệu tương ứng của khách hàng vào từng hàng của bảng.

3.5. Kết luận.
3.5.2. Kết luận.

Đại Học Bách Khoa Hà Nội, Khoa Điện Tử - Viễn Thông2004-2005
Nguời soạn:
PGS.TS. Nguy?n Việt Hương
email:
Th.S. Nguy?n Hoài Giang
email: giangnh0@yahoo.com
Xin cảm ơn!