HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

TRẦN VĂN SẢN

NGHIÊN CỨU, SO SÁNH CÁC PHƯƠNG PHÁP
PHÂN RÃ, DỊCH CHUYỂN SƠ ĐỒ QUAN HỆ Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: : 60.48.01

TÓM TẮT LUẬN VĂN THẠC SỸ KĨ THUẬT HÀ NỘI – 2012
1
- Thư viện của Học viện Công nghệ Bưu chính
Viễn thông
2
i. MỞ ĐẦU
i.1. Giới thiệu đề tài
Trong quản lý các cơ sở dữ liệu (CSDL), phụ thuộc
dữ liệu được hiểu là những mệnh đề mô tả các ràng buộc
mà dữ liệu phải đáp ứng trong thực tế. Nhờ có những mô
tả phụ thuộc này mà hệ quản trị cơ sở dữ liệu có thể quản
lý tốt được chất lượng dữ liệu. Lý thuyết về các phụ
thuộc dữ liệu đóng vai trò quan trọng trong việc mô tả
thế giới thực, phản ánh ngữ nghĩa dữ liệu trong cơ sở dữ
liệu. Phụ thuộc dữ liệu được Codd, tác giả của mô hình
dữ liệu quan hệ đặt nền móng từ những năm 70 với khái
niệm phụ thuộc hàm. Sau đó một loạt tác giả khác tiếp
tục phát triển các dạng phụ thuộc bậc cao, phụ thuộc mờ
cũng như xây dựng các hệ tiên đề cho các lớp phụ thuộc -
tức là đặt cơ sở lý thuyết về phụ thuộc dữ liệu.
Một điều khá tự nhiên là ngay từ những ngày đầu
phát triển lý thuyết thiết kế cơ sở dữ liệu, logic đã được
chọn như một ngôn ngữ hữu hiệu để đặc tả phụ thuộc dữ
liệu, do đó, trong số các loại hình phụ thuộc dữ liệu rất đa
dạng được đề xuất và phát triển sau này, các phụ thuộc


file dữ liệu dư thừa và loại bỏ các dị thường: không nhất
quán, dị thường khi thêm dòng, dị thường khi xóa dòng
của quan hệ, khi thực hiện phép cập nhật (sửa, thêm,
xóa).
Trong phép dịch chuyển sơ đồ quan hệ. Bản chất
của kỹ thuật này là loại bỏ khỏi sơ đồ quan hệ ban đầu
một số thuộc tính không quan trọng theo nghĩa chúng
không làm ảnh hưởng đến kết quả tính toán các đối tượng
đang quan tâm như bao đóng, khóa, Mặc dù sơ đồ quan
hệ thu được qua phép thu gọn không tương đương với sơ
đồ quan hệ ban đầu, nhưng ta có thể thu được các đối
tượng cần tìm bằng những phép toán đơn giản như loại
bỏ hoặc thêm một số thuộc tính. Điều lý thú là sau khi
loại bỏ một số thuộc tính thì một số phụ thuộc hàm sẽ
được loại bỏ theo, vì chúng trở thành các phụ thuộc hàm
tầm thường (có vế trái chứa về phải) hoặc mang thông tin
tiền định (đó là các phụ thuộc hàm dạng Ø→X).
5

i.2. Nội dung của đề tài, các vấn đề cần giải
quyết
Mục tiêu của luận văn là tìm hiểu kỹ thuật thu gọn
sơ đồ quan hệ dựa trên “phương pháp phân rã sơ đồ
quan hệ” và “phương pháp dịch chuyển sơ đồ quan
hệ”.
- Sử dụng một số thuật ngữ như dịch chuyển, phân
rã, chiếu của các sơ đồ quan hệ để làm sáng tỏ khái niệm

mềm toán học nói riêng để kiểm định và thể hiện các kết
quả lý thuyết.
i.4. Phạm vi ứng dụng
7
Các kết quả thu được có thể vận dụng cho các quy
trình thiết kế các cơ sở dữ liệu dùng trong các hệ thống
thông tin, cụ thể là:
Bảo toàn phụ thuộc hàm, không mất mát thông tin,
loại bỏ dư thừa dữ liệu. Đây là các tiêu chuẩn cơ bản của
hệ thống thông tin. Với các CSDL lớn và phức tạp có
nhiều thuộc tính, chúng ta phải dùng các phương pháp
biến đổi SĐQH để đưa chúng về dạng tối ưu, đáp ứng
được các tiêu chuẩn trên.
Về lý thuyết, luận văn tập trung vào các kết quả sau
đây:
- Khái niệm cơ sở lý thuyết của mô hình quan hệ.
- Khái niệm về phép phân rã sơ đồ quan hệ.
- Khái niệm về phép dịch chuyển sơ đồ quan hệ.
- Phát biểu và chứng minh các phương pháp phân rã
dọc sơ đồ quan hệ, phân rã có nối không tổn thất, phân rã
bảo toàn phụ thuộc, phân rã thành các dạng chuyển
BCNF.
- Phát biểu và chứng minh công thức tính bao đóng
qua phép dịch chuyển lược đồ quan hệ,

