Cơ sở dữ liệu

Database Course

LÝ THUYẾT CƠ SỞ DỮ LIỆU
Chuẩn hóa dữ liệu (Data normalization)
Chapter 5: Logical Database Design and The Relational Model
Mục tiêu: tránh sự dị thường (anomaly) trong các thao tác cập nhật dữ liệu
Insert anomalies
Deletion anomalies
Modification anomalies
Luật cơ bản: Mỗi bảng không nên thuộc về nhiều hơn 1 kiểu thực thể (hay kiểu quan hệ)
Chapter 5: Logical Database Design and The Relational Model
Chuẩn hóa dữ liệu
Cho lược đồ quan hệ:
Sv_mhoc(Ma_sv, ten, ngay_sinh, ten_mh, ngay_kt, diem)





Chapter 5: Logical Database Design and The Relational Model
Sự dị thường trong các phép cập nhật
Insert: Quan tâm đến nhiều thông tin lặp lại
Delete: Xóa Sv02 -> mất thông tin về môn học Lisp
Modify: Sửa tên của Sv01 thì phải sửa ở cả 3 records
Tách quan hệ trên thành 2 quan hệ:
SV Hoc






Đánh giá sự dị thường trong cập nhật (Insert/Delete/Modify) dữ liệu?
Chapter 5: Logical Database Design and The Relational Model
Sự dị thường trong các phép cập nhật
Cho lược đồ quan hệ R(A1, A2, .., An) và hai tập X, Y khác rỗng là tập con của tập thuộc tính của R
Định nghĩa:
FD X->Y (đọc là X xác định hàm Y) là đúng trong R nếu với mọi thể hiện r của R không có hai hàng có cùng giá trị trên X nhưng lại khác giá trị trên Y
FD X->Y là đúng trong R khi với mọi thể hiện r của R và bất kỳ 2 bộ t1, t2 nào đó mà t1[X] = t2[X] thì t1[Y] = t2[Y] (ti[X] là giá trị của X trong ti)
Chapter 5: Logical Database Design and The Relational Model
Phụ thuộc hàm (Functional dependency - FD)
Lưu ý:
Khóa trong quan hệ xác định hàm mọi thuộc tính khác
Nếu có X->Y chưa hẳn là Y->X

Ví dụ: Employee(Ssn, Name, Dob, Age, mgrSsn)
Ssn -> {Name, Dob, Age, mgrSsn}
Ssn -> name; name ->Ssn
Dob -> Age
Chapter 5: Logical Database Design and The Relational Model
Phụ thuộc hàm (Functional dependency - FD)
Nhận xét:
Name -> name, age -> age
If (Ssn -> name) then (Ssn, age -> name)
If (Ssn -> name) and (Ssn -> age) and (Ssn -> mgrSsn) Then (Ssn -> name, age, mgrSsn)
If (Ssn -> Dob) and (Dob -> age) then (Ssn -> age)
Cho R(U,F), pth X -> Y được gọi là một suy dẫn logic từ F, nếu với mọi thể hiện r của R thoả F, thì r cũng phải thoả X -> Y.
Bao đóng của tập phụ thuộc hàm F (ký hiệu F+) là tất cả các phụ thuộc hàm được suy dẫn logic từ F.
Chapter 5: Logical Database Design and The Relational Model
Dẫn xuất từ các phụ thuộc hàm
Tiên đề Armstrong
If Y X then X->Y (reflexivity)
If X->Y then XZ->YZ (Augmentation)
If X->Y and Y->Z then X->Z (Transitivity)

