TRƯỜNG ĐAI
HÀ NÔI
2
• HOC SƯPHAM
•
•

•

KHOA CÔNG NGHỆ THÔNG TIN

TA
• THI* NHƯ

BAO ĐÓNG VÀ CÁC THUẬT TOÁN
TÌM BAO ĐÓNG TRONG MÔ HÌNH
DỮ LIÊU
KHỐI
• DANG
•

KHÓA LUÂN
TỐT NGHIÊP ĐAI •HOC•
•
Chuyên ngành: Sư phạm Tỉn học

HÀ NỘI-NĂM 2016

«



HÀ NỘI - NĂM 2016


LỜI CẢM ƠN
Để hoàn thành khóa luận này em xin gửi lời biết ơn sâu sắc đến
PGS.TS Trịnh Đình Thắng, thày là người trực tiếp hướng dẫn, định hướng và
tận tình chỉ bảo em trong suốt quá trình học tập và nghiên cứu đề tài.
Em cũng xin gửi lời cảm ơn chân thành đến các thầy cô trong khoa
Công nghệ thông tin trường Đại học Sư phạm Hà Nội 2 đã tận tình dạy dỗ,
truyền đạt tri thức cho em trong suốt 4 năm em học tập tại trường. Đó là
những kiến thức sẽ giúp em trong cuộc sống và công việc sau này.
Em cũng xin bày tỏ sự biết ơn, cảm ơn đến gia đình, bạn bè đã luôn
đồng hành, giúp đỡ và tạo điều kiện cho em để em có thể hoàn thành khóa
luận này.
Trong quá trình thực hiện đề tài không thể tránh khỏi những thiếu sót.
Em mong nhận được sự góp ý của quý thầy cô và bạn bè.
Hà Nội, ngày 04 tháng 05 năm 2016
Sinh viên

Tạ Thị Như


LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung khóa luận 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. Trong khi
nghiên cứu có kế thừa thành quả của các nhà khoa học và các nhà nghiên cứu.
Các số liệu, kết quả nêu trong luận văn là trung thực, rõ ràng.
Neu tôi sai tôi xin chịu hoàn toàn trách nhiệm.
Hà Nội, ngày 04 tháng 05 năm 2016
Sinh viên

2.2.3. Phép trừ ....................................................................................... 18
2.2.4. Tích Đe - các................................................................................ 18
2.2.5. Tích Đề - các theo tập chỉ số....................................................... 18
2.2.6. Phép chiếu.................................................................................... 19
2.2.7. Phép chọn..................................................................................... 19


2.2.8. Phép kết nối..................................................................................20
2.2.9. Phép chia......................................................................................21
2.3. Phụ thuộc hàm.....................................................................................21
2.4. Bao đóng trong mô hình dữ liệu dạng khối......................................... 21
2.4.1. Bao đóng của tập phụ thuộc hàm..................................................21
2.4.2. Bao đóng của tập thuộc tính chỉ số.............................................. 22
CHƯƠNG 3: TÍNH CHẤT CỦA BAO ĐÓNG VÀ CÁC THUẬT TOÁN
TÌM BAO ĐÓNG TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI................. 26
3.1. Tính chất của bao đóng ừong mô hình dữ liệu dạng khối................... 26
3.2. Chương trình Demo tính bao đóng của tập thuộc tính chỉ số ừong mô
hình dữ liệu dạng khối................................................................................29
3.2.1. Giới thiệu bài toán........................................................................ 29
3.2.2. Các thuật toán tìm bao đóng........................................................ 29
3.2.3. Ngôn ngữ lập trình c # .................................................................. 31
3.2.4. Giao diện chương trình................................................................ 34
KẾT LUẬN................................................................................................... 37
TÀI LIỆU THAM KHẢO..............................................................................39


DANH MỤC CÁC KÝ HIỆU VÀ CHỮ CÁI VIẾT TẮT
Trong khóa luận này dùng thống nhất các ký hiệu và các chữ viết tắt sau:
Ký hiệu


3

Tồn tại

V

Với mọi

0

Rỗng

u

Hợp

n

Giao

3

Không tồn tại

c

Là con

3


