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 SƠN

Nghiªn cøu BAO §ã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, 2014 LỜI CẢM ƠN
Để hoàn thành luận văn này em xin chân thành gửi lời cảm ơn đến quý
thầy cô trong trường Đại học Sư phạm Hà Nội 2, các thầy trong Viện Công
nghệ thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các
anh chị thư viện Viện Công nghệ thông tin thuộc Viện Hàn lâm Khoa học và
Công nghệ Việt Nam, thư viện trường Đại học Công nghệ thông tin và truyền
thông – Đại học Thái Nguyên, trung tâm học liệu Đại học Thái Nguyên, thư
viện Đại học Công nghệ – Đại học Quốc gia Hà Nội đã quan tâm giúp đỡ
trong quá trình thực hiện đề tài. Nhờ đó tôi đã tiếp thu được nhiều ý kiến đóng
góp và nhận xét quý báu của quý thầy, cô thông qua các buổi trao đổi thông
tin và bảo vệ đề cương.
Em xin gửi lời cảm ơn sâu sắc nhất đến TS. Trịnh Đình Vinh đang công
tác tại trường Đại học Sư Phạm Hà Nội II đã trực tiếp hướng dẫn, định hướng
chuyên môn, quan tâm giúp đỡ tận tâm chỉ bảo trong quá trình thực hiện luận
văn.
Em xin bày tỏ sự biết ơn sâu sắc đến gia đình đã tạo mọi điều kiện tốt
nhất để em có thể hoàn thành tốt mọi công việc trong quá trình thực hiện luận
văn. Bên cạnh đó, em cũng xin gửi lời cảm ơn của mình tới bạn bè và đồng
nghiệp, luôn quan tâm, chia sẻ, động viên em trong suốt thời gian thực hiện
luận văn.
Mặc dù đã rất cố gắng trong quá trình thực hiện nhưng luận văn không MỤC LỤC

LỜI CAM ĐOAN ……………………………….………………………
LỜI CẢM ƠN … ………………………………………… …………….
MỤC LỤC ………………………………………………………………
BẢNG KÍ HIỆU CÁC CHỮ CÁI VIẾT TẮT……………………….……
DANH MỤC CÁC BẢNG ……………………………………………
DANH MỤC CÁC HÌNH…………………… … ……………………
MỞ ĐẦU ………………………………………….…………………… 1
KẾT QUẢ ĐẠT ĐƯỢC………………………………………………… 3
CHƯƠNG I : MÔ HÌNH DỮ LIỆU QUAN HỆ………………………… 5
1.1 Các khái niệm cơ bản………………………………….…… …5
1.2. Các phép toán đại số trên lược đồ quan hệ …………………….7
1.2.1. Phép hợp… …… ………………………………… 7
1.2.2. Phép giao……… ……………………….………… 8
1.2.3. Phép trừ… ……………………………………………8
1.2.4. Tích Đề - các ……………………………………… 9
1.2.5. Phép Chiếu.………………………………………… 10
1.2.6. Phép Chọn… ……………………………………… 11
1.2.7. Phép kết nối ….…………………………………… 12
1.2.8. Phép chia… ……………………………………… 14
1.3. Phụ thuộc hàm……………………………………………… 14
1.4. Hệ tiên đề Armstrong………………………………………….15
Trang
2.6.1. Định nghĩa………………………………………… 40
2.6.2. Thuật toán dịch chuyển………………………… 42
2.6.3. Biểu diễn dịch chuyển trong lược đồ khối …………43
Kết luận chương II.……………………………… ………………45
CHƯƠNG III: TÍNH CHẤT MỞ RỘNG CỦA BAO ĐÓNG…… ……46
3.1. Tính chất của bao đóng trong mô hình dữ liệu dạng khối… 46
3.2. Tính chất mở rộng của bao đóng trong mô hình dữ………….49
3.3. Phần mềm Demo tính bao đóng cảu tập thuộc tính chỉ số.… 52
3.3.1. Giới thiệu bài toán………………………………… 52
3.3.2. Thuật toán sử dụng trong chương trình…………… 52
3.3.3. Giao diện chương trình……….…………………… 54
Kết luận chương III……………………………………………….57
KẾT LUẬN…………………………………………………………… 58
TÀI LIỆU THAM KHẢO……………………………………………….59
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT

Trong luận á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 ý nghĩa
CSDL Cơ sở dữ liệu.
LĐQH Lược đồ quan hệ.
PTH Phụ thuộc hàm.
A, B, C Thuộc tính.
X, Y, Z Tập thuộc tính.


 Phép giao.
 Phép hợp.
 Không thuộc tập con

