B ộ• GIÁO DỤC VÀ ĐÀO
TẠO
•
•
TRƯỜNG ĐẠI
HỌC
s ư PHẠM
HÀ NỘI
2
•
•
•
•
===£0EQcs===

CHU QUANG ĐỨC

GIÀN GIAO CỦA CÁC TẬP ĐÓNG
TRONG MÔ HÌNH D ữ LIÊU DẠNG KHỐI

LUẬN VĂN THẠC SĨ MÁY TÍNH

HÀ NỘI, 2015


B ộ• GIÁO DỤC VÀ ĐÀO
TẠO
•
•
TRƯỜNG ĐẠI
HỌC

tập, nghiên cứu và giúp đỡ tôi rất nhiều trong quá trình làm luận văn thạc sĩ
này. Đặc biệt tôi xin cảm ơn thầy TS. Trịnh Đình Vinh đã tận tình hướng
dẫn, chỉ bảo cho tôi trong suốt quá trì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.
Hà nội, ngày 01 tháng 12 năm 2015
Hoc viên

Chu Quang Đứ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 thầy TS. Trịnh Đình Vinh.
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.

Hoc viên

Chu Quang Đức


MỤC LỤC

LỜI CẢM ƠN
LỜI CAM ĐOAN
DANH MỤC CÁC BẢNG
DANH MỤC CÁC HÌNH VẼ
DANH MỤC CHỮ VIẾT TẮT VÀ KÍ HIỆU
MỞ ĐẦU........................................................................................................... 1

Kết luận...................................................................................................... 47
CHƯƠNG 3: GIÀN GIAO CỦA CÁC TẬP ĐÓNG TRONG MÔ HÌNH DỮ
LIỆU DẠNG KHỐI....................................................................................... 49
3.1. Ánh xạ đóng và giàn giao của các tập đóng trong mô hình dữ liệu
dạng khối.............................................................................................56
3.1.1 Ảnh xạ đóng và lược đồ khối.................................................... 58
3.2. Tập sinh của ánh xạ đóng qua phép dịch chuyển của lược đồ khối.. .60
3.3. Mối quan hệ của tập sinh trên lược đồ khối và trên lược đồ lát cắt.. .62
Kết luận...........................................................................................................57
KẾT LUẬN.................................................................................................... 58
TÀI LIỆU THAM KHẢO.............................................................................. 59


DANH MỤC CẤC BẲNG

Bảng 1.1. Biểu diễn quan hệ r........................................................................... 5
Bảng 1.2. Biểu diễn ví dụ Nhân Viên................................................................6
Bảng 1.3. Biểu diễn quan hệ Sinh Viên.............................................................7
Bảng 1.4. Biểu diễn quan hệ r, í , r U ỉ ............................................................. 8
Bảng 1.5. Bảng biểu diễn quan hệ r, ỉ , r n j ...................................................8
Bảng 1.6. Biểu diễn các quanhệ r, s, r \s , s \ r ................................................ 9
Bảng 1.7. Biểu diễn quan hệ r , ^B>D (r ) ...........................................................
Bảng 2.1. Biểu diễn lát cắt r(RHọckỳ/).............................................................. 32
Bảng 2.2. Biểu diễn họ gồm 2 quan hệ Tị , r2..................................................33


DANH MỤC CẤC HÌNH VẼ

Hình 2.1. Biểu diễn khối điểm học viên DiemHV (R) ....................................31
Hình 2.2. Biểu diễn các khối r(R), s(R).........................................................34


n

Phép giàn giao

u

Phép hợp

\

Phép trừ

c

Tập con

3

Năm trong

G

Thuộc

Ể

Không thuộc
Anpha


E.Codd đề xuất năm 1970. Tuy nhiên do các quan hệ có cấu trúc phẳng
(tuyến tính) nên mô hình này chưa đủ đáp ứng đối vói các ứng dụng phức tạp,
các cơ sở dữ liệu có cấu trúc phi tuyến tính,...
Trong những năm gần đây, việc nghiên cứu nhằm mở rộng môhình dữ
liệu quan hệ đã được nhiều nhà khoa học quan tâm. Theo hướng nghiên cứu
này một mô hình dữ liệu mới đã được đề xuất đó là mô hình dữ liệu dạng
khối. Mô hình dữ liệu này được xem là một mở rộng của mô hình dữ liệu
quan hệ.
Để góp phần hoàn thiện về lý thuyết thiết kế của mô hình dữ liệu dạng
khối em đã chọn đề tài “Giàn giao của các tập đóng trong mô hình dữ liệu
dạng khối”. Trong đề tài này một số tính chất của giàn giao của các tập đóng
trong mô hình dữ liệu dạng khối đã được phát biểu và chứng minh.
2. Mục đích nghiên cứu
- Tìm hiểu về mô hình dữ liệu dạng khối.
- Tìm hiểu về giàn giao của các tập đóng, các tính chất của giàngiao
của các tập đóng trong mô hình dữ liệu dạng khối.


