Bài giảng môn Cơ sở dữ liệu: Chương 8 - Thiết kế cơ sở dữ liệu quan hệ

THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ

1

Tập PTH tối thiểu

• Tập PTH F là tối thiểu nếu thỏa các điều kiện sau

– Mọi PTH của F chỉ có một thuộc tính ở vế phải. – Không thể thay X  A thuộc F bằng Y  A với Y  X

mà tập mới tương đương với F.

– Nếu bỏ đi một PTH bất kỳ trong F thì tập PTH còn lại

không tương đương với F.

• Phủ tối thiểu (Minimal Covers) của tập PTH E là

tập PTH tối thiểu F tương đương với E.

• Nhận xét

– Mọi tập PTH có ít nhất một phủ tối thiểu.

2 Thuật toán tìm phủ tối thiểu (Bernstein, 1976) Thuật toán 3.3: Nhập: tập PTH E. Xuất: phủ tối thiểu F của E. Phương pháp : – B1: F := . – B2: (Tách các PTH để có vế phải là 1 thuộc tính)

Với mọi X  Y  E, Y = {A1, …, Ak}, Ai  U

F := F  {X  {Ai}}.

– B3: (Loại bỏ các thuộc tính dư thừa vế trái) Với mỗi X  {A}  F, X = {B1, …, Bl}, Bi  U

+ thì

Với mỗi Bi, nếu A  (X - {Bi})F

F := (F - {X  {A}})  {(X - {B})  {A}}.

– B4: (Loại bỏ các PTH dư thừa)

Với mỗi X  {A}  F

3

+ thì F := F - {X  {A}}.

G := F - {X  {A}} Nếu A  XG

Ví dụ tìm phủ tối thiểu

Tìm phủ tối thiểu của E = {A  BC, A  B, B  C,

AB  C} – B1: F = . – B2: F = {A  B, A  C, B  C, AB  C}. – B3: Xét AB  C + = C

(B)F F = {A  B, A  C, B  C}.

– B4: A  C thừa.

F = {A  B, B  C}.

4

Chuẩn hóa lược đồ CSDL

Các dạng chuẩn

– Dạng 1 (1 Normal Form - 1NF). – Dạng 2 (2 Normal Form - 2NF). – Dạng 3 (3 Normal Form - 3NF). – Dạng Boyce - Codd

(Boyce - Codd Normal Form - BCNF).

5

Dạng chuẩn 1

Định nghĩa 3.5: Quan hệ r(U) được gọi thuộc dạng chuẩn 1 nếu

và chỉ nếu mọi thuộc tính của r là thuộc tính đơn.

PHONG

TenP MaP TrPhg CacTruso

Kinh doanh 5 333445555

Go Vap, Thu Duc Không thuộc dạng chuẩn 1

Hanh chinh 4 987654321 Go Vap

PHONG

TenP MaP TrPhg Truso

Kinh doanh 5 333445555 Go Vap Thuộc dạng chuẩn 1

Kinh doanh 5 333445555 Thu Duc

Nhận xét: Dạng chuẩn 1 có thể dẫn đến sự trùng lặp dữ liệu. Do đó gây ra các dị thường về cập nhật dữ liệu

Hanh chinh 4 987654321 Go Vap

6

Dạng chuẩn 2 theo khóa chính (1)

Định nghĩa 3.6: Quan hệ r(U) được gọi là thuộc dạng chuẩn 2 nếu mọi thuộc tính không khóa của r phụ thuộc đầy đủ vào khóa chính của r.

r(U), K  U là khóa chính của r

– A  U là thuộc tính không khóa nếu A K. – X  Y là PTH đầy đủ nếu A  X thì (X - {A})  Y không đúng trên r.

Ví dụ

Ngược lại X  Y là PTH bộ phận.

Thuộc tính không khóa

NVIEN_DUAN PTH đầy đủ

MaNV MaDA SoGio TenNV TenDA Diadiem

FD1

FD2 PTH bộ phận

FD3

7 Dạng chuẩn 2 theo khóa chính (2)

NVIEN_DUAN

MaNV MaDA SoGio TenNV TenDA Diadiem

FD1

FD2

FD3

NV_DA1 NV_DA2 NV_DA3

MaNV MaDA SoGio MaNV TenNV MaDA TenDA Diadiem

FD1 FD2 FD3

3 lược đồ NV_DA1, NV_DA2, NV_DA3 thuộc dạng chuẩn 2

8 Dạng chuẩn 2 theo khóa chính (3)

NHANVIEN_PHONGBAN

TenNV MaNV NgSinh DChi MaPB TenPB TrPhong

FD1

FD2

Nhận xét

– Mọi lược đồ quan hệ thuộc dạng chuẩn 2 cũng thuộc

dạng chuẩn 1.

– Còn xuất hiện sự trùng lặp dữ liệu. Do đó gây ra các dị

thường về cập nhật dữ liệu.

Thuộc dạng chuẩn 2

9

Dạng chuẩn 3 theo khóa chính (1)

