Bài 17. Phép Tách Lược Đồ Quan Hệ

BÀI 17:
PHÉP TÁCH LUỢC ĐỒ QUAN HỆ





1/36
nội dung:

Tách lược đồ quan hệ
Phép tách bảo toàn phụ thuộc hàm
Thuật toán tách lược đồ thành 3NF
Tách không mất thông tin thành các
lược đồ ở dạng BCNF
Tổng kết
2/36
nội dung:

Tách lược đồ quan hệ
Phép tách bảo toàn phụ thuộc hàm
Thuật toán tách lược đồ thành 3NF
Tách không mất thông tin thành các
lược đồ ở dạng BCNF
Tổng kết
3/36
17.1. Tách lược đồ quan hệ

Định nghĩa:
Phép tách lược đồ quan hệ α =( U, F) là phép thay thế nó bằng một tập các lược đồ con αi=(Ui, Fi), i=1, …, k với điều kiện :
Ui i=1, …, k Ui=U, Fi=F/Ui
Phép tách đó được ký hiệu là: δ ={ U1, U2, …, Uk } là một phép tách khi đó R là một quan hệ trên U, kí hiệu:
mδ(R) =R[U1]*[U2]*…*[Uk]
4/36
17.1. Tách lược đồ quan hệ
Định nghĩa:
Phép tách kết nối không mất thông tin ( lossless-join decomposition)
Cho lược đồ quan hệ α =( U, F) và phép tách δ ={ U1, U2, …, Uk } đối với lược đồ đó.
Phép tách δ được gọi nối không mất thông tin nếu mọi quan hệ R trên U thì ta có mδ(R) =R,
Ngược lại nếu mδ(R) R thì phép tách δ là phép tách mất thông tin.
5/36
17.1. Tách lược đồ quan hệ

Bổ đề:
Cho lược đồ quan hệ α =( U, F) và phép tách δ ={ U1, U2, …, Uk } đối với lược đồ đó, R là một quan hệ trên U, gọi Ri=R[Ui] thì:
R mδ(R)
Nếu S= mδ(R) thì S[Ui]=Ri
mδ(mδ(R))= mδ(R)
6/36
17.1. Tách lược đồ quan hệ

Chứng minh:
a) Lấy tR, đặt ti=t.Ui, khi đó ti =t.UiR[Ui]
=> R[U1]*[U2]*…*[Uk]
Vậy t mδ(R) vậy R mδ(R)
b) Ta có RS =>R[Ui]  S[Ui] hay Ri S[Ui].
Cần chỉ ra rằng S[Ui]  Ri giả sử với một i mà tiS[Ui].
Khi đó t= S sao cho t[Ui]=ti.
7/36
17.1. Tách lược đồ quan hệ

Chứng minh:
Cũng vì tS sao cho t[Ui]=vj
=>có vj Ri sao cho t[Ui]=vj.
Trong trường hợp này t[Ui]  Ri.
Nhưng vì t[Ui]=ti và do đó S[Ui]  Ri từ đó Ri= S[Ui].
c) Nếu S= mδ(R) thì theo b) có S[Ui] = Ri.
Do vậy: mδ(S)= Ri= mδ(R)
8/36
17.1. Tách lược đồ quan hệ

Bài toán:

Cho lược đồ quan hệ α =( U, F) và phép tách δ, hỏi rằng phép tách đó có mất thông tin hay không, hay với phép tách δ cần kiểm tra xem đẳng thức mδ(R)=R, với mọi R(U)
9/36
17.1. Tách lược đồ quan hệ
Thuật toán kiểm tra phép tách kết nối có mất thong tin hay không?