Các qui tắc bổ sung
If X->Y and X->Z then X->YZ (Union)
If X->Y and WY->Z then WX->Z (Pseudotransitivity)
If X->Y and Z Y then X->Z (Decomposition)
Chapter 5: Logical Database Design and The Relational Model
Dẫn xuất từ các phụ thuộc hàm
Siêu khóa (seuperkey)
Là một hay một tập thuộc tính xác định duy nhất một hàng trong bảng
SK là siêu khóa của R khi với mọi t1, t2 thuộc bất kỳ thể hiện r của R ta luôn có t1[SK] ≠ t2[SK]
SK là siêu khóa của R <=> SK xác định hàm mọi thuộc tính của R (SK -> R)
Siêu khóa tối tiểu (minimal superkey)
Siêu khóa tối tiểu K là một siêu khóa kèm thêm tính chất là nếu loại bỏ khỏi K bất kỳ một thuộc tính nào đó thì K không còn là siêu khóa nữa
Chapter 5: Logical Database Design and The Relational Model
Khóa của lược đồ quan hệ
Định nghĩa khóa dựa trên tập phụ thuộc hàm
Cho R(U,F), U là tập thuộc tính, F là tập phụ thuộc hàm trong R
Với X U, X là một khóa của R nếu:
X->U F+ , và
Y X, Y ≠ X, mà Y->U F+
R phải có ít nhất 1 khóa và có thể có nhiều khóa
Chú ý:
Cho R(U), ta luôn có U->U. Nếu U thỏa điều kiện 2 ở trên thì U là khóa
Chapter 5: Logical Database Design and The Relational Model
Khóa của lược đồ quan hệ (2)
Khóa chính (primary key): Là một siêu khóa tối tiểu được người phân tích chọn để cài đặt
Khóa dự tuyển (candidate key): Là các siêu khóa tối tiểu khác không được chọn làm khóa chính
Khi cài đặt vào CSDL, khoá dự tuyển trở thành khóa duy nhất (unique key) và còn được gọi là khóa thứ cấp (secondary key)


Chapter 5: Logical Database Design and The Relational Model
Khóa của lược đồ quan hệ (3)
Khóa giúp cho việc nhận biết và tìm record một cách nhanh chóng trong các quan hệ
Ràng buộc đối với khóa chính: NOT NULL và UNIQUE
Ràng buộc đối với khóa dự tuyển: UNIQUE

Chapter 5: Logical Database Design and The Relational Model
Khóa của lược đồ quan hệ (4)
Bao đóng của tập thuộc tính X tương ứng tập phụ thuộc hàm F (ký hiệu là XF+) là tất cả các thuộc tính A sao cho X->A có thể được suy dẫn logic từ F
Thuật toán tìm XF+