2

- Phát biểu và chứng minh một số tính chất mở rộng của giàn giao của
các tập đóng trong mô hình dữ liệu dạng khối.
3. Nhiệm vụ nghiên cứu
- Tìm hiểu về mô hình dữ liệu quan hệ và giàn giao trong mô hình dữ
liệu quan hệ và giàn giao của các tập đóng trong mô hình dữ liệu dạng khối,
các tính chất của nó.
- Tìm hiểu về mô hình dữ liệu dạng khối.
- Phát biểu và chứng minh một số tính chất mở rộng của giàn giao của
các tập đóng trong mô hình dữ liệu dạng khối.
4. Đổi tượng và phạm vỉ nghiên cứu

dữ liệu dạng khối, phát biểu và chứng minh các tính chất của nó bằng khẳng
định tính đúng và mối quan hệ giữa giàn giao trên khối và trên lược đồ lát cắt
nhằm bổ xung góp phần hoàn thiện về mặt lý thuyết cho mô hình dữ liệu dạng
khối.


4

CHƯƠNG 1: MÔ HÌNH DỮ LIỆU QUAN HỆ VÀ GIÀN GIAO CỦA CÁC TẬP
ĐÓNG
- Mô hình dữ liệu quan hệ là một trong những mô hình được quan tâm nhiều
nhất hiện nay. Nhiều tác giả đã quan tâm nghiên cứu và đã thu được các kết
quả tốt. Một trong các kết quả này là giàn giao và các tính chất của nó.
- Mô hình dữ liệu quan hệ và giàn giao của nó sẽ được trình bày trong
phần dưới đây.
- Để hiểu rõ hơn về mô hình dữ liệu quan hệ và giàn giao các vấn đề
này được trình bày ở chương 1 đã được nói tới trong tài liệu [5], [9] ,[13].
1.1. Mô hình dữ liệu quan hệ
1.1.1. Tổng quan về mô hình dữ liệu quan hệ
Khái niệm toán học làm nền tảng cho mô hình dữ liệu quan hệ là các
quan hệ theo lý thuyết tập họp. Đó là tập con của tích Đề Các của một danh
sách các miền, mỗi miền đơn giản là một tập các giá trị. Ta có thể xem một
quan hệ như một bảng, trong đó mồi hàng là một bộ và mỗi cột là một thuộc
tính.
Ta có thể biểu diễn một sơ đồ thực thể - liên hệ trong mô hình quan hệ.
Khi đó các dữ liệu của sơ đồ thực thể - liên hệ được biểu diễn bởi hai loại
quan hệ:
- Một tập thực thể E có thể được biểu diễn bởi một quan hệ mà lược đồ
quan hệ của nó chứa tất cả các thuộc tính của tập thực thể đó. Mồi bộ của
quan hệ biểu diễn một thực thể trong thể hiện của E.


ra) là một hàm:

hj : u —

,Aị&U sao cho hj(Aị) G

.

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:
A

A2

h
^2

Ki

...
...

