Mở rộng phụ thuộc hàm và phụ thuộc đa trị

Chia sẻ: Nguyễn Minh Vũ | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

50
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

The aim of the paper is to give a generalization of functional and multivalued dependencies in an information system. The definitions are established under the assumption that there are some similarity relations between values of attributes. By using the so-called generalized dependency matrices we develop a necessary and sufficient condition for an extension dependency to be hold. Besides, some computational examples are given for illustration too.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mở rộng phụ thuộc hàm và phụ thuộc đa trị

’ Tap ch´ Tin hoc v` Diˆu khiˆ n hoc, T.23, S.2 (2007), 121— ı e e . . a ` . ’. ˆ ˆ ` ` ˆ MO RONG PHU THUOC HAM VA PHU THUOC DA TRI . . . . . . ` ˆ ˆ ` HO THU` N1 , HOANG THI LAN GIAO2 A . 1 Viˆn e . Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nam o e o e e e . . . a o . . 2 Khoa Cˆng Nghˆ Thˆng Tin, Dai hoc Khoa hoc Huˆ ´ o e o e . . . . Abstract. The aim of the paper is to give a generalization of functional and multivalued dependencies in an information system. The deﬁnitions are established under the assumption that there are some similarity relations between values of attributes. By using the so-called generalized dependency matrices we develop a necessary and suﬃcient condition for an extension dependency to be hold. Besides, some computational examples are given for illustration too. ´ ` a . e o a a o T´m t˘t. B`i b´o d˜ xˆy du.ng c´c dinh ngh˜ mo. rˆng vˆ phu thuˆc h`m v` phu thuˆc da tritrong o a a a a a ıa ’ o . . . . . . . .i n`y du.o.c thiˆt lˆp trˆn co. so. th`.a nhˆn viˆc tˆ n tai c´c ` ´ . ´ ’ u ıa o e a e a e o . a hˆ thˆng thˆng tin. C´c dinh ngh˜ m´ a e o o a . . . . . ` ’ . a . ’ u o ınh. B˘ ng c´ch su.dung c´c ma trˆn phu thuˆc a a a a o quan hˆ tu.o.ng tu. gi˜.a c´c gi´ tri cua nh˜.ng thuˆc t´ e . u a . . . . . . rˆng ch´ng tˆi da ra du.o.c mˆt diˆu kiˆn cˆn v` dudˆ mˆt phu thuˆc mo. rˆng thoa m˜n. Mˆt ’ o ’ o ’ a ’ . u o e e ` o o ` o mo o . a a ’ e . . . . . . . ´ ınh a a a sˆ v´ du minh hoa c˜ ng du.o.c tr` b`y trong b`i b´o. o ı . u . . ’. A ˆ 1. MO D` U ´ Cho A = (U, A) l` mˆt hˆ thˆng thˆng tin v´.i U l` tˆp c´c dˆi tu.o.ng v` A l`tˆp c´c a a o e o o o a a a o aa a . . . ´ . . .i mˆi u ∈ U v` a ∈ A ta k´ hiˆu u(a) l` gi´ tri thuˆc t´ a cua dˆi tu.o.ng u. ˜ ´ ’ o a y e a a . o ınh thuˆc t´nh. V´ o o ı o . . . . ` a ´ Nˆu X ⊆ A l` mˆt tˆp c´c thuˆc t´ ta k´ hiˆu u(X) l` bˆ gˆ m c´c gi´ tri u(a) v´.i a ∈ X . e a o a a o ınh y e a o o a . o . . . . . ´ ´ ´ o a a o e o e o V` vˆy, nˆu u v` v l` hai dˆi tu.o.ng thuˆc U , ta s˜ n´i u(X) = v(X) nˆu u(a) = v(a) v´.i moi ı a e . . . . thuˆc t´ a ∈ X . o ınh . ´ ´ o a a a a a o ınh, th` Y du.o.c goi l` phu thuˆc h`m v`o X ı Nh˘ c lai r˘ ng, nˆu X, Y l` c´c tˆp thuˆc t´ a . ` a e . . a . . . . ´ trˆn U v` k´ hiˆu X → Y nˆu e a y e e . ∀u, v ∈ U : u(X) = v(X) ⇒ u(Y ) = v(Y ). (1) ` u a a Ho.n n˜.a, b˘ ng c´ch d˘t Z = A \ (X ∪ Y ), ta n´i Y l` phu thuˆc da tri v`o X trˆn U v` a o a o e a . . . . a ´ e k´ hiˆu X →→ Y nˆu y e .  t(X) = u(X),  (2) ∀u, v ∈ U : u(X) = v(X) ⇒ ∃t ∈ U : t(Y ) = u(Y ),   t(Z) = v(Z). ’ ´ o a a . o Tuy nhiˆn, trong thu.c tˆ, c´ nh˜.ng phu thuˆc h`m v` phu thuˆc da tri m` c´c d˘ ng th´.c e u . e o u . . . . a a a .c su. nghiˆm ng˘t nh vˆy. Ch˘ng han, cho bang d˜. liˆu ’ ’ e a a a u e a o o ’ trong (1) v` (2) khˆng d`i hoi thu . . . . . . ˜ a ´ o ınh o o a . e e o e ´ o ınh sinh viˆn, d`o tao theo niˆn chˆ, v´.i ba thuˆc t´ l´.p, hotˆn, mˆn hoc. Dˆ thˆy thuˆc t´ e . . e . . ho tˆn l` phu thuˆc da tri v`o thuˆc t´ l´.p, ngh˜ l` moi sinh viˆn trong c`ng mˆt l´.p s˜ o o ınh o ıa a . e u o o e . . . a . . . e a 122 ` ˆ ˆ ` HO THU` N, HOANG THI LAN GIAO A . ´ ` ’ . a a o a o phai hoc c´c mˆn nh nhau. Bˆy gi`., nˆu nh` tru.`.ng da ra mˆt sˆ hoc phˆn tu. chon, v` v´.i o a o e o o . a . . . ´ .p c´ thˆ hoc c´c mˆn kh´c nhau (nhng du.o.c ’ ˜ ` o a mˆi hoc phˆn nh vˆy c´c sinh viˆn trong mˆt l´ o e . a o . a a a e o o . . . ’ ˜ ı u a o y e o ` a o ınh . e o xem l` Tu.o.ng du.o.ng), th` ch´ng ta vˆn c´ l´ do dˆ n´i r˘ ng thuˆc t´ ho tˆn phu thuˆc da a . . . ` oa a a u u a e e o o u u tri v`o thuˆc t´ l´.p, m˘c d` l´c n`y diˆu kiˆn (2) khˆng c`n d´ng n˜.a. R˜r`ng l` trong o ınh o . . . a . .`.ng ho.p n`y c´c dinh ngh˜a nh trˆn khˆng c`n ph` ho.p. M˘t kh´c, trong thu.c tˆ khˆng ´ a a . a a ı e o o u . tru o . . . e o ´ ´ ´ ` ´ u e a o o ınh a o o e a a a hiˆm khi nh˜.ng d˜. liˆu thu nhˆn du.o.c khˆng c`n ch´ x´c nh vˆn c´. Diˆu n`y ch˘c ch˘ n e u . . . . co. so. d˜. liˆu. ´ ’ u e c˜ng l`m cho ch´ng ta khˆng ph´t hiˆn hˆt moi phu thuˆc t` u a u o a e e o u . . . . . ’ ` a a u o e Dˆ g´p phˆn ph´t hiˆn c´c phu thuˆc tiˆm ˆ n trong d˜. liˆu, trong b`i n`y ch´ng tˆi s˜ e o a a e a o ` a e ’ u e . . . . . rˆng cua c´c kh´i niˆm phu thuˆc h`m v` phu thuˆc da ´ . ´ ´ ’ . ’ a a e o a a o o a e a cˆg˘ng da ra mˆt c´ch tiˆp cˆn mo o o a . . . . . . ´ a ’. rˆng n`y du.o.c thiˆt lˆp du.a trˆn mˆt h`m d´nh gi´ dˆ Tu.o.ng tu. gi˜.a a e . e o a a a o tri. C´c kh´i niˆm mo o a e . . . . . u . . a . ´ ´ ’ a . . e o u o a c´c gi´ tri trong bang d˜. liˆu. Khi su. Tu.o.ng tu. gi˜.a hai gi´ tri dat dˆn mˆt m´.c dˆ nhˆ t a a . u e . . . u . . ’ xem hai gi´ tri n`y l` “dˆ ng nhˆ t”. V´.i c´ch tiˆp cˆn n`y, c´c phu ` ´ ´ a a dinh, ch´ng ta c´ thˆ u o e a . a a o a o a e . a . . ’ ’ ´ ´ o o a ’ a o a o a ’ e e thuˆc thu.c ra l` phu thuˆc xˆ p xı. Dˆ kiˆ m ch´.ng mˆt phu thuˆc xˆ p xı n`o d´, ch´ng tˆi o u u o . . . . . . . o a a o c˜ng s˜ su. dung mˆt ma trˆn Tu.o.ng tu. ma trˆn phu thuˆc du.o.c su. dung trong [?]. u e ’ . . . . . ’ . . . . ´ ´ ˆ 2. CAC KHAI NIEM . ˜ ` o a e a . ’ o Cho hˆ thˆng thˆng tin A = (U, A). V´.i mˆ i V ⊆ U v` X ⊆ A, ta goi miˆn gi´ tri cua e o o . . ´ .p V trˆn X l` tˆp ho e a a . . dom(V, X) := {u(X) | u ∈ V }. ´ ´ ´ o ’ e u e Khi V = U ta viˆt dom(X) thay cho dom(U, X) v` ho.n n˜.a, nˆu X = {a}, ta chıviˆt mˆt e a . .n gian: V = dom({a}). ’ c´ch do a a ’ a a e o e a a a . Dˆ mo. rˆng c´c kh´i niˆm phu thuˆc, trˆn c´c tˆp gi´ tri Va , ngo`i quan hˆ b˘ ng nhau e ’ o a e ` . . . . . . a .ng ta gia dinh l` tˆ n tai mˆt h`m Tu.o.ng tu., phan ´nh dˆ gˆn nhau gi˜.a c´c gi´ ` ’ . ’ a a a o . o a o ` a u a thˆng th` o o . . . .o.c goi l` h`m tu.o.ng tu. trˆn tˆp tri. Mˆt c´ch ch´ x´c, mˆt ´nh xa s : Va × Va → [0, 1] du . o a ınh a o a . a a . e a . . . . . ´ ` ’ Va nˆu hai diˆu kiˆn sau thoa m˜n: e e e a . o 1. s(a1 , a2 ) = s(a2 , a1 ), v´.i moi a1 , a2 ∈ Va , . 2. s(a1 , a2 ) = 1 ⇔ a1 = a2 . a . s(a1 , a2 ) du.o.c goi l` m´.c tu.o.ng tu. gi˜.a hai gi´ tri a1 v` a2 . Cho α ∈ [0, 1], hai gi´ tri a1 v` a a . a . . a u . u .o.c goi l` α−tu.o.ng tu., v` k´ hiˆu a1 =α a2 , nˆu s(a1 , a2 ) α. R˜ r`ng khi h`m s chı ´ ’ a2 du . e o a a . a . a y e . a ı, o a ’ nhˆn hai gi´ tri 0 v` 1, th` v´.i moi α > 0, a1 =α a2 khi v` chı khi a1 = a2 . a a . . . ’ a o a o e Cho tˆp thuˆc t´ B = {b1 , b2 , · · · , bm } ⊆ A v` β, γ ∈ dom(B). Khi d´ β v` γ c´ thˆ a o ınh . . .i βi , γi ∈ dom(bi ), 1 i m. Dˆ tu.o.ng tu. gi˜.a β v` γ du.o.c a o o a xem l` hai d˜y (βi )i v`(γi )i , v´ a a . . u . dinh ngh˜ l` gi´ tri: ıa a a . . S(β, γ) = min{s(βi , γi ) | 1 i m}. (3) ’ ’ Bˆy gi`., gia su. γ ∈ dom(B) v` D ⊆ dom(B), ta goi dˆ thuˆc cua γ v`o D l` dˆ tu.o.ng a o a o ’ a a o . o . . . . l´.n nhˆ t gi˜.a γ v´.i c´c gi´ tri trong D . Cuthˆ, gi´ tri n`y du.o.c x´c dinh bo.i: ’ a . a ´ ’ a u a . o a tu o . . a . . e b(γ, D) = max S(γ, β). β∈D ´ ´ e e . u y e Mˆt c´ch tu. nhiˆn, ta tiˆp tuc d`ng k´ hiˆu β =α γ nˆu S(β, γ) α v` n´i r˘ ng β v` o a e a o ` a a . . . .o.ng tu.. C˜ng vˆy, ta n´i γ thuˆc v`o tˆp D v´.i m´.c α, v` k´ hiˆu γ ∈α D , nˆu ´ γ l` α−tu a o a a o a y e e u a o u . . . . . ’. ˆ ˆ ` ` ˆ MO RONG PHU THUOC HAM VA PHU THUOC DA TRI . . . . . . 123 ` ´ ’ ’ a b(γ, D) α. Mˆnh dˆ du.´.i dˆy cho ta mˆt sˆ t´ chˆ t co. ban cua c´c kh´i niˆm n`y m`viˆc a e a a e e e o a o o ınh a . . . . ´ .ng minh c´ thˆ suy ra tru.c tiˆp t`. dinh ngh˜ ’ ´ o e e u . ıa. ch´ u . ` e o Mˆnh dˆ 2.1. Cho B ⊆ A, D ⊆ dom(B), β, γ ∈ dom(B), ta c´ e . 1. S(β, γ) = S(γ, β); S(β, γ) = 1 ⇔ β = γ . 2. 0 b(γ, D) 1; b(γ, D) = 1 ⇔ γ ∈ D . ´ ı 3. Nˆu D ⊆ D ⊆ dom(B), th` b(γ, D) e b(γ, D ). 4. γ ∈α D ⇔ ∃β ∈ D, γ =α β. o ınh: a (tˆn lˆp tr`nh viˆn), b (tr` dˆ chuyˆn mˆn), V´ du 2.1. X´t hˆ thˆng v´.i ba thuˆc t´ ı . e e o o e a ı e ınh o e o . . ´ . . . lˆp tr` su. dung) du.o.c cho trong Bang 1. ’ ınh ’ . c (ngˆn ng˜ a o u . . ’ Ba ng 1 a A A A A A A A A B B b Bc Bc Bc Dip Dip Dip Ms Ms Bc Bc c PASCAL FORTRAN COBOL PASCAL C FORTRAN COBOL PASCAL C PASCAL ’ a ’ ’ ’ a u a . u o ınh Gia su. h`m tu.o.ng tu. gi˜.a nh˜.ng gi´ tri trong t`.ng thuˆc t´ du.o.c cho bo.i c´c bang sau . u . . ’ Bang 2. H`m tu.o.ng tu. trˆn Vb a . e b Bc Dip Ms Bc 1 0.6 0.8 Dip 0.6 1 0.3 Ms 0.8 0.3 1 ’ Ba ng 3. H`m tu.o.ng tu. trˆn Vc a . e c FORTRAN COBOL PASCAL FORTRAN 1 0.9 0.7 COBOL 0.9 1 0.7 PASCAL 0.7 0.7 1 C 0.8 0.6 0.6 C 0.8 0.6 0.8 1 D˘t B = {b, c}, β = (Bc, F OT RAN ), γ = (M s, COBOL) ∈ dom(B), ta c´ a o . S(β, γ) = min{s(Bc, M s), s(F ORT RAN, COBOL)} = min{0.8, 0.9} = 0.8. ` ˆ ˆ ` HO THU` N, HOANG THI LAN GIAO A . 124 M˘t kh´c, v´.i D = {Bc, Dip} ⊆ dom(b) v` M s ∈ dom(b), ta c´ a a o a o . b(M s, D) = max{s(M s, Bc), s(M s, Dip)} = max{0.8, 0.3} = 0.8. a Nhu. vˆy, β =0.8 γ v` M s ∈0.8 D. a . ’. ˆ ´ ` ´ ˆ ˆ INH CHAT 3. PHU THUOC MO RONG VA CAC T´ . . . Du.a trˆn quan hˆ α−tu.o.ng tu. trˆn c´c tˆp gi´ tri, ch´ng ta s˜ da ra c´c kh´i niˆm phu e e a . u e a a e . . . e a a . . . . rˆng. Mˆt c´ch ch´ x´c, ch´ ng ta c´ c´c dinh ngh˜ sau. o a ınh a u o a . ıa thuˆc h`m v` phu thuˆc da tri mo o o a a . o . . ’ . . . Dinh ngh˜ 3.1. Cho X, Y ⊆ A v` α ∈ [0, 1]. Ta n´i Y α−phu thuˆc h`m v`o X trˆn U v` ıa a o o a a e a . . . ´ e k´ hiˆu X →α Y nˆu y e . ∀u, v ∈ U : u(X) = v(X) ⇒ u(Y ) =α v(Y ). ’ Khi α = 1 ta nhˆn du.o.c dinh ngh˜ phu thuˆc h`m nguyˆn thuy. a ıa o a e . . . . . Dinh ngh˜ 3.2. Cho X, Y ⊆ A v` α ∈ [0, 1]. D˘t Z = A \ (X ∪ Y ). Ta n´i Y l` α−phu ıa a a o a . . . ´ ´ a e a y e e o thuˆc da tri v`o X trˆn U , v` k´ hiˆu X →→α Y , nˆu v´.i moi c˘p dˆi tu.o.ng u, v ∈ U sao o a o . . . . . . ` ` ´ ’ cho u(X) = v(X) = x, tˆ n tai dˆi tu.o.ng t ∈ U sao cho t(X) = x, dˆ ng th`.i thoa m˜n mˆt a o o . o o o . . ` e e trong hai diˆu kiˆn sau: . 1. t(Y ) = u(Y ) v` t(Z) =α v(Z), a a 2. t(Y ) =α u(Y ) v` t(Z) = v(Z). ` R˜ r`ng, khi α = 1 hai diˆu kiˆn trˆn tu.o.ng du.o.ng v` c˜ng tu.o.ng du.o.ng v´.i (2), nˆn ta o a a u o e e e e . ’ a e o e e u a . ıa ’ o c˜ng nhˆn du.o.c kh´i niˆm phu thuˆc da tri nguyˆn thuy. T`. c´c dinh ngh˜ mo. rˆng trˆn u a . . . . . . . ’ ˜ kiˆm tra du.o.c r˘ ng, nˆu 0 β ` ´ α 1, th` X →α Y (X →→α Y ) k´o theo X →β Y ı e dˆ e e e . a ˜ ´ ´ (X →→β Y ). Ngo`i ra, mˆt sˆ t´ chˆt cua phu thuˆc h`m v` phu thuˆc da tri vˆn c`n a o o ınh a ’ o a a o . . . . . . a o .i c´c phu thuˆc mo. rˆng. Diˆu d´ du.o.c kh˘ng dinh trong mˆnh dˆ du.´.i dˆy ’ ´ ` ` ’ o o a d´ng dˆi v´ a u o o e o e e o a . . . . . . ` Mˆnh dˆ 3.1. Cho X, Y, Z ⊆ A, α ∈ [0, 1]. Khi d´ e e o . ´ 1. Nˆu Y ⊆ X th` X →α Y. e ı ´ 2. Nˆu X →α Y th` X ∪ Z →α Y ∪ Z. e ı ´ 3. Nˆu X →→α Y th` X →→α A \ (X ∪ Y ). e ı ´ 4. Nˆu X →α Y th` X →→α Y. e ı Ch´.ng minh. u ’ ´ e ´ 1) Hiˆn nhiˆn d´ng v` ta d˜ biˆt, nˆu Y ⊆ X th` X →1 Y. e e u ı a e ı .i moi c˘p dˆi tu.o.ng u, v ∈ U nˆu u(X ∪ Z) = v(X ∪ Z) th` u(Z) = v(Z) v`u(X) = ´ ´ o e ı a 2) V´ . a o . . ı e o a v(X). V` X →α Y nˆn u(Y ) =α v(Y ). Do d´ u(Y ∪ Z) =α v(Y ∪ Z). Vˆy X ∪ Z →α Y ∪ Z. . ’ ´ ’ ’ o a ınh o a o a ı 3) Khˆng mˆ t t´ tˆ ng qu´t, gia su. X ∩ Y = ∅. Khi d´, d˘t Z = A \ (X ∪ Y ), th` . ´ a o Y = A \ (X ∪ Z). T`. X →→α Y suy ra v´.i moi c˘p dˆi tu.o.ng u, v ∈ U m` u(X) = v(X) = x u o a . . . ` ´ th` tˆ n tai dˆi tu.o.ng t ∈ U sao cho t(X) = x v` t(Y ) = u(Y ), t(Z) =α v(Z) ho˘c t(Y ) =α ı o . o a a . . u(Y ), t(Z) = v(Z). Do d´ X →→α Z . o ’. ˆ ˆ ` ` ˆ MO RONG PHU THUOC HAM VA PHU THUOC DA TRI . . . . . . 125 ´ 4) D˘t Z = A \ (X ∪ Y ). Do X →α Y nˆn v´.i moi c˘p dˆi tu.o.ng u, v ∈ U m` u(X) = a e o a . a o . . . ` o a a a v(X) = x ta c´ v(Y ) =α u(Y ). B˘ ng c´ch chon t = v ta nhˆn du.o.c t(X) = x, t(Z) = v(Z) . . . v` t(Y ) =α u(Y ). Vˆy X →→α Y . a a . ’ a a V´ du 3.1. X´t hˆ thˆng A = (U, {X, Y, Z}) du.o.c cho trong Bang 4, c´c h`m tu.o.ng tu. trˆn ı . e e o . . e . ´ .o.c cho trˆn Bang 5. ’ e VY v` VZ du . a ` ´ o ˜ a e ´ / ı o o a u a Khi d´, dˆ thˆy X →→0.8 Y . Nhng X →→0.9 Y v` c´ hai dˆi tu.o.ng t4 v`t5 c`ng b˘ ng . .o.ng v n`o ´ x1 trˆn thuˆc t´ X , m˘t kh´c t4 (Y ) = β1 v`t5 (Z) = γ3 , nhng khˆng c´ dˆi tu e o ınh a a a o o o . a . . ` ’ a o o a a a m` v(X) = x1 dˆ ng th`.i thoa m˜n (v(Y ) = β1 v` v(Z) =0.9 γ3 ) ho˘c (v(Y ) =0.9 β1 v` a . v(Z) = γ3 ). ’ ’ a Ba ng 4 Bang 5. C´c h`m tu.o.ng tu. trˆn VY v` VZ a a . e U t1 t2 t3 t4 t5 t6 t7 t8 X x1 x1 x1 x1 x1 x1 x2 x2 Y β1 β2 β3 β1 β3 β2 β1 β1 Z γ1 γ1 γ2 γ2 γ3 γ3 γ1 γ2 Y β1 β2 β3 β1 1 05 0.7 β2 0.5 1 0.9 β3 0.7 0.9 1 Z γ1 γ2 γ3 γ1 1 06 0.7 γ2 0.6 1 0.8 γ3 0.7 0.8 1 ’ ˆ ˆ 4. KIEM TRA β - PHU THUOC DA TRI . . . ` . ` 4.1. Diˆu kiˆn tˆ n tai - phu thuˆc da tri e e o o . . . . .c [?], dˆ nghiˆn c´.u phu thuˆc da tri, c´c t´c gia d˜ thiˆt lˆp ma ’ ´ . ’ a o e e u e a Trong mˆt b`i b´o tr´ o a a o . . . a a . .a v`o phˆn hoach trˆn c´c gi´ tri thuˆc t´ v` d˜ ch´.ng minh du.o.c r˘ ng, a e a a . o ınh a a u a trˆn phu thuˆc du a a o . . . . ` . . . .c l`moi phˆn tu. cua ma trˆn ` a ’ ’ a X →→ Y d´ ng khi v` chı khi ma trˆn phu thuˆc l` dˆy d˘c, t´ a . u a ’ a o a ` a u a . . . . . ` o a ` o a . o a o a ` a dˆu c´ gi´ tri 1. Trong tru.`.ng ho.p ma trˆn phu thuˆc l` gˆn d˘c (t´.c l` ch´.a phˆn l´.n c´c e a a u a u . . . . . ´ ´ ı u a o o ıt o a o ’ sˆ 1), th` ta c˜ ng nhˆn du.o.c mˆt phuthuˆc da tri xˆ p xı(t´.c l` bo di mˆt sˆ ´ bˆ n`o d´ cua o o o . . a ’ u a ’ . ´ . . . . . ´ ’ ’ a e ’ a bang d˜. liˆu th` nhˆn du.o.c phu thuˆc d´ng). Trˆn co. so. c´c kˆt qua n`y, mˆt thuˆt to´n u e ı a o u o a a e . . . . . . . .ng phu thuˆc v` phu thuˆc xˆ p xı du.a v`o ma trˆn phu thuˆc c˜ng d˜ du.o.c thiˆt ’ ´ ´ o a o a ’ . a a o u e a kiˆm ch´ e u . . . . . . . . ’ o a o o o ’ a u e a . lˆp. Ph´t triˆ n y to.ng d´, o. dˆy ch´ ng ta s˜ xˆy du.ng mˆt ma trˆn c´ vai tr` tu.o.ng tu. trong a a e ´ ’ . . . . o viˆc x´c dinh α−phuthuˆc da tri. e a . . . . . ’ a . e a . Trˆn U ta x´c dinh quan hˆ IND(X) x´c dinh bo.i e . u IND(X)v ⇔ u(X) = v(X); u, v ∈ U. ˜ e a e Dˆ kiˆm ch´.ng du.o.c r˘ ng IND(X) l` mˆt quan hˆ tu.o.ng du.o.ng trˆn U . Ta k´ hiˆu ho c´c l´.p e ’ u a o e y e . a o . ` . . . .o.ng du.o.ng cua U theo quan hˆ n`y bo.i [X] = {X1 , · · · , Xm }. R˜ r`ng, Y →→α Z d´ng trˆn ’ e a ’ o a u e tu . . dˆy ta chı han chˆ viˆc kiˆ m tra phu ’ ´ . ’ . U khi v` chı khi Y →→α Z d´ ng trˆn moi Xi . Do d´, o a a ’ u e o ’ e e e . . ˜ ´ ’ ’ thuˆc trˆn mˆ i Xi cˆ dinh. K´ hiˆu Z = A \ (X ∪ Y ). Gia su. dom(Xi , Y ) = {β1 , β2 , · · · , βp } o e o o . y e . . ˜ v` dom(Xi , Z) = {γ1 , γ2 , · · · , γq }. V´.i mˆi βj , γk ta k´ hiˆu a o o y e . Ej := {t(Z) | t ∈ Xi ; t(Y ) = βj } ⊆ dom(Z); Fk := {t(Y ) | t ∈ Xi ; t(Z) = γk } ⊆ dom(Y ).