Định nghĩa 3.7: Quan hệ r(U) được gọi là thuộc dạng chuẩn 3 nếu

– r thuộc dạng chuẩn 2. – Mọi thuộc tính không khóa của r không phụ thuộc bắc cầu vào khóa

Cho r(U)

chính của r.

– X  Y là PTH bắt cầu nếu Z  U, Z không là khóa và cũng không là tập

Ví dụ

con của khóa của r mà X  Z và Z  Y đúng trên r.

NHANVIEN_PHONGBAN

PTH bắt cầu TenNV MaNV NgSinh DChi MaPB TenPB TrPhong

FD1

FD2

FD3

10

Dạng chuẩn 3 theo khóa chính (2)

Thuộc dạng chuẩn 3

NV_PB1 NV_PB2

Nhận xét

– Mọi lược đồ quan hệ thuộc dạng chuẩn 3 cũng thuộc

dạng chuẩn 2.

– PTH bắt cầu là nguyên nhân dẫn đến trùng lặp dữ liệu. – Dạng chuẩn 3 là dạng chuẩn tối thiểu trong thiết kế

CSDL.

MaPB TenPB TrPhg TenNV MaNV NgSinh Diachi MaPB

11

Dạng chuẩn 2 tổng quát Định nghĩa 3.8: Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 2 nếu mọi thuộc tính không khóa của R phụ thuộc đầy đủ vào các khóa của R.

Cho R(ABCDEF) có 2 khóa là A và BC.

A B C D E F

FD1

FD2

FD3

FD4

FD5

Lược đồ R không thuộc dạng chuẩn 2

12

Dạng chuẩn 3 tổng quát Định nghĩa 3.9: Lược đồ quan hệ R được gọi là thuộc dạng

chuẩn 3 nếu PTH X  A đúng trên R thì – X là siêu khóa của R, hoặc – A là thuộc tính khóa của R.

R1(ABCDE) có 2 khóa là A và BC.

A B C D E

FD1

FD2

FD4

Lược đồ bên thuộc dạng chuẩn 2, nhưng không thuộc dạng chuẩn 3 FD5

13

3.4 Phân rã lược đồ quan hệ

Lược đồ quan hệ R(A1, …, An)

– Tập hợp tất cả các thuộc tính của các thực thể.

Xác định tập PTH F trên R. Phân rã

– Sử dụng các thuật toán chuẩn hóa để tách R thành tập

các lược đồ D = {R1, …, Rm}.

Yêu cầu

– Bảo toàn thuộc tính. – Các lược đồ Ri phải ở dạng chuẩn 3 hoặc Boyce-

Codd.

14

Phân rã bảo toàn PTH

Tính chất bảo toàn PTH

– Xét lược đồ R và tập PTH F. Giả sử R được phân rã

thành D = {R1, …, Rm}. • Đặt Ri(F) = {X  Y  F+ : X  Y  Ri}. • D được gọi là phân rã bảo toàn phụ thuộc hàm đối với F nếu

(R1(F)  …  Rm(F))+ = F+.

R111

A C D

Ví dụ R11 A

B C D FD1

FD1

FD2 R112

FD5 B D

FD5

15 Thuật toán phân rã lược đồ DC3 và bảo toàn PTH (Berstein 1976)

Thuật toán 3.6 Nhập: R(U), U = {A1, …, An} và tập PTH F. Xuất: D = {R1, …, Rm}, Ri ở dạng chuẩn 3.

– B1: Tìm phủ tối thiểu G của F. – B2: Với mỗi X  Aj  G, xây dựng lược đồ Ri(Ui),

Ui = X  {Aj}. Khóa chính của Ri là X.

– B3: Giả sử xong B2 ta có các lược đồ R1, …, Rm. Nếu U1  …  Um  U thì xây dựng thêm lược đồ Rm+1(Um+1), Um+1 = U - (U1  …  Um).

Khóa của Rm+1 là Um+1. – B4: Xuất các lược đồ Ri.

16

Ví dụ phân rã bảo toàn PTH (1)

Cho

– R(ABCDEFG) – F = {B  A, D  C, D  EB, DF  G} Tách về dạng chuẩn 3, bảo toàn PTH

– B1:

– B2:

• Phủ tối thiểu G = {B  A, D  C, D  B, D  E, DF  G}.

R(ABCDEFG)

R(DC) R(DB) R(DE) R1(BA) R3(DFG)

– B3:

R2(DBCE)

• Xuất D = {R1, R2, R3}.

17

Ví dụ phân rã bảo toàn PTH (2)

Cho

– R(ABCDEFGHI) – F = {B  A, D  C, D  EB, DF  G} Tách về dạng chuẩn 3, bảo toàn PTH

– B1:

– B2:

• Phủ tối thiểu G = {B  A, D  C, D  B, D  E, DF  G}.

R(ABCDEFG)

– B3:

R2(DBCE) R1(BA) R3(DFG)

– B4:

• Vì U1  U2  U3 = {ABCDEFG} nên đặt R4(HI).

• D = {R1, R2, R3, R4}.

18