Input:
Tập thuộc tính U
Tập phụ thuộc hàm F
Phép tách δ ={ U1, U2, …, Uk }
Output:
Xác định liệu phép tách δ có mất thông tin hay không.
10/36
17.1. Tách lược đồ quan hệ
Thuật toán:
Bước 1: Giả sử U ={ A1, A2, …, An }.
Ta xây dựng một bảng gồm k+1 dòng, n+1 cột (n=|U|, k=| δ|).
Cột thứ i (i=1..n) của bảng ứng với thuộc tính Ai .
Hàng thứ j (j=1..k) của bảng ứng với lược đồ con αj=(Uj,Fj). Tại cột i (i=1..n) và hàng j (j=1..k) ta điền ký hiệu aj ( ta gọi ký hiệu aj là tín hiệu chính) nếu thuộc tính AjUi .
Ngược lại ta điền bji ( ta gọi bji là tín hiệu phụ).
11/36
17.1. Tách lược đồ quan hệ
Thuật toán:
Bước 2: Biến đổi bảng như theo quy tắc như sau:
Với mỗi phụ thuộc hàm X→Y F, nếu trong bảng có hai hàng giống nhau trên tập thuộc tính X thì ta cần làm chúng giống nhau trên tập thuộc tính Y theo quy tắc sau:
- Nếu một trong hai giá trị là tín hiệu phụ thì ta sửa lại tín hiệu phụ thành tín hiệu chính tức là bji thành aj.
- Nếu cả hai là tín hiệu phụ thì ta sửa lại nột trong hai tín hiệu đó bằng một trong các ký hiệu bji, tức là chỉnh lại chỉ số cho giống nhau.
12/36
17.1. Tách lược đồ quan hệ
Thuật toán:
Bước 2:
Tiếp tục áp dụng các phụ thuộc hàm trong bảng cho tới khi không còn áp dụng được nữa.
Quan sát trong bảng cuối cùng:
- Nếu xuất hiên ít nhất một hàng gồm toàn tín hiệu chính (hàng gồm toàn ký hiệu a) thì phép tách δ có kết nối không mất thông tin.
- Ngược lại thì phép tách δ là phép tách có kết nối mất thông tin.
13/36
17.1. Tách lược đồ quan hệ
Ví dụ:
Cho lược đồ quan hệ α =( U, F) với
U={A1, A2, A3, A4, A5}
F={A1→A2A3, A2A4→A5, A2→A3}
δ ={A1A2A4, A2A3, A1A4A5}
Hỏi rằng phép tách δ trên có kết nối không mất thông tin không?
14/36
17.1. Tách lược đồ quan hệ
Giải:
Xây dựng bảng gồm 3 hàng, 5 cột:
Điền các tín hiệu vào bảng:
15/36
17.1. Tách lược đồ quan hệ
Giải:
Xây dựng bảng gồm 3 hàng, 5 cột:
Biến đổi bảng trên dựa vào tập phụ thuộc hàm F:
- Sử dụng phụ thuộc hàm A1→A2A3 ta biến đổi bảng
16/36
17.1. Tách lược đồ quan hệ
Giải:
Xây dựng bảng gồm 3 hàng, 5 cột:
Biến đổi bảng trên dựa vào tập phụ thuộc hàm F:
- Sử dụng phụ thuộc hàm A2A4→A5
17/36
17.1. Tách lược đồ quan hệ
Giải:
Xây dựng bẳng gồm 3 hàng, 5 cột:
Biến đổi bảng trên dựa vào tập phụ thuộc hàm F:
- Sử dụng phụ thuộc hàm A2→A3







Từ bảng ta thấy phép tách δ là phép tách kết nối không mất thông tin.
18/36
17.1. Tách lược đồ quan hệ

Định lý:
Cho lược đồ α =( U, F)
và phép tách δ={U1,U2}
nếu U1U2→U1U2 (1)
hoặc U1U2→U2U1 (2)
=> Phép tách δ là phép tách có kết nối không mất thông tin.
19/36
17.1. Tách lược đồ quan hệ
Chứng minh:
Giả sử U={A1, A2, …, An }, U1={A1, A2, …, Am },
U2={A1, A2, …, An }, U1U2={Ak, Ak+1, …, Am },
Ta lập bảng gồm 2 hàng, n cột và điền vào các tín hiệu:




