Thiết kế CSDL

CHƯƠNG IV: THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ
�1. Quá trình thiết kế cơ sở dữ liệu
�2. Phụ thuộc hàm
�3. Phép tính tách lược đồ quan hệ
�4. Chuẩn hoá lược đồ quan hệ
1. PHỤ THUỘC HÀM
1.1. Một số định nghĩa
1.2. Hệ tiên đề Armstrong
1.3. Tính đóng của tập thuộc tính X (X+F)
1.4. Phủ của tập phụ thuộc hàm. Tập phụ thuộc hàm tối tiểu
1.1. Một số định nghĩa
Định nghĩa 1:
Cho U là một tập thuộc tính, R(U) là một lược đồ quan hệ trên U. Giả sử X, Y ? U, Y được gọi là phụ thuộc hàm vào X trên lược đồ R(U), nếu ?r ? R(U) và ? t1, t2 ? r , t1[X]=t2[X] kéo theo t1[Y] = t2[Y]. Kí hiệu: X ? Y.
Một quan hệ r trên U được gọi là thoả mãn phụ thuộc hàm X? Y nếu và chỉ nếu t1[X] = t2[X] => t1[Y] = t2[Y], ? t1, t2 ? r.

1.1. Một số định nghĩa
Định nghĩa 1: (tiếp theo)
Cho tập F những phụ thuộc hàm (trên lược đồ quan hệ R(U)). Ta nói (X?Y) được suy diễn từ F nếu
? r ? R(U), r thoả F kéo theo r thoả X? Y. Kí hiệu F=(X?Y).
Bao đóng của tập phụ thuộc hàm F là tập phụ thuộc hàm được suy diễn từ F và kí hiệu F+.
F+ = {(X?Y) | F = (X?Y)}
Nếu F+ = F thì F được gọi là họ phụ thuộc hàm đầy đủ.


1.1. Một số định nghĩa
Định nghĩa 2:(Khoá)
Giả sử U là một tập thuộc tính, R=R(U) là một lược đồ quan hệ trên U và K ? U. K là khoá của R nếu:
(K?U) ?F+. Nghĩa là (? r ? R) (?t1, t2 ? r) t1[K]=t2[K] => t1=t2
Không có tập con thực sự nào của K xác định hàm U.


1.2. Hệ tiên đề Armstrong
Hệ tiên đề Armstrong gồm ba tính chất:
A1. Phản xạ:
Nếu Y ? X => X ? Y
A2. Tăng trưởng
X?Y => XZ?YZ (với Z ?U)
A3. Bắc cầu
Nếu X ?Y ? Y?Z => X?Z

Các quy tắc suy diễn bổ sung
Quy tắc hợp: X?Y?X?Z => X?YZ
Quy tắc bắt cầu giả: X?Y?WY?Z => WX?Z
Quy tắc tách: {X?Y, Z? Y} => X?Z
1.3. Bao đóng của tập thuộc tính X
Giả sử X là tập thuộc tính, F là tập phụ thuộc hàm. Bao đóng của X đối với tập phụ thuộc hàm F là tập những thuộc tính A sao cho (X?A) được suy diễn từ F nhờ hệ tiên đề Armstrong.
Nghĩa là X+F = {A | F =Arm (X?A)}
D?nh lý 1
F = Arm (X ?Y) <=> Y ? X+F
Kiểm tra một PTH (X ?Y) có được suy diễn từ F không?
Ta có thể sử dụng bổ đề 3.3
F = Arm (X ?Y) <=> Y ? X+F

