Một số phụ thuộc dữ liệu trong cơ sở dữ liệu dạng khối

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC

VÀ CÔNG NGHỆ VIỆT NAM

VIỆN CÔNG NGHỆ THÔNG TIN

TRỊNH ĐÌNH VINH

MỘT SỐ PHỤ THUỘC DỮ LIỆU

TRONG CƠ SỞ DỮ LIỆU DẠNG KHỐI

LUẬN ÁN TIẾN SĨ TOÁN HỌC

HÀ NỘI - 2011

1

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC

VÀ CÔNG NGHỆ VIỆT NAM

VIỆN CÔNG NGHỆ THÔNG TIN

TRỊNH ĐÌNH VINH

MỘT SỐ PHỤ THUỘC DỮ LIỆU

TRONG CƠ SỞ DỮ LIỆU DẠNG KHỐI

Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH

VÀ HỆ THỐNG TÍNH TOÁN

Mã số: 62.46.35.01

LUẬN ÁN TIẾN SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:

1. GS.TS. Vũ Đức Thi

2. PGS.TS. Nguyễn Kim Anh

HÀ NỘI – 2011

2

Lêi c¶m ¬n

®Ó hoµn thµnh luËn ¸n nµy, t«i ®· nhËn ®−îc sù gióp ®ì rÊt tËn t×nh cña

c¸c thÇy c« h−íng dÉn khoa häc, c¸c thÇy c« trong ViÖn CNTT vµ tr−êng

§HSP Hµ Néi 2. T«i xin c¶m ¬n c¸c thÇy c« trong ViÖn CNTT vµ tr−êng

§HSP Hµ Néi 2 ®· t¹o ®iÒu kiÖn häc tËp, nghiªn cøu, gióp ®ì t«i rÊt nhiÒu

trong qu¸ tr×nh lµm luËn ¸n. §Æc biÖt t«i xin c¶m ¬n thÇy GS. TS. Vò §øc Thi,

c« PGS.TS. NguyÔn Kim Anh ®· tËn t×nh h−íng dÉn, chØ b¶o cho t«i trong

toµn bé 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 ¸n

nµy.

TrÞnh §×nh Vinh

3

Lêi cam ®oan

T«i xin cam ®oan ®©y lµ c«ng tr×nh nghiªn cøu cña t«i d−íi sù h−íng

dÉn khoa häc cña c¸c thÇy c« GS.TS. Vò §øc Thi vµ PGS. TS. NguyÔn Kim

Anh.

C¸c sè liÖu, kÕt qu¶ nªu trong luËn ¸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.

T¸c gi¶ luËn ¸n

TrÞnh §×nh Vinh

4

môc lôc

Trang

Danh môc c¸c ký hiÖu vµ ch÷ viÕt t¾t ………………………………7

Danh môc b¶ng biÓu vµ h×nh vÏ …………………………………….8

Lêi më ®Çu …………………………………………………………....9

Ch−¬ng 1: M« h×nh c¬ së d÷ liÖu quan hÖ ………………………...13

1.1. C¸c kh¸i niÖm c¬ b¶n ……………………………………...13

1.1.1. Thuéc tÝnh vµ miÒn thuéc tÝnh ……………………13

1.1.2. Quan hÖ, l−îc ®å quan hÖ ………………………...13

1.1.3. Kho¸ cña quan hÖ ………………………………...14

1.2. C¸c phÐp to¸n ®¹i sè quan hÖ ……………………………...15

1.2.1. PhÐp hîp ………………………………………….15

1.2.2. PhÐp giao ………………………………………….15

1.2.3. PhÐp trõ …………………………………………...16

1.2.4. TÝch ®Ò c¸c ………………………………………...16

1.2.5. PhÐp chiÕu …………………………………………17

1.2.6. PhÐp chän …………………………………………17

1.2.7. PhÐp kÕt nèi ………………………………………..18

1.2.8. PhÐp chia …………………………………………..20

1.3. Phô thuéc hµm ……………………………………………..20

1.3.1. C¸c tÝnh chÊt cña phô thuéc hµm …………………21

1.3.2. HÖ tiªn ®Ò Armstrong vµ phÐp suy dÉn …..……….21

1.4. Bao ®ãng …………………………………………………...22

1.4.1. Bao ®ãng cña tËp phô thuéc hµm …………………22

1.4.2. Bao ®ãng cña tËp thuéc tÝnh ………………………22

1.4.3. Bµi to¸n thµnh viªn vµ thuËt to¸n t×m

5

bao ®ãng cña tËp thuéc tÝnh ………………………22

1.5. Khãa cña l−îc ®å quan hÖ ………………………………...24

1.6. Phñ cña tËp phô thuéc hµm ………………………………..26

1.7. Phñ tèi thiÓu cña tËp phô thuéc hµm ………………………26

1.7.1. Phô thuéc hµm cã vÕ tr¸i d− thõa …………………26

1.7.2. TËp phô thuéc hµm cã vÕ ph¶i gåm 1 thuéc tÝnh ….27

1.7.3. TËp phô thuéc hµm kh«ng d− thõa ……………….27

1.7.4. TËp phô thuéc hµm tèi thiÓu ………………………28

