Bộ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐAI HOC sư PHAM HÀ NÔI 2
• • • •
ĐINH THỊ Lực
PHÉP SUY DẪN CỦA CÁC PHỤ THUỘC HÀM TRONG MÔ
HÌNH DỮ LIÊU DANG KHỐI
• •
LUÂN VĂN THAC SỸ MÁY TÍNH
• •
Chuyên ngành: Khoa học máy tính Mã ngành: 60 48 01 01
Người hướng dẫn khoa học: PGS.TS. Trịnh Đình Thắng
Hà Nội, 2014
LỜI CẢM ƠN
Để hoàn thành luận văn này tôi đã nhận được sự giúp đỡ tận tình của thầy hướng dẫn
khoa học, của các thày cô trường Đại học Sư phạm Hà Nội 2. Tôi xin chân thành cảm ơn
các thầy cô trường Đại học Sư phạm Hà Nội 2 đã tạo điều kiện học tập, nghiên cứu và giúp
đỡ tôi rất nhiều ttong quá trình làm luận văn. Đặc biệt tôi xin cảm ơn thày PGS.TS Trịnh
Đình Thắng đã tận tình hướng dẫn, chỉ bảo tôi trong suốt quá tình học tập, nghiên cứu đề tài
và giúp đỡ tôi hoàn thành bản luận văn này.
Vĩnh Phúc, ngày 01 tháng 02 năm 2015 Học viên
Đỉnh Thi Lưc
• •
LỜI CAM ĐOAN
Tôi xin cam đoan đây là kết quả nghiên cứu của tôi dưới sự hướng dẫn khoa học
của PGS. TS Trịnh Đình Thắng.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố
trong bất kỳ công trình nào khác.
Học viên
Đỉnh Thị Lực
MỤC LỤC
class="bi x12 y1f w2 h6"
MỞ ĐẦU

4. Đối tượng và phạm vi nghiên cứu
Đối tượng, phạm vi nghiên cứu về các phép suy dẫn trong mô hình dữ liệu
dạng khối, các định lí tương đương.
5. Phương pháp nghiên cứu
Luận văn được thực hiện bằng phương pháp nghiên cứu lý thuyết: thu thập tài
liệu, phân tích các tài liệu và những thông tin liên quan đến đề tài, kết hợp các
nghiên cứu đã có trước đây của tác giả trong nước cùng với sự chỉ bảo, góp ý
của thầy hướng dẫn để hoàn thành nội dung nghiên cứu.
6. Những đóng góp mói của đề tài
- Phát biểu và chứng minh các tính chất của phụ thuộc kết nối trên khối
- Phát biểu và chứng minh tính chất của phụ thuộc phức họp trên khối.
- Đưa ra một số tính chất đặc trưng của phụ thuộc phức hợp trên khối tương
đương.
7. Cấu trúc của luân văn
Luận văn gồm: Lời mở đầu, ba chương nội dung, phàn kết luận và tài liệu
tham khảo.
Chương 1: Trình bày các khái niệm cơ bản nhất về mô hình quan hệ: Trình
bày các phép toán đại số ừên mô hình quan hệ, các vấn đề về phụ thuộc hàm,
khóa, bao đóng, các phép suy dẫn trên mô hình quan hệ.
Chương 2: Giới thiệu tổng quan về mô hình dữ liệu dạng khối: Định nghĩa
khối, lược đồ khối, khóa, đại số quan hệ trên khối, phụ thuộc hàm và các dạng
chuẩn của khối.
Chương 3: Phát biểu và chứng minh các tính chất của phụ thuộc kết nối trên
khối, phụ thuộc phức hợp trên khối. Đưa ra các tính chất đặc trưng của phụ
thuộc phức hợp trên khối.
CHƯƠNG 1: MÔ HÌNH cơ SỞ DỮ LIỆU QUAN HỆ VÀ CÁC PHÉP
SUY DẪN
1.1. Các khái niêm cơ bản
1.1.1. Thuộc tính và miền thuộc tính
Định nghĩa 1.1[6]