Cho U={A
1
,A
2
, ,A
n
} là một tập hữu hạn, không
rỗng các thuộc tính. Mỗi thuộc tính A
i
có một miền giá
trị là D(A
i
).
1.2. Các phép toán đại số quan hệ.
Trên các quan hệ ta có thể thực hiện các phép toán tập
hợp như hợp, giao, hiệu, các phép toán đó người ta
thường gọi là các phép toán đại số quan hệ,
1.2.1. Phép hợp
1.2.1. Phép giao
1.2.3. Phép trừ
1.2.3. Phép chiếu
1.2.5. Tích Descartes
1.2.6. Phép chọn
1.2.7. Phép chia
10
1.2.8. Phép nối tự nhiên
1.2.9. Phép nối có điều kiện

là tương đương nếu F
+
=G
+
. Ký hiệu F  G.
1.3.5. Các tập phụ thuộc hàm tối thiểu
Một tập phụ thuộc hàm là tối thiểu nếu nó thoả mãn các
điều kiện sau đây :
1. Mỗi vế phải của các phụ thuộc hàm F chỉ có một
thuộc tính.
2. Không tồn tại một phụ thuộc hàm X→A thuộc F
và tập con thực sự Z của X mà F
+
=(F-
{X→A}{Z→A})
+
.
3. Không tồn tại 1 phụ thuộc hàm X→A thuộc F mà
F
+
={F-{X→A}}
+

1.3.6. Bao đóng
Bao đóng F
+
của tập phụ thuộc hàm F, cho
lược đồ U = {A
1
, A


U).
(2) B  K: (K-{B})
+
 U.
Vậy tập K  U được gọi là khóa tối tiểu của sơ đồ
quan hệ W = <U, F> nếu K là tập tối tiểu kéo theo U.
1.4.2.Định nghĩa : Khoá của quan hệ R.
K

U được gọi là khoá của R nếu:
13
1. Mọi cặp t
i
và t
j
khác nhau của R ta luôn có t
i
.K 
t
j
.K
2. K là tối thiểu.
1.4.3.Định nghĩa : Khoá chính-khoá ngoại
Khoá chính của quan hệ R là một khoá của R được
chọn làm khoá chính.
Khoá ngoại của quan hệ R là trường dữ liệu đóng

Hình 1.1: Sơ đồ biểu thị mối liên hệ của các lớp chuẩn

1NF

2NF

3N
F

BCN
F