lĩnh vực nghiên cứu đóng vai trò nền tảng trong sự phát triển của Công nghệ
thông tin. Từ lâu lĩnh vực này đã được đề xuất và nghiên cứu. Và để xây dựng
được một hệ thống cơ sở dữ liệu tốt thì phải có các mô hình dữ liệu thích hợp.
Hiện nay đã có rất nhiều các mô hình được sử dụng trong các hệ thống cơ sở
dữ liệu như: mô hình thực thể - liên kết, mô hình mạng, mô hình phân cấp,
mô hình quan hệ... Trong đó, mô hình quan hệ được quan tâm đặc biệt hơn do
nó được xây dựng trên cơ sở toán học chặt chẽ. Tuy nhiên mô hình này chưa
đủ đáp ứng 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. Vì vậy, người ta đã đề xuất và nghiên cứu ra mô hình dữ liệu dạng
khối, mô hình này được coi là một mở rộng của mô hình dữ liệu quan hệ.
Do bao đóng có vai trò rất quan ừọng trong cơ sở dữ liệu nên để phát
triển và hoàn thiện mô hình dữ liệu dạng khối tôi chọn đề tài là “Bao đóng và
các thuật toán tìm bao đóng trong mô hình dữ liệu dạng khối“ cho khóa
luận của mình.
2. Mục đích nghiền cứu
- Tìm hiểu về mô hình dữ liệu dạng khối, bao đóng và các thuật toán tìm
bao đóng trong mô hình dữ liệu dạng khối.
- Xây dựng chương trình demo tìm bao đóng của tập thuộc tính chỉ số.
3. Nhiệm vụ nghiên cứu
- Tìm hiểu về mô hình dữ liệu dạng khối.
- Xây dựng chương trình demo tìm bao đóng của tập thuộc tính chỉ số
trên lược đồ khối.
4. Đối tượng và phạm vỉ nghiền cứu
- Đối tượng: Bao đóng trong mô hình dữ liệu dạng khối.
1


- Phạm vi: Mô hình dữ liệu dạng khối.
5. Ý nghĩa khoa học và thực tiễn của đề tài
- Xây dựng demo mô phỏng thuật toán tìm bao đóng trong mô hình dữ


Dom(Diachi) = {‘HN\ ‘BN‘, ‘HP‘}; Dom(DT) = {char(15)};
1.1.2. Quan hệ và lược đồ quan hệ [3, 5]
Quan hệ:
Cho u = {Xi, x 2,..., x 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 X i (i = 1, 2,..., n) có miền giá tri

Dx

. Khi đó, r là một tập các

bộ {hi, h2,..., hm} được gọi là quan hệ trên R với hj (j = 1,2,..., m) là một hàm:
hj = и —»Dx , x ^ u \ h ^ x ,) GDXi (i = 1, 2,..., n)
Ta CÓthể xem một quan hệ như một bảng mà trong đó mỗi hàng là một bộ và
một cột tương ứng với một thuộc tính. Biểu diễn bảng quan hệ r như sau:
Xi

x2

...

xn

hi(Xi)

hi(X2)

...

hi(Xn)

Một bộ giá trị là các thông tin của một đối tượng thuộc quan hệ. Bộ giá
trị cũng thường được gọi là một mẫu tin hay bản ghi, dòng của văn bản.
Một bộ q là một vectơ gồm n thành phàn thuộc tập hợp con của tích Đề - Các
miền giá trị của các thuộc tính và thỏa mãn tân từ đã cho của quan hệ.
Vỉ dụ 1.3: Xét bảng KHACHHANG ta có:
KHACHHANG
Tên khách hàng

MãKH

Địa chỉ

Điện thoại

A001

Trần Thị Ngọc Ánh

HN

01234567892

A002

Đô Đức Dương

BN

0914568124


