Bài giảng Lý thuyết thiết kế cơ sở dữ liệu

CHƯƠNG VI LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LiỆUNguyễn Hồng HạnhBộ môn Công Nghệ Phần Mềm,Khoa Công Nghệ Thông TinTrường Đại Học Xây Dựng 6.1 Một số vấn đề gặp phải khi tổ chức dữ liệuCho lược đồ quan hệ:Thi(MaSV, HotenSV, MonHoc, DiemThi)Xây dựng một quan hệ trên lược đồ quan hệ Thi:Một số vấn đề nảy sinh khi tổ chức dữ liệu theo lược đồ trên:Dư thừaBất thường khi sửaBất thường khi thêmBất thường khi xóaMaSVHoTenSVMonHocDiemThi00DTH189Nguyễn Văn ThànhMạng700DTH189Nguyễn Văn ThànhCSDL900DTH211Trần Thu HàPascal500DTH189Nguyễn Văn ThànhPascal86.1 Một số vấn đề gặp phải khi tổ chức dữ liệuHướng giải quyết:Phân rã lược đồ quan hệ Thi thành 2 lược đồ quan hệSinhVien( MaSV, HoTenSV)KetQua(MaSV,MonHoc,DiemThi)Mục đích nghiên cứu của chương 6:	Làm thế nào để đưa được từ một lược đồ cơ sở dữ liệu chưa tốt thành một lược đồ cơ sở dữ liệu tốt hơn nhằmtránh được dư thừa dữ liệu tránh các bất thường khi thêm, sửa, xóa dữ liệu đồng thời cho phép tìm kiếm thông tin một cách dễ dàng ?6.2 Phụ thuộc hàm( Functional dependencies - FD)6.2.1 Định nghĩa phụ thuộc hàm trong 1 quan hệCho- R(U) là 1 lược đồ quan hệ, U là tập các thuộctính.- X, Y  UTa nói X xác định hàm Y hay Y phụ thuộc hàm vào XNếu với  quan hệ r xác định trên R(U) và với 2 bộ t1 và t2 bất kỳ mà t1[X] = t2[X] thì t1[Y] = t2[Y].Ký hiệu: XYVí dụ: Phụ thuộc hàm của thuộc tính HoTenSV và MaSV được biểu diễn như sau:	MaSV HoTenSV6.2 Phụ thuộc hàm( Functional dependencies - FD)6.2.1 Định nghĩa phụ thuộc hàm trong 1 quan hệPhụ thuộc hàm X  X: phụ thuộc hàm hiển nhiênQuy ước:F: tập các phụ thuộc hàm được định nghĩa trên R(U)Trong tập F, chỉ cần mô tả các phụ thuộc hàm không hiển nhiên, các phụ thuộc hiển nhiên được ngầm hiểu đã có trong FVí dụ : Cho R(U)t1t2t3t4t5 Những phụ thuộc hàm nào sau đây thỏa r?A  D; AB D; E A; A EABCDEa1b1c1d1e1a1b2c2d2e1a2b1c3d3e1a2b1c4d3e1a3b2c3d1e16.2 Phụ thuộc hàm( Functional dependencies - FD)6.2.2 Một số tính chất của phụ thuộc hàmHệ tiên đề Amstrong:	1.Luật phản xạ (reflexivity)	X  Y  XY	 	2.Luật tăng trưởng(augmentation)	X  Y  XZ  YZ	3.Luật bắc cầu(transitivity) 	X  Y, Y  Z  X  ZHệ quả của hệ tiên đề Amstrong:	4.Luật hợp (the union rule)	Cho X  Y, X  Z  X  YZ	5.Luật tựa bắc cầu (the pseudotransitivity rule) 	Cho X  Y,WY Z  XW  Z	6.Luật tách (the decomposition rule): 	Cho X  Y, Z  Y  X  Z6.3 Bao đóng của một tập phụ thuộc hàmĐịnh nghĩa : Bao đóng của tập phụ thuộc hàm F là tập lớn nhất các phụ thuộc hàm có thể được suy diễn logic từ FKý hiệu là F+ Suy diễn logic	X  Y được suy diễn logic từ F nếu với mỗi quan hệ	r xác định trên R(U) thoả các phụ thuộc hàm trong F	thì cũng thoả X  Y F là họ đầy đủ (full family) nếu	F = F+ 6.4 Bao đóng của một tập thuộc tínhĐịnh nghĩa : Bao đóng của tập thuộc tính X là tập tất cả các thuộc tính được xác định hàm bởi X thông qua tập FKý hiệu là X+ X+ = { A  U | X  A  F+}Thuật toán tính bao đóng của 1 tập thuộc tínhBước 0 	X0 = X.Bước i Tính Xi từ Xi-1	Nếu Y  Z  F và Y  Xi-1 và A  Z và A không thuộc Xi-1	thì 	 Xi = Xi-1  A	ngược lại , Xi = Xi-1 .	Nếu Xi ≠ Xi-1	thì lặp Bước i	ngược lại, chuyển Bước nBước n 	X+ = Xi Ví dụ minh họa tính bao đóng của 1 tập thuộc tính6.5 Khóa tối thiểu đối với lược đồ quan hệĐịnh nghĩa :Cho lược đồ quan hệ R(U), tập phụ thuộc hàm F, U là tập thuộc tính; K  U, K được gọi là khóa tối thiểu của R nếu:K U thuộc F+ Với mọi tập con K’ của K thì K’ U không thuộc F+ Nhận xét: Nếu K là một khóa tối thiểu thìBao đóng K+ =U ( từ K suy ra được mọi thuộc tính trong U)K là tập thuộc tính nhỏ nhất có tính chất như vậy6.5 Khóa tối thiểu đối với lược đồ quan hệThuật toán tìm khóa tối thiểuBước 0 	K0 = U.Bước i Nếu (Ki-1 \ {Ai})  U	thì 	 Ki = Ki-1 \ {Ai}) 	ngược lại , Ki = Ki-1 .	Nếu Ki ≠ Ki-1	thì lặp Bước i	ngược lại, chuyển Bước nBước n 	K = Ki Ví dụ minh họa tìm khóa tối thiểu6.6 Phủ tối thiểu của một tập phụ thuộc hàm6.6.1 Nhận xét về phụ thuộc hàmTừ một tập các phụ thuộc hàm có thể suy diễn ra các phụ thuộc hàm khácTrong một tập phụ thuộc hàm cho sẵn có thể có các phụ thuộc hàm dư thừa Làm thế nào để có được một phụ thuộc hàm tốt ???6.6 Phủ tối thiểu của một tập phụ thuộc hàm6.6.2 Tập phụ thuộc hàm tương đương (equivalent functional dependancy)Cho F và G là hai tập phụ thuộc hàm, ta nói F và G tương đương (hay F phủ G hoặc G phủ F ) và ký hiệu là F+ = G+ nếu và chỉ nếu mỗi phụ thuộc hàm thuộc F đều thuộc G + và mỗi phụ thuộc hàm thuộc G đều thuộc F + .Ký hiệu:	F ≈ GVí dụR(A,B,C)	F={	AB;	AC;	BA;	CA;	BC}	G={	AB; CA; BC}Chứng minh F và G tương đương6.6 Phủ tối thiểu của một tập phụ thuộc hàm6.6.3 Tập phụ thuộc hàm không dư thừaĐịnh nghĩa: Tập phụ thuộc hàm F là không dư thừa nếu trong F không tồn tại một phụ thuộc hàm nào mà khi loại bỏ đi phụ thuộc hàm đó, cho ta một tập phụ thuộc hàm tương đương với F.Thuật toán tìm phủ không dư thừa của một tập phụ thuộc hàmBước 0 	F0 = F.Bước i Nếu (Fi-1 \ {Li  Ri }) ≈ F	thì 	 Fi = Fi-1 \ {Li  Ri }	ngược lại , Fi = Fi-1 .	Nếu Fi ≠ Fi-1	thì lặp Bước i	ngược lại, chuyển Bước nBước n 	F’= Fi 6.6 Phủ tối thiểu của một tập phụ thuộc hàm6.6.4 Định nghĩa phủ tối thiểuF được gọi là một tập phụ thuộc hàm tối thiểu nếu F thoả đồng thời ba điều kiện sau: a)	Vế phải của F chỉ có một thuộc tính. b)	Không  f: X  A  F và Z  X mà:	F + = (F  (X  A)  (Z  A))+ c)	Không  X  A  F mà:	F + = (F  (X  A))+Trong đó - vế phải của mỗi phụ thuộc hàm ở điều kiện a) chỉ có một thuộc tính, nên bảo đảm không có thuộc tính nào ở vế phải là dư thừa. - điều kiện b) bảo đảm không có một thuộc tính nào tham gia vế trái của phụ thuộc hàm là dư thừa.- điều kiện c)bảo đảm cho tập F không có một phụ thuộc hàm nào là dư thừa.6.6 Phủ tối thiểu của một tập phụ thuộc hàm6.6.4 Thuật toán tìm phủ tối thiểuVào: Tập thuộc tính U, F = {Li  Ri : i = 1..n} Ra: Phủ tối thiểu F của tập phụ thuộc hàm F Thuật toánB.1. 	Biến đổi F về dạng F1={Li  Ai}trong đó Aj là 1 thuộc 	tính bất kỳ thuộc U (thoả mãn điều kiện a)B.2. 	Loại bỏ thuộc tính thừa trong vế trái của các phụ thuộc	hàm	Lần lượt giản ước từng thuộc tính trong vế trái của 	từng phụ thuộc hàm trong F1 thu được F1’. Nêu F1’ ≈ 	F1 thì loại bỏ thuộc tính đang xét	Khi không có sự giản ước nào xảy ra nữa ta thu được 	F2 thỏa mãn điều kiện bB.3.	 Loại bỏ các phụ thuộc hàm dư thừa trong F2.6.7 Phép tách các lược đồ quan hệMục đích Thay thế một lược đồ quan hệ R(A1 , A2 ,, An ) bằng một tập các lược đồ con {R1 , R2 ,  , Rk } trong đó Ri ⊆ R và R= R1 ∪ R2 ∪ . ∪ Rk .Yêu cầu phép tách	- Bảo toàn thuộc tính, ràng buộc 	- Bảo toàn dữ liệu6.7 Phép tách các lược đồ quan hệ6.7.1 Phép tách không mất mát thông tin ( Lossless join)Định nghĩa:	Cho lược đồ quan hệ R(U), phép tách R thành các lược đồ con {R1 , R2 ,  , Rk } được gọi là phép tách không mất mát thông tin đối với một tập phụ thuộc hàm F nếu với mọi quan hệ r xác định trên R thỏa mãn F thì: 	r= ∏R1 (r) ⋈ ∏R2 (r) ⋈ . ⋈ ∏Rk (r)Ví dụ: Supplier (sid,sname,city,pid,pname,colour,quantity)	⤋	S1(sid, sname, city)	SP1(pid,pname,colour,quantity)6.7 Phép tách các lược đồ quan hệ6.7.2 Kiểm tra tính không mất mát thông tinVào: R(A1, A2, , An), F, phép tách {R1, R2, , Rk} Ra: phép tách là mất mát thông tin hay không? Thuật toánB.1. Thiết lập một bảng k hàng, n cột	Nếu Aj là thuộc tính của Ri thì điền aj vào ô (i,j).	Nếu không thì điền bij.B.i. Xét f = X⟶Y  F.	Nếu 2 hàng t1, t2 thuộc bảng : t1[X] = t2[X] thì	t1[Y] = t2[Y], ưu tiên đồng nhất về giá trị a	Lặp cho tới khi không thể thay đổi được giá trị nào 	trong bảng.B.n. Nếu bảng có 1 hàng gồm các kí hiệu a1, a2,  , an	thì phép tách là không mất mát thông tin.	Ngược lại, phép tách không bảo toàn thông tin.6.7 Phép tách các lược đồ quan hệ6.7.3 Phép tách bảo toàn tập phụ thuộc hàmHình chiếu của tập phụ thuộc hàm	Cho sơ đồ quan hệ R, tập phụ thuộc hàm F, phép tách	{R1, R2,  , Rk} của R trên F.	Hình chiếu Fi của F trên Ri là tập tất cả X ⟶ Y  F+ :	XY ⊆ Ri . Phép tách sơ đồ quan hệ R thành {R1, R2,  , Rk} là	một phép tách bảo toàn tập phụ thuộc hàm F nếu	(F1 ∪ F2 ∪  ∪ Fk)+ = F+	hay hợp của tất cả các phụ thuộc hàm trong các hình	chiếu của F lên các sơ đồ con sẽ suy diễn ra các phụ	thuộc hàm trong F.6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.1 Một số định nghĩa cơ bảnĐịnh nghĩa 1:	Cho R(U) là một lược đồ quan hệ với U là tập các thuộc tính, F là tập các phụ thuộc hàm trên R và AUChúng ta nói: A là thuộc tính khóa( prime) nếu A thuộc một khóa tối thiểu nào đó của R. Ngược lại A được gọi là thuộc tính không khóa (nonprime).	Ví dụ:	R(ABCD) 	F= {AB ⟶ C , BC ⟶ A,B ⟶ D}Lược đồ trên có 2 khóa tối thiểu AB, BCA, B, C : thuộc tính khóa; D : thuộc tính không khóa6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.1 Một số định nghĩa cơ bảnĐịnh nghĩa 2:	Cho R(U) là một lược đồ quan hệ với U là tập các thuộc tính, F là tập các phụ thuộc hàm trên R và X ⊆ U, AUChúng ta nói: 	A là phụ thuộc bắc cầu vào X nếu tồn tại một tập thuộc tính Y, Y ⊆ U sao cho X ⟶ Y, Y ⟶ A thuộc F+ nhưng Y ⟶ X không thuộc F+ . Ngược lại A không phụ thuộc bắc cầu vào X hay A phụ thuộc trực tiếp vào X	6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.2 Dạng chuẩn 1 (1NF)Định nghĩa :	 Một sơ đồ quan hệ R được gọi là ở dạng chuẩn 1 nếu tất cả các miền giá trị của các thuộc tính trong R đều chỉ chứa giá trị nguyên tố Giá trị nguyên tố là giá trị mà không thể chia nhỏ ra được nữa Ví dụ: Quan hệ không ở 1NF và quan hệ saukhi chuẩn hóa về 1NF6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.3 Dạng chuẩn 2 (2NF)Định nghĩa :	Một sơ đồ quan hệ R được coi là ở dạng chuẩn 2 nếu sơ đồ quan hệ này ở 1NF 	Tất cả các thuộc tính không khóa đều phụ thuộc hàm	đầy đủ vào khóa chính.Phụ thuộc hàm đầy đủ	Cho lược đồ quan hệ R(U), F là tập phụ thuộc hàm trên R. X, Y ⊆ U. Y được gọi là phụ thuộc đầy đủ vào X nếu:	- X ⟶ Y thuộc F+	- !∃ X’⊂ X : X’ ⟶ Y  F+ 	Các phụ thuộc hàm không đầy đủ còn gọi là phụ thuộc bộ phận.6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.3 Dạng chuẩn 2 (2NF)Ví dụ	Sales(sid, sname, city, item, price)	F = {sid ⟶ (sname,city), (sid, item) ⟶ price} Khóa chính (sid,item) Thấy sname, city không phụ thuộc hàm đầy đủ vào khóa chính  Sales không thuộc 2NF Chuẩn hoá	S(sid, sname, city)	Sales (sid, item, price)6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.3 Dạng chuẩn 3 (3NF)Định nghĩa: Một sơ đồ quan hệ R được coi là ở dạngchuẩn 3 nếu Sơ đồ quan hệ này đã ở dạng 2NF Mọi thuộc tính không khóa đều không phụ thuộc bắccầu vào khóa chínhVí dụ:	ItemInfo(item, price, discount).	F = {item ⟶ price, price ⟶ discount} thuộc tính không khóa discount phụ thuộc bắc cầu vào khóa chính item. Vậy quan hệ này không ở dạng 3NF. 	 Chuẩn hoá	ItemInfo(item, price)	Discount(price, discount)6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.4 Tách bảo toàn tập phụ thuộc hàm về dạng chuẩn 3 (3NF)Vào: R(U), F (giả thiết F là phủ tối thiểu) Ra: Phép tách bảo toàn tập phụ thuộc hàm về 3NF Thuật toánB1. 	Với các Ai  U, Ai ∉ F thì loại Ai khỏi R và lập 1 	quan hệ mới cho các AiB2. 	Nếu ∃ f  F, f chứa tất cả các thuộc tính của R thì 	kết quả là RB3.	 Ngược lại, với mọi X ⟶ A  F, xác định một quan 	hệ Ri(XA).	Nếu X ⟶ Ai, X ⟶ Aj thì tạo một quan hệ chung 	R’(XAiAj)6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.4 Tách bảo toàn tập phụ thuộc hàm về dạng chuẩn 3 (3NF)Ví dụ:	Cho R = {A,B,C,D,E,F,G}	F = {A ⟶ B, ACD ⟶ E, EF ⟶ G} 	Xác định phép tách bảo toàn tập phụ thuộc hàm	về 3NF.Giải:	B1. 	không lập được quan hệ nào mới.	B2. 	 !∃ f  F: f chứa tất cả các thuộc tính của R	B3. 	A ⟶ B 	⇛ R1(AB)	ACD ⟶ E 	⇛ R2(ACDE)	EF ⟶ G 	⇛ R3(EFG)6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.4 Tách không mất mát thông tin và bảo	toàn tập phụ thuộc hàm về 3NF Yêu cầu: Bảo toàn tập phụ thuộc hàm (như thuật toán trên) Đảm bảo là có một lược đồ con chứa khóa của lược đồ được tách Các bước tiến hành:B1. 	Tìm một khóa tối thiểu của lược đồ quan hệ R đã	choB2. 	Tách lược đồ quan hệ R theo phép tách bảo toàn	tập phụ thuộcB3. 	Nếu 1 trong các lược đồ con có chứa khóa tối 	thiểu thì kêt quả của B2 là kêt quả cuối cùng.	Ngược lại, thêm vào kết quả đó một lược đồ quan 	hệ được tạo bởi khóa tối thiểu tìm được ở B1.6.8 Các dạng chuẩn đối với lược đồ quan hệ6.8.4 Tách không mất mát thông tin và bảo	toàn tập phụ thuộc hàm về 3NF Ví dụ	Cho R(A,B,C,D,E,F,G).	F = {A ⟶ B, ACD ⟶ E, EF ⟶ G}GiảiB1. 	Khóa tối thiểu cần tìm là ACDF (xem slide 9+10 )B2. 	Phép tách bảo toàn tập phụ thuộc hàm R cho 3 	lược đồ con	R1(AB), R2(ACDE), R3(EFG) (xem slide 27 )B3. 	Do khóa ACDF không nằm trong bất kỳ một lược 	đồ con nào trong 3 lược đồ con trên, ta lập một 	lược đồ con mới R4(ACDF)	Kết quả cuối cùng ta có phép tách R thành 4 lược 	đồ con {R1, R2, R3, R4} là một phép tách không 	mất mát thông tin và bảo toàn tập phụ thuộc 	hàm.KẾT LUẬNTầm quan trọng của thiết kế CSDL ảnh hưởng đến chất lượng dữ liệu lưu trữ Hiệu quả của việc khai thác dữ liệu Mục đích của thiết kế CSDL: tránh Dư thừa dữ liệu Dị thường dữ liệu khi thêm/xoá/sửa đổi Hiệu quả trong tìm kiếm  Đưa về các dạng chuẩn 2NF: giản ước sự dư thừa để tránh các dị thường khi 	 cập nhật 3NF: tránh các dị thường khi thêm/xoá