4N
F
15
Chương 2
CÁC PHƯƠNG PHÁP PHÂN RÃ SƠ ĐỒ QUAN
HỆ
Chương này giới thiệu các phép “phân rã sơ đồ
quan hệ”, tức là tách sơ đồ quan hệ trên thành các sơ đồ
quan hệ con với mong muốn các sơ đồ quan hệ con mới
này sẽ đạt dạng chuẩn cao hơn sơ đồ quan hệ ban đầu
Các đối tượng chúng ta sẽ phân rã là các sơ đồ quan
hệ W=<U,F> trong đó U={A

>, ký hiệu: W| >{W
1
, W
2
, , W
k
} trong
đó
F
i

Ui
(F
+
) và U =

k
i 1
U
i
.
2.2.Các phương pháp phân rã dọc sơ đồ quan hệ
16
2.2.1. Phân rã W=<U,F> có nối không tổn thất
Định nghĩa : Phép phân rã W| >{W
1
, W

= R[U
i
]. F
i
 π
Ui
(F
+
) và U =

k
i 1
U
i
là một phân
rã của W. Đặt G =

k
i 1
F
i.
2.2.3. Phân rã thành các dạng chuẩn BCNF
Định nghĩa : Phép phân rã W | > {W
1
,W
2
, ,W
k
}; W
i

17
Phân rã tổng hợp là phân rã thành BCNF, bảo
toàn phụ thuộc, có nối không tổn thất.
Định nghĩa: Cho W=<U, F>; W| >{W
1
, W
2
, ,
W
k
}; W
i
= <U
i
, F
i
>; F
i
=
Ui
(F
+
) là một phân rã của W
thành các BCNF bảo toàn phụ thuộc, có nối không tổn
thất nếu phép phân rã thỏa mãn cả 3 điều kiện trên.

Chương 3

và tập thuộc tính M  U. Ta nói sơ đồ quan hệ W2 nhận
được từ sơ đồ quan hệ W1 qua phép dịch chuyển theo tập
thuộc tính M, nếu sau khi loại bỏ mọi xuất hiện của các
thuộc tính của M trong sơ đồ W1 thì thu được sơ đồ W2.
19
Nếu sau khi thực hiện phép dịch chuyển theo M cho
SĐQH W1 ta thu được SĐQH W2 thì ta viết W2 =
W1\M.
Thao tác loại bỏ M được thực hiện trên sơ đồ W1 =
<U,F> để thu được sơ đồ W2=<V,G> như sau:
1. Tính V = U\M có độ phức tạp O(n) với n là số
lượng thuộc tính trong U.
2. Mỗi PTH XY trong F ta tạo ra PTH X\MY\M
cho G. Thủ tục này ký hiệu là G=F\M. Tính F\M
đòi hỏi độ phức tạp O(mn) với m là số lượng PTH
trong F.
Như vậy W2=W1\M = <U\M,F\M> được thực hiện
với độ phức tạp O(mn), tức là tuyến tính theo chiều dài
dữ liệu vào (của SĐQH W1).
Sau khi thực hiện thủ tục G = F\M nếu:
 G chứa các PTH tầm thường (dạng XY, X Y)
thì ta loại các PTH này khỏi G.
G chứa các PTH trùng lặp thì ta bớt các PTH này.
3.1.2. Thuật toán dịch chuyển sơ đồ quan hệ

PTH có vế trái chứa vế phải:
X,YU: XY  (XYF)
3. Cả hai vế trái và phải của mọi PTH trong F rời
nhau (không giao nhau): f  F:
LS(f)RS(f) = 
4. Các vế trái của mọi PTH trong F khác nhau đôi
một:
f, g  F: LS(f) = LS(g)  f = g
Trong đó:
LS(F): Tập các thuộc tính xuất hiện trong vế trái.
RS(F): Tập các thuộc tính xuất hiện trong vế phải.
Cụ thể là:

Ff
fLSFLS

 )()(
và

Ff
fRSFRS

 )()(

Nhóm tính chất 2-4 cho biết F có dạng thu gọn tự
nhiên. Như vậy SĐQH là cân bằng khi và chỉ khi tập
PTH có dạng thu gọn tự nhiên và mọi thuộc tính đều xuất
hiện ít nhất một lần ở vế trái, một lần ở vế phải.
3.1.5: Phép dịch chuyển sơ đồ quan hệ đến tập M
3.1.5.1: Định nghĩa phần bù của tập thuộc tính M

2
là bù của U
1
.
3.1.5.2: Định nghĩa phép dịch chuyển
SĐQH đến tập M
Cho hai SĐQH W1 = <U,F>, W2 = <V,G> và tập
thuộc tính M  U. Ta nói SĐQH W2 nhận được từ
SĐQH W1 qua phép dịch chuyển W1 đến tập thuộc tính
M, nếu sau khi loại bỏ mọi xuất hiện của các thuộc tính
của
M
= U\M trong lược đồ W1 thì thu được lược đồ
W2. Vậy W2 = W1 -
M
.
3.2: Phép chiếu sơ đồ quan hệ
Cho SĐQH W = <U,F> và tập thuộc tính M  U.
3.2.1: Định nghĩa phép chiếu của tập phụ thuộc
hàm F lên tập thuộc tính M.
Phép chiếu của tập phụ thuộc hàm F lên tập thuộc
tính M, ký hiệu Π
M
(F) là phép loại bỏ các thuộc tính
không thuộc M trong tập phụ thuộc hàm F.
23
3.2.2 : Định nghĩa phép chiếu của SĐQH W =

<M, Π
M
(F)> được gọi là không hợp lệ nếu tập phụ thuộc
hàm Π
M
(F) không thỏa mãn trên tập thuộc tính M.
3.3. Nhận xét, so sánh phương pháp phân rã và
dịch chuyển SĐQH
24
3.3.1. Một vài nhận xét đối với các phương pháp phân
rã:
Khi phân rã SĐQH ta nên phân rã thành bao nhiêu
sơ đồ con? và trong mỗi sơ đồ con nên lấy những thuộc
tính nào? phụ thuộc hàm nào thì tốt? Đây
là vấn đề lý thuyết mà em chưa tìm được câu trả lời chắc
chắn.
3.32. Một vài nhận xét đối với phương pháp dịch
chuyển:
Đối với phép dịch chuyển M, để có thể ứng dụng
được phép dịch chuyển ta nên lấy tập M như thế nào? Vì
sau phép dịch chuyển M của SĐQH W1 ta nhận được
SĐQH W2 và trong W2 có thể có những PTH kiểu


X. Đây cũng là dạng PTH em không hiểu. Dạng
PTH này có trong thực tế không?
Tuy nhiên theo yêu cầu của Thầy hướng dẫn nội