Bộ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC sư PHẠM
HÀ NỘI 2
NGUYỄN VĂN HÂN
MỘT SÓ TÍNH CHẤT MỞ RỘNG CỦA KHÓA
TRONG MÔ HÌNH DỮ LIÊU DANG KHỐI
• •
LUẬN VĂN THẠC SĨ MÁY TÍNH
Bộ GIÁO DỤC VÀ ĐÀO TẠO • • • TRƯỜNG ĐẠI HỌC sư PHẠM
HÀ NỘI 2
•
HÀ NỘI, 2014
•
• 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
• Luận văn tốt nghiệp cao học được hoàn thành tại Đại học Sư phạm
Hà Nội 2. Có được luận văn tốt nghiệp này, tác giả xin bày tỏ lòng biết ơn sâu sắc
tới trường Đại học Sư phạm Hà Nội 2, Phòng Sau đại học, đặc biệt là PGS.TS
Trịnh Đình Thắng đã trực tiếp hướng dẫn, dìu dắt, giúp đỡ tác giả với những chỉ
dẫn khoa học quý giá trong suốt quá trình triển khai, nghiên cứu và hoàn thành đề
tài “Những tính chất mở rộng của khóa trong mô hình dữ liệu dạng khối”.
• Xin chân thành cám ơn các Thầy Cô giáo - Các nhà khoa học đã
trực tiếp giảng dạy truyền đạt những kiến thức chuyên ngành khoa học máy tính
cho bản thân tác giả trong những năm qua.
• Tác giả rất mong nhận được sự đóng góp, phê bình của quý thầy
Cô, các nhà khoa học, đọc giả và các bạn đồng nghiệp.
• Xin chân trọng cảm ơn!
• Hà Nội, ngày 10 tháng 12 năm 2014
• Học viên
• Nguyễn Văn Hân
• LỜI CAM ĐOAN

• e • Thuộc.
• 3 • Tồn tại.
• È
• Không tồn
tại.
• Ể
• Không
thuộc.
• V • Với mọi.
• 0 • Rỗng.
• n • Phép giao.
• u • Phép hợp.
• i
• Không thuộc
tập con
•
• DANH MUC CÁC HÌNH VẼ
•
•
• I. MỞ ĐẦU
1. Lý do chọn đề tài
• Những năm gần đây, việc nghiên cứu tìm ra các mô hình mới đáp ứng
các ứng dụng phức tạp, các cơ sở dữ liệu có cấu trúc tuyến tính và phi tuyến tính được
các nhà nghiên cứu trong và ngoài nước quan tâm. Một trong những mô hình mới này
là mô hình dữ liệu dạng khối. Mô hình dữ liệu này có thể xem là một mở rộng của mô
hình dữ liệu quan hệ.
• Trong quản lý cơ sở dữ liệu(CSDL), khóa là yếu tố liên kết giữa các
(CSDL) với nhau. Nhờ có khóa mà hệ quản trị ( CSDL) có thể quản lý tốt được chất
lượng dữ liệu
• Để góp phần hoàn chỉnh thêm về mô hình dữ liệu dạng khối và việc sử

