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ệ

Khi đó t=<t1, t2, …, tk>∈ 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
1
*
=
i
k
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


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