DANH MỤC CÁC BẢNG
Bảng 1.1. Bảng ví dụ về quan hệ r………………………………………….6
Bảng 1.2. Bảng quan hệ Sinhvien………………………………………… 6
Bảng 1.3. Bảng biểu diễn quan hệ Sinhvien1  Sinhvien2.…………….….7
Bảng 1.4. Bảng biểu diễn quan hệ Sinhvien1  Sinhvien2.……………… 8
Bảng 1.5. Bảng biểu diễn quan hệ Sinhvien1 – Sinhvien2.…………… …9
Bảng 1.6. Bảng biểu diễn quan hệ Sinhvien2 – Sinhvien1….…………… 9


MỞ ĐẦU

1. Lý do chọn đề tài:
Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được tập trung
nghiên cứu và phát triển của công nghệ thông tin, nhằm giải quyết các bài
toán quản lý, tìm kiếm thông tin trong những hệ thống lớn, đa dạng, phức tạp
cho nhiều người sử dụng trên máy tính. Từ những năm 70 của thế kỉ trước,
mô hình dữ liệu quan hệ do Edgar Frank Codd (Nhà khoa học máy tính người
Anh) đưa ra với cấu trúc hoàn chỉnh đã tạo nên cơ sở nền tảng cho các vấn đề
nghiên cứu lý thuyết về CSDL.
Để có thể xây dựng được một hệ thống cơ sở dữ liệu tốt, người ta
thường sử dụng các mô hình dữ liệu thích hợp. Ngoài những mô hình được sử
dụng trong hệ thống cơ sở dữ liệu đã có từ lâu và được rộng rãi trên Thế giới
như: mô hình thực thể - liên kết, mô hình mạng, mô hình dữ liệu, mô hình
phân cấp, mô hình quan hệ …
Trong 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ệ.
Để góp phần hoàn chỉnh thêm về mô hình dữ liệu dạng khối tôi chọn đề
tài là “Nghiên cứu bao đóng trong mô hình dữ liệu dạng khối”cho luận văn
của mình.
Bao đóng có vai trò rất quan trọng trong cơ sở dữ liệu. Với mục tiêu
tìm hiểu về bao đóng trong mô hình dữ liệu dạng khối cũng như các khái

2
Chương I: Mô hình dữ liệu quan hệ.
Chương này đã trình bày một số các khái niệm cơ bản nhất trong mô hình dữ
liệu quan hệ. Trình bày các phép toán cơ bản, các khái niệm về phụ thuộc
hàm, bao đóng, khóa cùng với các tính chất của chúng. Ngoài ra các thuật
toán tìm khoá, bao đóng và phép dịch chuyển lược đồ trong mô hình dữ liệu
quan hệ cũng được trình bày trong chương này.
Chương II : Mô hình dữ liệu dạng khối.
Nội dung chương này trình bày các khái niệm cơ bản trong mô hình dữ liệu
dạng khối như : khái niệm về khối, lược đồ khối, lát cắt. Trình bầy các phép
toán cơ bản trên khối, khái niệm về bao đóng của tập phụ thuộc hàm, bao
đóng của tập thuộc tính chỉ số, khóa của lược đồ khối cùng với các thuật toán
tìm bao đóng, tìm khóa của lược đồ khối. Ngoài ra chương này còn trình bầy
phép dịch chuyển của lược đồ khối .
Chương III : Tính chất mở rộng của bao đóng trong mô hình dữ liệu
dạng khối.
Phát biểu và chứng minh tính chất của bao đóng, tính chất mở rộng của bao
đóng tập thuộc tính chỉ số trong mô hình dữ liệu dạng khối, xây dựng chương
trình Demo minh họa thuật toán tìm bao đóng của tập thuộc tính chỉ số trong
mô hình dữ liệu dạng khối.
Kết quả đạt được:
- Tìm hiểu về mô hình dữ liệu dạng khối cũng là một mở rộng tự nhiên của
mô hình dữ liệu quan hệ trong đó tìm hiểu kĩ hơn về bao đóng của tập chỉ số
và một vài tính chất cơ bản của nó trong mô hình dữ liệu dạng khối.

4 - Phát biểu và chứng minh các tính chất mở rộng của bao đóng tập thuộc tính
chỉ số trong mô hình dữ liệu dạng khối.
- Giới thiệu bài toán và xây dựng chương trình Demo tính bao đóng của tập

,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
(i = 1,2, ,n) có miền giá trị là D
A
i
.
Khi đó, r là một tập các
bộ {h
1
, h
2
, , h
m
} được gọi là quan hệ trên R với h
j
(j=1, 2, , m) là một hàm:
h
j
= U → D
A
i
, A
i
U | h
j

(A
n)
h
2
(A
1
) h
2
(A
2
) h
2
(A
n)

h
m
(A
1
) h
m
(A
2
) h
m
(A
n)