Thuật toán (tìm X+F)
Input: Tập hữu hạn thuộc tính U,
Tập phụ thuộc hàm F ={Li ?Ri , i=1..m}
Tập X ? U.
Output: X+F
Phương pháp:
Bước 1: Gán X0 = X
Bước 2: Giả sử tìm được Xk
Nếu tồn tại một Li ? Ri ?F và Li ? Xk thì tính Xk+1 = Xk? Ri
Ngược lại, chuyển sang bước 3
Bước 3: Gán X+F = Xk và kết thúc thuật toán.
Ví dụ: Tính X+F
Cho F = {AB?C, C?A, BC?D, ACD?B, D?EG, BE?C, CG?BD, CE?AG} và X=BD. Tìm X+F
Giải
X0 = X
Chọn D?EG, ta có: X1= X0 ?EG = BDEG
Chọn BE?C, ta có: X2= X1 ?C = BCDEG
Chọn C?A, ta có: X3= X2 ?A = ABCDEG
Dừng X+F = ABCDEG



Các tính chất của bao đóng của tập thuộc tính X+
Nếu X,Y là các tập con của tập thuộc tính Q thì ta có các tính chất sau đây:
1. Tính phản xạ: X ⊆ X+
2. Tính đơn điệu: Nếu X ⊆ Y thì X+ ⊆ Y+
3. Tính luỹ đẳng: X++ = X+
4. (XY)+ ⊇ X+Y+
5. (X+Y)+ = (XY+)+= (X+Y+)+
6. X → Y∈ F+ ⇔ Y ⊆ X+
7. X → Y ⇔ Y+ ⊆ X+
1.4. Phủ của tập các phụ thuộc hàm.
Tập phụ thuộc hàm tối tiểu
Cho F và G là hai tập PTH.
Ta nói F phủ G nếu G+ ?F+
F và G được gọi là tương đương nhau nếu F phủ G và ngược lại, kí hiệu: F ~ G
Để kiểm tra hai tập PTH tương đương và tập nào phủ tập nào, ta sử dụng tính đóng của tập thuộc tính.


Ví dụ:
Kiểm tra xem hai tập PTH sau có tương đương không?
F ={A?B, B?A, A?C, C?A, B?C}.
G1= {A?B, B?C, C?A}

Tập PTH hàm tối tiểu
Tập phụ thuộc hàm F là tối tiểu nếu:
Vế phải của mỗi PTH có đúng một thuộc tính.
Không thể bỏ đị một PTH nào trong F mà vẫn thu được một tập PTH tương đương với nó.
Không thể bỏ đi bất kì một thuộc tính nào ở vế trái của một PTH nào trong F mà vẫn thu được một tập phụ thuộc hàm tương đương với nó.

Thuật toán tìm tập PTH tối tiểu F.
1. Tách các PTH hàm của F về phải hơn một thuộc tính thành các PTH vế phải chỉ có một thuộc tính (được F1)
2. Loại bỏ những PTH của F1 dư thừa ta thu được F2
3. Loại bỏ những thuộc tính dư thừatrong vế trái của các PTH trong F2 ta được F3.
(F3 chính là tập PTH tối tiểu tương đương với F.)
Ví dụ:
Cho F ={A?B, B?A, A?C, C?A, B?C}. Ta có hai tập PTH tương đương với nó là:
F1= {A?B, B?C, C?A}
F2= {A?B, B?A, A?C, C?A}
1.5. Tập phụ thuộc hàm rút gọn tự nhiên
Cho tập PTH F={ Fi: Li  Ri; Li, Ri  U; i = 1  m }, F ở dạng rút gọn tự nhiên nếu như:
Li  Ri = 
Li  Lj  i  j ( i,j = 1...m)

