Bài giảng Cơ sở dữ liệu quan hệ: Chương 5

CHƯƠNG V:

PHỤ THUỘC HÀM

Nội dung chi tiết

1. Phụ thuộc hàm 2. Hệ tiên đề Amstrong 3. Bao đóng phụ thuộc hàm, tập thuộc tính 4. Bài toán thành viên 5. Tập PTH tương đương 6. Tập PTH tối thiểu – Phủ tối thiểu 7. Khóa của quan hệ

07/11/2012 11:02 AM 2

I. Phụ thuộc hàm

Định nghĩa: Cho R(U), với R là quan hệ và U là tập thuộc tính. Cho X,Y ⊆U, phụ thuộc hàm X → Y (đọc là X xác định

Y) được định nghĩa là:

∀ t, t’ ∈ R nếu t.X = t’.X thì t.Y = t’.Y

(Có nghĩa là: Nếu hai bộ có cùng trị X thì có cùng trị Y Cách đọc: X xác định Y hay Y phụ thuộc hàm vào X -X gọi là vế trái của PTH, Y là vế phải của PTH

Phụ thuộc hàm thường được ký hiệu là FD hay F (Functional Dependencies)

07/11/2012 11:02 AM 3

Ví dụ 1:

 Trong quan hệ SV(MaSV,Ten,Diachi,Ngaysinh), mỗi thuộc tính Ten, Diachi, Ngaysinh đều phụ thuộc hàm (pth) vào thuộc tính MaSV.

 Mỗi giá trị MaSV xác định duy nhất một giá trị tương ứng

đối với từng thuộc tính đó. Khi đó, có thể viết : - - -

DIACHI TEN NGAYSINH

MaSV MaSV MaSV

07/11/2012 11:02 AM 4

 Ví dụ 2: Cho quan hệ R(A,B,C,D) như sau:

R (A B C D)

a 1 x 2

a 1 y 2

b 2 x 1

b 2 y 1

 Cho biết các phụ thuộc hàm nào liệt kê dưới đây được thoả trong

A B C

C

quan hệ R ở trên? - - - - - -

f1: A f2: A f3: A f4: AC f5: A f6: D

D A

07/11/2012 11:02 AM 5

Nhận xét:

- Phụ thuộc hàm là công cụ để biểu diễn một cách hình thức các

ràng buộc.

- PTH được ứng dụng giải quyết các bài toán tìm khoá, tìm phủ

tối thiểu và chuẩn hoá các quan hệ trong cơ sở dữ liệu.

Y thì không thể nói gì về Y

- Nếu X - Ví dụ:

 Có MSV Tên thì không thể khắng định Tên MSV vì có thể có

nhiều sinh viên cùng tên

 Có MSV Ngaysinh thì không thể khắng định Ngaysinh MSV vì có

thể có nhiều sinh viên sinh cùng ngày

07/11/2012 11:02 AM 6

 Biểu diễn phụ thuộc hàm:

- Dùng đường nối mũi tên từ các thuộc tính vế trái đến các

thuộc tính vế phải của tất cả các phụ thuộc hàm

 Ví dụ: MƯỢN(Sốthẻ, Mãsốsách, Tênngườimượn, Tênsách, Ngàymượn)

Tênngườimượn Tênsách

- Với các phụ thuộc hàm:

FD1: Sốthẻ FD2: Mãsốsách FD3: Sốthẻ, Mãsốsách

Ngàymượn

 Có sơ đồ phụ thuộc hàm như sau: MƯỢN

Tên sách Ngàymượn

Sốthẻ

Tên người mượn

Mã số sách

FD2

FD1

FD3

07/11/2012 11:02 AM 7

II. Hệ tiên đề Amstrong

 Năm 1974, Amstrong đưa ra hệ luật dẫn hay các tính chất của phụ thuộc hàm, gọi là hệ tiên đề Amstrong  các nguyên tắc biến đổi của pth

 Định nghĩa:

- F là tập pth trên quan hệ R(U) và A B là một pth với A, B U. Nói rằng, pth A B được suy diễn logic từ F nếu với mỗi quan hệ r xác định trên R thỏa các phụ thuộc hàm trong F thì cũng thỏa phụ thuộc hàm A B.

 Ví dụ:

- Tập phụ thuộc hàm F = { A B, B C} - Ta có phụ thuộc hàm A C là phụ thuộc hàm được suy dẫn

từ tập F

07/11/2012 11:02 AM 8

* Hệ tiên đề Amstrong:

U . Ký hiệu: XY = X Y. Ta có các luật sau :

X thì X Y

VD: ABC

Y thì XZ

YZ

ABD

D thì ABC

VD: Nếu C

Y và Y

Z thì X Z EG YZ

CDEF

C, C Y và X CD và AB Y và Z

EG thì AB Z thì X EF thì AB Y thì X

CDEF thì AB

Z CD và AB EF

Y và WY

Z thì XW

 Cho X, Y, Z, W 1. Luật phản xạ: Nếu Y 2. Luật bổ sung - tăng trưởng: Nếu X 3. Luật bắc cầu: Nếu X VD: Nếu có AB 4. Luật hợp: Nếu X VD: Nếu AB 5. Luật tách: Nếu X VD: Nếu AB 6. Luật tựa bắc cầu:

Nếu X VD: Nếu AB

Z EF và DEF G thì ABD

07/11/2012 11:02 AM 9

 Ví dụ 1: Cho R = ABC và tập F = { AB C , C A }. Áp dụng hệ tiên đề Amstrong CMR: BC ABC

07/11/2012 11:02 AM 10

 Ví dụ 2: Cho lược đồ quan hệ R (A, B, C, D, E, G, H) và tập phụ thuộc hàm F = {BD, ABC, CDE, ECGH, GA}. Áp dụng hệ tiên đề Amstrong để tìm chuỗi suy diễn cho: AB  E và AB G

Thực hiện: 1. AB C (gt) 2. AB  BC (tăng cường thêm B) 3. B  D (gt) 4. BC  DC (t/c thêm C) 5. CD  E (gt) 6. BC  E ( bắc cầu 4 và 5) 7. AB  E (bắc cầu 2 và 6) 8. AB  EC (hợp 1 và 7) 9. EC  GH (gt) 10. AB  GH ( bắc cầu 8 và 9) 11. AB  G (tách)

07/11/2012 11:02 AM 11

 Ví dụ 3: Cho R= {A, B, C, E, F } Và F= { AB C, C B , ABC  E, F A}. Áp dụng hệ tiên đề

Amstrong. CMR: FB  E

Thực hiện: 1. F  A ( gt) 2. FB  AB ( tăng cường) 3. AB  C (gt) 4. ABC  C (tc) 5. ABC  E (gt) 6. ABC  EC ( hợp 4 và 5) 7. AB  E ( tách 6) 8. FB  E ( bắc cầu 2 và 7)

07/11/2012 11:02 AM 12

 Ví dụ 4:

- Hãy dùng hệ tiên đề Armstrong để chứng minh:

Y và U

V thì XU

YV

- Nếu X

 Chứng Minh:

1. Từ X

Y ( gt)

2. Có XU

YU, (tăng trưởng U vào (1) )

3. Từ U

V (gt)

4. Có YU

YV (tăng trưởng Y vào (3)

YV ( bắc cầu (2) và (4) )

5. Có XU

07/11/2012 11:02 AM 13

III. Bao đóng

1. Các khái niệm cơ bản  Gọi F là tập các pth trên tập thuộc tính U, X U .  Bao đóng của phụ thuộc hàm: là tập tất cả các PTH được suy diễn logic từ tập pth F, kí hiệu là F+

Nhận xét: Nếu F+ = F thì F là họ đầy đủ của các pth

07/11/2012 11:02 AM 14

 Bao đóng của tập thuộc tính X: là tất cả các thuộc tính A mà phụ thuộc hàm X A có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong. Kí hiệu: X+

X+ = { A U | X

F+ }

 Nhận xét:

X+

F+  Y

X+ => Có nghĩa là: X Y được suy

- X - X Y

diễn từ hệ tiên đề Amstrong khi và chỉ khi Y

X+

07/11/2012 11:02 AM 15

2. Thuật toán tìm bao đóng của tập thuộc tính

Cho X U là tập thuộc tính => Tìm X+

Thuật toán CLOSURE(X,F). -Input: Tập thuộc tính X và tập phụ thuộc hàm F

-Output: Tìm bao đóng X+ của F

-Thực hiện: Lần lượt tính các X0, X1, X2, …, theo các bước sau:

 Bước 1: Đặt X0 = X  Bước 2: Lần lượt xét các phụ thuộc hàm của F nếu tồn {Z}, ngược lại, đặt

tại pth Y Z F mà Y Xi thì Xi+1 = Xi Xi+1 = Xi

 Bước 3: Nếu ở bước 2 mà không tính được Xi+1 thì Xi chính là bao đóng của tập thuộc tính X, ngược lại lặp lại bước 2.

07/11/2012 11:02 AM 16

Ví dụ 1:

 Cho R = (A, B, C, D, E, G) và pth F = {AB C, C A, BC D, ACD B, D EG, BE C,

CG BD, CE AG}. Tính: (BD)+

07/11/2012 11:02 AM 17

Ví dụ 2:

 Cho R = (A,B,C,D,E,H) và  F = { AB → C, BC → AD, D → E, CE → B}  Tính (AB)+?

07/11/2012 11:02 AM 18

 Ví dụ 3: U = (ABCDEGH) và tập pth F ={A  D, AB 

DE, CE G, EH}. - Tính bao đóng X+ với X= (AB )

 Ví dụ 4: Cho R = { A, B, C, D, E} Và F = {A  C, B C, CD, DE  C, CE A}

- Tính bao đóng X+ với X = ( AE)

07/11/2012 11:02 AM 19

Bài tập áp dụng:

C, BC

A }. Tính:

D, D

E, E

 Cho LĐQH p = (U,F) với U = ABCDE,  F = { A - (AB)+ - (BD)+ - (D)+ - Kiểm tra xem CE->A; DE->A có là thành viên của F

07/11/2012 11:02 AM 20

Ví dụ:

EG A C D BD B

(f1) (f2) (f3) (f4) (f5) (f6) (f7) AG (f8)

AB C D C BE BC CG ADC CE

VD: Cho R(ABCDEG) F = { } Cho X= BD. Tính ( BD)+

07/11/2012 11:02 AM 21

3. Bài toán thành viên

 Là bài toán để xác định một phụ thuộc hàm bất kỳ có

là thành viên của tập phụ thuộc hàm F đã cho

 Định nghĩa: X Y là thành viên của F nếu X Y F+  Thuật toán:

- Bước 1: Tính X+ - Bước 2: So sánh X+ với Y nếu Y X+ thì khẳng

định X

Y là thành viên của tập phụ thuộc hàm F

07/11/2012 11:02 AM 22

Ví dụ 1:

 Cho F = { AB

E, BE

I, E

C, CI

D }

CD suy được từ F.

- Chứng minh AB

 Tính (AB)+ = ABEICD => (AB)+ chứa CD

- Vậy AB CD được suy từ F

07/11/2012 11:02 AM 23

 Ví dụ 2: Cho R= { A, B, E, I, G, H} và

F= { AB  C, B D, CDE, CE  GH, G A}

- Chứng minh rằng: AB  G

 Ví dụ 3:Cho U= (ABEGHI) và pth F = {AB  E, AG I,

BEI, E  G, GI H} - Chứng minh rằng nếu quan hệ r xác định trên W thoả F thì

cũng thoả AB  GH

07/11/2012 11:02 AM 24

Ví dụ 4:

E; D

BC }

 Cho R(ABCDE) và tập PTH F  F = { A CD; C  Yêu cầu: Xác định

B có là thành viên của F E có là thành viên của F D có là thành viên của F

- A - D - B

07/11/2012 11:02 AM 25

 Chú ý:

- có thể áp dụng hệ tiên đề Amstrong để kiểm tra một pth có là thành viên của F hay không bằng cách áp dụng lần lượt các luật để suy ra pth cần chứng minh

07/11/2012 11:02 AM 26

 Ví dụ 1: Cho F = { AB

E, BE

I, E

C, CI

D }

- Chứng minh AB

CD suy được từ F bằng cách áp dụng các

luật của hệ tiên đề Amstrong.

 1. AB --> E, Giải thiết  2. E --> C, Giả thiết  3. AB --> C, Bắc cầu từ (1) và (2)  4. AB --> BE, Tăng cường (1) bởi B  5. BE --> I, Giả thiết  6. AB --> I, Bắc cầu (4) và (5)  7. ABC --> CI, Tăng cường (6) bởi C  8. AB --> ABC, Tăng cường (3) bởi AB

07/11/2012 11:02 AM 27

 9. AB --> CI, bắc cầu (7) và (8)  10. CI --> D, Giả thiết  11. AB --> D, Bắc cầu (9) và (10)  12. ABC --> CD, Tăng cường (11) bởi C  13. AB --> CD, Bắc cầu (8) và (12)

07/11/2012 11:02 AM 28

IV. Tập phụ thuộc hàm tương đương

 Hai tập pth F và G được gọi là tương đương nếu:

- mọi pth của F đều có thể suy được từ G - mọi pth của G đều có thể suy được từ F

có nghĩa là F+ = G+

 Khi đó ta nói F phủ G (hay G phủ F). Kí hiệu : F G  Thuật toán kiểm tra sự tương đương của 2 tập PTH

- F phủ G: X - G phủ F: X

Y G, tính X+ từ F, sau đó kiểm tra xem Y X+ Y F, tính X+ từ G, sau đó kiểm tra xem Y X+

07/11/2012 11:02 AM 29

C, AC F = { A G = { A CD, E

D, E AD, E H } AH }

 Ví dụ 1: Xét hai tập phụ thuộc hàm CMR: F và G là tương đương với nhau  Chứng minh F phủ G: Tìm bao đóng các vế trái của các phụ thuộc

hàm trong G, ta có:

{A}+ = { A, C, D }; {E}+ = {E, A,D,H,C}

- Các bao đóng này chứa các vế phải tương ứng. Suy ra F phủ G.  Chứng minh G phủ F: Tìm bao đóng của các vế trái của các phụ

thuộc hàm trong F theo G. Ta có

{A}+ ={A,C,D}, {AC}+ = { A,C,D}, {E}+ = {E,A,H,C,D},

- Các bao đóng này chứa các vế phải tương ứng. Suy ra G phủ F.

Vậy: G tương đương với F.

07/11/2012 11:02 AM 30

 Ví dụ 2: Cho lược đồ Q = ABCDE và hai tập PTH:  F={A BC, A D, CD E} và G={A BCE, A ABD,

CD E}

 Hỏi:

- F có tương đương với G không - F có tương đương với G’ = { A BCDE } không

07/11/2012 11:02 AM 31

VI. Tập PTH tối thiểu - Phủ tối thiểu

Định nghĩa: Ta nói tập pth F là tối thiểu nếu:

-Vế phải của các pth trong F chỉ có 1 thuộc tính  không có thuộc tính ở vế phải dư thừa -Không tồn tại X A trong F và một tập con thực sự Z của X {Z A} tương đương với F  không có sao cho F\{X A} thuộc tính ở vế trái dư thừa -Không tồn tại X A trong F sao cho F\{X A} tương đương với F  không có phụ thuộc hàm dư thừa

Nhận xét:

-Tất cả các tập PTH đều có PTH tối thiểu tương đương với nó -Có thể có nhiều phủ tối thiểu

07/11/2012 11:02 AM 32

1. PTH có vế phải 1 thuộc tính

 Mỗi tập PTH F luôn tương đương với tập PTH G trong đó

các PTH của G đều có vế phải là một thuộc tính.

 Ví dụ:

07/11/2012 11:02 AM 33

2. PTH có vế trái không dư thừa

 F là tập PTH có vế trái không dư thừa nếu F không chứa

các PTH có vế trái dư thừa

 PTH có vế trái dư thừa:

 Ví dụ:

07/11/2012 11:02 AM 34

* Thuật toán loại khỏi F các PTH có vế trái dư thừa

 Input: Tập pth F  Output: Tập pth F không có pth có vế trái dư thừa  Thuật toán

- Bước 1: Với mỗi pth X

Y của F thì thực hiện

bước 2

- Bước 2: Với mỗi A

Y F+ thì thay X

Y bằng A

 Nếu A  Lặp lại bước 2 đến khi vế trái X không dư thừa.

07/11/2012 11:02 AM 35

Ví dụ 1

 Cho PTH  Xét PTH

 Như vậy:

- B là dư thừa trong PTH AB - Trong F thay AB Kết quả: F={A

D bằng A BC, B

D C, A

07/11/2012 11:02 AM 36

 Ví dụ 2: Cho F = { AB -> CD, B -> C, C -> D} - Kiểm tra xem F có chứa pth có vế trái dư thừa

07/11/2012 11:02 AM 37

3. Tập PTH không dư thừa

 F là tập PTH không dư thừa nếu không tồn tại

 Thuật toán loại khỏi F các PTH dư thừa

Input: Tập PTH F

- - Output: Tập F không có PTH dư thừa - Thuật toán:

 Bước 1: Với mỗi PTH X  Bước 2: Nếu X

Y trong F Y là thành viên của F – {X

Y} thì loại X

khỏi F

 Bước 3: Lặp lại bước 2 cho đến khi hết các PTH cần xét

07/11/2012 11:02 AM 38

Ví dụ 1:

 Cho F = {A BC, B D, AB D}. Tìm Tập pth không dư thừa

07/11/2012 11:02 AM 39

4. Thuật toán tìm phủ tối thiểu

 Input: Tập PTH F  Output: Phủ tối thiểu của F  Thuật toán

- Bước 1: Đưa tất cả các PTH trong F về dạng PTH vế

phải chỉ có 1 thuộc tính

- Bước 2: Loại khỏi F các PTH có vế trái dư thừa - Bước 3: Loại khỏi F các PTH dư thừa

 Nhận xét:

- Thuật toán luôn tìm được ít nhất 1 phủ tối thiểu. - Nếu trật tự loại các PTH trong F khác nhau có thể có các

phủ tối thiểu khác nhau.

07/11/2012 11:02 AM 40

* Các bước thực hiện:

 Bước 1: Đặt G:=F  Bước 2: Tách các pth có vế phải nhiều thuộc tính bằng các pth có

vế phải chỉ có một thuộc tính - Thay thế tất cả các pth X {A1, A2, …, An} trong G bằng n pth con: X

A1, X A2, …, X An

 Bước 3: xóa lần lượt các thuộc tính trong vế trái của pth mà vế trái

có nhiều thuộc tính  loại bỏ thuộc tính dư thừa ở vế trái - Với mỗi pth X A trong G, với mỗi thuộc tính B trong X nếu ((G-{X {(A-{B}) A}) là tương đương với G, thì thay thế A A bằng

A})

(X-{B}) A trong G  Bước 4: loại bỏ pth dư thừa

- Với mỗi pth X A trong G, nếu (G-{X A}) tương đương với G, thì

loại bỏ pth X A ra khỏi G (loại bỏ phụ thuộc hàm dư thừa)

07/11/2012 11:02 AM 41

Ví dụ 1

 Cho F={AB CD, B C, C D}. Tìm tập pth tối thiểu  Loại PTH có vế trái dư thừa:

- Xét AB

CD, giả sử dư A cần CM B

CD là thành viên của

F: B+={BCD} => đúng dư A. C; C

- Nên F = {B

CD; B

F = {B

D; C

C; B

 Đưa về dạng PTH có vế phải 1 thuộc tính  Loại khỏi F các PTH dư thừa

- Dễ thấy B

D là dư thừa

Vậy phủ tối t hiểu của F = {B

C; C

07/11/2012 11:02 AM 42

Ví dụ 2:

 Cho tập thuộc tính R = {PCHART} và tập phụ thuộc hàm

F như sau: - F = { P → CHART, CH → PART, C → T, A → R }

 Tìm phủ tối thiểu của tập pth

07/11/2012 11:02 AM 43

Ví dụ 3

C, C

A, C

B, A

 Tìm phủ tối thiểu cho tập phụ thuộc hàm: A, B C, B Áp dụng thuật toán trên, chúng ta có thể tìm được các phủ

tối thiểu sau: - Do A B và B C nên A C là thừa. - Do C B và B A nên C A là thừa.

 Bỏ những phụ thuộc hàm thừa đi, ta có {A B, B A,

B C, C B} là một phủ tối thiểu. - Do A B và B C nên A C là thừa. - Do có B C và C A nên B A là thừa. - Do có C A và A B nên C B là thừa.

 Bỏ những phụ thuộc hàm thừa đi, ta nhận được một phủ

tối thiểu khác là {A B, B C, C A}

07/11/2012 11:02 AM 44

Bài tập:

 Bài 1:

B, B

A}.

F; A CD; B

- Cho G = { AB C, A - F = {AB - Tìm phủ tối thiểu của F,G.

 Bài 2:

- Cho F = { A C, BD E, B D, B E, C AD } - Tìm phủ tối thiểu của F

07/11/2012 11:02 AM 45

VII. Khóa của quan hệ

1. Định nghĩa:

U là khoá của R nếu thoả mãn hai điều kiện sau :

- Cho R(A1, …,An) là lược đồ quan hệ; - Tập các thuộc tính U = { A1, A2, .. , An} - Tập các pth F= { f1, f2, .. ,fn} xác định trên R. - K

U (1): K (2): Không tồn tại K'

K mà K'

07/11/2012 11:02 AM 46

 Thông thường có nhiều hơn một khóa tối thiểu trong

một lược đồ quan hệ

 Ví dụ: R = ABC, F = { AB C, C A }.

- AB là một khóa tối thiểu vì: AB ABC thuộc F+ nhưng A

ABC và B ABC không thuộc F+

- BC là một khóa tối thiểu vì: BC ABC thuộc F+ nhưng C

ABC và B ABC không thuộc F+

07/11/2012 11:02 AM 47

 Thuật toán tìm siêu khóa:

- Cho lược đồ quan hệ R = (U,F). Để kiểm tra X U

là siêu khóa, thực hiện:  Tính X+  Kiểm tra nếu X+ = U (X+ chứa tất cả các thuộc

tính của quan hệ) thì X là siêu khóa

 ngược lại nếu X+ U thì X không là siêu khóa

07/11/2012 11:02 AM 48

C, CG

B, A

I, B

H},

 Ví dụ 1: Cho quan hệ R = (A, B, C, G, H, I) và tập PTH F = {A H, CG  Kiểm tra AG là siêu khóa của R?

- Dùng thuật toán tính bao đóng (AG)+. - Nếu (AG)+ chứa tất cả thuộc tính của R thì AG là siêu khóa

của R.

07/11/2012 11:02 AM 49

2. Thuật toán tìm khóa

 Input:

- Lược đồ quan hệ R(A1,A2,…An) - Tập thuộc tính U {A1,A2,…An} - Tập PTH F

 Output: Khóa của quan hệ R  Ý tưởng: Bắt đầu từ tập U vì U+ = U. Ta bớt dần các phần tử của U

để nhận được tập bé nhất mà bao đóng của nó vẫn bằng U.

 Các bước:

- Bước 1: Gán K = U - Bước 2: Loại khỏi K lần lượt từng thuộc tính A mà ( K\A)+ =U - Lặp lại bước 2 đến khi không loại khỏi K được nữa

 Nhận xét: Thuật toán trên chỉ tìm được một khoá trong sơ đồ quan hệ. Nếu cần tìm nhiều khoá, ta thay đổi trật tự loại bỏ các phần tử của K.

07/11/2012 11:02 AM 50

Ví dụ 1:

 cho R = { A,B,C,D,E,G,H,I} và  F= { AC → B, BI → ACD, ABC → D , H→ I , ACE → BCG

, CG → AE }  Tìm khóa ? (1)

07/11/2012 11:02 AM 51

Ví dụ 2:

 Cho LĐQH r( R) với R = ABCDEF và tập PTH

F = {AB C, C D , AD  E, F A} Tìm khóa của lược đồ quan hệ

07/11/2012 11:02 AM 53

3. Thuật toán tìm khóa cải tiến

 Input:

- Lược đồ quan hệ R(A1,A2,…An) - Tập thuộc tính U {A1,A2,…An} - Tập PTH F

 Output: Khóa của quan hệ R  Ý tưởng: Bắt đầu từ tập Left(U) (tập các thuộc tính vế trái) và các thuộc tính không xuất hiện ở cả hai vế

 Các bước:

- Bước 1: Gán K = Left(U) U (U\(Left(U) U Right(U))) - Bước 2: Loại khỏi K phần tử A mà ( K\A)+ =U

 Nhận xét: Thuật toán nhanh hơn do số phần tử cần

xét ít hơn.

07/11/2012 11:07 AM 54

Ví dụ 1:

 Cho LĐQH r( R) với R = ABCD và tập  PTH F = {AB → C, B → D, D → B}  Tìm khóa của lược đồ quan hệ

07/11/2012 11:02 AM 55

* Thuật toán tìm tất cả các khóa

 Một số khái niệm cơ bản:

- Tập thuộc tính nguồn (TN): bao gồm các thuộc tính chỉ xuất hiện ở vế trái, không xuất hiện ở vế phải của pth và các thuộc tính không xuất hiện ở vế trái lẫn vế phải của pth.

- Tập thuộc tính đích (TĐ) : bao gồm các thuộc tính chỉ xuất hiện ở vế phải

không xuất hiện ở vế trái của pth.

- Tập thuộc tính trung gian (TG): Chứa thuộc tính ở vế trái lẫn vế phải của pth.

 Thuật toán:

- Bước 1 Tạo tập nguồn TN và tập trung gian TG - Bước 2: Nếu TG=0(rỗng) thì K=TN, kết thúc. ngược lại qua bước 3. - Bước 3: tìm tất cả tập con Xi của tập trung gian. - Bước 4: tìm siêu khóa Si bằng cách với mọi Xi, nếu (TN U Xi)+=Q+ thì Si = TN U

{Xi} - Bước 5:

 

khỏi

siêu

loại

tập

thì

bỏ

Sj=ABC

tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu với mọi Si, Sj thuộc S nếu Si chứa trong Sj thì loại bỏ tập Sj ra khỏi siêu khóa (VD: Si=AB, khóa) S còn lại chính là tập khóa cần tìm.

07/11/2012 11:02 AM 56