Chapter 5: Logical Database Design and The Relational Model
Bao đóng của tập thuộc tính
Input: R(U, F), X U
Output: XF+
Phương pháp:
X0 = X;
Lặp: Xi+1 = Xi Z sao cho (Y->Z) F và Y Xi cho đến khi Xi+1 = Xi
Ta có XF+ = Xi
Chapter 5: Logical Database Design and The Relational Model
Thuật toán tìm khoá
Cho R(U,F), các ký hiệu trong thuật toán tìm khoá:
Uright(ULeft): Các thuộc tính ở vế phải của tất cả các PTH
N = U – Uright: Các thuộc tính cô lập (không xuất hiện trong bất kỳ FD nào) và các thuộc tính chỉ xuất hiện ở vế trái của các FD
=> N khoá
D = Uright – Uleft: Các thuộc tính chỉ xuất hiện ở vế phải của các FD
=> D khoá
L = U – (N D): là các thuộc tính có thể thuộc hoặc không thuộc khoá
Thuật toán tìm tất cả các khoá của một lược đồ quan hệ dựa trên tập PTH
Chapter 5: Logical Database Design and The Relational Model
Input: R(U, F)
Output: Các khoá của R
Phương pháp:
N = U – Uright. Nếu NF+ = U, thì N là khoá duy nhất của R. Giải thuật dừng
Tìm D = Uright – Uleft, L = U – (N D):
Với mọi Li L: Thử với từng Li, các Li có ít phần tử làm trước
X = N Li, Nếu XF+ = U thì X là một khoá của R
Lưu ý: Nếu X = N Li là khoá thì không thử với các Lj L mà Li Lj
Thuật toán tìm khoá (2)
Chapter 5: Logical Database Design and The Relational Model
Phân rã (decomposition) một lược đồ quan hệ R(U) là thay R bằng tập các lược đồ quan hệ con R1, R2, .., Rk của R sao cho
U1 U2 … Uk = U, với Ui là tập thuộc tính của Ri, trong đó giao của các Ui không nhất thiết phải rỗng
Phân rã các lược đồ quan hệ
Khi muốn khôi phục lại r (thể hiện của R) ta thực hiện phép kết của các ri ( thể hiện của Ri tương ứng)
Hỏi:
Dữ liệu lưu tại các ri có phản ánh trung thực r hay không?
Khi cần có thể khôi phục lại được r từ các ri hay không?
Chapter 5: Logical Database Design and The Relational Model
Cho R(U,F). Nếu R được phân rã bởi phép phân rã ρ thành các Ri, sao cho với mọi thể hiện r(R) thoả tập phụ thuộc hàm F, ta có được r = s (với s có được bằng cách kết các ri), lúc đó ρ được gọi là một phân rã bảo toàn nội dung.
Phân rã bảo toàn nội dung
Khi phân rã bảo toàn nội dung, r ban đầu luôn được tái tạo một các trung thực bằng cách kết nối các ri
Kết trong trường hợp này gọi là kết không mất thông tin (lossless join)
Chapter 5: Logical Database Design and The Relational Model
Định lý:
Cho R(U,F). Phân rã R thành R1, R2 là bảo toàn nội dung (btnd) tương ứng với F nếu và chỉ nếu
R1 R2 -> R1 - R2 hay R1 R2 -> R2 - R1
Phân rã bảo toàn nội dung (2)
Ví dụ: R(ABC), F = {A -> B}
Nếu R được phân rã thành R1(AB) và R2(AC) thì btnd
Nếu R được phân rã thành R1(AB) và R2(BC) thì không btnd
=> Một phép phân rã có btnd hay không là còn tùy thuộc vào tập pth
Chapter 5: Logical Database Design and The Relational Model
Phân rã bảo toàn phụ thuộc hàm
Chiếu của một tập pth F trên tập thuộc tính Z, ký hiệu ¶Z(F), là tập các phụ thuộc hàm X -> Y trong F+ sao cho XY Z
Khi phân rã R(U, F) thành các Ri(Ui, Fi) thì:
Ui = U và Fi = ¶Ui (F)
Phép phân rã ρ là bảo toàn pth nếu:
Fi suy dẫn được tất cả các pth trong F
Chapter 5: Logical Database Design and The Relational Model
Phân rã bảo toàn phụ thuộc hàm (2)
Các pth trong F là các ràng buộc toàn vẹn trên R
Khi phân rã btnd nhưng không bảo toàn pth thì dữ liệu có thể được phục hồi giống như ban đầu nhưng không đảm bảo ràng buộc toàn vẹn dữ liệu
Những pth không được bảo toàn trong phép phân rã cần được kiểm tra, thông qua việc kết nối một số ri, trong quá trình cập nhật dữ liệu
Trường hợp lý tưởng là phân rã vừa btnd vừa bảo toàn pth
Chỉ những phép phân rã bảo toàn nội dung mới được cài đặt

Chapter 5: Logical Database Design and The Relational Model
Chuẩn hoá dữ liệu và các dạng chuẩn
Định nghĩa:
Dạng chuẩn (normal form): Là trạng thái của một quan hệ có được do áp dụng những quy tắc liên quan đến pth của quan hệ đó.

Chuẩn hoá dữ liệu (data normalization) là quá trình phân rã lược đồ quan hệ chưa chuẩn hoá (có dạng chuẩn thấp) thành các lược đồ quan hệ nhỏ hơn nhưng ở dạng chuẩn cao hơn (có cấu trúc tốt hơn)
Chapter 5: Logical Database Design and The Relational Model
Các bước chuẩn hoá
C�c bu?c chu?n hố d? li?u

Chapter 5: Logical Database Design and The Relational Model
Thuộc tính nguyên tố
Thuộc tính nguyên tố (prime attribute)
Còn gọi là thuộc tính khoá (key attribute)
Là thành phần của ít nhất 1 khóa dự tuyển trong R