Thuật toán tìm tập PTH rút gọn tự nhiên
B1. Loại bỏ các thuộc tính ở vế phải có mặt ở cả 2 vế trên cùng một PTH
B2. Nếu: Li→Ri và Lj→ Rj (với Li = Lj) thì thay 2 PTH này bởi PTH mới: Li → Ri  Rj
Ví dụ: Tìm tập PTH rút gọn tự nhiên F
F= {AB ? BC
B ? D
BE ? GA
CD ? E
BE ? DC }
=>
F`= {AB ? C
B ? D
BE ? GADC
CD ? E }
2. KHÓA
2.1. Siêu khóa:
Cho một lược đồ quan hệ R= ( U, F), S  U, S được gọi là siêu khóa của  nếu S+ = U.
2.2. Khóa:
Cho một lược đồ quan hệ R= U, F), K  U, K được gọi là khóa của R nếu K là siêu khóa nhỏ nhất (ít thuộc tính nhất) trong các siêu khóa S ( Not  X  K | X+ = U).
2.3. Giải thuật tìm một khóa:
Input: U, F
Output: K ? U, K+ = U
Actions:
K=U
For each an attrib A in K
If (K-A)+ =U then
K=K-A
Endif
Endfor
Return K
Ví dụ:
Cho U={ ABCDEGHI }
F={ A → BCDEGHI; B → IDGE; G → H; I → DEGB; BC→A}
Tìm khóa
K= ABCDEGHI
- Xét A: (k –A)+ = U => K= BCDEGHI
- Xét B: (k –B)+ = (CDEGHI)+ = U => K= CDEGHI
- Xét C: (k –C)+ = (DEGHI)+ = DEGHI <> U => K=CDEGHI
- Xét D: (k –D)+ = (CEGHI)+ = CEGHIBDA =U => K= CEGHI
- Xét E: (k –E)+ = (CGHI)+ = CGHIEDBA = U => K= CGHI
- Xét G: (k –G)+ = (CHI)+ = CHIDEGBA = U => K= CHI
- Xét H: (k –H)+ = (CI)+ = CIDEGBAH = U => K= CI
- Xét I: (k –I)+ = C+ = C <> U => K= CI
Khoá của lược đồ quan hệ trên là : CI
2.4. Giải thuật tìm tất cả các khóa
Bước 1: Đưa tập phụ thuộc hàm F về dạng rút gọn tự nhiên.

Bước 2:

Bước 3: Xác định lược đồ quan hệ R’ = R – U0 I; U’=U – U0 I
F’: là tập PTH của F xác định trên tập thuộc tính U’
( F’ : F/ U’)
Bước 5: xác định khóa KR ’
Bước 6: đưa về khóa KR = U0  KR’

Ví dụ:
Cho U={ ABCDEGHIJL }
F={AI ?IECD, ADJ ?GH, CDL ? ABD, CDL?EHL }
Tìm khĩa c?a ?
- Bu?c 1: F={AI?ECD, ADJ ? GH; CDL ? ABEH }
- Bu?c 2: U0 = ABCDEGHIJL - ABCDEGH = IJL
- Bu?c 3: I= ABCDEGH - ACDIJL = BEGH
- Bu?c 4: U` = ABCDEGHIJL - BEGHIJL = ACD
=> F`={ A? CD, CD ? A}
- Bu?c 5: X�c d?nh khĩa KR` = {A, CD}
- Bu?c 6: x�c d?nh khĩa KR = IJL ? {A, CD} = {AIJ L, CDIJ L}
3. CHUẨN HÓA CƠ SỞ DỮ LIỆU
3. 1. Chuẩn hóa lược đồ quan hệ của CSDL
Chuẩn hóa CSDL là quá trình áp dụng các qui tắc để chuyển các lược đồ quan hệ thành các dạng chuẩn cao hơn nhằm hạn chế những bất thường khi thao tác trên CSDL.

