Bài giảng Cơ sở dữ liệu - Chương 4: Lý thuyết thiết kế cơ sở dữ liệu quan hệ - Nguyễn Hồng Phương
10/11/2019
Nội dung
• Tổng quan về thiết kế CSDLQH
• Phụ thuộc hàm
• Phép tách các sơ đồ quan hệ (SĐQH)
• Các dạng chuẩn đối với các SĐQH
Lý thuyết thiết kế
cơ sở dữ liệu quan hệ
Nguyễn Hồng Phương
Bộ môn Hệ thống thông tin
Viện Công nghệ thông tin và Truyền thông
Đại học Bách Khoa Hà Nội
1
2
Tổng quan về thiết kế CSDLQH
Các vấn đề đối với CSDL VD
• Dư thừa dữ liệu: Hãng nào cung ứng nhiều hơn 1
mặt hàng thì thông tin của hãng đó sẽ bị lặp lại
trong bảng (VD S1), mặt hàng được cung ứng bởi
nhiều hãng cũng bị lặp lại (VD Screw)
• Dị thường dữ liệu khi thêm: Nếu có một hãng
chưa cung cấp mặt hàng nào, vậy giá trị cho thuộc
tính product và quantity trong bộ dữ liệu mới được
thêm vào sẽ không được xác định
• Vấn đề của một sơ đồ quan hệ được thiết
kế chưa tốt:
Giả sử ta cần một cơ sở dữ liệu lưu trữ thông tin
về các hãng cung ứng. Sơ đồ quan hệ được thiết
kế trong đó tất cả các thuộc tính cần thiết được
lưu trong đúng 1 quan hệ:
Suppliers(sid, sname, city, numofemps, product, quantity)
• Dị thường dữ liệu khi xóa: Nếu một hãng chỉ
cung cấp 1 mặt hàng, nếu ta muốn xóa thông tin
về sự cung cấp này thì ta sẽ mất thông tin về hãng
cung cấp
sid
S1
S1
S2
S3
sname
Smith
Smith
J&J
city
NOE
100
100
124
75
product quantity
London
London
Paris
Screw
Nut
50
100
78
• Dị thường dữ liệu khi sửa đổi: Do thông tin bị
lặp lại nên việc sửa đổi 1 bộ dữ liệu có thể dẫn đến
việc không nhất quán trong dữ liệu về một hãng
nếu sơ sót không sửa đổi trên toàn bộ các bộ giá
Screw
Bolt
Blake
Tokyo
100
4
trị liên quan đến hãng đó
1
10/11/2019
Đề xuất giải pháp
Mục đích của chuẩn hoá
• Xác định được 1 tập các lược đồ quan hệ,
cho phép tìm kiếm thông tin một cách dễ
dàng, đồng thời tránh được dư thừa dữ
liệu.
• Nếu sơ đồ trên được thay thế bằng
2 sơ đồ quan hệ
–Supp(sid, sname, city, numofemps)
–Supply(sid, product, quantity)
• Hướng tiếp cận:
– Một trong những kỹ thuật được sử dụng là Tách
các lược đồ quan hệ có vấn đề thành những lược
đồ quan hệ chuẩn hơn. Phụ thuộc hàm
(functional dependencies) được sử dụng để nhận
biết các lược đồ chưa chuẩn và đề xuất hướng
cải tiến.
thì tất cả các vấn đề nêu ở trên sẽ
được loại bỏ. Tuy nhiên, khi tìm
kiếm dữ liệu thì phải kết nối 2 bảng
chứ không chỉ là chọn và chiếu trên
1 bảng như ở cách thiết kế trước.
5
6
Phụ thuộc hàm
Ví dụ
• Ví dụ 1: AB C
• Định nghĩa:
– Cho R(U) là một sơ đồ quan hệ với U là tập
thuộc tính {A1, A2,…,An}. X, Y là tập con không
rỗng của U.
– Nói X xác định hàm Y, hay Y là phụ thuộc hàm
vào X (viết: X Y) nếu với một quan hệ r xác
định trên R(U) và với 2 bộ bất kỳ t1, t2 thuộc r
mà t1[X] = t2[X] thì t1[Y] = t2[Y]
A
B
C
D
a1 b1 c1 d1
a1 b1 c1 d2
a1 b2 c2 d1
a2 b1 c3 d1
• Bản chất, nếu 2 bộ giống nhau về giá trị
của các thuộc tính X thì cũng giống nhau về
giá trị của các thuộc tính Y.
• Ví dụ 2: trong cơ sở dữ liệu mẫu dùng trong
chương 3, ta có bảng S, với mỗi giá trị của sid
đều tồn tại một giá trị tương ứng cho sname,
city và status. Do đó, có sid sname, sid
city, sid status
• Phụ thuộc hàm là một trường hợp của ràng
buộc toàn vẹn, tổng quát hóa khái niệm
7
8
khóa.
2
10/11/2019
Hệ quả của hệ tiên đề Amstrong
Hệ tiên đề Amstrong đối với phụ thuộc hàm
Cho
• Luật hợp (union)
– R(U) là 1 sơ đồ quan hệ, U là tập các thuộc tính.
– X,Y,Z,W U
– Ký hiệu: XY = X Y
Nếu XY, XZ thì XYZ.
• Luật tựa bắc cầu (pseudo-transitivity)
Nếu XY, WYZ thì XWZ.
• Luật tách (decomposition)
Nếu XY, Z Y thì XZ
• Phản xạ (reflexivity)
Nếu Y X thì XY
• Tăng trưởng (augmentation)
Nếu XY thì XZYZ
• Bắc cầu (transitivity)
Nếu XY, YZ thì XZ
9
10
Ví dụ
Bao đóng của một tập phụ thuộc hàm
• Ví dụ 1:
• Định nghĩa:
Cho tập phụ thuộc hàm {ABC, CA}
Chứng minh: BC ABC
– Cho F là một tập phụ thuộc hàm. Bao đóng của
F ký hiệu là F+ là tập lớn nhất chứa các phụ
thuộc hàm có thể được suy ra từ các phụ thuộc
hàm trong F.
C A
BC AB
AB C
BC AB, AB ABC
AB ABC
BC ABC
• Đặc điểm của bao đóng của một tập pth:
– Có thể rất lớn
• Ví dụ 2:
– Chi phí rất tốn kém cho việc tìm kiếm
Cho lược đồ quan hệ R(ABEIJGH) và tập
phụ thuộc hàm F = {ABE, AGJ, BEI,
EG, GIH}
• Vấn đề đặt ra: Kiểm tra xem một pth có được suy
diễn từ một tập pth có sẵn không => sử dụng bao
đóng của một tập thuộc tính đối với tập pth
Chứng minh: AB GH
11
12
3
10/11/2019
Bao đóng của một tập các thuộc tính
đối với một tập các pth
Thuật toán 1: Tìm bao đóng của một tập thuộc tính
đối với tập phụ thuộc hàm
• Vào: Tập hữu hạn các thuộc tính U, tập các pth F
trên U, X U
• Thuật Ftoán
• Định nghĩa:
– Cho một sơ đồ quan hệ R(U), F là một tập
• Ra: X+
pth trên U. X là tập con của U. Bao đóng của
tập thuộc tính X đối với tập F, ký hiệu là X+
F
(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 F
B0
X0 = X
Bi
Tính Xi từ Xi-1
YZ F và Y Xi-1 và A Z và A Xi-1
X+ = {A U| X A F+}
Nếu
thì
Xi = Xi-1 A
• Có thể thấy, định nghĩa về bao đóng của
một tập thuộc tính dựa trên bao đóng
của tập pth.
ngược lại, Xi = Xi-1
Nếu Xi Xi-1
thì
lặp Bi
• =>Thuật toán xác định bao đóng của
ngược lai, chuyển Bn
một tập thuộc tính
Bn X+F= Xi
13
14
Ví dụ
Bổ đề
• XY được suy diễn từ tập F dựa trên
hệ tiên đề Amstrong khi và chỉ khi Y
• Cho R(U) , U = {A, B, C, D, E, F}
F = {ABC, BCAD, DE, CFB}
Tính (AB)+
X+
F
• Chứng minh:
• Thực hiện:
–Giả sử Y=A1...An, với A1,...,An là các
thuộc tính và YX+
–Bước 0: X0 = AB
–Từ định nghĩa X+ ta có XAi. Áp dụng
tiên đề Amstrong cho mọi i, suy ra XY
nhờ luật hợp.
–Bước 1: X1 = ABC (do AB C)
–Bước 2: X2 = ABCD (do BCAD)
–Bước 3: X3 = ABCDE (do DE)
–Ngược lại, giả sử có XY, áp dụng hệ tiên
đề Amstrong cho mỗi i, ta có XAi, AiY
–Bước 4: X4 = ABCDE
nhờ luật tách. Từ đó suy ra YX+
15
16
4
10/11/2019
Khoá tối thiểu
Thuật toán 2: Tìm khoá tối thiểu
• Định nghĩa: Cho lược đồ quan hệ R=<U,F>, U
là tập thuộc tính, F là một tập các phụ thuộc
hàm xác định trên U. K được gọi là khoá tối
thiểu của R nếu:
• Vào: U = {A1, A2, …, An} , F
• Ra: khoá tối thiểu K xác định được
trên U và F
• Thuật toán
– K⊆U
– K→U ∈ F+
– Với ∀K’⊂K, thì K’→U ∉ F+
B0
Bi
K0= U
Nếu (Ki-1\{Ai})→U
thì
ngược lại,
Ki= Ki-1\ {Ai}
• Với những gì đã đề cập trong phần bao
đóng ở trên, có thể nói, để thỏa mãn là một
khoá tối thiểu thì K+ = U và K là tập thuộc
tính nhỏ nhất có tính chất này.
17
Ki= Ki-1
Bn+1 K = Kn
18
Thuật toán khác tìm tất cả các khóa
trong lược đồ quan hệ
Ví dụ
•
•
Cho U = {A, B, C, D, E}
• U là tập tất cả các thuộc tính CSDL
• F là tập phụ thuộc hàm
• L(left): là các thuộc tính xuất hiện bên trái
• R(right): là các thuộc tính xuất hiện ở vế phải
• S(superkey): là tập các siêu khóa
• K(key) : là tập các khóa
F = {ABC, ACB, BCDE}. TÌm một khoá tối thiểu của
một quan hệ r xác định trên U và F
•
•
•
Thực hiện
B0: K0= U = ABCDE
B1: Kiểm tra xem có tồn tại phụ thuộc hàm (K0\{A})U
(BCDEU) hay không. Ta cần phải sử dụng thuật toán 1 để
kiểm tra điều kiện tương đương là (BCDE)+ có bằng U không.
(BCDE)+= BCDE , khác U. Vậy K1 = K0 = ABCDE
•
B2: Tương tự, thử loại bỏ B ra khỏi K1 ta có (ACDE)+
ABCDE = U. Vậy K2 = K1 \ {B} = ACDE
=
•
•
•
•
B3: K3 = ACDE
B4: K4 = ACE
B5: K5 = AC
Vậy AC là một khoá tối thiểu mà ta cần tìm
19
20
5
10/11/2019
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
• Tập thuộc tính nguồn (TN): gồm các
thuộc tính chỉ xuất hiện ở vế trái, không
xuất hiện ở vế phải của F và các thuộc tính
không xuất hiện ở cả vế trái và vế phải của
F. Vậy TN = U \ R
• Ví dụ: Cho sơ đồ U = {A, B, C, D, E}
L = {A, B} R = {B, C, E}
TN = U \ R = {A, D}
• Tập thuộc tính đích (TĐ): gồm các
thuộc tính chỉ xuất hiện ở R, không
xuất hiện ở L. Vậy TĐ = R \ L
• Ví dụ : Cho L = {A, B, C, D, E}
R = {E, F, G, H}
TĐ = {F, G, H}
21
22
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
•
•
Thuật toán:
• Tập thuộc tính trung gian (TG):
chứa các thuộc tính xuất hiện ở cả L
và R
Bước 1: Tìm tập thuộc tính nguồn TN và tập thuộc tính trung
gian TG
Bước 2: Nếu TG = ∅ thì K(Key) = TN, và kết thúc thuật toán,
xuất ra K của tập cơ sở dữ liệu <U,F>
•
• Vậy TG = L ∩ R
• Ví dụ: Cho L = {A, B, C, D, E}
R = {D, E, F, G}
•
•
•
Ngược lại, nếu TG ≠ ∅ thì qua bước 3
Bước 3: Tìm tất cả các tập con Xi của TG
Bước 4: Tìm Siêu khóa (Si)
Với ∀Xi, nếu (TN U Xi)+ = U thì khi đó Si = TN U Xi
•
•
Bước 5: Tìm Khóa (Ki) bằng cách loại bỏ các siêu khóa không
tối thiểu
Với mọi Si Sj thuộc S, nếu Si chứa trong Sj thì loại bỏ Sj ra
Vậy TG = L ∩ R = {D, E}
khỏi tập siêu khóa. Khi đó, tập S còn lại chính là tập khóa cần
tìm
23
24
6
10/11/2019
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
• Ví dụ :
S = {AB, ABC, ED, EDF}
Nhận thấy AB chứa trong ABC, ED chứa trong EDF,
vậy cần loại bỏ ABC và EDF.
Vậy S = {AB, ED} chính là tập khóa cần tìm
• Ví dụ : Cho một tập cơ sỡ dữ liệu R = <U,
F>, với U = {ABC},F = {AB→C, C→A}. Tìm
tất cả các khóa thuộc tập cơ sở dữ liệu trên.
• Lời giải:
– L = {ABC}
– TN = {B}
R = {CA}
TG = {AC}≠∅ nên ta làm tiếp bước 3
– Ta có tập con Xi của tập TG = {0, A, C, AC}
– Lấy từng thuộc tính thuộc tập con Xi của tập TG hợp với
TN ta có các thuộc tính sau:
25
26
Thuật toán khác tìm tất cả các khóa trong
lược đồ quan hệ
Nhận xét về phụ thuộc hàm
•
•
•
•
S1 = TN U ∅ = B Ta có B+ = B ≠ U nên S1 = B không là siêu
khóa
S2 = TN U A = AB Ta có AB+ = ABC = U nên S2 = AB là siêu
khóa
S3 = TN U C = BC Ta có BC+ = ABC = U nên S3 = BC là siêu
khóa
S4 = TN U AC = ABC Ta có ABC+ = ABC = U nên S4 = ABC là
siêu khóa
Vậy ta có tập siêu khóa S = {AB, BC, ABC}.
Tuy nhiên, vì AB chứa trong ABC và BC chứa trong ABC nên
loại bỏ siêu khóa ABC ra khỏi tập siêu khóa
• Từ một tập các pth có thể suy diễn ra
các pth khác
• Trong một tập pth cho sẵn, có thể có
các pth bị coi là dư thừa
Làm thế nào để có được một tập pth tốt?
•
•
•
Vậy ta có, tập khóa K = {AB,BC} là khóa của lược đồ quan
hệ
27
28
7
10/11/2019
Ví dụ
Hai tập phụ thuộc hàm tương đương
• Cho sơ đồ quan hệ R(U) với U = {A, B, C, D, E, F}
F = {ABC, DEF, CBD}
G = {ACB, DEF, BCD}
Hỏi F và G có phải là 2 tập pth tương đương hay
không?
• Thực hiện:
• Định nghĩa: Tập pth F là phủ của tập pth G,
hay G là phủ của F, hay F và G tương
đương nếu F+ = G+, kí hiệu là F ≅ G
• Kiểm tra tính tương đương của 2 tập pth
– Bước 1. Nếu với pth fi F, fi có dạng XfiYfi,
Đối với các phụ thuộc hàm trong F
mà fi G+ thì F+ G+. Kiểm tra fi G+ bằng
– f1= ABC. AB+ = ABCDEF = U. Vậy f1 ∈ G+
cách kiểm tra Yfi (Xfi)+
G
G
– f2= DEF ∈ G nên chắc chắn ∈ G+
– Bước 2. Tương tự, nếu pth gj G, mà gj F+
– f3= CBD. C+ = C không chứa BD. Vậy f3 ∉ G+
G
thì G+ F+
– Kết luận F ≇ G
– Bước 3. Nếu F+ G+ và G+ F+ thì F ≅ G
29
30
Tập phụ thuộc hàm không dư thừa
Phủ tối thiểu của 1 tập phụ thuộc hàm
• Đ/N: Tập phụ thuộc hàm F là không dư
thừa nếu không XYF sao cho F\{XY}
F.
• Đ/N: Fc được gọi là phủ tối thiểu của 1
tập pth F nếu thỏa mãn 3 điều kiện:
• Thuật toán 3: Tìm phủ không dư thừa của
–(Đk1) Với f Fc, f có dạng X A, trong
đó A là 1 thuộc tính.
–(Đk2) Với f = XY Fc, ! A X (A là 1
thuộc tính) mà (Fc \ f) U {(X \ A)Y} ≅
một tập pth
– Vào: Tập thuộc tính U, F = {Li Ri | i = 1..n}
– Ra : Phủ không dư thừa F’ của F
– Thuật toán
B0 F0= F
Fc
Bi Nếu Fi-1\ {LiRi} Fi-1
thì
ngược lại, Fi = Fi-1
Bn+1 F’ = Fn
Fi = Fi-1 \ {LiRi}
–(Đk3) ! XA Fc mà Fc \ {XA} ≅ Fc
31
32
8
10/11/2019
Thuật toán 4: Tìm phủ tối thiểu của
một tập phụ thuộc hàm
Ví dụ 1
•
•
•
Vào: Tập thuộc tính U, F = {LiRi: i = 1..n}
Ra: phủ tối thiểu Fc của tập phụ thuộc hàm F
Thuật toán
B.1. Biến đổi F về dạng F1={Li Aj}
trong đó Aj là 1 thuộc tính bất kỳ thuộc U (thoả mãn đk1)
• U = {A,B,C}
F = {ABC, BC, AB, ABC}. Tìm phủ
tối thiểu của F?
B.2. Loại bỏ thuộc tính thừa trong vế trái của các phụ thuộc
– F1 = {AB, AC, BC, ABC}
hàm
Lần lượt giản ước từng thuộc tính trong vế trái của từng
– Xét các pth trong F1 mà vế trái có nhiều hơn 1
thuộc tính, chỉ có ABC. Giản ước A thì ta còn
BC có trong F1, vậy A là thuộc tính thừa.
Tương tự ta cũng tìm được B là thừa, vậy loại bỏ
luôn ABC khỏi F1. F2 = {AB, AC, BC}
– Bỏ pth thừa: AC là thừa. Vậy Fc = {AB,
BC}
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, thu được
F2 thỏa mãn đk2
B.3. Loại bỏ phụ thuộc hàm dư thừa
Lần lượt kiểm tra từng phụ thuộc hàm f. Nếu F2 \ f ≅ F2
thì loại bỏ f
Khi không còn phụ thuộc hàm nào có thể loại bỏ thì thu đươc
F3 thoả mãn đk3
B.4. Fc = F3
33
34
Ví dụ 2
Ví dụ 2 (tiếp)
Tìm phủ tối thiểu của tập pth sau:
F = {AB, ABCDE, EFG, ACDFEG}
–F21={AB, ACDE, EFG, ACDFE,
ACDFG}
• Bước 1: có F1={AB, ABCDE, EFG,
ACDFE, ACDFG}
–Xét pth ACDE:
• Bước 2: F20=F1={AB, ABCDE, EFG,
ACDFE, ACDFG}
•Thử giản ước C, có (AD)+ 1=ADB, không chứa
E, vậy ADE không đượcF2suy diễn ra từ F2
1
– Loại bỏ thuộc tính thừa ở vế trái của 4 pth
•Thử giản ước D, có (AC)+ 1=ACB, không chứa
ABCDE, EFG, ACDFE và ACDFG
E, vậy ACE không thể sFu2y diễn ra từ F2
1
– Xét ABCDE:
. Giả sử giản ước A, còn BCDE, kiểm tra BCDE có được
–Xét pth EFG:
0
suy ra từ F20 không, ta tính (BCD)+
(BCD)+ 0= BCD,
F2
F2
•Thử giản ước F, có E+ 1=E, không chứa G, vậy
EG không thể suy dFiễ2n ra từ F2
•Thử giản ước E, có F+ 1=F, không chứa G, vậy
không chứa E, vậy BCDE không được suy diễn ra từ
F20, do đó A không phải là thuộc tính thừa trong pth
đang xét.
1
F2
. Giả sử giản ước B, tính (ACD)+ 0=ACDBE, chứa E, vậy
1
F2
FG không thể suy diễn ra từ F2
35
36
0
ACDE được suy diễn ra từ F2
9
10/11/2019
Ví dụ 2 (tiếp)
Ví dụ 2 (tiếp)
–Xét pth ACDFE:
–Xét ACDFG:
•Thử giản ước A, có (CDF)+ 1=CDF, không
•Thử giản ước A, có (CDF)+ 2=CDF, không
chứa E, vậy CDFE khôngF2thể suy diễn ra từ
F2
chứa G, vậy CDFG không thể suy diễn ra từ
1
2
F2
F2
•Thử giản ước C, có (ADF)+ 1=ADFB, không
•Thử giản ước C, có (ADF)+ 2=ADFB, không
chứa E, vậy ADFE khôngF2thể suy diễn ra từ
F2
chứa G, vậy ADFG không thể suy diễn ra từ
1
2
F2
F2
•Thử giản ước D, có (ACF)+ 1=ACFB, không
•Thử giản ước D, có (ACF)+ 2=ACFB, không
chứa E, vậy ACFE khôngFt2hể suy diễn ra từ
F2
chứa G, vậy ACFG không thể suy diễn ra từ
1
2
F2
F2
•Thử giản ước F, có (ACD)+ 1=ACDBE, chứa E,
•Thử giản ước F, có (ACD)+ 2=ACDBE, không
vậy ACDE có thể suy diễFn2 ra từ F2
F2
1
chứa G, vậy ACDG không thể suy diễn ra từ
•F22={AB, ACDE, EFG, ACDFG}
F2
2
37
38
Ví dụ 2 (tiếp)
Phép tách các sơ đồ quan hệ
0
2
• Bước 3: F3 =F2 ={AB, ACDE, EFG,
ACDFG}
• Mục đích
–Thay thế một sơ đồ quan hệ R(A1, A2, …,
An) bằng một tập các sơ đồ con {R1, R2,
…, Rk} trong đó Ri R và R = R1 U R2 U …
U Rk
– Loại bỏ các pth dư thừa trong F30
– Xét AB: (A)+=A không chứa B
– Xét ACDE: (ACD)+=ACDB không chứa E
– Xét EFG: (EF)+=EF không chứa G
– Xét ACDFG: (ACDF)+=ACDFBEG, chứa G. Vậy
loại bỏ pth này trong F30, thu được: F31={AB,
ACDE, EFG}
•Yêu cầu của phép tách
–Bảo toàn thuộc tính, ràng buộc
–Bảo toàn dữ liệu
1
• Vậy FC= F3 ={AB, ACDE, EFG}
39
40
10
10/11/2019
Định lý tách đôi
Phép tách không mất mát thông tin
• Đ/N: Cho lược đồ quan hệ R(U) phép tách R
thành các sơ đồ con {R1, R2, …, Rk} được gọi là
phép tách không mất mát thông tin đ/v 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ì:
• Cho lược đồ quan hệ R(U), tập pth F , phép tách R
thành R1(U1), R2(U2) là một phép tách không mất
mát thông tin nếu 1 trong 2 phụ thuộc hàm sau là
thỏa mãn trên F+:
U1 ∩ U2 U1 - U2
U1 ∩ U2 U2 - U1
r = R1(r) ⋈ R2(r) ⋈ … ⋈
(r)
Rk
• Hệ quả: Cho lược đồ quan hệ R(U) và phụ thuộc
hàm XY thỏa mãn trên R(U). Phép tách R thành
2 lược đồ con R1(U1), R2(U2) là một phép tách
không mất mát thông tin với:
• Ví dụ: Phép tách mất mát thông tin
Supplier(sid, sname,city,NOE, pid, pname,colour,quantity)
S1(sid,sname,city,NOE)
SP1(pid,pname,colour,quantity)
và
U1 = XY
U2 = XZ
Z = U \ XY
• Ví dụ: Phép tách không mất mát thông tin
S1(sid,sname,city,NOE)
và
SP2(sid,pid,pname,colour,quantity)
41
42
Thuật toán 5: Kiểm tra tính không mất
mát thông tin của 1 phép tách
Ví dụ
•
•
•
Và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án
B.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.
• R=ABCD được tách thành R1=AB, R2 =BD,
R3=ABC, R4=BCD.
• F = {AC, BC, CDB, CD}
• B1: Tạo bảng gồm 4 hàng, 4 cột
B.i. Xét f = XY F
Nếu 2 hàng t1, t2 thuộc bảng: t1[X] = t2[X] thì đồng
nhất
A
a1
b21
a1
b41
B
C
D
b14
a4
b34
a4
t1[Y] = t2[Y], ưu tiên về giá trị a
Lặp cho tới khi không thể thay đổi được giá trị nào trong
R1
R2
R3
R4
a2
a2
a2
a2
b13
b23
a3
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
a3
43
44
11
10/11/2019
Ví dụ (tiếp)
Ví dụ (tiếp)
• Từ C D, ta có
• B2 & 3:
• Từ A C, ta có
A
B
C
D
A
B
C
a3
b23
a3
a3
D
b14
a4
R1
R2
R3
R4
a1
a2
a2
a2
a2
a3
a3
a3
a3
a4
a4
a4
a4
R1
R2
R3
R4
a1
a2
a2
a2
a2
b21
a1
b21
a1
b34
a4
b41
b41
A
B
C
D
b14
a4
• Vậy, có 2 hàng có toàn các giá trị aj,
chứng tỏ phép tách đã cho không mất
mát thông tin
• Từ B C, ta có
R1
R2
R3
R4
a1
a2
a2
a2
a2
a3
a3
a3
a3
b21
a1
b34
a4
b41
45
46
Ví dụ
Phép tách bảo toàn tập phụ thuộc hàm
• Hình chiếu của tập phụ thuộc hàm
• Ví dụ 1: R = {A, B, C} F = { AB, BC, CA}
được tách thành R1 = AB, R2 = BC. Phép tách
này có phải là bảo toàn tập phụ thuộc hàm
không?
• Ví dụ 2: R = {A, B, C} , F = {ABC, CB}
được tách thành R1 = AB, R2 = BC. Phép tách
này có bảo toàn tập pth không, có mất mát
thông tin không?
• Ví dụ 3: R = { A, B, C, D} , F = {AB, CD}
được tách thành R1 = AB, R2 = CD. Phép tách
này có bảo toàn tập pth không, có mất mát
thông tin không?
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ả XY
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.
• Vậy một phép tách có bảo toàn tập phụ thuộc
hàm thì không đảm bảo là nó sẽ không mất mát
thông tin và ngược lại
47
48
12
10/11/2019
Các dạng chuẩn đối với SĐQH
Dạng chuẩn 1 (1NF)
• Vấn đề thiết kế CSDL quan hệ:
– Có cần thiết phải tinh chỉnh thiết kế?
– Thiết kế có được đã là tốt hay chưa?
• Đị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ố
=> các dạng chuẩn: có một vài dạng chuẩn, có thể coi
như là một số các vấn đề về dư thừa dữ liệu hay dị
thường dữ liệu đã được ngăn ngừa hay tối thiểu hóa
– Giá trị nguyên tố là giá trị mà không thể chia
nhỏ ra được nữa
• Một quan hệ r xác định trên sơ đồ quan hệ ở dạng
chuẩn 1 thì quan hệ đấy là ở dạng chuẩn 1
• Ví dụ: Quan hệ không ở dạng chuẩn 1 và quan hệ
sau khi chuẩn hóa về dạng chuẩn 1
• Các dạng chuẩn mà chúng ta quan tâm
– Dạng chuẩn 1 (1NF)
– Dạng chuẩn 2 (2NF)
– Dạng chuẩn 3 (3NF)
– Dạng chuẩn Boyce-Code (BCNF)
sname
Blake
Smith
city
London
Paris
product
sname
Blake
city
item
Nut
price
100
name
price
100
120
75
London
Nut
Bolt
Blake
Smith
London
Paris
Bolt
120
75
50
Screw
Screw
49
Dạng chuẩn 2 (2NF)
Phụ thuộc hàm đầy đủ
• Định nghĩa: Một sơ đồ quan hệ R được
coi là ở dạng chuẩn 2 nếu
• Định nghĩa: 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:
–Sơ đồ quan hệ này ở 1NF
–Tất cả các thuộc tính không khoá đều
phụ thuộc hàm đầy đủ vào khoá chính
- XY thuộc F+
- ! X’ X : X’Y F+
(Lưu ý, A là một thuộc tính khoá nếu A
thuộc một khoá tối thiểu nào đó của R.
Ngược lại A là thuộc tính không khoá)
• Các phụ thuộc hàm không đầy đủ còn
gọi là phụ thuộc bộ phận
51
52
13
10/11/2019
Ví dụ
Dạng chuẩn 3 (tiếp)
• Sales(sid, sname, city, item, price)
• F = {sid(sname,city),
(sid,item)price}
• Định nghĩa: Một sơ đồ quan hệ R được
coi là ở dạng chuẩn 3 nếu
–Sơ đồ quan hệ này ở 2NF
–Mọi thuộc tính không khoá đều không
phụ thuộc bắc cầu vào khoá chính
• Khoá chính (sid,item), ta có sname,
city không phụ thuộc hàm đầy đủ vào
khoá chính => Quan hệ Sales không
thuộc 2NF
• S(sid, sname, city) và Sales (sid,
item, price) là quan hệ thuộc 2NF
53
54
Phụ thuộc bắc cầu
Ví dụ
• Ví dụ 1: Trong ví dụ tách về dạng chuẩn 2,
có: S (sid, sname, city) và Sales(sid, item,
price).
Xét quan hệ S, pth sid sname, city tồn tại
trên S, sid là khoá chính, các thuộc tính
không khoá sname, city đều phụ thuộc trực
tiếp vào sid. S thuộc 3NF. Tương tự, có
Sales cũng thuộc 3NF
• Định nghĩa: Cho sơ đồ quan hệ R(U).
F là tập pth trên R(U). X,Y,Z U.
Nói Z là phụ thuộc bắc cầu vào X
nếu ta có XY, YZ thuộc F+.
Ngược lại, ta nói Z không phụ thuộc
bắc cầu vào X
• Ví dụ 2:
– ItemInfo(item, price, discount). F = {itemprice,
pricediscount}. Khoá chính là item, thuộc tính
không khoá discount phụ thuộc bắc cầu vào khoá
chính item. Vậy quan hệ này không ở 3NF.
– ItemInfo(item, price) và Discount(price,
discount) thuộc 3NF.
55
56
14
10/11/2019
Dạng chuẩn Boyce-Codd
Dạng chuẩn Boyce-Codd (tiếp)
• Định nghĩa:
• Hình oval thể hiện thuộc tính/tập thuộc tính
• Các cung thể hiện các pth
– Một sơ đồ quan hệ R(U)với một tập phụ thuộc
hàm F được gọi là ở dạng chuẩn Boyce-Codd
(BCNF) nếu với XA F+ thì
– A là thuộc tính xuất hiện trong X hoặc
– X chứa một khoá của quan hệ R.
• Trong một quan hệ ở BCNF, các pth không
tầm thường duy nhất là một khóa xác định
một số thuộc tính. Do đó, mỗi bộ được xem
là một thực thể hoặc liên kết, được nhận
diện bởi một khóa và được mô tả bởi các
thuộc tính còn lại.
Nonkey
attr1
Nonkey
attr2
Nonkey
attrk
...
Key
• Nếu một quan hệ ở BCNF, mỗi trường của
mỗi bộ chứa thông tin không thể được suy
diễn ra từ các giá trị trong các trường khác
(mà chỉ sử dụng các pth)
57
58
Dạng chuẩn Boyce-Codd (tiếp)
Tách bảo toàn tập phụ thuộc hàm về 3NF
• Ví dụ
• 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án
– R = {A,B,C} ; F = {ABC , CB}.
– R không phải ở BCNF vì CB, C không phải là
khoá
• Chú ý:
B1. 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 Ai
B2. Nếu f F, f chứa tất cả các thuộc tính của R
(đã bỏ các Ai ở bước trên) thì kết quả là R
– Một quan hệ thuộc 3NF thì chưa chắc đã thuộc
BCNF. Nhưng một quan hệ thuộc BCNF thì thuộc
3NF
B3. Ngược lại, với mỗi X A F, xác định một
quan hệ Ri(XA).
Nếu XAi, XAj thì tạo một quan hệ chung
R’(XAiAj)
59
60
15
10/11/2019
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ụ
• Yêu cầu:
Cho R = {A,B,C,D,E,F,G}
– Bảo toàn tập phụ thuộc hàm (như thuật toán
trên)
F = {AB, ACDE, EFG} (đã tối thiểu)
• Xác định phép tách bảo toàn tập phụ thuộc
hàm về 3NF
– Đảm bảo là có một lược đồ con chứa khoá của
lược đồ được tách
• Các bước tiến hành
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
B1. Tìm một khoá tối thiểu của lược đồ quan hệ R đã cho
B2. Tách lược đồ quan hệ R theo phép tách bảo toàn tập phụ
thuộc hàm.
B3. Nếu 1 trong các sơ đồ con có chứa khoá 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 sơ đồ quan hệ được
tạo bởi khoá tối thiểu tìm được ở 1
B3. AB
ACDE
EFG
R1(AB)
R2(ACDE)
R3(EFG)
61
62
Ví dụ
Ví dụ (tiếp)
• Cho R(U) trong đó U = {A,B,C,D,E,F,G}. F =
• Dùng kết quả của ví dụ ở phần tách bảo
toàn tập phụ thuộc hàm ta có một phép
tách R thành 3 sơ đồ con R1 = AB, R2=
ACDE, R3 = EFG
• Do khoá ACDF không nằm trong bất kỳ một
sơ đồ con nào trong 3 sơ đồ con trên, ta lập
một sơ đồ con mới R4 = ACDF
• Kết quả cuối cùng ta có phép tách R thành
4 sơ đồ 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
{AB, ACDE, EFG}
• Tìm một khoá tối thiểu của R:
K0 = ABCDEFG
K1 = K0 do nếu loại A thì BCDEFG U không
thuộc F+
K2 = K1 \{B} = ACDEFG do ACDEFG U thuộc F+
K3 = K2 do nếu loại C thì ADEFG U không thuộc
F+
K4 = K3 do nếu loại D thì ACEFG U không thuộc
F+
K5 = K4 \{E} = ACDFG do ACDFG U thuộc F+
K6 = K5 do nếu loại F thì ACDG U không thuộc
F+
tập phụ thuộc hàm
K7 = K6 \{G} = ACDF do ACDF U thuộc F+
63
64
• Vậy khoá tối thiểu cần tìm là ACDF
16
10/11/2019
Tách không mất mát thông tin về BCNF (tiếp)
Tách không mất mát thông tin về BCNF
• Vào: Sơ đồ quan hệ R, tập phụ thuộc hàm F.
• Các ràng buộc toàn vẹn:
• Ra: phép tách không mất mát thông tin bao gồm
một tập các sơ đồ con ở BCNF với các phụ thuộc
hàm là hình chiếu của F lên sơ đồ đó.
– CCSJDPQV, JPC, SDP, JS
CSJDPQV
• Cách tiến hành
– Giả sử R không ở BCNF, XR, A là một thuộc tính trong R,
XA là một pth gây ra vi phạm BCNF. Tách R thành R-A
và XA
SDP
– Nếu cả R-A và XA chưa ở BCNF, tiếp tục thực hiện việc
tách như trên.
SDP
CSJDQV
• Ví dụ:
JS
– Contracts(contractid, supplierid, projectid, deptid, partid,
qty, value)
– Viết gọn là CSJDPQV
SJ
CJDQV
65
66
Bài tập
Kết luận
• Tầm quan trọng của thiết kế CSDL
Cho sơ đồ S(U), U = {A, B, C, D, E, F,
G, H}, tập phụ thuộc hàm
F={ABCDE, CDE, ABCFG}
Hãy chuẩn hóa S về dạng chuẩn 3 với
phép tách bảo toàn thông tin và phụ
thuộc hàm.
– ả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
– Tránh 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ị thuờng
khi cập nhật
– 3NF: tránh các dị thường khi thêm/xoá
67
68
17
10/11/2019
Lời hay ý đẹp
"Nếu anh thấy một gia đình hạnh phúc,
anh nên tin rằng ở trong gia đình có
một người đàn bà biết quên mình."
(René Bazin)
69
70
18
18 trang
16781
Free
Bạn đang xem tài liệu "Bài giảng Cơ sở dữ liệu - Chương 4: Lý thuyết thiết kế cơ sở dữ liệu quan hệ - Nguyễn Hồng Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_co_so_du_lieu_chuong_4_ly_thuyet_thiet_ke_co_so_du.pdf