(i=l, 2,
ề
Ta có thể xem một quan hệ như một bảng, trong đó mỗi hàng (phần tử)
là một bộ và mỗi cột tương ứng với một thành phần gọi là thuộc tính. Biểu
diễn quan hệ r thành bảng như sau:
Ai A2

A
n
hi(Aj) hi(A
2
)

hi(A
n
)
H
2
( A 0 h
2
(A
2
)

h
2
(A
n
)


} được viết là R(U)
hoặc R(A
b
A
2
,A
n
).
Định nghĩa 1.4[6]
Khoá của quan hệ г xác định trên tập thuộc tính U={A
b
A
2
, A
n
} là tập
con К çU sao cho bất kỳ hai bộ khác nhau ti, t
2
e r luôn thoả ti(K) Ф
h
l
Bảng 1.1:
Biểu diễn quan hệ
r. Ví dụ 1.2: Sinhviên
MaSV HOTEN NS DC KHOA
SV01 A 24/01/92 ĐN TOAN
SV02 В 3/05/92 VP LY
SV03 В 3/05/92 VP TOAN
7
t

2
У1 z
2
x
2
У2 Zl
x
2
У2 z
2
(A
MaSV HOTEN NS DC KHOA
SV01 А 24/01/92 ĐN TOAN
SV02 В 3/05/92 VP LY
SV03 В 3/05/92 VP TOAN
9
b)Phép giao
- Phép giao của hai quan hệ khả hợp г và s, kí hiệu là r ris, là tập tất cả các bộ
thuộc cả hai quan hệ r và s. Ta có:
r N s = {t I terAt Gs}
Ví du 1.5:
1.2.2. Phép trừ và tích Đề-các
a) Phép trừ
Phép trừ của hai quan hệ khả họp r và s, kí hiệu: r - s là tập tất cả các bộ thuộc
r nhưng không thuộc s. Ta có:
r-s={t|terAtỂs}
b) Tích Đề-các
Cho quan hệ r xác định trên tập thuộc tính {Ai, A
2
, A

2
У2
Zl
r - s =
(A
в C)
s - r = (A
в С)
x
2
yi z
2
x
2
У2
z
2
x
2
У2
Zl
(A
В
C) ; s (A
В
C
)
Xi У1
Z l X i
У1

2
,Ьщ) I (a
b
a
2
,a
n
) er A (bl b
2
,Ьщ) es}
Bảng 1.2: Biểu diễn các quan hệ r, s và quan hệ rx s.
1.2.3. Phép chiếu, phép chọn và phép kết nổi
a) Phép chiếu
Cho г là một quan hệ n ngôi xác định trên tập thuộc tính ư={A
b
A
2
,A
n
}, X là
tập con của ư. Phép chiếu của quan hệ r trên tập thuộc tính X, kí hiệu là П (r),
là tập các bộ của r xác định trên tập thuộc tính X. Ta có:
rur) = {t.x| ter}.
Phép chiếu thực chất là phép toán giữ lại một số thuộc tính cần thiết của quan
hệ và loại bỏ những thuộc tính không càn thiết.
Ví du 1.8:
1
Ví du 1.7 :
•
А в

z
2
x
2
У1
z
2
Xl У1 Zl
x
2
yi z
2
x
2
У2
z
2
x
2
У1
z
2
Xl
У2
z
2
x
2
У2
Zl

Cho r là một quan hệ và F là một biểu thức logic trên các thuộc tính của
r. Phép chọn trên quan hệ r với biểu thức chọn F, kí hiệu là 5p (r), là tập tất cả
các bộ của r thoả mãn F. Ta có: Ô
F
(r) = {t I t€r A F(t)}.
1
( A
B
c
D)
X l
1
X
4
y i 5 y 2
Z l
5
z
5
X l
8
X
5
y i 1 y 4
Ví du 1.9:
Cho hai quan hệ r(U) và s(V). Đặt M = u n v . Phép kết nối(tự nhiên) hai
quan hệ r(ư) và s(V), ký hiệu r*s, cho ta quan hệ giữa các bộ được dán tò các
bộ u của quan hệ R với mỗi bộ V của quan hệ s (sao cho các trị trên miền
thuộc tính chung M của hai bộ này giống nhau).
P(UV)= r*s= {u*v I u6r, v6s, U.M=V.M}