quan hệ gồm tất cả các bộ thuộc r hoặc thuộc s hoặc thuộc cả hai quan hệ. Ta
có:
r ^ J 5 = { í l í e r hoặc í e ỉ Ị
4


Ví dụ 1.4: Cho hai bảng
Khachhang 1

Khachhang2

MãKH

Địa chỉ

A001

HN

A002

BN

A003

HP

MãKH

Địa chỉ


VP

Bảng 1.3. Biểu diễn quan hệ Khachhangl ^ Khachhang2
1.2.2. Phép giao [3]
Cho hai quan hệ r và s khả họp. Giao của r và s kí hiệu là r n s là một
quan hệ gồm tất cả các bộ thuộc r và thuộc s. Ta có:
m s = \t\t e r v b ts s }
Ví dụ 1.5: Cho hai bảng:
Khachhangl

MãKH

Địa chỉ

A001

HN

A002

BN

A003

HP

5



Khachhangl n Khachhang2

Bảng 1.4. biểu diễn quan hệ Khachhangl n Khachhang2
1.2.3. Phép trừ [3]
Cho hai quan hệ r và s khả hợp. Hiệu của r và s kí hiệu là 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 = {í 11 E r và t Ể s}
Ví dụ 1.6: Cho hai bảng:
Khachhangl

Khachhang2

Mã ICH

Địa chỉ

AOOl

HN

A002

BN

АООЗ

HP

MãKH



Địa chỉ

A004

VP

Bảng 1.6 . biểu diễn quan hệ Khađứiang2 - Khachhangl
1.2.4. Tích Đề - các [3]
Cho hai quan hệ r và s bất kỳ có tập thuộc tính lần lượt là Ui và Ư2.
Tích Đề - các của r và s kí hiệu là r X s là một quan hệ ừên Ư1 n Ư2 gồm tất cả
các bộ ghép được từ các bộ của r và s. Ta có:
r X s — ị t — ị u , v ) /V m e r , V e s }

Ví dụ 1.7: Cho hai bảng
MaKH

MaSP

SoHD

A001

MTD

0111

A002

OC3

A001

MTD

0111

MTD

Máy tính DELL

A001

0C3

0111

0C3

0 cứng 3GB

A001

CKD

0111

CKD

Chuột không dây


Bảng .7. Biêu diên quan hệ r X s

7

TenSP


1.2.5. Phép chiếu [3]
Cho quan hệ r xác định trên tập thuộc tính ư và X c ư . Phép chiếu của
quan hệ r trên tập thuộc tính X, kí hiệu là

(/) là tập các bộ của r xác định

trên X, ta có:
I X f ( r ) = ' M ’l í e r }
Thực chất của phép chiếu 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 (trùng lặp).
Ví dụ 1.8: Cho bảng r gồm những thuộc tính sau:
A

B

c

D

a

1


2

I

5

D

Ta có: Y ln ir)

và ta có: r L (r)

B

D

1

2

2

4

8

5

6



01678325235

A004

Đoàn Tuyêt Trinh

VP

01287343527

Bảng 1.8. Bảng khách hàng
8

Điện thoại


cần lấy một số thuộc tính khách hàng mà chỉ quan tâm đến mã số, địa
chỉ, điện thoại thì phép chiếu sẽ được sử dụng như sau:
ĨỈM ã K H ,Đ ia c H Đ ie n tH o a f-k h a C h h a n 8 Ì = q u a n h ệ k ế t q u ả

1.2.6. Phép chọn [3]
Phép chọn là phép toán lọc lấy ra một tập con các bộ của quan hệ đã
cho thỏa mãn một điều kiện xác định. Điều kiện đó được gọi là điều kiện chọn
hay biểu thức chọn.
Biểu thức chọn F được định nghĩa là một tổ họp logic của toán hạng, mỗi toán
hạng là một phép so sánh đơn giản giữa hai biến là hai thuộc tính hoặc giữa
một biến là một thuộc tính và một giá trị hằng. Biểu thức chọn F cho giá trị
đứng hoặc sai đối với mỗi bộ đã cho của quan hệ khi kiểm tra riêng bộ đó.
- Các phép toán so sánh ừong biểu thức F: >, <, =, >,
01234567892

A002

Đô Đức Dương

BN

0914568124

A003

Nguyên Ngọc Khánh

HP

01678325235

A004

Đoàn Tuyêt Trinh

BN

01287343527

Chọn khách hàng có địa chỉ ở BN, ta là như sau: ỏ

Địa ch i= ‘BN‘ (Khachhang)