/*2(A)

h (A2)

...



COI

А

2 6 /0 3 /9 0

HN

P5

C02

В

19/05/91

SL

P5

C03

В

20/11/92

VP

P6

7

Sinh viên:
MaSV

HOTEN

NS

DC

PLV

COI

A

2 6 /0 3 /9 0

HN

P5

C02

B

19/05/91

SL

A

B

c

A

B

c

ax

h

Cl

ữị

h

^1

a2 b2

c2

a2 h



«2

b2

cl

a2

b2

c2

Bảng 1.4. Biểu diễn quan hệ r, s, r u s.
* Phép giao
-

Cho hai quan hệ r và s khả họp. Giàn giao của r và s ký hiệu:

r n s , là một quan hệ gồm tập tất cả các bộ thuôc r thuộc 5. Ta có:
r n s = {í|íer vàíes}.

Ví du 1.5

в

С

А


с

ữị

h

C1

А

rrii:

Bảng 1.5. Bảng biểu diễn quan hệ r , s , r r \ s.
* Phép trừ
-

Cho hai quan hệ r và 5 khả hợp, Hiệu của r và 5 kí hiệu: r \ s là tập

tất cả các bộ thuộc r nhưng không thuộc 5. Ta có: r - s = {t 11 e r và t Ể 5 }


9

Ví dụ 1.6
A

В

с


А

В

С

А

В

с

a2 b2

c2

a2

h

c2

a2 b2

C1

s \r :

Bảng 1.6. Biểu diễn các quan hệ r, s , r \ s , s \ r.
* Tích Đề các

V—I hoặc so sánh >,<,=, >,}*,
c

D
4

X

5

Bảng 1.7. Biểu diễn quan hệ r , ^B>D (r ) •
Minh họa quan hệ r và phép chọn của r theo tiêu chuẩn B > D
* Phép kết nối tự nhiên
Cho hai quan hệ R(ỊJ) và S(V). Đặt M - U nV . Phép kết nối (tự
nhiên) hai quan hệ R(U) và iS(V), kí hiệu R * s , cho ta quan hệ chứ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ệ

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 \u g R , v g S , uM -

vM ) .

s

(sao cho


11

Nếu M = u n V = 0 , R * s sẽ cho ta tích Descartes, trong đó mỗi bộ
của quan hệ R sẽ được ghép với mọi bộ của quan hệ s .


mà ^(X ) = í2(X)ứủ tx{Y) = t2(Ỵ).
* Các tính chất của phụ thuộc hàm
Cho lược đồ quan hệ R xác định trên tập thuộc tính и - {A ^A ị,...,^},
cho X , Y , z , w œ U thì ta có một số tính chất cơ bản của các phụ thuộc hàm
như sau:

1. Nếu Y œ X thì X ^ Y .
2. Nếu X

thì X W ^ Y W .

3. Neu X —»y,y

thì x - > z .

4. Nếu X ^ Y ,YZ -> w thì x z -> w.
5. Nếu X -> y ,Z -> w thì XZ->ỈW.
6. Nếu X

thì x z ->y.

7. Nếu X ->y, X - > z thì X ->ỵz.
8. Nếu

thì X -> y .

9. Nếu X —>YZ, z -> w y thì X ->KZW.
1.4. Bao đóng
Định nghĩa 1.7

While tepmoi ^ tepcu do
Begin
Tepcu:= tepmoi;
For each

w —»z in

F do

If tepmoi 3 w then tepmoi:= Tepmoi u Z
End;
Retum(tepmoi);
End.
Vi du: 1.8.
Cho tập thuộc tính u - {A, B, c , D, E ,G ,H } và tập phụ thuộc hàm
F = { A —>D, A B —>DE, CE —>GE, E —>H}

Tính (ABj)?
Bước 0: x 0 = AB.
Bước l :Xị = X

q

u {D} vì 3 A —» D thoả mãn điều kiện.

Bước 2 :X 2 = X ị^ j {E} vì 3 AB —>DE thoả mãn điều kiện.
Bước 3: x 3 = x 2 u {H} vì 3E —» H thoả mãn điều kiện.


14


Format: Key (U,F)
Input:
- Tập thuộc tính

u

- Tập PTH F
Output: - Khóa K c ư thỏa:
(i). K +=U
(it). V A e K : ( K \ A ) + * u
Method
K:=U\
For each attribute A in u do
If A in Closure (X \A ,F)then
K :-K \A
endif;
return K;
end Key.
Môt số tính chất của khóa.
Các tính chất đơn giản
Cho lược đồ quan hệ (ơ ,F )khi đó:
1. K C u là một khóa khi và chỉ khi u phụ thuộc đầy đủ vào K .
2. Hai khóa 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 khóa.
Ví dụ: 1.9.
Cho lược đồ quan hệ R - (A,B, C,D) và tập phụ thuộc hàm F - {A —»
C,AB —» DC},khoá là {A,B} Khi đó thuộc tính A,B gọi là thuộc tính khoá,
còn thuộc tính D, c gọi là thuộc tính không khóa.


Hoán vị vai trò của các tập X và Y ta tìm được f(Xf(Y)) =f(XY).
(C5) Từ XY 3 X, XY 3 Y và tính đồng biến củ f ta suy ra f(XY) 3 f(X) và
f(XY) 3 f(Y). Lấy hợp theo từng vế của hai bao hàm thức trên ta thu
được f(XY) ^f(X)f(Y).