з
У У2 У2 У2 Уз
Z l X
z
2
1.3. Các phụ thuộc hàm
Khi xét đến mối quan hệ giữa dữ liệu ừong CSDL quan hệ một trong
nhưng yếu tố quan trọng nhất được xét đến là sự phụ thuộc giữa các thuộc tính
này với thuộc tính khác. Từ đó có thể xây dựng những ràng buộc cũng như loại
bỏ đi những dư thừa dữ liệu trong một CSDL.
Phụ thuộc hàm là những mối quan hệ giữa các thuộc tính trong CSDL
quan hệ. Khái niệm về phụ thuộc hàm có một vai trò rất quan trọng trong việc
thiết kế mô hình dữ liệu. Một trạng thái phụ thuộc hàm chỉ ra rằng giá trị của
một thuộc tính được quyết định một cách duy nhất bởi giá trị của thuộc tính
khác.Sử dụng các phụ thuộc hàm để chuẩn hóa lược đồ quan hệ về dạng chuẩn
3 hoặc chuẩn Boye-Codd.
Định nghĩa 1.6 [6]
Cho lược đồ quan hệ R xác định trên tập thuộc tính Ư, và X, Y < = u .
Nói rằng, X xác định hàm Y hay Y phụ thuộc hàm vào X và kí hiệu X —» Y
nếu với mọi quan hệ r xác định ừên R và với hai bộ bất kỳ ti, t
2
ẼR mà ti(X) =
t
2
(X) thì ti(Y) = t
2
(Y).
1.3.1. Các tính chất của phụ thuộc hàm [6]
Cho lược đồ quan hệ R xác định trên tập thuộc tính и = {Al,
A

Tính chất 6) Nếu X -► Ythì XZ->Y.
Tính chất 7)Nếu X Y, z thì X -► YZ.
Tính chất 8)Nếu X YZ thì X -► Y.
Tính chất 9) Nếu X -> YZ, z -> wv thì X -> YZW.
1.3.2. Hệ tiên đề Amstrong và các phép suy dẫn[6]
Gọi R là quan hệ trên tập thuộc tính u. Khi đó với các tập thuộc tính
X, Y, Z£ u ta có hệ tiên đề Amsừong như sau:
1- Tính phản xạ: Nếu Y Q X thì X — > Y
2- Tính tăng trưởng: Neu X —> Y thì xw -> YW
3- Tính bắc cầu: Neu X -> Y, Y -> z thì X -> z Định lý
1.1
Hệ tiên đề Amsừong là đúng và đầy
đủ Chứng minh:
a) Tính đúng.
1) Với mọi ti, t
2
- r(R) và ti(X) = t
2
(X), cần chứng minh ti(Y) = t
2
(Y).
Thật vậy, từ giả thiếtti(X) = t
2
(X) mà Yç X suy ra ti(Y) = t
2
(Y).
Vậy từ tiCX) = t
2
(X) =» ti(Y) = t
2

t
(YW)= t
2
(YW).
Vậy từ ti(XW) = t
2
(XW) =» ti(YW)= t
2
(YW).
3)Với mọi ti, t
2
t r(R) và ti(X) = t
2
(X), càn chứng minh ti(Z) = t
2
(Z)
Phản chứng: Giả sử ti(Z) #
2
(Z).
Theo giả thiết X —> Y nên ti(X) = t
2
(X) => ti(Y) = t
2
(Y).
1
Mặt khác, cũng theo giả thiết có Y —» z nên ti(Y) = t
2
(Y) =>ti(Z)=
t
2

, bởi vì nếu V C x
+
thì w — * ■ V sẽ thỏa mãn trên r. Vậy phải có
ít nhất một thuộc tính A Q x
+
. Theo tính chất phản xạ nếu CI x
+
thì X —»w,
mà w —> V nên X —» V (theo tính chất bắc cầu). Do A ^X
+
nên X —>• A hay
A E x
+
. Điều đó là vô lý, bởi vì A Ể x
+
Kết luận với mọi phụ thuộc hàm F đều thỏa trên r.
T I Ế P T H E O T A C H Ứ N G T Ỏ R Ằ N G X —> Y K H Ô N G
T H Ỏ A M Ã N F R E N R Thật vậy, giả sử X —» Y ứiỏa trên r(R). Như
vậy X cX
+
và Yc x
+
, vì nếu không sẽ vi phạm sự bằng nhau trên các bộ ti, t
2

của X và Y. Nhưng nếu Yc x
+
ứiì X —> Y sẽ suy diễn được từ F (theo tính chất
phản xạ). Điều này mâu thuẫn với giả thiết X —> Y không suy diễn được từ F.
Như vậy X —> Y không thể thỏa mãn trên r.