Thuộc tính không nguyên tố (nonprime attribute)
Là thuộc tính không phải là thuộc tính nguyên tố
Còn gọi là thuộc tính không khoá (nonkey attribute)

Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 1 (First normal form – 1NF)



VD: Lược đồ quan hệ sau không đạt 1NF
Family



=> Làm thế nào để Family đạt 1NF?

Lược đồ quan hệ đạt 1NF nếu mọi hàng trong quan hệ tương ứng có cùng số thuộc tính và các thuộc tính này chỉ chứa các trị nguyên tố
Chapter 5: Logical Database Design and The Relational Model
PTH đầy đủ & PTH riêng phần
PTH đầy đủ (full FD)
X -> Y là pth đầy đủ của Y vào X nếu không có tập con Z nào của X mà Z -> Y đúng trong R

Phụ thuộc hàm riêng phần (partial FD)
Là phụ thuộc hàm không đầy đủ
Y là pth riêng phần vào X (trong pth X->Y) nếu có tập con của X mà Z->Y đúng trong R.
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 2 (Second normal form – 2NF)



Định nghĩa khác:
Lược đồ quan hệ R đạt 2NF nếu:
R đạt 1NF
Mọi thuộc tính không nguyên tố A trong R phụ thuộc hàm đầy đủ vào R
Lược đồ quan hệ R đạt 2NF nếu với mọi FD X->Y đúng trong R thì:
A X hoặc
A là thuộc tính nguyên tố trong R hoặc
X không là tập con của một khoá nào hoặc
X là siêu khoá trong R
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 2 (2)
VD: Lược đồ quan hệ sau không đạt 2NF
Inventory




FD: warehouse -> WHouse-address (vi phạm!!!)
{part, warehouse} -> quantity
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 2 (3)
Lược đồ Inventory nên được phân rã thành các lược đồ sau:
P(part, warehouse, quantity)
F = {part, warehouse -> quantity}

W(warehouse, WHouse-address)
F = {warehouse -> WHouse-address}
Chapter 5: Logical Database Design and The Relational Model
Phụ thuộc hàm bắc cầu (transitive FD)


Đọc là: “A phụ thuộc bắc cầu vào X trong R” hay “X->A là pth bắc cầu”
Định nghĩa khác:
Phụ thuộc hàm X->A đúng trong R là bắc cầu nếu tồn tại tập con khác rỗng của R, Z không phải là tập con của một khoá nào trong R, và các pth X->Z và Z->A là đúng trong R
Nếu X->Z
Z ->X Thì X->A là pth bắc cầu
Z->A
A (X Z)
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 3 (Third normal form – 3NF)




Định nghĩa khác:
Lược đồ quan hệ R đạt 3NF nếu:
R đạt 2NF
Không có thuộc tính không nguyên tố nào của R phụ thuộc hàm bắc cầu vào khoá của R
Lược đồ quan hệ R đạt 3NF nếu với mọi FD X->A đúng trong R thì:
A X hoặc
A là thuộc tính nguyên tố trong R hoặc
X là siêu khoá trong R
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 3 (2)
Ví dụ: SUPPLIER(Id, sname, cname, city)
F = {Id->sname,
Id->cname, cname->city, Id->city}
SUPPLIER nên được phân rã thành các lược đồ sau
S(Id, sname, cname)
F ={Id -> sname, cname}
C(cname, city)
F = {cname -> city}

2NF
3NF
3NF
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 3 (3)
Ví dụ: LOACATION(city, street, zip-code)
F = {city, street -> zip-code, zip-code -> city}
Khoá 1: city, street
Khoá 2: street, zip-code
Lược đồ Location dạt 3NF vì thuộc tính city ở vế phải của FD zip-code -> city là thuộc tính nguyên tố.
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn 3 (4)
Ví dụ: LOACATION(city, street, zip-code)

Vấn đề:
Sự lặp lại của <484, NY> và <473, LA> là dư thừa trong bảng LOCATION
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn Boyce-Codd (BCNF)