U1 U2 U1U2 U2 U1
20/36
17.1. Tách lược đồ quan hệ
Giả sử (1) là đúng. Ta thấy hai hàng của bảng trên giống nhau trên miền U1U2={Ak, Ak+1, …, Am }
=>Nên chúng phải giống nhau trên miền U1 U2.
Trên miền U2 U1 :
=>Tất cả các tín hiệu phụ trên miền U2 U1 đều được thay bằng các tín hiệu chính tương ứng trên hàng 2.
Sau khi thay thì toàn bộ dòng 1 gồm toàn các tín hiệu chính.
=>Do vậy phép tách δ là phép tách có kết nối không mất thôngtin
21/36
17.1. Tách lược đồ quan hệ
Hệ quả: Cho lược đồ α =( U, F), X, YU.
Nếu X→YF+ thì phép δ={U1,U2} với U1=XY, U2=XZ trong đó Z=UXY.
=>Phép tách δ là phép tách có kết nối không mất thông tin.
Thật vậy:
Ta có U1U2=X, U1 U2=Y
Theo giả thiết thì X→Y nên U1U2→ U1 U2
Theo định lý trên thì phép tách δ là phép tách có kết nối không mất thông tin.
22/36
17.1. Tách lược đồ quan hệ
Bổ đề: Mọi lược đồ quan hệ chỉ có hai thuộc tính đều ở dạng BCNF
Cho lược đồ α =( U, F), gọi δ ={ U1, U2, …, Uk } là phép tách không mất thông tin của α đối với F.
Gọi Fi là hình chiếu của F lên Ui (i= ) tức là Fi={X→Y|X→YF+ và XYUi}
Gọi б={ Ui1, Ui2, …, Uim } là phép tách không mất thông tin của lược đồ con αi =( Ui, Fi)
Khi đó phép tách lược đồ α thành
{ U1, U2, …, Ui-1, Ui1, Ui2, …, Uim, Ui+1,…, Uk} đối với F là phép tách có kết nối không mất thông tin.
23/36
17.1. Tách lược đồ quan hệ
Bổ đề:
Mọi lược đồ quan hệ chỉ có hai thuộc tính đều ở dạng BCNF
Giả thiết α và δ như trong phần a) gọi:
σ ={ U1, U2, …, Uk, Uk+1, …, Un} là phép tách của α thành tập các lược đồ con bao gồm cả δ
=>σ cũng là phép tách không mất thông tin đối với F.
24/36
nội dung:

Tách lược đồ quan hệ
Phép tách bảo toàn phụ thuộc hàm
Thuật toán tách lược đồ thành 3NF
Tách không mất thông tin thành các
lược đồ ở dạng BCNF
Tổng kết
25/36
17.2. Phép tách bảo toàn phụ thuộc hàm
Hình chiếu của một phụ thuộc hàm trên một tập thuộc tính:
Cho lược đồ quan hệ α =( U, F), ZU hình chiếu của tập F lên tập thuộc tính Z, ký hiệu là F và nó được xác định như sau:
F/Z={X→Y|X→Y F+ và XYZ}
Định ngĩa này không yêu cầu X→Y phải thuộc về F nhưng phải thuộc về F+
Trong đó:
X và Y phải là các tập con của Z.
26/36
17.2. Phép tách bảo toàn phụ thuộc hàm

Thuật toán:
Tìm hình chiếu của một tập phụ thuộc hàm lên tập thuộc tính
Để tìm hình chiếu của F lên Z ta lấy các tập con thực sự X của Z, đóng vai trò là vế trái của các phụ thuộc hàm.
Tính X+
Gán Y=( X+Z)X
Khi đó X→Y là một phụ thuộc hàm F/Z
27/36
17.2. Phép tách bảo toàn phụ thuộc hàm
Bảo toàn phụ thuộc hàm:
Cho lược đồ quan hệ α =( U, F)
Và δ ={ U1, U2, …, Un } là một phép tách của α.
Gọi Fi là hình chiếu của F lên Ui
Phép tách δ được gọi là phép tách bảo toàn phụ thuộc hàm F nếu như :
( )+= F+
28/36
nội dung:

