Môn CƠ SỞ DỮ LIỆU
Chương 6:
Chuẩn hóa
cơ sở dữ liệu
2
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
3
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)

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.
6
1. PHÉP KẾT NỐI BẢO TOÀN TT (tt)

Ví dụ:
7
2. PHÉP TÁCH BẢO TOÀN PTH
Cơ sở lý thuyết

Cho phân rã p = {Q
1
,Q
2
,…Q
k
} 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 Q

Dữ liệu ra: phép tách p có bảo toàn phụ thuộc hàm hay không ?
8
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 thức theo
kích thước của F.
9
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 Q
i
(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

với F.
11
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
12
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}

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
16
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


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
18
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ử <Q,F> được phân rã thành lược đồ CSDL C ={<Qi,Fi>}. 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+
2. (∪ FI )+ = F+
19
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
={<Qi,Fi>} bằng phương pháp tổng hợp.

gọi đó là Ki (Ki cũng là một mảng 2 chiều)
21
4. TIẾP CẬN TỔNG HỢP … (tt)
Thuật toán (tt) Bước 4:
1. H = ∅
2. Gom các nhóm có siêu khóa đại diện tương đương vào nhóm FI và thành lập tập phụ
thuộc hàm H chứa các phụ thuộc hàm là các siêu khóa tương đương: ∀ Ni,Nj (i ≠ j )
có các siêu khóa đại diện tương ứng là Ki , Kj
{ Nếu KI ⇔ Kj { Đưa nhóm Nj vào trong nhóm Ni
H = H ∪ {Ki → Kj ; Kj → Ki}
Loại bỏ nhóm Nj
}}
3. Loại bỏ khỏi PTT những phụ thuộc hàm thuộc H+ đồng thời loại bỏ khỏi nhóm Fi
những phụ thuộc hàm có trong tập H .
∀ f: X → A ∈ PTT
{ Nếu X → A ∈ H { PTT = PTT - {f}
Nếu f ∈ Fi thì Fi=FI − {f}
}}
Đặt PTT1 = PTT
22
4. TIẾP CẬN TỔNG HỢP … (tt)
Thuật toán (tt) Bước 5:
1/ Tìm tập phụ thuộc hàm PTT2 sao cho: (PTT2 ∪ H)+ = (PTT1 ∪ H)+
∀ f ∈ PTT1
{ Nếu {{PTT1 − f} ∪ H }+ = {PTT1 ∪ H }+ thì
{ PTT1 = PTT1 - f
Nếu f ∈ Fi thì FI = FI − {f}}}
PTT2 = PTT1
2 Đưa các phụ thuộc hàm thuộc H vào các nhóm F
I

Thuật toán cho bước 7 là:
SI , Kj (Si là siêu khóa của một nhóm, Kj là một khóa của quan hệ phổ quát
{ Nếu Kj Si thì
{ Bảo toàn thông tin và bảo toàn phụ thuộc hàm =đúng
Break; }
}
Nếu bảo toàn thông tin và bảo toàn phụ thuộc hàm thì
Bảo toàn thông tin và bảo toàn phụ thuộc hàm
Ngược lại
"Không bảo toàn thông tin hoặc không bào toàn phụ thuộc hàm, cần thêm một quan
hệ sau:"
C = C ∪ Q(Q*,F*)
Với Q* ={Một khóa của quan hệ phổ quát }
F* = ∅
25
4. TIẾP CẬN TỔNG HỢP … (tt)
Ví dụ: Cho lược đồ quan hệ Q(ABCDGH) vào tập PTH
F={ 1.GH → A, 2.AG → B,
3.CD →G,
4.GH → D,
5.C → A,
6.BH → C,
7.CD → H}
Kết quả đến bước 2: PTT(F) = F
Bước 3: Gom nhóm cùng vế trái
Nhóm 1={1,4}; Nhóm 2={2}; Nhóm 3={3,7}; Nhóm 4={5}
Nhóm 5={6}