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

s ư PHẠM
HÀ NỘI
2
•
•
•
•
===£oCQGa===

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 CẢM ƠN

Để hoàn thành luận văn này tôi đã nhận được sự giúp đỡ tận tình của
thầy hướng dẫn khoa học TS. Trịnh Đình Vinh, cùng các thầy cô trường Đại
học Sư phạm Hà Nội 2, các thầy cô trong ban giám hiệu và các thầy cô trong
trường THPT Mê Linh. Tôi xin chân thành cảm ơn các thầy cô trường Đại
học Sư phạm Hà Nội 2, trường THPT Mê Linh đã tạo điều kiện cho tô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

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
2.1.2. Lát cắt......................................................................................... 32
2.2. Đại số trên khối................................................................................... 34
2.3. Phụ thuộc hàm trên khối..................................................................... 42
2.4. Bao đóng trong mô hình dữ liệu dạng khối........................................ 44
2.5. Khoá của lược đồ khối đối với tập phụ thuộc hàm F trên R ..............45

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

Hình 2.3. Biểu diễn 2 khối r, 5 khả hợp........................................................ 35
Hình 2.4. Biểu diễn các khối r , í , r u 5.........................................................36
Hình 2.5. Biểu diễn các khối r , 5 , m i ..........................................................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 ’ = rip (/)....................................................39
Hình 2.8. Biểu diễn khối

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

Y nghĩa

K íhỉêu
•

PTH

Phụ ứiuộc hàm.

LĐQH

Lược đô quan hệ

LS

Vê trái

RS

Vê phải

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

J3

Bêta

3

Tôn tại

Fh

Phụ thuộc hàm Fh

AXĐ

Anh 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ô
hình dữ liệu phân cấp, mô hình dữ liệu hướng đối tượng, mô hình dữ liệu
datalog và mô hình dữ liệu quan hệ. Trong số các mô hình dữ liệu này thì có
ba mô hình dữ liệu thường được sử dụng là mô hình dữ liệu phân cấp, mô
hình dữ liệu mạng và mô hình dữ liệu quan hệ. Đối vói ba mô hình này thì
mô hình dữ liệu quan hệ được quan tâm hơn cả. Mô hình này được

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

- Đố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ệ.
Chương 2: Giới thiệu tổng quan về mô hình dữ liệu dạng khối: Định nghĩa
khối, lược đồ khối, lát cắt, khóa của khối, các phép toán đại số trên khối, đại
số quan hệ trên khối, phụ thuộc hàm, bao đóng trong mô hình dữ liệu dạng
khối, khóa của lược đồ khối R đối vói tập phụ hàm F và giàn giao của các
tập đóng trong mô hình dữ liệu dạng khối.
Chương 3: Trình bày khái niệm về giàn giao của các tập đóng trong mô hình

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.

Mỗi liên hệ giữa tập E],E2,...,Ek âuợ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 E ị,E 2,....,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) = {‘H N \ ‘SL\ ‘ĐB’...}
1.1.3. Quan hệ, lược đồ quan hệ
Định nghĩa 1.2
Cho u - {Al,A2,...,An }lh. một tập hữu hạn các phần tò khác rỗng, trong
đó Aị (i = 1, 2

là các thuộc tính. Mồi thuộc tính Aị có miền giá trị là

Da . Khi đó r là một tập các bộ {hị, hỵ,..., 1%} được gọi là quan hệ trên R
với h j(j = 1, 2

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)

...

W A i)

...

...

...

...

hm(,A2)

...

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


6

Ví du 1.2.
Nhân viên:
MaNV

HOTEN

NS

DC

PLV

COI

А

2 6 /0 3 /9 0

HN

P5

C02

В

19/05/91

SL

P5

C03