• Chương 3: Một số tính chất mở rộng của khóa trong mô hình dữ liệu dạng
khối.
• Sau cùng là Phụ lục và Tài liệu tham khảo
• CHƯƠNGI MÔ HÌNH CÁC DỮ LIỆU QUAN HỆ VÀ
MỘT SỐ TÍNH CHẤT VỀ KHÓA
1.1. Giới thiệu về mô hình dữ liệu quan hệ
• Mô hình dữ liệu quan hệ (Ralational Data Model) gọi tắt là mô hình
quan hệ, do EF.Codd đề xuất năm 1970. Nền tảng lý thuyết của nó là khái niệm lý
thuyết tập hợp trên các quan hệ, tức là tập của các bộ giá trị.
• Mô hình dữ liệu quan hệ là mô hình được nghiên cứu nhiều nhất, và
thực tiễn đã cho thấy rằng nó có cơ sở lý thuyết vững chắc nhất. Mô hình dữ liệu này
cùng Yới mô hình thực thể kết hợp đang được sử dụng rộng rãi trong việc phân tích
và thiết kế CSDL hiện nay. Các vấn đề của cơ sở dữ liệu được trình bày trong [4], [5],
[7]. [8]. [9].
7
• Sau đây là các khái niệm của mô hình dữ liệu quan hệ.
1.2. Thuộc tính và miền thuộc tính [4], [5]
• Định nghĩa 1.1
• Thuộc tính là các đặc điểm riêng của một đối tượng. Mỗi thuộc tính có
một tên gọi và phải thuộc về một kiểu dữ liệu nhất định.
• Kiểu dữ liêu
• Các thuộc tính được phân biệt qua tên gọi và phải thuộc một kiểu dữ
liệu nhất định (số, chuỗi, ngày tháng, logic, hình ảnh, ). Kiểu dữ liệu ở đây có thể là
kiểu vô hướng hoặc là kiểu có cấu trúc. Nếu thuộc tính có kiểu dữ liệu là vô hướng thì
nó được gọi là thuộc tính đơn hay thuộc tính nguyên tố, nếu thuộc tính có kiểu dữ liệu
có cấu trúc thì ta nói rằng nó không phải là thuộc tính nguyên tố Miền giá trị
• Thông thường mỗi thuộc tính chỉ chọn lấy giá trị trong một tập con của
kiểu dữ liệu và tập hợp con đó được gọi là miền giá trị của thuộc tính. Ký hiệu DOM
(tên thuộc tính).
• Ví dụ , tập các ký tự số có chiều dài chính xác là 7, là miền của thuộc