1NF
2NF
3NF
BCNF
3.2. D?ng chu?n 1 (1NF)
Định nghĩa: Một lược đồ quan hệ R(A1, A2, …, An) được gọi là đạt dạng chuẩn 1 nếu mọi thuộc tính A1, A2, …, An của nó đều có giá trị đơn.
Ví dụ: Cho lược đồ quan hệ VATTU(MAVT, TENVT, SOLG_DONGIA).
Xét quan hệ trên lược đồ quan hệ VATTU.
Do thuộc tính SOLG_DONGIA của lược đồ VATTU có giá trị là danh sách nên nó không phải lược đồ ở 1NF. Để nó ở 1NF, ta tách thuộc tính SOLG_DONGIA thành các thuộc tính đơn sau:
VATTU(MAVT, TENVT, SOLG_DONGIA)  VATTU(MAVT, TENVT, SOLG, DONGIA).
3.3. D?ng chu?n 2 (2NF)
a .Phụ hàm đầy đủ: Một lược đồ quan hệ R(A1, A2, …, An) X, Y là các tập con của R. PTH X Y trên R gọi là PTH đầy đủ nếu không tồn tại tập con X’ của X (X’X) mà X’Y.
Ví dụ 1:
Cho lược đồ qhệ CTHD(SOHD, MAMH, SOLG, DONGIA)
SOHD,MAMH SOLG là PTH đầy đủ. Vì
SODH  SOLG
MAMH  SOLG

Ví d? 2:
Cho lược đồ qhệ CTHD(SOHD, MAMH, TENMH, SOLG, DONGIA)
SODH, MAMH  TENMH không là PTH đầy đủ. Vì
MAMH  TENMH

3.3. D?ng chu?n 2 (2NF)
b. Định nghĩa: Môt lược đồ quan hệ được gọi là đạt dạng chuẩn 2 nếu nó đạt dạng chuẩn 1 và mọi thuộc tính không phải là thành phần của khóa đều phụ thuộc hàm đầy đủ vào khóa.

Ví dụ 1:
Cho lược đồ qhệ CTDH(SOHD, MAMH, TENMH, SOLG, DONGIA)
SODH,MAMH  TENMH không là PTH đầy đủ. Vì
MAMH  TENMH
Nên ta tách CTHD thành 2 lược đồ con:
CTHD(SOHD, MAMH, SOLG, DONGIA)
MATHANG(MAMH, TENMH)

3.4. D?ng chu?n 3 (3NF)
a. PTH bắc cầu: Cho lược đồ quan hệ R(A1, A2, …, An) X là một tập con của R. Thuộc tính Ai(i:1..n) được gọi là PTH bắc cầu vào X nếu tồn tại tập Y sao cho:
i. X  Y và YAi
ii. Y  X
iii. Ai X và Ai Y
Ví d?:
Cho lược đồ quan hệ:
HV(MAHV, HOTEN, MALOP, TENLOP)
Phụ thuộc hàm MAHV  TENLOP là PTH bắc cầu vì:

3.4. D?ng chu?n 3 (3NF)
b. Định nghĩa: Môt lược đồ quan hệ được gọi là đạt dạng chuẩn 3 nếu:
Nó đạt dạng chuẩn 2
Mọi thuộc tính không phải là thành phần của khóa đều không phụ thuộc bắc cầu vào khóa.


Ví d?:
Cho lược đồ quan hệ:
HV(MAHV, HOTEN, MALOP, TENLOP)
Phụ thuộc hàm MAHV  TENLOP là PTH bắc cầu vì:


Nên HV vi pham dạng chuẩn 3. Để HV đạt 3NF ta tách nó thành hai lược đồ sau:
LOP(MALOP, TENLOP)
HV(MAHV, HOTEN, MALOP)

3.5. Dạng chuẩn BCNF (Boye Codd)
Định nghĩa: Một lược đồ quan hệ R(A1, A2, ., An) gọi là đạt dạng chuẩn BCNF mà mọi thuộc tính Ai X mà X ? Ai thì X phải là khóa của R.
Ví dụ:
Cho lược đồ quan hệ R(A, B,C ) với tập phụ thuộc hàm
AB ? C, C ? A)
Lược đồ quan hệ trên không đạt chuẩn BCNF vì có phụ thuộc hàm C ? A mà C không phải là khóa của lược đồ.
Tính chất
Một lược đồ quan hệ đạt dạng chuẩn BCNF thì nó đạt dạng chuẩn 3NF.
4. PHÉP TÁCH CÁC LƯỢC ĐỒ QUAN HỆ
4.1. Khái niệm về phép tách
4.2. Phép tách với kết nối không thất thoát
4.3. Kiểm tra tính kết nối không thất thoát của một phép tách.
4.4. Phép tách bảo toàn phụ thuộc hàm
4.1. Khái niệm về phép tách
,Cho U1, U2, ., Uk sao cho U = U1 ? U2 ?, .,? Uk và không nhất thiết các U1, U2, ., Uk rời nhau. Việc thay thế lược đồ R=(U, F) bởi R1 = (U1, F1), ., Rk=(Uk, Fk) được gọi là phép tách lược đồ quan hệ đã cho (U, F). Kí hiệu là ?=(R1, R2, ., Rk) hay ?=(U1,., Uk)
Với: Fi là chiếu của F lên tập thuộc tính Ui
(?Z(F) = {(X ?Y)?F+ , XY ? Z} là chiếu của F lên Z.)