F
+
để chỉ lấy bao đóng của X theo tập phụ thuộc hàm
F. Tính chất của bao đóng:
1) X çx
+
2) Nếu X ç Y thì X
+
ÇY
+
3) X -> x
+
4) x
++
= x
+
5) X
+
Y
+
ç (XY)
+
6) (X
+
Y)
+
= (XY
+
)= (XY)
+

8) Để chứng minh x
++
=x
+
ta đi chứng minh x
+
ç x
++
và ngược lại
9) x
++
ç x
+
10) Theo tính chất 1 ta có X
+
Ç X
++
. Ta cần chứng minh X
+
11) Lấy A G x
++
, chứng minh A G x
+
.
12) Do A e X^=>X
+
-► A(l).
13) Mặt khác theo tính chất 3 ta có: X —> x
+
(2).

+
ç (XY)
+
(3).
22) Từ (1), (2) và (3) suy ra X
+
YÇ (XY)
+
=>(X
+
Y)
+
Ç (XY)
++
=
(XY)
+
(theo tính chất 4).
23) Vậy ta có =>(X
+
Y)
+
Ç (XY)
+
(4).
24) Mặt khác ta cũng có: X Ç x
+
(tính chất 1) ^XYÇ X
+
Y Từ XYÇ

b) Giả sử CÓA <= x
+
ta càn chứng minh X—>Y.
31) Do Y Q x
+
=>x
+
— > Y(luật phản xạ).
32) Mặt khác: X—> X
+
(ứieo tính chất 3).
33) Suy ra: X—► Y(luật bắc cầu).
34)Chứng minh X-> Yvà Y—> X о X
+
= Y
+
ta có:
a) Giả sử có X—> Y và Y—> X ta cần chứng minh x
+
=Y
+
.
35) Do X-> Y =>Y£X
+
36) => Y
+
ç x
++
.
37) =* Y

+
nên ta có
42) Y
+
Q x
+
(Г)
x
+
ç Y
+

(2’)
43) Theo tính chất 1 ta có Y ç Y
+
mà Y
+
ç X
+
=>Y Ç x
+
^ X->Y
(theo tính chất 7).
1
1.4.2. Bài toán thành viên và thuật toán tìm bao đóng của tập thuộc tính
• Bài toán thành viên:
44) Nói rằng X —» Y là thành viên của F nếu X —> Y € F
4-
.
45) Một vấn đề quan trọng khi nghiên cứu lý thuyết cơ sở dữ liệu là khi

} với A i . - . An là các
thuộc tính và Y C x
+
. Từ định nghĩa x
+
ta có X —> Ai, áp dụng hệ tiên đề
Amstrong cho mỗi i suy ra X —» Y nhờ luật họp.
48) Ngược lại, giả sử ta có X — > Y, áp dụng hệ tiên đề Amstrong
cho mỗi i ta có X —» Ai, AiGY nhờ luật tách, suy ra Ai G x
+
. Từ đó, suy ra Y
£ x
+
.
49) Vậy X —► Y 6 F
+
.
50) Thuâttoán 1.1:
51) Xác định xem một phụ thuộc hàm X —»Y có tồn tại không?
52)Vào: u, F, X, Y c u.
53) Ra : Kiểm tra X -► Y 6 F
+
54) Phương pháp
55) Bước 1: Tìm bao đóng của tập thuộc tính X: X
F
+
56) Bước 2: Kiểm tra Y C x
+
nếu đúng thì X —> Y 6 F
+