thuộc hai đối tượng khác nhau.
1.3. Quan hệ và lược đồ quan hệ [4], [7]
• Định nghĩa 1.2
• Cho u = {A
b
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 Ai (i = 1,2, n) có miền giá trị là Dom(Ai). Khi đó r là một tập các
bộ {h
b
h
2
, h
m
} được gọi là quan hệ trên R với hj (j=l, 2, m) là một hàm:
• hj = и —> u D
A
, sao cho hj(Ai) e D
Ai
(i=l, 2,
• Aị eU
• Ta có thể xem một quan hệ như một bảng mà trong đó mỗi hàng (phần
tử) là một bộ và mỗi cột tương ứng với một thuộc tính. Biểu diễn quan hệ r thảnh
bảng như sau:
•
• Nhân xét:
- Định nghĩa này là quan trọng, toàn bộ cơ sở dữ liệu dựa trên định nghĩa này,

(A
2
)
•
• h
m
(A
n)
• Bảng 1.1: Bảng ví dụ quan hệ r
9
• MẢT HÀNG
• Mã
hàng
• Tên
hàng
• Màu
săc
• Trọng
lượng
• Tỉnh
• P1 • Gạch
men
• Trăng • 120 • Hà
Nội
• P2 • Sơn • Xanh • 450
• Ninh
Bình
• P3 • Kính • Nâu • 800 • Bình
Định
• P4 • Bôn

3
,114}, ở đây đối YỚi bản ghi thứ
• nhất (dòng thứ nhất) chúng ta có
1
0
• hi(Mã hàng) = Pi
• hi(Tên hàng) = Gạch men
• hi(Màu sắc) = Trắng
• hi (Trọng lượng) =120
• hi(Tỉnh) = Hà Nội.
1.4. Khóa của lược đồ quan hệ. [5], [7]
• Định nghĩa 1.3
• Giả sử r = { h
b
h
2
, , h
m
} là một quan hệ, s = < R, F > là một sơ đồ quan
• hệ, trong đó R = {a
b
a
2
, , an} là tập các thuộc tính, F là tập tất cả các phụ
• thuộc hàm trên R. Gọi Y là một họ f trên R và A ç R. Khi ấy A là một khoá
• của r ( tương ứr» Ц một khoá của s, một khóa
của Y) nếu: f
• A—> R ( A -> R e F
+
, (A, R) eY). r

được.
• Dù rằng dễ thấy A có thể chính bằng R nhưng người ta vẫn phải đi tìm
khóa tối tiểu, tức là khóa nhỏ nhất mà không thể nhỏ hơn được nữa để việc so sánh
các giá trị khóa YỚi nhau trong quá trình tìm kiếm bản ghi là nhanh nhất.
• Một sơ đồ quan hệ có thể có nhiều khóa.
1.5. Phu thuôc hàm.
• •
• Khái niệm về phụ thuộc hàm trong một quan hệ là rất quan trọng trong
việc thiết kế mô hình dữ liệu. Năm 1970 E.F Codd đã đề cập phụ thuộc hàm trong mô
hình dữ liệu quan hệ, nhằm giải quyết việc phân rã không tổn thất thông tin. Định
nghĩa về khái niệm này được phát biểu như sau:
• Định nghĩa 1.4
• Cho R = { a
b
a
2
, , an } là tập các thuộc tính, r = { hi, h
2
, , h
m
} là một
quan hệ trên R, và А, в ç R ( А, в là tập cột hay tập thuộc tính ). Khi đó ta nói A xác
định hàm cho в hay в phụ thuộc hàm vào A trong r ( ký pháp А —» В ) nếu:
• ( V hi, hj e r) (( Va e А ) ( hi(a) = hj(a)) => ( Vb € в ) ( hi(b) = hj(b) ))
• г f
• Ta sẽ viết (А, B) hay А —> в thay cho А—>
в Đặt F
r
={(A, B):A,BçR,A^B}
• Lúc đó F

• 30 Láng
Hạ
• Hà
Nội
• 3
• SP2
A0003
• Đặng Nhật
Minh
• Mê Linh • Hà
Nội
• 3
• SP2
A0004
• Vũ Thúy
Minh
• 89 Văn
lãng
• Lạn
g Sơn
• 0
• SP2
A0005
• Trần Khắc
Minh
• 40 Trần
hưng đạo
• Hải
Dương
• 2

• Neu X -» Y và z -» w thì xz —» YW
7, Tính tích lũy
• Neu X -» Y và Y —» ZW thì X -» YZW
1.5.2. Hệ tiên đề Armstrong.
• Năm 1974, Armstrong đã chỉ ra được bốn đặc trưng cho một tập phụ
thuộc hàm của một file dữ liệu nào đó. Chúng được gọi là hệ tiên đề Armstrong.
• Định nghĩa 1.5
• Cho trước R = {a
b
a
2
, , an} là một tập hữu hạn không rỗng các thuộc
• tính.
• ta gọi P(R) X P(R) = {(A, B) : А, В e R }
• Khi đó : Y ç= P(R) X P(R) là họ f nếu
V A, B, c, D ç R có
1) . (A, A)eY
2) . (A, B) G Y, (В, С) G Y => (A, С) G Y
3) . (A, B)e Y,AçC,DçB=> (C, D)EY
4) . (A, B) e Y, (C, D) e Y => (A u с, в uD) e Y
• Hệ quả (Tính đầy đủ cuả hệ tiên đề Armstrong)
• Armstrong đã chỉ ra rằng, nếu Y là một họ f tuỳ ý thì tồn tại quan hệ
r sao cho F
r
= Y.
1
4
•(A, A) e F
r
• A

2
•
• Có ứiể ứiấy rằng Ĩ1 và r
2
khác nhau nhưng F
r
i = F
r2
.
• Như vậy là tương quan giữa các lớp quan hệ với các lớp họ phụ
thuộc hàm được thể hiện bằng hình vẽ sau:
•
• Lớp các quan hệ
các phụthuộchàm
1.6. Hàm đóng.
• Định nghĩa 1.6
• -
>

С
•
1
5
• Một hàm L : P(R) —» P(R), ( P(R) là tập các tập con của R ) được
gọi là hàm đóng trên R nếu với mọi A,B € P(R):
- AçL(A)
- Nếu A ç В thì L(A) ç L(B)
- L (L(A)) = L (A).
• Định lý 1.1
•Neu F là một họ f và chúng ta đặt Lp(A) = { a: a eR: (A,{a}) eF}