Địa chi = ‘BN‘ (Khachhang)


1.2.7. Phép k ấ nối [3]
Cho 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 giá ừị trên miền
thuộc tính chung M của hai bộ này giống nhau).
P(UV) = r * s - Ịh*vm g r,v G s ,u M - vM ]
Nếu M = u n v = ậ , r*s sẽ cho ta tích Đề - Các, ừong đó mỗi bộ của quan
hệ r sẽ được ghép với mọi bộ của quan hệ s.
1.2.8. Phép chia [2, 3]
Cho hai quan hệ r(U) và r(V) = {Al, A2,...,

An},

V c u . Phép chia của

quan hệ r cho quan hệ s ký hiệu là ĩ" ■=■s , là một quan hệ trên Ư - V gồm các
bộ t sao cho tồn tại bộ MẽSvà ghép t với u ta được bộ thuộc r:
r - rS = {t I Vw e s , ( t , u ) s r }
Ví dụ 1.10: Cho quan hệ sau và tìm khách hàng mua sản phẩm chuột không
dây và máy tính với số lượng lớn hơn 2 (một trong 2 sản phẩm không có sản
phẩm nào có số lượng là 0 ).
Khachhang

Tên khách hàng

Chuột không dây


3

2

Khachhangdapung Tên khách hàng
Nguyễn Thùy Dương

10


1.3. Phụ thuộc hàm [3, 5]
Khi xét đến mối quan hệ giữa dữ liệu trong cơ sở dữ liệu 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 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 cơ sở dữ liệu.
Phụ thuộc hàm là mối quan hệ giữa các thuộc tính trong cơ sở dữ liệu.
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 ừạ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.
Định nghĩa 1.1 [3]
Cho lược đồ quan hệ R xác định trên tập thuộc tính u. Cho X, Y là hai
tập con của Ư. 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 trên R và với 2 bộ ti, Í2 bất kỳ mà
ti(X)=t 2(X)thì ti(Y)=t 2(Y).
Ví dụ 1.11: Ta có quan hệ SINHVIEN như sau:
MaSV

Hoten

Tinh


Tuyên Quang

3

Bảng 1.10. Quan hệ SINHVIEN
Trong quan hệ SINHVIEN, dựa vào định nghĩa phụ thuộc hàm của quan hệ ta
có:
{Tinh} —» {Khuvuc}
{MaSV} —> {Hoten, Tinh, Khuvuc}
Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc (phụ thuộc dữ liệu) xảy
ra tự nhiên nhất giữa các tập thuộc tính.

11


1.3.1. Các tính chất của phụ thuộc hàm [3, 5]
Cho lược đồ quan hệ R xác định trên tập thuộc tính u = { Ai, A2,...,
An}, cho X, Y, z, w c 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:
- N ế u Y C X thì X—>Y.
- Nếu X—>Y thì XW—>YW.
- NẾU X—>Y, Y->Z thì x-> z.
- Nếu X->Y, Y Z^W thì x z ^ w (Tính tựa bắc cầu).
- Nếu X—»Y, Z->W thì XZ->YW (Tính cộng đầy đủ).
- Nếu X—»Y thì XZ—>Y.
- Nếu X->Y, X->Z thì X—>YZ.
- Nếu X—>YZ thì X->Y.
- Nếu X—>YZ, Z->W thì X->YZW.
1.3.2. Hệ tiên đề Armstrong [3, 5]

G thì F+ CI G+.

• Tính chất lũy đẳng: Với mọi tập phụ thuộc hàm F ta luôn có F++= F+.
Vỉ dụ 1.12: Cho F = {A—>B, C->X, BX->Z}. Khi đó AC -> z G F+ ?
- Vì A —>В =oAX -> в х .
- Từ АХ —» BX, kết hợp в х —» z, suy га АХ —» Z.
- Từ С -> X =>АС -> АХ.
- Áp dụng tính chất bắc càu, AC —» AX và AX —» z suy ra AC —>z £ F4^.
1.4.2. Bao đóng của tập thuộc tính [3, 5]
Định nghĩa 1.3 [3]
Cho lược đồ quan hệ R xác định trên tập thuộc tính и, X Ç U . Bao đóng
của tập thuộc tính X kí hiệu là x +: là tập tất cả các thuộc tính A mà X —>A
được suy diễn từ F. Ta có: x += {A I X —>A £ F+}.
Các tỉnh chất của bao đóng:
• Tính phản xạ: X czX+.
• Tính đơn điệu: Nếu X Y và Y->X