(Phñ tèi thiÓu cña tËp phô thuéc hµm)

1.8. C¸c d¹ng chuÈn cña l−îc ®å quan hÖ ………………………28

1.9. Phô thuéc ®a trÞ ……………………………………………30

1.9.1. §Þnh nghÜa phô thuéc ®a trÞ ………………………30

1.9.2. C¸c tÝnh chÊt cña phô thuéc ®a trÞ ………………..31

1.10.KÕt luËn ch−¬ng 1 ………………………………………..32

Ch−¬ng 2 : M« h×nh c¬ së d÷ liÖu d¹ng khèi …………………..33

2.1. Khèi, l−îc ®å khèi ………………………………................33

2.2. L¸t c¾t ...................................................................................34

2.3. Kho¸ cña khèi …………………………………………….35

2.4. §¹i sè quan hÖ trªn khèi …………………………………...37

2.4.1. PhÐp hîp …………………………………………..37

2.4.2. PhÐp giao ………………………………………….37

2.4.3. PhÐp trõ …………………………………………..37

2.4.4. TÝch §Ò C¸c ………………………………………38

2.4.5. TÝch §Ò C¸c theo tËp chØ sè ……………………….38

2.4.6. PhÐp chiÕu …………………………………………38

2.4.7. PhÐp chän …………………………………………39

2.4.8. PhÐp kÕt nèi ……………………………………….39

6

2.4.9. PhÐp chia ………………………………………….40

2.5. Phô thuéc hµm ……………………………………………41

2.6. Bao ®ãng cña tËp thuéc tÝnh chØ sè ………………………..43

2.7. Kho¸ cña l−îc ®å khèi R ®èi víi

tËp c¸c phô thuéc hµm F trªn R ……………………………45

2. 8. D¹ng chuÈn cña khèi ……………………………………...46

2.9. Phñ cña tËp phô thuéc hµm ………………………………...48

2.10. KÕt luËn ch−¬ng 2 ………………………………………..50

Ch−¬ng 3: phô thuéc ®a trÞ, phô thuéc ®a trÞ xÊp xØ vµ

α-phô thuéc hµm trong m« h×nh d÷ liÖu d¹ng khèi ……51

3.1. Phô thuéc ®a trÞ trong m« h×nh d÷ liÖu d¹ng khèi ………….51

3.2. C¸c tÝnh chÊt cña Phô thuéc ®a trÞ ………………………….53

3.3. Phô thuéc ®a trÞ xÊp xØ trong m« h×nh d÷ liÖu d¹ng khèi …..61

3.4. C¸c tÝnh chÊt cña phô thuéc ®a trÞ xÊp xØ …………………..63

3.5. α-Phô thuéc hµm vµ α-bao ®ãng trong m« h×nh

d÷ liÖu d¹ng khèi ………………………………………….71

3.5.1. Kh¸i niÖm xÊp xØ møc α ………………………….71

3.5.2. α-phô thuéc hµm vµ α-bao ®ãng …………………..73

3.6. KÕt luËn ch−¬ng 3 ………………………………………….84

PhÇn kÕt luËn ………………………………………………………...85

Danh môc c«ng tr×nh c«ng bè cña t¸c gi¶ …………………………..87

Danh môc tµi liÖu tham kh¶o ………………………………………..88

7

danh môc c¸c ký hiÖu vµ c¸c ch÷ 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

A, B, C thuéc tÝnh.

X, Y, Z tËp thuéc tÝnh.

XY X∪Y (hîp cña 2 tËp thuéc tÝnh X vµ Y).

ABC [A, B, C] (tËp thuéc tÝnh gåm 3 phÇn tö A, B, C).

Dom(A) miÒn gi¸ trÞ cña thuéc tÝnh A.

r hoÆc r(R) khèi r trªn tËp R.

x(i)

= (x, Ai

) c¸c thuéc tÝnh chØ sè cña l−îc ®å khèi (x∈id, i= 1.. n).

id(i) = {x(i)⎜x∈id } tËp c¸c thuéc tÝnh chØ sè cña l−îc ®å khèi.

r sè phÇn tö cña khèi r.

r ' sè phÇn tö cña khèi con r’ cña khèi r.

8

danh môc c¸c b¶ng biÓu vµ c¸c h×nh vÏ

B¶ng biÓu ý nghÜa

B¶ng 1.1 BiÓu diÔn quan hÖ r………………………………..13

B¶ng 1.2 BiÓu diÔn c¸c quan hÖ r, s vµ r x s…………………16

B¶ng 3.1 Quan hÖ gÇn nhau trªn miÒn gi¸ trÞ cña A1………..74

H×nh vÏ ý nghÜa

H×nh 2.1 BiÓu diÔn khèi nh©n viªn (NV(R))…..……………34

H×nh 2.2 BiÓu diÔn khèi Canbo……………………………..41

H×nh 3.1 BiÓu diÔn khèi Sinhviªn1………………………....52

H×nh 3.2 BiÓu diÔn khèi Sinhviªn2………………………....62

H×nh 3.3 BiÓu diÔn khèi Sinhviªn3………………………....74