4.2. Phép tách với kết nối không thất thoát
Gọi ri = ?Ui (r) là chiếu của quan hệ r lên tập thuộc tính Ui.
m?(r) = r1* r2 * . * rk là kết quả của phép kết nối tự nhiên các chiếu của r lên các tập con thuộc tính của phép tách ?.
Phép tách U thành {U1, U2, ., Uk} được gọi là kết nối không thất thoát (LJ), nếu với mỗi quan hệ r của lược đồ này, ta đều có r = m? (r).
Định lý
Cho một lược đồ quan hệ R, ? = (R1, R2, ., Rk) là một phép tách trên R, r là quan hệ của lược đồ R. Khi đó:
a. r ? m?(r)
b. nếu s = m?(r) thì si = ri với si = ?Ui (s)
c. m? (m?(r)) = m?(r)




4.3. Kiểm tra tính kết nối không thất thoát của một phép tính
Input: Tập U ={A1, A2, ., An}, Tập PTH F, phép tách
?=(U1, U2, ., Uk).
Output: ? có phải là phép tách kết nối thất thoát không?

Phương pháp
Lập bảng k x n. k dòng đại diện cho U1, ., Uk; và n cột đại diện cho A1, A2, ., An.
Tại dòng i, cột j ghi là aj nếu Aj ?Ui, ngược lại ghi bij
Với mỗi PTH (X?Y), xét từng cặp dòng có giá trị bằng nhau trên X ta đổi các ký hiệu trên các dòng này bằng nhau trên Y, theo quy tắc:
Nếu một trong hai ký hiệu là aj thì ký hiệu kia sẽ được đổi thành ai.
Nếu cả hai ký hiệu là bij thì lấy ký hiệu tùy ý gán cho cả hai.
Quá trình lặp trên sẽ kết thúc nếu không thay đổi được bảng nữa.
Nếu có một dòng toàn là ký hiệu ai thì phép tách là không thất thoát.

Ví dụ
Cho U = ABCDE, U1=AD, U2=AB, U3=BE, U4=CDE, U5=AE
Tập phụ thuộc hàm là: A ?C, B?C, C?D, DE?C, CE?A
Ví dụ
Xét PTH: A ? C
Ví dụ
Xét PTH: B? C
Ví dụ
Xét PTH: B? C
Ví dụ
Xét PTH: C? D
Ví dụ
Xét PTH: DE? C
Ví dụ
Xét PTH: CE? A
3.4. Phép tách bảo toàn phụ thuộc hàm
?Z(F) = {(X ?Y)?F+ , XY ? Z}
Kí hiệu là ?=(R1, R2, ., Rk) với Ri =(Ui, Fi) là một phép tách của lược đồ R=(U, F).
Một phép tách ? được gọi là bảo toàn tập phụ thuộc hàm F nếu: phủ F
Ví dụ:
Mỗi thành phố (City) có nhiều đường (Street), các đường có thể trùng tên ở hai thành phố khác nhau. Mỗi đường của mỗi thành phố được có một mã (Zip code).
Như vậy ta có lựơc đồ quan hệ CSZ với:
U=CSZ
F= {CS?Z, Z?C}