В

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ị: (COI, A, 26 / 03 / 90, HN, P5) là một bộ.
Nếu có một bộ t - (dị, d2,

Gr , r xác định trên u , x c ư 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 = [Aị, A2,...,An}ẫxxạc viết là R(Aị, 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ộ (Dị,

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 и - {Aị,A2,...,An}, к Œи
được gọi là khóa của quan hệ r nếu như với mọi tị,t2 e r ■
>h ^ h thì tồn tại
ít nhất một thuộc tính Aphải là khóa.
Tập thuộc tính К n> К và к là khoá.
Ví dụ 1.3. Cho quan hệ sinh viên như ở bảng 1.3 dưới đây.

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

P5

C03

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à 5 ký hiệu: r u s , là
một quan hệ gồm tập tất cả các bộ thuộc r hoặc thuộc s .
rU 5 = { í|íer

V íes}.

Ví du 1.4

A

B

c

A

B

c

ax

h

Cl

ữị

h

^1

a2 b2

c2

a2 h

c2

a2 b2

C1

s:


8

rUí:

A

В

с

ax

h

cì

«2

h

c2

«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

в

С

А

В

с

ax h

c\

ax

h

c\

a2 b2

c2

a2 h

c2

a2 b2

C1

А

В

с

ữị

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

В

с

А

В

с

al

h

C1

ữị

h

C1

a2 b2

c2

a2 h

c2

a2 b2

cl

А

В

С

А

В

с

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

Cho 2 quan hệ r , s bất kỳ, có tập thuộc tính lần lượt là Uị và u 2 với
и ị n U 2 = 0 . Tích Đề-các của r, s ký hiệu: r x s là quan hệ trên Uị r ì ư 2
gồm tập tất cả các bộ ghép được từ các bộ của r và 5. Ta có:
r x í = {í = (M ,v)/uer, v e í} .
* Phép chiếu
Phép chiếu thực sự 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.
- Cho quan hệ r xác định trên tập thuộc tính и , X là tập con của и .
Phép hợp chiếu của quan hệ r trên tập thuộc tính X , kí hiệu là
các bộ của r xác định trên X . Ta có:

, là tập

{t.x 11Gr }.

* Phép chọn
- Phép chọn là phép toán lấy ra một tập con các bộ của quan hệ đã cho


10

thoả 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.
- Điều kiện chọn là một tổ họp logic của một bài toán hạng trong đó
mỗi toán hạng là một phép toán so sánh giữa 2 thuộc tính có cùng miền giá trị
hoặc giữa một thuộc tính với giá trị hằng.
- F là phép toán logic:

A

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

- Cho quan hệ r 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: ổp (r), là tập tất cả
các bộ của r thoả mãn F .

ổF (r) = {t I í e r a F ( í ) đúng}.
Ví du 1.7

c

A

B

a
b

1
2

c

4

d

8
1

e

X

y
z
X

y

D

4
5
4
5
4

A

B

c

4

d

8

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 .

- 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 .
* Phép chia
- Cho hai quan hệ r(JJ) và s(V) vói u = {Aị,...,An}, V d u . Phép chia
của hai quan hệ r cho quan hệ s ký hiệu: r-i-s là quan hệ trên u \ v gồm
các bộ t sao cho tồn tại bộ u e s và ghép t vói u ta được bộ thuộc r :
r + S = { t ỉ \ / U G s , t u G r }.

1.3. Phu• thuôc
• hàm
Khi xét đến mối quan hệ giữa các dữ liệu trong CSDL quan hệ thì một
trong nhưng yếu tố quan trọng nhất được xét đến là sự phụ thuộc giữa các
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 CSDL.
Phụ thuộc hàm là những mối quan hệ giữa các thuộc tính trong CSDL
quan hệ. 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 trạ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. Sử dụng các phụ thuộc hàm để chuẩn hóa lược đồ quan hệ về dạng
chuẩn 3 hoặc chuẩn Boye-Codd.
Định nghĩa 1.6
Cho lược đồ quan hệ R xác định trên tập thuộc tính u , và X ,Y c ( /
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 hai bộ bất kỳ tị, t2 eR


12

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

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 IF 1= / ) .
Tính chất của bao đóng:
1) X

œ X +.

2) Neu X

œY

thì x + œ Y+.

3) x ^ x +.
4) x ++ = x +.
5) X +y + ç ( X ,F ) +.


13

6) (X +Y)+ = (XY+) = (X7)+ .
7) X ^ y o y c X +.
8) X - > y và Y ^ > X o 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 )
Begin
Tepcu:= 0 ; tepmoi:= X ;

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

Bước 4 \ X 4 = X 3
Vậy ABp ={ABDEH}
1.5. Khoá
Định nghĩa 1.8
Cho LĐQH a = (U,F). Tập thuộc tính k ^ u được gọi là khóa của
LĐQH a nếu:
ạ). K + = u
(U). VA Ei K\ (K\ A)+ ^ u

Hai điều kiện trên tương đương vói:
(í). K ^ U

0 0 . VAg K : K \ A ^ > U
Nếu K thỏa điều kiện (ỉ) (hoặc ( ỉ )) thì K được gọi là một siêu khóa.
Thuộc tính A e 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 a = U,F ta kí hiệu UK là tập các thuộc tính khóa của a
và ơ 0 là tập các thuộc tính không khóa của a .
Dễ thấy Uk \Uq 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 Ả 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 G(K \ A)+.
Algoiithm Key


15

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.

16

1.6. Giàn giao của các tập đóng trong mô hình quan hệ
1.6.1 Ánh xạ đóng
Định nghĩa 1.9
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 ç и ta có các tính chất (C1)-(C3) sau đây:
(С 1) Tính phản xạ:f(X) 3 X,
(C2) Tính đồng biến hay đơn điệu: Neu 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 n Y ) e f(X)nf(Y)
Chứng minh
(C4) Theo tính phản xạ của AXĐ f ta сỏf(X)

2

X, do đó f(X)Y

2

XY.

Theo tính chất đồng biến của f ta cóf(f(X)Y) 3 f(XY). Mặt khác, do X
ÇZXY, Y œ XY, vận dụng tính đồng biến của f ta có f(X)af(XY) và Y œ
XY œ f(XY), do đỏ/(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) af(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 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).