BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
======

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 SƯ PHẠM HÀ NỘI 2
======

CHU QUANG ĐỨC

GIÀN GIAO CỦA CÁC TẬP ĐÓNG
TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

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

Người hướng dẫn khoa học: TS. Trịnh Đình Vinh

HÀ NỘI, 2015


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
1. Lý do chọn đề tài ....................................................................................... 1
2. Mục đích nghiên cứu ................................................................................. 1
3. Nhiệm vụ nghiên cứu ................................................................................ 2
4. Đối tƣợng và phạm vi nghiên cứu............................................................. 2
5. Phƣơng pháp nghiên cứu........................................................................... 2
6. Những đóng góp mới của đề tài ................................................................ 2
7. Cấu trúc của luận văn ................................................................................ 2
CHƢƠNG 1: MÔ HÌNH DỮ LIỆU QUAN HỆ VÀ GIÀN GIAO CỦA CÁC
TẬP ĐÓNG ....................................................................................................... 4
1.1. Mô hình dữ liệu quan hệ ........................................................................ 4
1.1.1. Tổng quan về mô hình dữ liệu quan hệ ........................................ 4
1.1.2. Thuộc tính và miền thuộc tính ...................................................... 5
1.1.3. Quan hệ, lƣợc đồ quan hệ ............................................................. 5
1.1.4. Khóa của quan hệ .......................................................................... 6
1.2. Các phép tính của đại số quan hệ ........................................................... 7
1.3. Phụ thuộc hàm ...................................................................................... 11
1.4. Bao đóng .............................................................................................. 12


1.5. Khoá ..................................................................................................... 14
1.6. Giàn giao của các tập đóng trong mô hình quan hệ ............................. 16
Kết luận ....................................................................................................... 29
CHƢƠNG 2: MÔ HÌNH DỮ LIỆU DẠNG KHỐI ........................................ 30
2.1. Mô hình dữ liệu dạng khối ................................................................... 30
2.1.1. Khối, lƣợc đồ khối ...................................................................... 30


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
Hình 2.3. Biểu diễn 2 khối r , s khả hợp. ....................................................... 35
Hình 2.4. Biểu diễn các khối r, s, r  s. ......................................................... 36
Hình 2.5. Biểu diễn các khối r, s, r  s ........................................................... 37
Hình 2.6. Biểu diễn các khối: r , s, s \ r . ......................................................... 37
Hình 2.7. Biểu diễn các khối r , r ,   P (r ). ................................................... 39
Hình 2.8. Biểu diễn khối  x4  y 4 (r ) ................................................................ 41


DANH MỤC CHỮ VIẾT TẮT VÀ KÍ HIỆU

Ý nghĩa

Kí hiệu
PTH

Phụ thuộc hàm.

LĐQH

Lƣợc đồ quan hệ

LS

Vế trái

RS




Anpha



Bêta



Tồn tại

Fh

Phụ thuộc hàm Fh

AXĐ

Ánh xạ đóng


1

MỞ ĐẦU
1. Lý do chọn đề tài
Hệ thống cơ sở dữ liệu (CSDL) là một lĩnh vực rất quan trọng trong
ngành Khoa học máy tính. Việc khai thác hệ thống này có hiệu quả là một vấn
đề cấp bách hiện nay. Hiện nay ngƣời ta thƣờng sử dụng các hệ thống cở sở
dữ liệu nhƣ: Mô hình dữ liệu thực thể - liên kết, mô hình dữ liệu mạng, mô

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 vi nghiên cứu
- Đối tƣợng nghiên cứu giàn giao của các tập đóng trong mô hình dữ
liệu dạng khối.
- Phạm vi nghiên cứu trong mô hình dữ liệu dạng khối.
5. Phương pháp nghiên cứu
Trong quá trình triển khai đề tài, chúng tôi sử dụng chủ yếu các phƣơng
pháp: Thu thập tài liệu, phân tích, suy luận, tổng hợp, đánh giá tài liệu về lƣợc
đồ khối, mô hình dữ liệu dạng khối, lƣợc đồ khối. Từ đó đề xuất ra 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.
6. Những đóng góp mới của đề tài
- Tìm hiểu mô hình dữ liệu dạng khối.
- Tìm hiểu giàn giao của các tập đóng trong mô hình dữ liệu dạng khối
và các tính chất của nó.
- 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 và trên lát cắt.
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.


3

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ố trên mô hình quan hệ, các vấn đề về phụ thuộc hàm,
bao đóng, khóa và giàn giao của các tập đóng trong mô hình quan hệ.

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.
Mỗi liên hệ giữa tập E1, E2 ,..., Ek đƣợc biểu diễn bởi một quan hệ có
lƣợc đồ quan hệ chứa các thuộc tính trong các khóa của E1, E2 ,...., Ek . Bằng
cách đặt lại tên cho các thuộc tính nếu cần, ta đảm bảo rằng không có hai tập
thực thể trong danh sách có các thuộc tính cùng tên, ngay cả khi hai tập thực
thể này chỉ là một.