71) Tính (AB)
+
F ?
72) Bước 0 : Xo = AB.
73) Bước 1: Xi = XO u {D} vì 3 A — > D thoả mãn điều kiện.
74) Bước 2: X2 = XI и {E} vì 3 AB —» DE thoả mãn điều kiện.
75) Bước 3: Хз = X2 и {H} vì 3 E —> H tìioả mãn điều kiện.
76) Bước 4 : X Ạ = X3.
77) Vậy AB
+
F = {ABDEH}
1.5. Khoá và các dạng chuẩn của ỉược đồ quan hệ Định nghĩa 1.9[6]
78) Cho lược đồ quan hệ R xác định trên tập thuộc tính и = {Ab A
2
, A
n
}, F
là
79) một tập phụ thuộc hàm xác định trên и, к Ç и, к được gọi là siêu khoá
của lược đồ quan hệ R nếu phụ thuộc hàm к —>u G F
4-
, nghĩa là tập thuộc tính
к là siêu khoá nếu K
+
= u.
2
80) Định nghĩa 1.10[6]
81) Cho lược đồ quan hệ R xác định trên tập thuộc tính и = {Al, A
2
A

M
- {Ai}) Nếu (Kj_i - {Ai})
+
= Ư với AịE
K
ÍA
.
91) IKì-1 nếu ngược lại.
92) Kết thúc khi Kị = Ki_i.
93) Nếu muốn tìm các khóa khác (nếu có) của lược đồ quan hệ, ta có thể
thay đổi thứ tự loại bỏ các phần tử của Ко.
1.6. Các phép suy dẫn trên mô hình quan hệ.
94) Định nghĩa 1.11[5] [6]
2
95) Cho tập phụ thuộc hàm F xác định trên tập thuộc tính u và f là một phụ
thuộc hàm ừên u. Ta nói phụ thuộc hàm f được suy dẫn theo quan hệ từ tập
phụ thuộc hàm F kí hiệu F I- f nếu mọi quan hệ r thỏa F thì cũng thỏa f.
96) Định nghĩa 1.12 [5][6]
97) Cho tập phụ thuộc hàm F xác định trên tập thuộc tính Ư và f là
một phụ thuộc hàm ừên u. Ta nói phụ thuộc hàm f được suy dẫn theo tiên đề
(hoặc suy dẫn logic) tò tập phụ thuộc hàm F kí hiệu F 1= f nếu f e F
+
. Nói cách
khác f được suy dẫn theo các tiên đề từ tập phụ thuộc hàm F nếu như áp dụng
hệ tiên đề Amstrong đối với các phụ thuộc hàm trong F thì sau hữu hạn làn ta
sẽ thu được f.
98) Để xem xét các phép suy dẫn trên mô hình quan hệ ta hãy xét các phụ
thuộc hàm sau đây:
1.6.1. Phụ thuộc kết nối (Join Dependencies)
99) Định nghĩa 1.13[1 ]

114) Hệ quả:
115) Cho PRS = (U, D, dom) là một lược đồ nguyên thủy
• Nếu X, Y c Ư, thì (X-> ->Y oXY*X (Ư-Y)
• Neu X, YcU vói Xiu x
2
= u thì
Xi*X
2
»XinX
2
116) ^ Xi P1X2 —^ ^ X2 Có thể coi mvd là một trường hợp mở
rộng của fd và là một trường họp đặc biệt của jd. Đáng tiếc là chưa tìm
thấy một hệ tiên đề xác đáng đầy đủ cho lớp jd như đối với mvd và fd.
Tuy nhiên một thuật toán quyết định cho bài toán suy diễn trong lớp ràng
buộc gồm các fd và jd, gọi là S Ă N Đ U Ổ Ỉ ( chase) được đưa ra bởi
Maier, Mendelzon và Sagiv năm 1975. Thuật toán liên quan đến một số
khái niệm sau đây.
2
1) NG_U
ONG
2) BIA 3) BIA 4) BAR
5) NG_
UONG
6) An 7) Tiger 8) Tiger 9) Ngôi
sao
10) An
11) An 12)Carlas
berg
13) Tiger 14) Phư
ơng

2
Ầ
, . . . J A G U }là tập hợp các ký hiệu được chỉ
số hóa bởi u và tập số nguyên dương gọi là các biến không được
phân biệt (undisitinguished variables) sao cho v
d
n v
n
=<D
• Một tablea T(Ư) là một quan hệ trên ư, ừong đó mỗi thuộc tính
AịeU, dom (Ai) = K}u V
n
119) Định nghĩa 1.15[1]
120) Cho lược đồ RS = (U, V,
dom, M, SC) j: Xi* x
2
* x
k
là jd trên
PRS, (uf
=1
, Xi = U)
*Bảng khỏi tạo đối với j là một table T(U) = {z
ls
J
K
) thỏa 2 điều kiện sau :
(1)Vi=l, ,k; VA
G
X

,
36)
2
37)
K
38) a
B
39) a
c
40) K
41)
3
42)
K
43) bi 44) ac 45) a
D

Trích đoạn Đại số quan hệ trên khối [5] Phép kết nố

---