Bảng 1.1. Ví dụ về quan hệ r
Bộ của quan hệ[6]

K
) thì t.X = (d
1
, d
2
, , d
K
).
Lược đồ quan hệ
[6,7]
Mã SV Họ và tên Lớp Điểm TB

T001 Nguyễn Lan Anh TIN1

7
T002 Nguyễn Văn Bình TIN1

6
T003 Trần Thị Trang TIN2

8
T004 Lưu Văn Nam TIN3

4 7 Tât cả các thuộc tính trong một quan hệ cùng với mối liên hệ giữa chúng

Sinhvien1  Sinhvien2 MaSV Địa chỉ
KT01 HN
KT02 HN
KT03 LS
MaSV Địa chỉ
KT01 HN
KT04 YB

MaSV Địa chỉ
KT01 HN
KT02 HN
KT03 LS
KT04 YB
Bảng 1.3. Biểu diễn quan hệ sinhvien1

sinhvien2

8 MaSV Địa chỉ
MaSV Địa chỉ
KT01 HN
KT04 YB
MaSV Địa chỉ
KT01 HN
MaSV Địa chỉ
KT01 HN
KT02 HN
KT03 LS
MaSV Địa chỉ
KT01 HN
KT02 HN
KT03 LS 9 MaMH TenMH MaMH
LTP Lập trình pascal LTP
CTDL Cấu trúc dữ liệu CTDL

Sinhvien1 – Sinhvien2
Bảng1.5. Biểu diễn quan hệ Sinhvien1–Sinhvien2
Sinhvien2 – Sinhvien1


và bảng s Tích đề - các của 2 bảng trên là r x s :

MaSV Địa chỉ
KT02 VP
KT03 LS
MaSV Địa chỉ
KT04 YB
MaSV MaMH Diem
TIN001 LTP 6
TIN002 CTDL 7
TIN003 MANG 8

10 D

2
4
5

MaSV MaMH Diem MaMH TenMH
TIN001 LTP 6 LTP Lập trình Pascal
TIN001 LTP 6 CTDL Cấu trúc dữ liệu
TIN002 CTDL 7 LTP Lập trình Pascal
TIN002 CTDL 7 CTDL Cấu trúc dữ liệu

A B C D
a 1 i 2
b 2 g 4
c 8 h 5
d 6 g 2
e 2 i 5
B D
1 2
2 4
8 5
6 2 11 Mã SV Lớp Điểm TB
T001 TIN1

7
T002 TIN1

6
T003 TIN2

8
T004 TIN3

4


T002 Nguyễn Văn Bình TIN1 6
T003 Trần Thị Trang TIN2 8
T004 Lưu Văn Nam TIN3 4 12 r
s

F

Bảng 1.9. Biểu diễn phép chọn :

Điểm TB 5
(Sinhvien)
- Các phép toán logic trong biểu thức F:  (và),  (hoặc),  (phủ định).
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àδ
F
(r) , là tập tất cả
các bộ của r thoả mãn F. Ta có: δ
F
(r) = { t | tr F(t) = đúng}.
Ví dụ : Cho bảng
Sinhvien

T001 Nguyễn Anh TIN1 7
T002 Nguyễn Bình TIN1 6
T003 Trần Trang TIN2 8
r
s
F13 = δ
F
(r x s)
Điều kiện kết nối F là tổ hợp logic của các toán hạng trong đó mỗi toán hạng
là một phép so sánh giữa thuộc tính của r và s.
Tùy theo tính chất của biểu thức điều kiện và yêu cầu của kết quả mà có thể
chia phép nối thành phép nối tự nhiên, nối bằng, nối so sánh, nửa nối và tự
nối. Trong đại số quan hệ, các phép toán là tương đương khi chúng cho cùng
kết quả. Phép nối tương đương với kết quả của hai phép đại số quan hệ là
phép nhân và phép hạn chế.
Ví dụ : Cho 2 quan hệ
Sinhvien

Và bangma
14 Ma SV là T003 nhưng cột: Họ và tên nhận giá trị rỗng.
1.2.8. Phép chia[6,7]:
Cho hai quan hệ r(U) và r(V) = {A
1
,A
2
,…,A
n
}, V U. Phép chia của quan hệ
r cho quan hệ s ký hiệu là : r ÷ s là một quan hệ trên U – V gồm các bộ t sao
cho tồn tại bộ u s và ghép t với u ta được bộ thuộc r:
r  s ={ t |  us, (t,u)r}
Ví dụ : Cho quan hệ sau và tìm sinh viên có Điểm các môn học 1 và 2  6
điểm(một trong 2 môn không có điểm nào dưới 5điểm)
Sinhvien
Diemcantim Sinhviendapung

1.3. Phụ thuộc hàm