Định nghĩa khác:
Lược đồ quan hệ R đạt BCNF nếu nếu với mọi FD X -> A đúng trong R thì X là siêu khóa:

Lược đồ quan hệ R đạt BCNF nếu với mọi FD X->A đúng trong R thì:
A X hoặc
X là siêu khoá trong R
Chapter 5: Logical Database Design and The Relational Model
Dạng chuẩn Boyce-Codd (BCNF - 2)
Ví dụ: SCL(student, course, lecturer)
F = {student, course -> lecturer
lecturer -> course}
Khoá 1: student, course; khoá 2: student, lecturer
SCL không đạt BCNF vì lecturer không là siêu khóa.
SCL đạt 3NF vì thuộc tính course của FD
lecturer -> course là thuộc tính nguyên tố.
Lược đồ SCL nên được phân rã thành:
R1 (lecturer, course); R2 (lecturer, student)

Chapter 5: Logical Database Design and The Relational Model
Chuẩn hoá CSDL
Chuẩn hoá các lược đồ quan hệ
Ví dụ:
S(s#, city, status, p#, qty)
F = { s# -> city, s# -> status, city -> staus,
(s#, p#) -> qty, (s#, p#) -> city, (s#, p#) -> status}
Khoá 1: s#, p#
Đạt 1NF
Không đạt 2NF vì có các FD: s# -> city; s# -> status
Chapter 5: Logical Database Design and The Relational Model
Chuẩn hoá CSDL (2)
Phân rã S(s#, city, status, p#, qty) thành các lược đồ:
SP(s#, p#, qty)
SUPPLIER(s#, city, status)
F = { s# -> city, city -> staus, s# -> status}

Lược đồ SUPPLIER đạt 2NF nhưng không đạt 3NF
Tiếp tục phân rã SUPPLIER thành:
SUPPLIER(s#, city)
LOACTION(city, status)
BCNF
2NF
BCNF
BCNF
Chapter 5: Logical Database Design and The Relational Model
Tổng kết về chuẩn hoá CSDL
Mục tiêu của các dạng chuẩn trên quan hệ là hạn chế những dư thừa trong dữ liệu lưu trữ.
Những dư thừa dữ liệu là do phát sinh từ mối liên quan giữa các mục dữ liệu thể hiện qua các phụ thuộc hàm.
Dư thừa dữ liệu dẫn đến những dị thường khi thêm, xoá, cập nhật dữ liệu.
Chapter 5: Logical Database Design and The Relational Model
Tổng kết về chuẩn hoá CSDL (2)
Trong 2NF và 3NF vẫn còn dư thừa dữ liệu
2NF: loại được sự phụ thuộc riêng phần vào khoá, vẫn tồn tại phụ thuộc bắc cầu vào khoá.
3NF: loại được sự phụ thuộc bắc cầu vào khoá đối với những thuộc tính không nguyên tố.
BCNF: loại bỏ mọi dư thừa dữ liệu mà phụ thuộc hàm có thể tạo ra (không thể suy ra giá trị tại một ô nào trong bảng bằng cách chỉ sử dụng các phụ thuộc hàm cùng với các số liệu đang có trong bảng).
Dạng chuẩn của 1 lược đồ csdl bằng với dạng chuẩn của lược đồ quan hệ có dạng chuẩn thấp nhất
Chapter 5: Logical Database Design and The Relational Model
Tổng kết về chuẩn hoá CSDL (3)
Để đạt được dạng chuẩn cao (ít dư thừa dữ liệu), một lược đồ quan hệ thường được phân rã thành nhiều lược đồ quan hệ con.
Một lược đồ quan hệ luôn có thể được phân rã thành các lược đồ quan hệ con đạt 3NF vừa bảo toàn nội dung vừa bảo toàn phụ thuộc hàm.
Một lược đồ quan hệ luôn có thể được phân rã thành các lược đồ quan hệ con đạt BCNF bảo toàn nội dung nhưng có thể không bảo toàn được tập phụ thuộc hàm.