Khóa - Siêu Khóa
Giải thuật tìm tất cả các khóa
Các dạng phụ thuộc hàm
Sự dư thừa dữ liệu và các dị thường khi cập nhật
Dạng chuẩn 1
Dạng chuẩn 2
Dạng chuẩn 3
Dạng chuẩn BCNF
Phi chuẩn hóa
24 trang |
Chia sẻ: haohao89 | Lượt xem: 3377 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Giáo trình cơ sở dữ liệu chương 6: Chuẩn hóa lược đồ cơ sở dữ liệu quan hệ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 6. CHUẨN HÓA LƯỢC ĐỒ
CSDL QUAN HỆ
GV: Trần Ngân Bình
tnbinh@cit.ctu.edu.vn
6.2
Nội Dung
Khóa - Siêu Khóa
Giải thuật tìm tất cả các khóa
Các dạng phụ thuộc hàm
Sự dư thừa dữ liệu và các dị thường khi cập nhật
Dạng chuẩn 1
Dạng chuẩn 2
Dạng chuẩn 3
Dạng chuẩn BCNF
Phi chuẩn hóa
6.3
Khóa - Siêu Khóa
Khái niệm: Cho lược đồ quan hệ α = , K ⊆ U
)K được gọi là siêu khóa của α nếu : K+ = U ( hay K -> U)
)K được gọi là khóa của α nếu:
K là siêu khóa
K là siêu khóa nhỏ nhất: ∀ X ⊂ K, X không là siêu khóa,
hay X --> U
Nhận xét:
)Một LĐQH có thể có một hoặc nhiều siêu khóa, và một hoặc
nhiều khóa.
)Các khóa có thể có số lượng thuộc tính khác nhau.
)Hai khóa phân biệt không thể bao nhau: Nếu K1 ≠ K2, thì K1
⊄ K2 và K2 ⊄ K1.
6.4
Ví dụ khóa & siêu Khóa
Ví dụ: Dữ liệu về các cầu thủ bóng đá gồm các thuộc
tính:
)U = { TENCT, MAU_AO, SO_AO, DOI, TINH, HLV, DIEM,
Km }
)F = { TINH → Km
MAU_AO → TINH, DOI, HLV
DOI, TINH → MAU_AO, HLV
MAU_AO, SO_AO → U }
Từ tập PTH F ta có thể suy ra:
)Có siêu khóa K: K={DOI, TINH, SO_AO, MAU_AO }
)Và có khóa K1, K2 :
K1= { MAU_AO, SO_AO}
và K2= {DOI, TINH, SO_AO}
6.5
Giải Thuật Tìm Tất Cả Các Khóa (1)
Phép dịch chuyển LĐQH:
) Cho LĐQH α = , X ⊆ U.
) Phép dịch chuyển LĐQH trên X cho ta một LĐQH α’ = α\X =
, trong đó:
U’ = U \ X
F’ = { Li \ X → Ri \ X , i= 1..m}.
Nếu Ri \ X = φ thì bỏ đi PTH đó.
Ðịnh lý cơ bản:
)Cho LĐQH α = , X, Y ⊆ U, X∩Y =φ
) thì:
(XY)+α = X (Y)+α \ X
6.6
Giải Thuật Tìm Tất Cả Các Khóa (1)
Ví dụ: Giả sử tìm (AGHI)+ trên lược đồ quan hệ α gồm:
U = { ABCDEGHIJ }
F = { AG → BC BCE→ G C → DAB }
AD → EC IB→ DJ
Ta có thể tìm AGH(I)+α \ {AGH}
α’ = α \ {AGH } = , U’ = BCDEIJ
F’ = { φ → BC BCE → φ
D → EC IB→ DJ C → DB }
Ö I+α’ = IBCDJE
Ö (AGHI)+α = AGH (I)+α’ = AGHIBCDJE = ABCDEGHIJ
Hệ quả: X+α = X (φ)+α \ X
6.7
Giải Thuật Tìm Tất Cả Các Khóa (2)
Ðịnh lý: Gọi Kα là tập hợp tất cả các khóa của LĐQH α, và:
)U0 = ∩ Kα : là tập các thuộc tính nằm trong mọi khóa.
)M = ∪ Kα : là tập các thuộc tính khóa hay tập thuộc tính
nguyên thủy.
) I = U\M: là tập các thuộc tính không nằm trong mọi khóa.
)Khi đó: với X ⊆ U thì:
Kα = X ⊕ Kα \ X ⇔ X ⊆ U0
Kα = Kα \ X ⇔ X ⊆ I
Chú ý: phép tóan ⊕:
)X ⊕ { Y1, Y2,...Yn} = {XY1,XY2,... XYn}
6.8
Giải Thuật Tìm Tất Cả Các Khóa (2)
Giải thuật tìm Kα:
)Bước1: Ðưa F về dạng rút gọn tự nhiên
)Bước 2:Tính U0 = U - ∪ R i
)Bước 3: Tính I = ∪ R i - ∪ L i
)Bước 4: Xác định α’= α\U0I
)Bước 5: Tìm Kα’
)Bước 6: Kα = U0 ⊕ Kα’
m
i=1
m
i=1
m
i=1
6.9
Ví Dụ Tìm Tất Cả Các Khóa
Ví dụ: Cho α= với U = ABCDEGHIJL
F = { AI → ECD ABJ → GH CDL → ABEH}
1. F đã ở dạng rút gọn tự nhiên.
2. U0 = U - ∪ Ri = IJL
3. I = ABCDEGHIJL - ABCDIJL = EGH
4. α’ = α \ U0I =
U’ = U - U0I = ABCD
F’ = { A → CD CD→ AB}
5. Vì A+ = ABCD = U’, (CD)+ = ABCD
Î K α’ = { A, CD}
6. K α = U0 ⊕ K α’ = IJL ⊕ {A, CD } = {AIJL, CDIJL}
6.10
Các Dạng Phụ Thuộc Hàm
Phụ thuộc từng phần: Phụ thuộc hàm X Æ A được
gọi là phụ thuộc từng phần nếu X là tập con thật sự
của một khóa của R.
)Ví dụ: SAIP, F = {SÆ A, SI Æ P} => khóa là SI.
A: không là thuộc tính nguyên tố. S Æ A: là phụ thuộc
hàm từng phần
Phụ thuộc hàm đầy đủ (phụ thuộc hàm sơ cấp):
Phụ thuộc hàm X Æ A được gọi là phụ thuộc đầy đủ
nếu không tồn tại tập con thật sự Y ⊂ X nào để Y Æ A
xảy ra. Như vậy, phụ thuộc đầy đủ vào khóa ngược
lại với phụ thuộc từng phần.
6.11
Các Dạng Phụ Thuộc Hàm
Phụ thuộc truyền: Phụ thuộc hàm X Æ A được gọi
là phụ thuộc truyền nếu X không là tập con thật sự
của bất kỳ khóa nào.
)Ví dụ : SIDM, F = {SI Æ D, SD Æ M}, khóa là SI
M không là thuộc tính nguyên tố.
SD ⊄ SI => SD Æ M là phụ thuộc hàm truyền.
Hay tồn tại sơ đồ: SI Æ SD Æ M, nên SD Æ M là phụ
thuộc hàm truyền.
Phụ thuộc trực tiếp: Phụ thuộc hàm X Æ A được gọi
là phụ thuộc trực tiếp nếu không tồn tại tập thuộc tính
Y, với Y ≠ X, Y ≠ A thỏa: XÆ Y và Y Æ A
6.12
Chuẩn hóa CSDL
Một CSDL được thiết kế không tốt sẽ dẫn đến nhiều vấn
đề rắc rối nảy sinh khi sử dụng như dư thừa dữ liệu, dị
thường khi cập nhật.
Vấn đề đặt ra là làm sao thiết kế được một CSDL tốt.
Chuẩn hóa CSDL là một kỹ thuật dùng để tạo ra một
tập các quan hệ với các thuộc tính đáp ứng được các
yêu cầu cho trước về dữ liệu của một công ty
Có nhiều dạng chuẩn: 1NF, 2NF, 3NF, BCNF,…
Một CSDL không chuẩn đạt chuẩn 3 sẽ:
)Dẫn đến dữ liệu dư thừa => dữ liệu không nhất quán
)Có thể dẫn đến những tình trạng dị thường khi cập nhật dữ
liệu
6.13
Các Dạng Chuẩn Của Một LĐQH
Các bảng được chuẩn
hóa hoàn toàn
Dạng chuẩn thứ tư
Dạng chuẩn thứ hai
Dạng chuẩn thứ nhất
Loại bỏ các dị thường
có thể có
Loại bỏ các phụ thuộc hàm đa trị
Dạng chuẩn Boyce-Codd
Dạng chuẩn thứ ba
Loại bỏ các phụ thuộc hàm không khóa
Loại bỏ các phụ thuộc hàm truyền
Loại bỏ các phụ thuộc hàm từng phần
Loại bỏ các nhóm lặp lại
Các bảng chưa chuẩn
:
:
6.14
Dạng Chuẩn 1 (1NF)
Một quan hệ thỏa 1NF nếu mọi thuộc tính của R đều
khác trống, PTH vào khóa và không được mang giá
trị kép.
Ví dụ: Bảng không chuẩn
6.15
Đưa về 1NF:
Cách 1: San phẳng
=> tạo ra nhiều dữ liệu dư thừa
6.16
Đưa về 1NF:
Cách 2: Tách thành các bảng
6.17
Dị thường khi cập nhật
Dị thường khi xen:
)Thêm vào một Tài sản mới cần cho thuê?
Dị thường khi xóa
)Muốn xóa một hợp đồng cho thuê
Dị thường khi cập nhật
)Khi cập nhật tên của một chủ nhà ?
)=> phải cập nhật tất cả các dòng liên quan?
6.18
Dạng chuẩn 2 (2NF)
Một quan hệ thỏa 2NF là một quan hệ thỏa 1NF và
không tồn tại bất cứ một PTH từng phần nào trong
quan hệ
Nhận xét:
)Ðể biết một quan hệ R có thỏa dạng chuẩn 2 hay không, ta
phải xác định khóa của R. Từ đó, mới có thể xác định các
PTH nào là PTH từng phần.
)Chỉ có các quan hệ có khóa gồm hai thuộc tính trở lên thì
mới có thể không thỏa dạng chuẩn 2.
6.19
Ví dụ: QH không thỏa 2NF
Khóa chính
Không thoả
dạng chuẩn 2
6.20
Đưa về 2NF
Tách các thuộc tính phụ thuộc một phần vào khóa
=> đưa vào quan hệ mới
Khóa chính
6.21
Dạng chuẩn 3 (3NF)
Một quan hệ thỏa 3NF là một quan hệ thỏa 2NF và
không tồn tại bất cứ một PTH truyền nào trong quan
hệ
Khóa chính
Khóa chính
Khóa chínhKhông thoả
dạng chuẩn 2
6.22
Đưa về 3NF
Tách các thuộc tính không phụ thuộc trực tiếp vào khóa
=> đưa vào quan hệ mới
CSDL thỏa dạng chuẩn 3 là:
1. Customer (Customer_No, Cname)
2. Rental (Customer_No, Property_No, RentStart, RentFinish)
3. Property_for_Rent (Property_No, Paddress, Rent, Owner_N)
4. Owner (Owner_No, Oname)
6.23
Dạng chuẩn Boyce-Codd (BCNF)
Ðịnh nghĩa: Một sơ đồ QH được xem là ở dạng chuẩn
BCNF nếu nó thỏa dạng chuẩn thứ 3 và không tồn tại
bất cứ PTH nào mà vế trái không phải là siêu khóa.
Ví dụ: R = (CSZ),
F ={ CS Æ Z, Z Æ C}, khóa là CS, CZ.
) Có phụ thuộc hàm Z Æ C với Z không là siêu khóa
) => R(CSZ) không thỏa BCNF.
Ví dụ: Một khách hàng khi mua một loại hàng nào đó
thì chỉ liên hệ với một nhân viên duy nhất:
)LIÊN_HỆ (MAKH, LOẠI_HÀNG, MANV)
)Nếu Cty qui định: mỗi nhân viên chỉ phụ trách một loại hàng
hóa: MANV Æ LOAI_HANG
)=> Quan hệ LIEN_HE không thỏa chuẩn BCNF
6.24
Phi chuẩn hóa
(Denormalization)
Tạo sự rườm rà để cho hệ thống tránh
)Phải kết nối thường xuyên nhiều quan hệ
)VD: THISINH(SOBD, HO, TEN, NSINH, MABTS)
BTS(MABTS, TENBTS)
=> THISINH(SOBD, HO, TEN, NSINH, MABTS, TENBTS)
Mặc dù có PTH truyền => Phải phát biểu ràng buộc này
Phải tính toán thường xuyên các giá trị dẫn xuất
)VD:
HÓAĐƠN (STT_HĐ, NGÀY, TENKH, TRIGIA_HĐ)
CHITIẾT_HĐ (STT_HĐ, MA_HANG, DGIA, SOLG)