Chương 6 cung cấp cho người học những kiến thức về chuẩn hóa cơ sở dữ liệu. Các nội dung chính được trình bày trong chương này gồm có: Phép kết nối bảo toàn thông tin, phép tách bảo toàn phụ thuộc hàm, cách tiếp cận phân rã để thiết kế CSDL, cách tiếp cận tổng hợp để thiết kế CSDL.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cơ sở dữ liệu: Chương 6 - ThS. Hồ Đắc Quán
- Môn CƠ SỞ DỮ LIỆU
Chương 6: Chuẩn hóa
cơ sở dữ liệu
- Nội dung
1. PHÉP KẾT NỐI BẢO TOÀN THÔNG TIN
Cơ Sở Lý Thuyết
Thuật Toán Kiểm Tra Tính Kết Nối Bảo Toàn
Thông Tin
2. PHÉP TÁCH BẢO TOÀN PHỤ THUỘC HÀM
Cơ sở lý thuyết
Thuật toán
3. CÁCH TIẾP CẬN PHÂN RÃ ĐỂ THIẾT KẾ CSDL
4. CÁCH TIẾP CẬN TỔNG HỢP ĐỂ THIẾT KẾ CSDL
2
- 1. PHÉP KẾT NỐI BẢO TOÀN T.TIN
Cơ Sở Lý Thuyết
Nếu Q là một lược đồ quan hệ được tách thành các
lược đồ con Q1,Q2,...,Qk và F là tập phụ thuộc
hàm, nói rằng phép tách (phân rã ) là phép tách có
bảo toàn thông tin đối với F nếu với mỗi quan hệ r
trên Q thỏa F:
Q = Q1(r) * Q2 (r)* . . * Qk(r)
Tức là r được tạo nên từ phép kết nối tự nhiên của
các hình chiếu của nó trên Qi ( i =1..k)
3
- 1. PHÉP KẾT NỐI BẢO TOÀN TT (tt)
Thuật Toán Kiểm Tra Tính Kết Nối Bảo Toàn Thông Tin
Dữ liệu vào: Lược đồ quan hệ Q(A1,A2,…An) và tập các phụ
thuộc hàm F, phép tách = {Q,Q,…,Qk}.
Dữ liệu ra: Phép tách có bảo toàn thông tin hay không?
(1)Thiết lập bảng với k + 1 dòng, n + 1 cột . Cột j ứng với thuộc tính
AJ(i=1...n), hàng i ứng với lược đồ quan hệ Qi(i=1…k). Tại ví trí
hàng i, cột j ta điền ký hiệu Aj nếu AJ Qi,
Đầu tiên đặt t=1 và đặt vào các ô còn lại của bảng ký hiệu bt theo
chiều từ trái sang phải và từ trên xuống dưới, sau đó tăng t lên một
đơn vị và lặp lại thao tác điền bt như trên. Cho đến khi mọi ô của
bảng điều đã có ký hiệu.
(2)Xét lần lượt các phụ thuộc hàm trong F, áp dụng cho bảng vừa mới
thành lập ở trên. Giả sử xét (X Y) F, chúng ta tìm những hàng
giống nhau ở tất cả các thuộc tính của X, nếu thấy những hàng
như vậy ta sẽ làm cho các ký hiệu của hai hàng này bằng nhau ở tất
cả các thuộc tính của Y.
4
- 1. PHÉP KẾT NỐI BẢO TOÀN TT (tt)
Thuật Toán Kiểm Tra Tính Kết Nối Bảo Toàn Thông Tin (tt)
Khi làm cho 2 ký hiệu này bằng nhau, ta gặp 3 trường hợp sau đây:
nếu một trong hai ký hiệu là AJ thì cho ký hiệu kia trở thành AJ,
nếu hai ký hiệu là bk hoặc bl thì có thể cho chúng trở thành bt hoặc
bt (với t=min (k,l)),
nếu cả hai ký hiệu là aj thì giữ nguyên (lúc đó chỉ số j của các ký
hiệu này phải giống nhau)
Chú ý rằng bước này có thể được lặp lại (cho các phụ thuộc hàm) cho
đến khi không còn áp dụng được nữa (nghĩa là cho đến khi nào ở
một lần duyệt qua tất cả các phụ thuộc hàm trong F mà bảng không
có sự thay đổi nào.
(3)Xét bảng kết quả, nếu thấy trong bảng này có một hàng chứa toàn
aj (i=1..n) thì kết luận đó là phép tách bảo toàn thông tin, ngược lại
thì là phép tách m
ất mát thông tin. 5
- 1. PHÉP KẾT NỐI BẢO TOÀN TT (tt)
Ví dụ:
6
- 2. PHÉP TÁCH BẢO TOÀN PTH
Cơ sở lý thuyết
Cho phân rã p = {Q1,Q2,…Qk} của một lược đồ quan hệ, và tập phụ
thuộc hàm F. Hình chiếu của F trên một tập các thuộc tính Z ký
hiệu Z(Q) là tập các phụ thuộc hàm X Y F+ sao cho XY
Z . Ta nói phân rã p bảo toàn tập phụ thuộc hàm F nếu hợp của tất
cả các phụ thuộc hàm trong Qi(F) với i=1..k suy ra được tất cả các
phụ thuộc hàm trong F.
Lý do p cần bảo toàn tập F đó là vì các phụ thuộc hàm trong F có
thể được xem là các ràng buộc toàn vẹn cho quan hệ Q. Nếu các
phụ thuộc hình chiếu không suy ra được F thì khi biểu diễn Q qua
p , chúng ta có thể thấy rằng giá trị hiện hành của các Qi biểu diễn
một quan hệ Q không thỏa F, ngay cả nếu p là phép tách không mất
thông tin ứng với F. Khi đó mỗi thao tác cặp nhật trên mỗi Ri sẽ
cần phải thực hiện một phép nối để kiểm tra lại rằng các ràng
buộc không bị vi phạm.
Dữ liệu vào: Một phân rã p={Q1,Q2,…Qk} và một tập các phụ thuộc
hàm F(f1,f2,…,fm}
Dữ liệu ra: phép tách p có b
ảo toàn phụ thuộc hàm hay không ? 7
- 2. PHÉP TÁCH BẢO TOÀN PTH (tt)
Phép tách bảo toàn phụ thuộc hàm
Về nguyên tắc,chúng ta có thể dễ dàng kiểm tra xem một
phân rã p = {Q1,Q2,…Qk} có bảo toàn tập phụ thuộc F
hay không. Chúng ta chỉ cần tính F+ rồi chiếu nó trên tất
cả các thành phần Qi. Sau đó lấy hợp của các tập phụ
thuộc kết quả rồi kiểm ra xem tập này có tương đương
với F hay không ?
Tuy nhiên trong thực tế, tính F+ là một công việc hết sức
khó khăn vì số lượng các phụ thuộc chứa trong nó thường
là hàm mũ theo kích thước của F. Nhưng có một cách để
kiểm tra tính bảo toàn này mà không cần phải tính F+;
phương pháp này có chi phí thời gian tỷ lệ với hàm đa
8
- 2. PHÉP TÁCH BẢO TOÀN PTH (tt)
Thuật toán
Chúng ta gọi G là hợp của các Qi(F), để tính xem G có tương
đương với F hay không chúng ta xét mỗi phụ thuộc hàm X Y F
và xác định xem X+ (được tính ứng với G) có chứa Y hay không ?
nếu có thì phụ thuộc hàm này thuộc G.
Chúng ta định nghĩa phép toán Q trên tập các thuộc tính Z ứng với
một tập phụ thuộc F là phép thế Z bằng Z ((Z Q)+ Q) trong đó
bao đóng luôn được lấy ứng với F, phép toán này nối Z với những
thuộc tính A sao cho (Z Q) A QF. Do đó chúng ta tính X+ ứng
với G bằng cách khởi đầu với X, qua danh sách các Qi, chúng ta lần
lượt thực hiện các phép toán Qi với mỗi i, nếu tại một lần lặp nào
đó không có một phép toán Qi nào làm thay đổi các tập thuộc tính
hiện có thì chúng ta đã thực hiện xong; tập kết quả là X+
Nếu Y là một tập con của Z, là kết quả của thực hiện các phép trên
thì X Y G+ , nếu mỗi phụ thuộc hàm trong F đều thuộc G thì là
đúng, ngược lại là sai.
*Chú ý: M ột phân rã có thể bảo toàn thông tin nhưng không chắc b9ảo
- 3. TIẾP CẬN PHÂN RÃ ĐỂ TK CSDL
Theo quan điểm của cách tiếp cận này, các quan hệ con của cấu
trúc cơ dở dữ liệu ban đầu sẽ lần lượt được phân rã thành những
quan hệ con với số thuộc tính ít hơn, sao cho cấu trúc kết quả đạt
các tiêu chuẩn đề ra ở mức cao nhất. Quá trình phân rã là một quá
trình được lặp lại đối với các quan hệ con nào được đánh giá là còn
có thể phân rã.
*PHÂN RÃ MỘT LƯỢC ĐỒ Q THÀNH CÁC LƯỢC ĐỒ CON
DẠNG chuẩn BCK VA BẢO TOÀN THÔNG TIN
Cơ Sở Lý Thuyết
Bổ đề 1:
Giả sử Q là một lược đồ quan hệ với tập phụ thuộc hàm F, gọi
p={Q1,Q2,…,Qk } là một phân rã của Q có nối không mất ứng với
Q. nếu Q1 được phân rã thành hai lược đồ con (S1.S2) có nối không
mất, thì phân rã của Q thành (S1,S2,Q2,…,Qk) cũng có nối không
mất ứng với F.
10
- 3. TIẾP CẬN PHÂN RÃ …(tt)
Bổ đề 2:
a)Mỗi lược đồ có hai thuộc tính đều ở dạng chuẩn BCK
b)Nếu Q không đạt dạng chuẩn BCK thì chúng ta có thể
tìm được các thuộc tính A và B trong Q sao cho (Q AB)+
A. và phụ thuộc (Q AB)+ B có thể đúng trong trường
hợp này (nhưng đó là điều không quan trọng).
từ đây ta có thể phát biểu thêm mệnh đề đảo cho mệnh
đề này như sau:
b')Nếu trong Q không tìm được các thuộc tính A và B sao
cho (Q AB)+ A. và phụ thuộc (Q AB)+ B thì Q đã
đạt chuẩn BCK
11
- 3. TIẾP CẬN PHÂN RÃ …(tt)
Thuật Toán 1
Input: Cho lược đồ quan hệ phổ quát Q và tập phụ thuộc hàm F
Output: Lược đồ CSDL tương ứng đạt dạng chuẩn BCK.
Để phân rã [Q,F] ta thực hiện theo thủ tục đệ qui như sau:
Thủ tục phân rã(Q,F)
If Nếu Không tìm ra cặp A,B trong Q thỏa bổ đề thứ 2 trên thì Exit
Y = Q
WHILE TimAB(Y,F) {Tìm A,B thỏa bổ đề trên}
{Y=YB}
Q = Q A
Phân rã 2(Q,F) {gọi đệ qui}
12
- 3. TIẾP CẬN PHÂN RÃ …(tt)
Thuật Toán 1 (tt)
Chương trình chính của thuật toán Phân rã
Do
{ Gọi thủ tục Phân rã 2 (Q,F)
p = p Y
Q Q A
}
While Not TimAB(Q,F)
p = p
Kết thúc chương trình chính
13
- 3. TIẾP CẬN PHÂN RÃ …(tt)
Thuật Toán 2
phân rã(Q,F)
Xét f X Y F là phụ thuộc hàm làm cho [Q,F] vi phạm
dạng chuẩn BC
{
Tách Q thành Q1 và Q2 theo quy tắc sau:
Q1=Q[XY]; F1 = X Y
Q2=Q[Q+ Y] và cập nhật lại F=[F [các phụ thuộc hàm
có liên quan đến Y]
Phân rã (Q2,F) // công việc này tiếp tục cho đến khi XY
Q2+
} 14
- 3. TIẾP CẬN PHÂN RÃ …(tt)
*PHÂN RÃ MỘT LƯỢC ĐỒ Q THÀNH CÁC LƯỢC ĐỒ CON DẠNG 3NF CÓ
BẢO TOÀN PHỤ THUỘC
Không phải lúc nào cũng có thể phân rã một lược đồ quan hệ thành dạng BC mà vẫn
bào toàn được các phụ thuộc hàm, tuy nhiên chúng ta luôn có thể tìm được một
phân rã luôn bảo toàn phụ thuộc hàm thành dạng chuẩn cấp 3
Thuật toán:
Dữ liệu vào:
Lược đồ quan hệ Q và tập phụ thuộc hàm F, chúng ta giả sử rằng F đã ở dạng
phủ cực tiểu mà vẫn không làm mất tính tổng quát.
Dữ liệu ra:
Một phân rã bảo toàn phụ thuộc của Q sao cho mỗi lược đồ quan hệ con đều đạt
chuẩn 3NF ứng với hình chiếu của F trên lược đồ đó.
Nếu có những thuộc tính của R không nằm trong một phụ thuộc nào của F dù
ở vế phải hay vế trái của F thì ta loại chúng ra khỏi Q.
Nếu có một phụ thuộc hàm nào của F mà liên quan đến tất cả các thuộc tính của
Q thì kết quả ra chính là Q ( Q không thể phân rã)
Cứ mỗi phụ thuộc hàm X A F thì XA là một lược đồ cần tìm
15
- 3. TIẾP CẬN PHÂN RÃ …(tt)
*PHÂN RÃ LƯỢC ĐỒ Q THÀNH CÁC LƯỢC ĐỒ CON DẠNG
CHUẨN 3 VỪA BẢO TOÀN PHỤ THUỘC VỪA BẢO TOÀN
THÔNG TIN
Có thể phân rã một lược đồ thành các lược đồ con đạt dạng chuẩn
BCK có nối không mất, và chúng ta cũng có thể phân rã một lược
đồ thành 3NF bảo toàn phụ thuộc hàm. Liệu chúng ta có thể tìm
được một phân rã thành 3NF mà có cả hai đặc tính là bào toàn tập
phụ thuộc và có tính kết nối không mất thông tin hay không ? Chúng
ta có thể làm được điều đó thông qua phương pháp rất đơn giản
(mà hiệu quả ) sau đây:
Tìm một phân rã p của Q có dạng 3NF như vừa mới phân tích ở trên
,và tìm một khóa X của Q, thì X p là một phân rã của Q mà tất cả
các lược đồ quan hệ đều có tính kết nối không mất và bảo toàn phụ
thuộc, phân rã cuối cùng là X p, nghĩa là X chỉ thêm vào p nếu X
chưa có trong p.
16
- 3. TIẾP CẬN PHÂN RÃ …(tt)
Đánh giá các thuật toán phân rã
Thuật toán không quan tâm về chất lượng của các phụ
thuộc hàm trong tập F ban đầu, nghĩa là có hay không
những phụ thuộc hàm không đầy đủ, có hay không những
phụ thuộc hàm bắc cầu.
Tất cả các quan hệ kết quả đều đạt chuẩn BC
Tùy theo thứ tự các phụ thuộc hàm được xem xét, trong
quá trình phân rã, mà kết quả có thể khác nhau. Số lượng
các quan hệ con cũng có thể khác nhau.
Thuật toán không quan tâm đến việc xác định khóa của
các quan hệ con.
Kết quả có thể chứa một quan hệ con mà ngữ nghĩa của
nó có thể không có ích cho ứng dụng
17
- 4. TIẾP CẬN TỔNG HỢP ĐỂ TK CSDL
Cách tiếp cận tổng hợp không đòi hỏi người thiết kế phải phác
thảo một cấu trúc dữ liệu ban đâu, chỉ cần xác định danh sách các
thuộc tính cần được quan tâm và danh sách các quy tắc quản lý
của môi trường ứng dụng được diễn đạt dưới dạng các phụ thuộc
hàm.
Mục tiêu của cách tiếp cận này là các quan hệ con tối thiểu đạt
chuẩn 3 và bảo toàn tiêu chuẩn bảo toàn phụ thuộc hàm.
Một số khái niệm liên quan
Điều kiện bảo toàn thông tin: Cho lược đồ quan hệ phổ quát
Co( Q,F), giả sử được phân rã thành lược đồ CSDL C
={}. C là bảo toàn thông tin đối với Co khi và chỉ khi tồn
tại một quan hệ Qj C sao cho khóa của Qj là khóa của Q.
Điều kiện bảo toàn phụ thuộc hàm
Co và C được gọi là bảo toàn phụ thuộc hàm nếu thỏa đồng thời:
1. ( QI )+ = Q+
18
- 4. TIẾP CẬN TỔNG HỢP … (tt)
Thuật toán
Input: Cho lược đồ quan hệ phổ quát Co( Q,F), tìm lược đồ CSDL
C ={} bằng phương pháp tổng hợp.
Output: Xuất các C ={}
Bước 0:
Tách vế phải của các phụ thuộc hàm sao cho các phụ thuộc hàm chỉ
có một thuộc tính ở vế phải (như thuật toán tìm phủ tối thiểu)
Bước 1:
f F biến f thành một phụ thuộc hàm đầy đủ như trong thuật
toán tìm phủ tối thiểu(như thuật toán tìm phủ tối thiểu)
Bước 2:
Loại bỏ tất cả các phụ thuộc hàm dư thùa, ta được một phủ tối
thiểu(như thuật toán tìm phủ tối thiểu)
Gọi tập ph
ụ tối thiểu thu được của bước này là PTT 19
- 4. TIẾP CẬN TỔNG HỢP … (tt)
Thuật toán (tt) Bước 3:
1/ Gom những phụ thuộc hàm thuộc PTT thành những nhóm Ni có
cùng vế trái.(Ni là mảng 2 chiều, nội dung của nhóm là chỉ số của
những phụ thuộc hàm có trong PTT)
Thuật toán gom nhóm những phụ thuộc hàm có cùng vế trái:
f: Xi Yi, g : Xj Yj F (i j)
{Nếu Xi Xj
Đưa g vào cùng nhóm của nhóm chứa f
Loại nhóm g
}
2/Tìm các siêu khóa đại diện cho mỗi nhóm Ni: Lấy vế trái của phụ
thuộc hàm thứ nhất của nhóm i (tức là N(1,i ) làm siêu khóa của Ni
và gọi đó là Ki (Ki cũng là m
ột mảng 2 chiều) 20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