Tách lược đồ quan hệ
Phép tách bảo toàn phụ thuộc hàm
Thuật toán tách lược đồ thành 3NF
Tách không mất thông tin thành các
lược đồ ở dạng BCNF
Tổng kết
29/36
17.3. thuật toán tách lược đồ thành 3NF
Thuật toán tách lược đồ thành 3NF:
Input: Cho lược đồ quan hệ α =( U, F)
Output: Các lược đồ ở dạng 3NF
α1 =( U1, F1), α2 =( U2, F2),…, αn =( Un, Fn) thảo mãn:

quan hệ R trên U => R[U1]*R[U2]*…*R[Un]=R
K1, K2,…, Kn lá các khóa của lược đồ tương ứng
30/36
17.3. thuật toán tách lược đồ thành 3NF
Thuật toán:
Bước 1: Tìm một khóa K của lược đồ α
Bước 2: Tìm một phủ G của tối thiểu của F
G={K1→A1, K2→A2,…, Kp→Ap}
Bước 3: Gép các phụ thuộc hàm có cùng vế trái trong G để thu được phủ
G={K1→X1, K2→X2,…, Kn→Xn}
Bước 4: Phép tách δ={K1X1, K2X2,…, KnXn} nếu khóa K không có mặt trong thành phần nào của δ thì them thành phần K vào δ.
Bước 5: Return δ.
31/36
17.4. Tách không mất thông tin thÀnh các lược đồ ở dạng BCNF
Cho lược đồ quan hệ α =( U, F), và phép tách δ ={ U1, U2, …, Uk }, phép tách một lược đồ thành một tập các lược đồ ở dạng BCNF là phép tách thỏa mãn:
Phép tách δ là phép tách kết nối không mất thông tin.
Tất cả các lược đồ con αi =( Ui, Fi) đều ở dạng BCNF.
32/36
17.4. Tách không mất thông tin thÀnh các lược đồ ở dạng BCNF
Phương pháp:
Xuất phát từ một phụ thuộc hàm X→A nào đó của F, phụ thuộc hàm X→A này vi phạm điều kiện BCNF
=> Ta xây dựng phép tách δ ={ U1, U2}, tương ứng với lược đồ α1 và α2 sao cho:
Phép tách đó là phép tách kết nối không mất thông tin.
Phụ thuộc hàm X→A là phụ thuộc hàm của lược đồ α1 và nó thỏa mãn điều kiên của BCNF trong lược đồ này.

33/36
17.4. Tách không mất thông tin thÀnh các lược đồ ở dạng BCNF
Nếu như lược đồ α1 và α2 vẫn chưa ở dạng BCNF thì tiếp tục quá trình đó, vì các điều vi phạm BCNF đều bị loại bỏ, cuối cùng ta thu được một tập các lược đồ con đếu ở dạng BCNF và quá trình tách cuối luôn luôn đảm bảo phép tách kết nối không mất thông tin.
Ví dụ:
Cho lược đồ quan hệ α =( U, F) với U=CRHTSG và C: Course, T: Teacher, H: Hour, R: Room, S: Student, G: Group
F={C→T, HR→C, CH→R, CS→G, HS→R}
34/36
17.4. Tách không mất thông tin thÀnh các lược đồ ở dạng BCNF
Nhận xét:
Lược đồ này có duy nhất một khóa là SH
Lược đồ này chưa ở dạng BCNF
Ta thấy lược đồ α=( U, F) có phụ thuộc hàm CS→G vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U1=CGS, U2=CTHRS
Ta thấy lược đồ α2=( U2, F2) có phụ thuộc hàm C→T vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U3=CT, U4=CHRS
Ta thấy lược đồ α4=( U4, F4) có phụ thuộc hàm CH→R vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U5=CHR, U6=CHS
35/36
17.4. Tách không mất thông tin thÀnh các lược đồ ở dạng BCNF
α=( U, F)
U1=CGS
F1={ CS→G} K=CS
U2=CTHRS
F2={C→T, HR→C, CH→R, HS→R}
K=HS
U6=CHS
F6={HS→C}
K=HS
U3= CT
F3={C→T}
K=C
U5=CHR
F5={HR→C, CH→R}
K=HR, K=HC
U4=CTHRS
F2={HR→C, CH→R, HS→R}
K=HS
36/36