Các thuật toán tìm bao đóng:
Tính liên tiếp tập các thuộc tính Xo, Xi, X2,... theo phương pháp sau:


14


CHƯƠNG 2: MÔ HÌNH DỮ LIỆU DẠNG KHỐI
2.1. Khối, Lược đồ khối, Lát cắt [1, 2, 4]
2.1.1. Khối, Lược đồ khối
Định nghĩa 2.1 [4]
Gọi R = (id; Ai, Аг,.. An) là một bộ hữu hạn các phần tử, trong đó id
là tập chỉ số hữu hạn khác rỗng, Ai (i =
Ai

1, n )

là các thuộc tính. Mỗi thuộc tính

(i = 1,n) có miền giá trị tương ứng là dom(A). Một khối r trên tập R, kí

hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ
từ tập chỉ số id đến các miền giá trị của thuộc tính Ai (i =

1, n) .

Nói một cách

khác:
t Gг(л) <5>t = Ịí' : iá —» dom(Aị)j i = 1,n
Ta kí hiệu khối đó là r(R) hoặc r(id; Ai, Аг,..., An), hoặc kí hiệu đơn
giản là r. Khi đó khối r(R) được gọi là lược đồ khối R. Như vậy, trên cùng
một lược đồ khối R ta có thể xây dựng được nhiều khối khác nhau.

DH
300

-350-

A03

350

CD

DH

/

CD

250

A03

DH
/
ThS

350

Aûî
t,


« - 03/2016
-

02/2016

01/2016

Hình 2.1 : Biểu diễn khối nhân viên NV(R)
Khi đó ta có:

• Lương của Hhân viên ti ở tháng 1/2016 là: ti(l/2016, luong) = 300.
• Tên của cán bộ Ì2 vào tháng 2/2016 là: t2(2/2016, ten) = ‘Y‘.
• Trình độ của cán bộ Ì3 tháng 3/2016 là: t3(3/2016, triiứi_do) = ‘CD‘.
2.1.2. Lát c ầ [1,2,4]
Cho R = (id; Al, Ả 2 y.. An), r(R) là một khối trên R. Với mỗi X€ id ta ký
hiệu r(Rx) là một khối với Rx = ({x}; Ai, Аг,.. An) sao cho:
1»n

íx 6 ' & ) * 4 = ỉ í =í' } i = x

với 1 6 r(R),
và í = { t*

:Ш —> đ o m (A ị

)} >=ĩ^

ở đây tỵix) = t l (л) với ỉ = 1>и.
Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm X .
Vỉ dụ 2 .2 : Với khối NV(R), R = (id; Al, A2, Аз, A 4). Trong đó: id = {1/2016,


A03

z

400

CD

Ta có các mệnh đê sau:
Mệnh đề 2.1 [4]
Cho R = (id; Al, Аг,.. An). r(R) là một khối trên R. Với mỗi X G id thì
lát cắt r(Rx) là một quan hệ. Trong trường họp tập chỉ số id chỉ gồm 1 phần tử
thì r(R) trở thành một quan hệ.
Như vậy mỗi quan hệ r(Ai, A2,..., An) là một trường hợp đặc biệt của
khối, đó chính là khối r(R) với R = ({x}; Ai, Аг,..., An).
Mệnh đề 2.2 [4]
Cho R = (id; Al, Ả 2 ,.. An), r(R) là một khối ừên R. Khi đó tồn tại một
họ quan hệ duy nhất biểu diễn họ {r(Rx)}xeid các lát cắt của r(R). Ngược lại
không đúng, nghĩa là với một họ quan hệ cho trước biểu diễn họ các lát cắt
của một khối nào đó thì khối tìm được không duy nhất.
2.2. Các phép toán Đại số quan hệ trên khối [2,4]
Cho г là một khối trên R = (id;

A l,

Аг,..

An).