Bài tập 1:

Cho lược đồ quan hệ R(ABCDE) và tập phụ

thuộc hàm:

F = {A -> B; CD -> E; B -> C} 1. Tìm một khóa của lược đồ. 2. Tìm tất cả các khóa của lược đồ. 3. Cho biết dạng chuẩn cao nhất của lược đồ trên? Nếu chưa đạt dạng chuẩn 3 hãy tìm một phép phân rã thành các lược đồ con đạt dạng chuẩn 3 và bảo toàn thông tin.

19

Tìm một khóa

Áp dụng các bước tìm bao đóng của tập các

thuộc tính:

+ = BCDE  K = ABCDE. + = ABCDE  K = ACDE.

+ = ADEBC  K = ADE.

+ = AEBC  K = ADE. + = ADBCE  K = AD.

• Lặp 1: (BCDE)F • Lặp 2: (ACDE)F • Lặp 3: (ADE)F • Lặp 4: (AE)F • Lặp 5: (AD)F

AD là khoá.

20

- Khóa là AD, R không đạt 2NF vì A  B - Tìm một phép phân rã tách lược đồ trên thành các lược đồ

con đạt dạng chuẩn 3.

Cho lược đồ quan hệ R(ABCDE) và tập phụ thuộc hàm:

F=Ftt = {A -> B; CD -> E; B -> C}

R(ABCDE)

R1(BC)

R2(ADEB) {A -> B}

R21(AB) R22(ADE)

21

- Khóa là AD, R không đạt 2NF vì A  B - Tìm một phép phân rã tách lược đồ trên thành các lược đồ

con đạt dạng chuẩn 3.

Cho lược đồ quan hệ R(ABCDE) và tập phụ thuộc hàm:

F=Ftt = {A -> B; CD -> E; B -> C}

22

Bài tập 2

Cho lược đồ quan hệ R(A,B,C,D,E,G,H,I,J,K) và tập

các phụ thuộc hàm:

F = {A -> B ; C -> D,H,I ; I,J -> K ; B,C -> A ; H,C -> E} 1. Tìm một khóa của lược đồ. 2. Tìm tất cả các khóa của lược đồ. 3. Cho biết dạng chuẩn cao nhất của lược đồ trên?

Nếu chưa đạt dạng chuẩn 3 hãy tìm một phép phân rã thành các lược đồ con đạt dạng chuẩn 3 và bảo toàn thông tin.

23

1. Tìm một khóa của lược đồ

Áp dụng các bước tìm bao đóng của tập các thuộc

tính:

+ = R  K = BCDEGHIJK +  R  K = BCDEGHIJK

+  R  K = BCDEGHIJK + = R  K = BCEGHIJK. + = R  K = BCGHIJK +  R  K = BCGHIJK

• Lặp 1: (ABCDEGHIJK)F • Lặp 2: (BCDEGHIJK) F • Lặp 3: (BDEGHIJK) F • Lặp 4: (BCEGHIJK) F • Lặp 5: (BCGHIJK ) F • Lặp 6: (BCGHIJK ) F • Lặp 7: (BCGIJK ) F • Lặp 8: (BCGJK ) F • Lặp 9: (BCGK ) F • Lặp 10: (BCGJ ) F

+= R  K = BCGIJK + = R  K = BCGJK +  R  K = BCGJK + = R  K = BCGJ

24

2. Tìm tất cả các khóa của lược đồ

Có 2 khóa:

K1=(BCGJ) K2=(ACGJ)

25

Cho biết dạng chuẩn cao nhất

R không đạt 2NF vì C  D

26

Bài tập

Cho lược đồ quan hệ R(A,B,C,D,E,G) và tập các phụ

thuộc hàm:

F = {A -> D ; E->B ;A,E->G ; B->C} 1. Tìm một khóa của lược đồ. 2. Tìm tất cả các khóa của lược đồ. 3. Cho biết dạng chuẩn cao nhất của lược đồ trên?

Nếu chưa đạt dạng chuẩn 3 hãy tìm một phép phân rã thành các lược đồ con đạt dạng chuẩn 3 và bảo toàn thông tin.

27

a.,b. AE là khóa c. Phân rã: F = {A -> D ; E->B ;A,E->G ; B->C} - R không đạt 2NF vì có PTH A->D, D không phụ

thuộc đầy đủ vào khóa.

R(ABCDEG)

R1(BC)

R2(ABDEG) {A -> D ; E->B ;A,E->G}

R21(EB) R22(ADEG)

{A -> D ; A,E->G} R221(AD) R222(AEG)

28

Bài tập ví dụ:

Cho lược đồ quan hệ R(A,B,C,D,E) và tập các phụ thuộc hàm:

F = {AB -> C ; AB->D ;D->A ; BC-D,BC->E} Cho biết dạng chuẩn cao nhất của lược đồ trên? Nếu chưa đạt dạng chuẩn 3 hãy tìm một phép phân rã thành các lược đồ con đạt dạng chuẩn 3, bảo toàn thông tin, bảo toàn PTH.