5

1.1.2. Thuộc tính và miền thuộc tính
Định nghĩa 1.1
- Thuộc tính là đặc trƣng của các quan hệ.
- Miền thuộc tính là tập giá trị mà từ đó ta có thể rút ra các giá trị cụ thể
xuất hiện trong các cột biểu diễn thuộc tính, ký hiệu: DOM (tên thuộc tính).
Ví dụ 1.1. Nhanvien : MaNV, Hoten, NgSinh, Đchi )
DOM(MaNV) = {char (4) }; DOM(Hoten) = {char (3) };
DOM(NgSinh) = {date}; DOM(Đchi) = {„HN‟, „SL‟, „ĐB‟…}
1.1.3. Quan hệ, lược đồ quan hệ
Định nghĩa 1.2
Cho U  {A1, A2 ,..., An } là một tập hữu hạn các phần tử khác rỗng, trong
đó Ai (i  1, 2,..., n) là các thuộc tính. Mỗi thuộc tính Ai có miền giá trị là
DAi . Khi đó r là một tập các bộ {h1, h2 ,..., hn} đƣợc gọi là quan hệ trên R

với h j ( j  1, 2,...,  m) là một hàm:


h2 ( An )

…

…

…

…

…

hm

hm ( A1)

hm ( A2 )

…

hm ( An )

Bảng 1.1. Biểu diễn quan hệ r.


6

Ví dụ 1.2.
Nhân viên:

C 03

B

20 / 11/ 92

VP

P6

Bảng 1.2. Biểu diễn ví dụ Nhân Viên.
Trong đó các thuộc tính là MaNV : mã nhân viên; HOTEN : họ
tên; NS : ngày sinh; DC : địa chỉ; KHOA : khoa.
Bộ giá trị: (C 01, A,26 / 03 / 90, HN , P5) là một bộ.
Nếu có một bộ t  (d1, d2 , d3,..., dm )  r , r xác định trên U , X  U thì
t ( X ) đƣợc gọi là giá trị của tập thuộc tính X trên bộ t .

Định nghĩa 1.3
Tập tất cả các thuộc tính cần quản lý của một đối tƣợng cùng với mối
liên hệ giữa chúng đƣợc gọi là lược đồ quan hệ. Lƣợc đồ quan hệ R với tập
thuộc tính U  {A1, A2 ,..., An} đƣợc viết là R( A1, A2 ,..., An ) hoặc R(U ) , quan
hệ r xác định trên lƣợc đồ R(U ).
Khái niệm tất cả các bộ ( D1, D2 ,...., Dn )
1.1.4. Khóa của quan hệ
Định nghĩa 1.4
Cho quan hệ r xác định trên tập thuộc tính U  {A1, A2 ,..., An} , K  U
đƣợc gọi là khóa của quan hệ r nếu nhƣ với mọi t1, t2  r , t1  t2 thì tồn tại
ít nhất một thuộc tính A  K sao cho t1. A  t2. A và mọi K1  K , K1 không
phải là khóa.
Tập thuộc tính K '  K và K là khoá.

19 / 05 / 91

SL

P5

C 03

B

20 / 11/ 92

VP

P6

Bảng 1.3. Biểu diễn quan hệ Sinh Viên.
Trong quan hệ sinh viên ở bảng 1.3 ta thấy khóa của quan hệ này là
MaSV .

1.2. Các phép tính của đại số quan hệ
- Phép toán tập hợp: Hợp, giao, trừ, tích Đề-các.
- Phép toán quan hệ: Chiếu, chọn, kết nối, chia.
Định nghĩa 1.5
Hai quan hệ r và s đƣợc gọi là khả hợp nếu nhƣ hai quan hệ này xác
định trên cùng tập thuộc tính và các thuộc tính cùng tên có cùng miền giá trị.
* Phép hợp
- Cho 2 quan hệ r và s khả hợp. Hợp của r và s ký hiệu: r  s , là
một quan hệ gồm tập tất cả các bộ thuộc r hoặc thuộc s .
r  s  {t t  r  t  s} .

b1

c1

b2

c2

a2

b1

c2

b2

c1


8
r s:

A

B

C

a1



r:

r s:

A

B

C

a1

b1

s:

A

B

C

c1

a1

b1

c1

tất cả các bộ thuộc r nhƣng không thuộc s . Ta có: r  s  {t t  r và t  s}


9

Ví dụ 1.6

r:

r \ s:

A

B

C

a1

b1

s:

A

B

C

c1


C

a2

b2

c2

a2

b1

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
Cho 2 quan hệ r , s bất kỳ, có tập thuộc tính lần lƣợt là U1 và U 2 với
U1  U 2   . Tích Đề-các của r , s ký hiệu: r  s là quan hệ trên U1  U 2