2
, a
3
, a
4
} г {aj
-» {a
3
, a
4
} cột 1 xác định hàm với cột 3 cột 4 F = J {a
2
} -» {a
3
}
cột 2 xác định hàm với cột 3
• {a
3
} —» {84}
cột 3 xác định hàm YỚi cột 4
1.8. Bao đóng
1.8.1. Bao đóng của các tập phụ thuộc hàm.
• Định nghĩa 1.8
•Giả sử F là tập các phụ thuộc hàm trên sơ đồ quan hệ s — < R,F >. Gọi F
+
là
tập tất cả các phụ thuộc hàm có thể suy dẫn lôgic từ F bởi các luật của hệ tiên đề
Armstrong. Khi ấy F
+
được gọi là bao đóng của F.

+
5, (X
+
Y)
+
= (XY
+
)
+
= (X
+
Y
+
)
+
=(XY)
+
6, X —> Y oYcX
+
1
7
7, X —» Y « Y
+
c=X
+
8, X —> x
+
và x
+
—> X

+
. Thật vậy: X -» Y => tồn tại k sao cho
Y = A
k
c u Ai= x
+
Y c x
+
=> x
+
= Y u (X
+
- Y) => X -> Y u (X
+
- Y) => X —
> Y
• Từ đó, ta có thuật toán sau:
• Thuật toán 2.1: Xác định xem một phụ thuộc hàm X —> Y có tồn tại hay
không?
• Đầu vào: U,F,X,YcU Đầu ra: Kết
luận sự tồn tại của X —» Y Phương pháp
• Bước 1: Tìm bao đóng của tập thuộc tính X: X
+
F
Bước 2: Kiểm tra YcX
+
nếu đúng thì X —» Y e F
+
.
• Ngược lại, X —» Y Ể F

Thật vậy, theo thuật toán tìm bao đóng ta có fj = Xj -» Yj để Xị.1 =2 Xj và Xi = Xi_i u
Yj X
M
-> Yj (2). Từ (1) và (2) => X —» Yj (3).
• Từ (1) và (3) => X-> Xj_,và Yj = Xi => X -> Xi. Vậy Xi e x
+
• Ta chứng minh A çz x
+
=> A ÇZ Xj để kết luận Xi 2 x
+
• A Ç x
+
nên có một phụ thuộc hàm X —> A. Theo thuật toán tìm bao
đóng thì X Ç Xi => A çXi. Nên ta có điều phải chứng minh.
• Ví dụ: Cho tập thuộc tính и = {А, в, с, D, Е, G, H} và tập phụ thuộc
hàmF = {A -» D, AB -» DE, CE ^ G, E -> H}
• Tính (AB)
+
F
• Bước 0 : x
0
= AB
• Bước 1 : X! = Xo u {D} vì có A —» D thỏa mãn điều kiện
1
9
• Bước 2: x
2
= Xi u {E} YÌ có AB —» DE thỏa mãn điều kiện
• Bước 3: x
3

khoá cũng khác nhau. Nếu loại bỏ một phần thông tin về khóa thì thông tin của các
thuộc tính còn lại không thể xác định được. Như vậy khoá là tập các thuộc tính sao
2
0
cho bao đóng của nó là nhỏ nhất. Nghĩa là nếu thêm hoặc loại bỏ các phần tử của
khoá sẽ là dư thừa hay thiếu thông tin.
1.9.1. Các tính chất của khóa trong lược đồ quan hệ [8]. [9].
• Các tính chất đơn
giản Cho LĐQH (U,F). Khi
đó
1. К çU là một khoá khi và chỉ khi и phụ thuộc đầy đủ vào K.
2. Hai khoá khác nhau của một LĐQH không bao nhau.
3. Mọi LĐQH đều có ít nhất một khoá.
• Đ ị n h 1 ý 1.3
• ( Đặc trưng của các thuộc tính khóa )
• Cho К là một khóa của LĐQH а = (U,F). Khi đó với mọi tập con X của к ta có:
• x
+
nK = X.
• Chứng minh
• Vì X cX
+
vàXçK nên XcX
+
nK. Ta cần chứng minh X
+
n к Œ X. Giả sử А
e X
+
nK và A gX. Ta xét tập M = K\A. Dễ thấy XçM. Ta có, theo tính chất đồng

khóa. Giả sử A là một thuộc tính có trong vế phải của PTH L—>AR' nào đó của F. Ta
chứng minh A sẽ không xuất hiện trong một khóa K nào đấy của a. Thật vậy, xét tập
X = Ư\A. Dễ thấy X 3L và X
+
= XAR' = ư và do đó X là siêu khóa. Từ siêu khóa X
không chứa A ta lấy ra được một khóa K không chứa A.
1.9.2. Thuật toán tìm khóa của một quan hệ, giao của các khóa.
• Input: r = {h
l5
h
2
, , h
m
} là một quan hệ trên tập các thuộc tính R (R = {ai,
• &2V» Sn})
• Output: K là một khoá tối tiểu của
r Phương pháp:
• Bước 1: Từ r = {h
l5
h
2
, , h
m
}, tính E
r
= {Eỹ : 1< i < j < m } là hệ bằng
nhau Bước 2: Từ E
r
tính M
r

r
- Thuật toán này nếu thay đổi thứ tự các thuộc tính của R ta có thể tìm thấy
một khoá khác.
• Ví dụ: Xét quan hệ chuyen hang trong bảng sau: shh: Số hiệu
2
2
của hãng cung cấp shmh: số hiệu của mặt hàng được cung cấp
sluong: Số lượng hàng cung cấp trong chuyển hàng E34 = { shh }
• Bước 2: TínhM
r
= {{ shh, sluong },{ ngay, shmh }}
• Bước 3: Ko = R = { ngay, shh, shmh, sluong }
• Ki = Ko \ { ngay } = { shh, shmh,
sluong } vậy Ki = { shh, shmh, sluong }
• K
2
= Ki \ { shh } = { shmh, sluong }
• K
3
= K
2
\ { shmh } = { shh, sluong } e M
r

K4 = K
3
\ { sluong } = { shh, shmh }
• Vậy khoá tối tiểu của quan hệ chuyen hang: K={shmh, sluong }
* Thuật toán xác định giao các khóa trong LĐQH
Algorithm Keylntersec Format: KeyIntersec(U,F)

+
= K
+
= Ư.
1.10. Dạng chuẩn của các hệ khóa [5]. [9].
• Định nghĩa 1.11 ( Định nghĩa về Sperner).
• Giả sử r là một quan hệ, s = <R,F> là một sơ đồ quan hệ, Y là một họ f
trên R, và AçR. Khi đó A là một khóa của r (tương ứng là một khóa của s,
• một khóa của Y) nếu A—>R (A-»ReF
+
’ (A,R)eY). Chúng ta gọi A là một
• r
• khóa của r (tương ứng của s, của Y) nếu.
- A là một khóa của r (s, Y),
- Bất kỳ một tập con thực sự của A không là khóa của r (s, Y).
- Chúng ta ký pháp K
r
(Ks, Ky) tương ứng là tập tất cả các khóa của r
• (S,Y).
- Chúng ta gọi K (ở đây K là một tập con của P(R)) là một hệ Spemer trên R nếu
với mọi A, B e K kéo theo AỂB.
- Có thể thấy K
r
,K
S
, Ky là các hệ Spemer trên R.
• Ví dụ: Ta có bảng quan hệ sau:
• BANHANG
• MH • TEN_HANG
• SO_LUONG

ứng) nếu với mỗi sơ đồ quan hệ S=<R,F> mà K
s
= K thì s là 2NF( 3NF, BCNF tương
ứng).
• Bây giờ chúng ta cho điều kiện cần và đủ để một hệ Spemer bất kỳ là
• 2NF.
• Cho K là một hệ Spemer trên R. Đặt Kp= [a&R\3A&K\a&A } và K
n
=R-
• Kp.Kp(K
n
) được gọi là tập các thuộc tính cơ bản (thứ cấp) của K.
• Cho trước sơ đồ quan hệ s = <R,F>, chúng ta nói rằng phụ thuộc hàm A
-^BeF là thừa nếu hoặc A=B hoặc có C-»DeF sao cho CcA và BcD.
• Định lý 1.6
• Cho К là hệ Spemer trên R. Khi đó к là 2NF nếu và chỉ nếu K
n
= Ф
Chứng minh:
• Theo định nghĩa của quan hệ 2NF, hệ Spemer và K
n
ta có thể thấy nếu K
n
= Ф
thì К là 2NF.
• Bây giờ ta giả thiết К là 2NF . Ký pháp K'
1
là tập các phản khóa của K.
Từ К, K'
1