gồm tập tất cả các bộ ghép đƣợc từ các bộ của r và s . Ta có:
r  s  {t  (u, v) / u  r, v  s} .

B

C

D

a

1

x

b

2

c

 B  D (r )

A

B

C

D

4


x

5

e

1

y

4

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(U ) và S (V ) . Đặt M  U  V . Phép kết nối (tự
nhiên) hai quan hệ R(U ) và S (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ệ 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 u  R, v  S , u.M  v.M }.


11
Nếu M  U  V  , 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 .
- Kết nối bằng (Equi - Join): Là phép kết nối trong đó tất cả các phép so
sánh trong điều kiện F đều là bằng.
- Kết nối tự nhiên (Natural - Join): Là phép kết nối bằng trên các thuộc
tính trùng tên của hai quan hệ trong đó một thuộc tính trùng tên sẽ bị loại khỏi
quan hệ kết quả, Kí hiệu : r  s .

2. Nếu X  Y thì XW  YW .
3. Nếu X  Y ,Y  Z thì X  Z .
4. Nếu X  Y ,YZ  W thì XZ  W.
5. Nếu X  Y , Z  W thì XZ  YW .
6. Nếu X  Y thì XZ  Y .
7. Nếu X  Y , X  Z thì X  YZ .
8. Nếu X  YZ thì X  Y .
9. Nếu X  YZ , Z  WV thì X  YZW .
1.4. Bao đóng
Định nghĩa 1.7
Cho tập phụ thuộc hàm F , bao đóng của tập phụ thuộc hàm F kí hiệu
F  là tập lớn nhất chứa các phụ thuộc hàm đƣợc suy diễn từ các phụ thuộc

hàm thuộc F . Vậy F  ( f | F | 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   ( X ,Y ) .


13
6) ( X Y )  ( XY  )  ( XY ) .
7) X  Y  Y  X  .
8) X  Y và Y  X  X   Y  .
Thuật toán bao đóng:
Vào: Tập thuộc tính X , tập phụ thuộc hàm F và lƣợc đồ khối R .
Ra: X  bao đóng của X đối với F trên R .
BAO DONG 1( X , F , R)


Hai điều kiện trên tƣơng đƣơng với:
(i ' ) . K  U

(ii ' ) . A  K : K \ A  U

Nếu K thỏa điều kiện (i ) (hoặc (i ' )) thì K đƣợc gọi là một siêu khóa.
Thuộc tính A U đƣợc gọi là thuộc tính khóa (nguyên thủy hoặc cơ
sở), nếu A có trong một khóa nào đấy. A đƣợc gọi là thuộc tính không khóa,
(phi nguyên thủy hoặc thứ cấp) nếu A không có trong bất kỳ khóa nào.
Cho LĐQH   U , F ta kí hiệu U K là tập các thuộc tính khóa của 
và U 0 là tập các thuộc tính không khóa của a .
Dễ thấy U K U 0 là một phân hoạch của U .
Thuật toán tìm một khóa của LĐQH.
Tư tưởng:
Xuất phát từ một siêu khóa K tùy ý của LĐQH, duyệt lần lƣợt các
thuộc tính A của K nếu bất biến ( K \ A)   U đƣợc bảo toàn thì loại A khỏi
K có thể thay kiểm tra ( K \ A)  U bằng kiểm tra A  ( K \ A) .

Algorithm Key


15

Format: Key (U , F )
Input:
- Tập thuộc tính U
- Tập PTH F
Output: - Khóa K  U thỏa:
(i ) . K   U

Cho tập U và ánh xạ f: Subset(U)  Subset(U) đƣợc gọi là đóng trên tập
U nếu với mọi tập con X, Y  U ta có các tính chất (C1)-(C3) sau đây:
(C1) Tính phản xạ: f(X)  X,
(C2) Tính đồng biến hay đơn điệu: Nếu X  Y thì f(X)  f(Y),
(C3) Tính lũy đẳng: f(f(X)) = f(X).
(C4) f(Xf(Y)) = f(XY)
(C5) f(XY)  f(X)f(Y)
(C6) f (X  Y)  f(X)  f(Y)
Chứng minh
(C4) Theo tính phản xạ của AXĐ f ta có f(X)  X, do đó f(X)Y  XY.
Theo tính chất đồng biến của f ta có f(f(X)Y)  f(XY). Mặt khác, do X
 XY, Y  XY, vận dụng tính đồng biến của f ta có f(X)  f(XY) và Y 

XY  f(XY), do đó f(X)Y  f(XY). Lại theo tính chất đồng biến và tích
lũy đẳng của f ta có f(f(X)Y)  f(f(XY) = f(XY). Từ hai bao hàm thức
vừa chứng minh ta suy ra f(f(X)Y) = f(XY).
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  X, XY  Y và tính đồng biến củ f ta suy ra f(XY)  f(X) và
f(XY)  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).