Phụ thuộc đơn điệu trong cơ sở dữ liệu mờ theo cách tiếp cận ngữ nghĩa lân cận của đại số gia tử

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

Thêm vào BST

Báo xấu

28
lượt xem 2
download

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

Fuzzy databases with linguistic data based on hedge algebras were introduced, where the evaluation of queries containing linguistic data was transformed into that of traditional queries. On this new viewpoint, in this paper a notion of linear functional dependencies in these databases will be defined reasonably. The problems related to increasingly and decreasingly linear functional dependencies will be considered.

Chủ đề:

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

Lưu

Nội dung Text: Phụ thuộc đơn điệu trong cơ sở dữ liệu mờ theo cách tiếp cận ngữ nghĩa lân cận của đại số gia tử

’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.24, S.1 (2008), 20–31 ı a ` e e . . . . . ’ . ˜. ˆ ˆ ˆ `. PHU THUOC DO N DIEU TRONG CO SO DU LIEU MO . . . . ´ ’ ´ ’. ˆ ´ ˆ ˆ ˜. ˆ THEO CACH TIEP CAN NGU NGH˜ LAN CAN CUA DAI SO GIA TU IA ˆ . . . ˜ ` ˜ ˆ ´ ˆ ˆ ˆ ` NGUYEN CAT HO1 , NGUYEN CONG HAO2 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 Dai hoc khoa hoc Huˆ ´ e . . . Abstract. Fuzzy databases with linguistic data based on hedge algebras were introduced in [1, 6, 15], where the evaluation of queries containing linguistic data was transformed into that of traditional queries. On this new viewpoint, in this paper a notion of linear functional dependencies in these databases will be deﬁned reasonably. The problems related to increasingly and decreasingly linear functional dependencies will be considered. ´ ´ . ´ ’ u e ’ a T´m t˘t. Co. so. d˜. liˆu m`. v´.i ng˜. ngh˜ du.a trˆn c´ch tiˆp cˆn dai sˆ gia tu. d˜ du.o.c nghiˆn c´.u o a o o u ıa . e a e a e u . . o . .o.ng gi´ c´c truy vˆn liˆn quan dˆn thˆng tin ngˆn ng˜. du.o.c du.a ´ ´ o a e e o o u trong [1, 6, 15], trong d´ c´c viˆc lu . a a a e . . ’ ` e ’ o vˆ viˆc thao t´c lu.o.ng gi´ kinh diˆn. Trˆn co. so. d´, trong b`i b´o n`y kh´i niˆm phu thuˆc h`m e . a a e e a a a a e o a . . . . ´ e ´ ’ u e do.n diˆu trong co. so. d˜. liˆu m`. s˜ du.o.c dinh ngh˜ v` nghiˆn c´.u. C´c vˆn dˆ liˆn quan dˆn phu e o e ıa a e u a a ` e e . . . . . ’ thuˆc h`m do.n diˆu t˘ng v` phu thuˆc h`m do.n diˆu giam c˜ ng du.o.c xem x´t. o a e a a o a e u e . . . . . . ’. A ˆ 1. MO D` U ´ e ` a ’ u e ’ Co. so. d˜. liˆu (CSDL) m`. v` c´c vˆ n dˆ liˆn quan d˜ du.o.c nhiˆu t´c gia trong v` ngo`i o a a a ` e a e a a . . .´.c quan tˆm nghiˆn c´.u v` d˜ c´ nh˜.ng kˆt qua d´ng kˆ [1, 6 − 9, 11 − 15]. C´ nhiˆu c´ch ´ ` a ’ a nu o a e u a a o u e e’ o e ´ . ´ . ´ . ´ ’ a tiˆp cˆn kh´c nhau nhu. c´ch tiˆp cˆn theo l´ thuyˆt tˆp m`. [9, 13], theo l´ thuyˆt kha n˘ng e a a a e a y e a o y e .o.ng tu. [8, 12, 14]... Tˆ t ca c´c c´ch tiˆp cˆn trˆn nh˘ m muc d´ n˘m b˘t v` xu. l´ mˆt ` ´ ´ a ’ y o ´ ´ . a ’ a a e a e a a [7], tu . . ıch a . ´ ´ ’ o o c´ch thoa d´ng c´c thˆng tin khˆng ch´ x´c, khˆng ch˘c ch˘n hay nh˜.ng thˆng tin khˆng a a a o o ınh a o a a u ’ ´ ´ ´ e a ` ’ dˆy du. V´.i su. xuˆ t hiˆn c´c thˆng tin m`., khˆng ch˘c ch˘n trong CSDL s˜ l`m thay dˆ i a o . a o o o a a e a o . . liˆu ca trong pham vi c´ ph´p v` ng˜. ngh˜ ’ c˘n ban viˆc thao t´c d˜ e ’ a e a u . u a a u ıa. . . . nh˜.ng u.u diˆ m cua cˆ u tr´c dai sˆ gia tu. (DSGT) [2 − 5], t´c gia trong [1, 6, 15] ’ ´ ´ ’ a ’ ’ Nh` o u e u a . o .a ra v` nghiˆn c´.u CSDL m`. du.a trˆn c´ch tiˆp cˆn cua dai sˆ gia tu., trong d´ ng˜. ´ a ´ ’ ’ d˜ du a a e u o . e a e o u . . o . du.o.c lu.o.ng h´a b˘ ng c´c ´nh xa dinh lu.o.ng cua DSGT. Theo c´ch tiˆp cˆn ´ . ’ a e a ngh˜ ngˆn ng˜ ıa o u o ` a a a . . . . . ’ ’ cua DSGT, ng˜. ngh˜ ngˆn ng˜. c´ thˆ biˆ u thi b˘ ng mˆt lˆn cˆn c´c khoang du.o.c x´c dinh u ıa o u o e’ e’ a o a a a . ` . . . a . ´ ’.i dˆ do t´ m`. cua c´c gi´ tri ngˆn ng˜. cua mˆt thuˆc t´ v´.i vai tr` l` biˆn ngˆn ng˜.. ’ a ’ bo o ınh o a . o u o o ınh o o a e o u . . . Trong b`i b´o n`y ch´ng tˆi s˜ nghiˆn c´.u c´c phu thuˆc h`m do.n diˆu t˘ng v` giam trong a a a u o e e u a o a e a a ’ . . . ´ CSDL m`. v` mˆi quan hˆ gi˜.a ch´ng. o a o e u u . ´ ’. ˆ 2. DAI SO GIA TU . ´ ’ X Cho mˆt DSGT tuyˆn t´ dˆy du AX = (X , G, H, Σ, φ, ≤), trong d´ Dom(X ) = X l` o e ınh ` a o a . . . ’ . ˜. ˆ ˆ ˆ `. PHU THUO C DO N DIEU TRONG CO SO DU LIEU MO . . . . 21 ` ` ’ miˆn c´c gi´ tri ngˆn ng˜. cua thuˆc t´ ngˆn ng˜. X du.o.c sinh tu. do t`. tˆp c´c phˆn thu. e a a . o u ’ o ınh o u u a a a . . . . +, W , c−, 0 } b˘ ng viˆc t´c dˆng tu. do c´c ph´p to´n mˆt ngˆi trong tˆp H, Σ ` 1 sinh G = {1, c a e a o a e a o o a . . . . . .i ng˜. ngh˜ l` cˆn trˆn d´ng v` cˆn du.´.i d´ng cua tˆp H(x), t´.c ’ a a a u v` Φ l` hai ph´p t´ v´ a a e ınh o u ıa a a e u o u . . . ` n t`. sinh l` Σx = supremumH(x) and Φ x = inf imumH(x), trong d´ H(x) l` tˆp c´c phˆ u a o a a a a . ´ ´ ’ ra t`. x, c`n quan hˆ ≤ l` quan hˆ s˘p th´. tu. tuyˆn t´ trˆn X cam sinh t`. ng˜. ngh˜ cua u o e a e a u . e ınh e u u ıa ’ . . .. V´ du, nˆu ta c´ thuˆc t´ Thunhap l` “Tˆ ng thu nhˆp cua cˆng nhˆn trong ’ ´ ’ o ngˆn ng˜ o u ı . e o o ınh a o a a . . ´ a ´ ´p, rˆ t cao, ho.n cao, kha n˘ng cao, rˆ t thˆ p, ´ ’ a a mˆt th´ng”, th` Dom(T hunhap) = { cao, thˆ o a ı a a . .n, kha n˘ng, ´ } v` ≤ mˆt ´ ´ ´ ´ ’ a ’ a 1 kha n˘ng thˆ p, ´ thˆ p,...}, G = {1, cao, W , thˆ p, 0}, H = {rˆ t, ho a ıt a a a ıt a o . . tu. cam sinh t`. ng˜. ngh˜ cua c´c t`. trong Dom(T hunhap), ch˘ng han ta c´ rˆ t ’ ´ quan hˆ th´ . ’ e u u u ıa ’ a u a o a . . ’ a cao > cao, ho.n cao > cao, kha n˘ng cao < cao, ´ cao < cao. ıt ’ Cho tˆp c´c gia tu. H = H − ∪ H + , trong d´ H + = {h1, ..., hp} v` H − = {h−1 , ..., h−q}, a a o a . .i h < ... < h v` h < ... < h , trong d´ p, q > 1. K´ hiˆu f m : X → [0, 1] l` dˆ do v´ 1 o o y e a o p a −1 −q . . . cua DSGT AX . Khi d´ ta c´ mˆnh dˆ sau. ` t´ m` ’ ınh o o o e e . ` ’ Mˆnh dˆ 2.1. Dˆ do t´ m`. f m v` dˆ do t´ m`. cua gia tu. µ(h), ∀h ∈ H, c´ c´c t´ e e o ınh o a o ınh o ’ o a ınh . . . ´ chˆ t sau: a (1) f m(hx) = µ(h)f m(x), ∀x ∈ X. (2) f m(c−) + f m(c+ ) = 1. (3) f m(hi c) = f m(c), trong d´ c ∈ {c− , c+}. o −q≤i≤p, i=0 (4) f m(hi x) = f m(x), x ∈ X . −q≤i≤p, i=0 (5) {µ(hi ) : −q ≤ i ≤ −1} = α v` {µ(hi ) : 1 ≤ i ≤ p} = β, trong d´ α, β > 0 v` a o a α + β = 1. ` ´ ’ ’ ’ X Dinh ngh˜ 2.1. Gia su. AX = (X , G, H, Σ, Φ, ≤) l` mˆt DSGT dˆy du, tuyˆn t´ v` tu. ıa a o a e ınh a . . . .o.ng u.ng l` c´c dˆ do t´ m`. cua ngˆn ng˜. v` cua gia tu. h thoa m˜n ’ ’ ´ a a o o u a ’ a do, f m(x) v` µ(h) tu a ınh o ’ . ´ ` ’ ’ o c´c t´ chˆ t trong Mˆnh dˆ 2.1. Khi d´, ta n´i v l` ´nh xa cam sinh bo.i dˆ do t´ m`. f m a ınh a e e o o aa ınh o . . . ´ ’ a . cua ngˆn ng˜. nˆu n´ du.o.c x´c dinh nhu. sau: o u e o . W (1) v(W ) = κ = f m(c−), v(c− ) = (κ − αf m(c− ) = βf m(c− ), v(c+) = κ + αf m(c+ ), (2) v(hj x) = v(x) + Sgn(hj x){ j o i=Sign(j) µ(hi )f m(x) − ω(hj x)µ(hj )f m(x)}, trong d´ 1 ω(hj x) = [1 + Sgn(hj x)Sgn(hphj x)(β − α)] ∈ {α, β}, 2 v´.i moi j, −q ≤ j ≤ p v` j = 0. o a . − − Φ Φ (3) v(Φ c ) = 0, v(Σc ) = κ = v(Φc+ ), v(Σc+ ) = 1, v` v´.i moi j, −q ≤ j ≤ p v` j = 0, a o a . ta c´: o j−1 v(Φhj x) = v(x) + Sgn(hj x){ i=sign(j) µ(hi )f m(x)} v` a v(Σhj x) = v(x) + Sgn(hj x){ j−1 i=sign(j) µ(hi )f m(x)}. . ’ . ˜. ˆ `. 3. CO SO DU LIEU MO . X´t mˆt CSDL {U ; Const}, trong d´ U = {A1 , A2, ..., An} l` tˆp v˜ tru c´c thuˆc t´ e o o a a u . a o ınh, . . . . liˆu cua CSDL. Mˆi thuˆc t´ A du.o.c g˘n v´.i mˆt miˆn ˜ ´ ` Const l` mˆt tˆp c´c r`ng buˆc d˜ e ’ a o a a a o u . o o ınh a o o e . . . . . . ´ thuˆc t´ cho ph´p nhˆn c´c gi´ tri gi´ tri thuˆc t´ a . o ınh, k´ hiˆu l` Dom(A), trong d´ mˆt sˆ y e a o o o o ınh e a a a . . . . . . ´ m`. lu.u tr˜. trong CSDL hay trong c´c cˆu truy vˆn v` du.o.c goi l` thuˆc t´ m`.. Nh˜.ng o u a a a a a o ınh o u . . . 22 ˜ ` ˜ ˆ ´ ˆ ˆ ˆ ` NGUYEN CAT HO, NGUYEN CONG HAO ´ e’ o ınh e’ thuˆc t´ c`n lai du.o.c goi l` thuˆc t´ kinh diˆ n. Thuˆc t´ kinh diˆ n A du.o.c g˘n v´.i o ınh o . o ınh . . . . a . . a o . A m` miˆn tri cua n´ tˆ n tai th´. ` ` mˆt miˆn gi´ tri kinh diˆ n, k´ hiˆu l` DA . Thuˆc t´ m` o e a . e’ y e a o ınh o a ` e u . . . . ’ o o . . tuyˆn t´ s˜ du.o.c g˘n mˆt miˆn gi´ tri kinh diˆ n D v` mˆt miˆn gi´ tri ngˆn ng˜. LD ´ ` ´ ` e’ o e a . o u tu e ınh e o e a . A a A . . . a . ’ ’ ` n tu. cua mˆt DSGT. Dˆ bao dam t´ nhˆ t qu´n trong xu. l´ ng˜. ngh˜ d˜. ´ ’ ’ ’ ’ y u hay l` tˆp c´c phˆ a a a a o e ınh a a ıa u . . ˜ ´ ´ ´ e’ u e ’ o ’ liˆu trˆn co. so. thˆng nhˆ t kiˆ u d˜. liˆu cua thuˆc t´ m`., mˆi thuˆc t´ m`. s˜ du.o.c g˘n e e a o ınh o o o ınh o e . . . . . a .i mˆt ´nh xa dinh lu.o.ng v : LD → D du.o.c x´c dinh bo.i mˆt bˆ tham sˆ dinh lu.o.ng ´ ’ v´ o o a o o o . A A A . . . . . a . . . . . vˆy, mˆi gi´ tri m`. x cua A s˜ du.o.c g´n mˆt nh˜n gi´ tri thu.c vA (x) ∈ DA du.o.c ˜ a . o ’ ’ o e o a a . . cua A. Nhu a . . a . . ’ ’ xem nhu. gi´ tri dai diˆn cua x. Viˆc d´nh gi´ dˆ tu.o.ng tu. gi˜.a c´c d˜. liˆu cua mˆt thuˆc e e a a o a . . u a u e o o . . . . . . . ´ ’ t´ A du.o.c du.a trˆn kh´i niˆm lˆn cˆn m´.c k cua mˆt gi´ tri m`., v´.i k l` sˆ nguyˆn du.o.ng. ınh e a e a a u o a . o o a o e . . . . . ’ 3.1. Khoang m`. cua kh´i niˆm m`. o ’ a e o . ’ ´ ’ ’ ’ Gia su. thuˆc t´ X c´ miˆn tham chiˆu thu.c l` khoang [a, b]. Dˆ chuˆ n h´a, nh`. o ınh o ` e e e’ a o o . . a . vˆy dˆu l` khoang [0, 1]. Khi ’i tuyˆn t´ ´ o ´ ´ ` ’ ’ mˆt ph´p biˆn dˆ o e e e ınh, ta gia thiˆt moi miˆn nhu a ` a e e e . . . ´t (2) trong Mˆnh dˆ 2.1 cho ph´p ta xˆy du.ng hai khoang m`. cua hai kh´i ` ’ o ’ a d´, t´ chˆ o ınh a e e e a . . − + − + .i dˆ d`i tu.o.ng u.ng l` f m(c−) ’ niˆm nguyˆn thuy c v` c , k´ hiˆu l` I(c ) v` I(c ) v´ o a e e a y e a a o . ´ a . . ` ´ ’ v` f m(c+ ) sao cho ch´ng tao th`nh mˆt phˆn hoach cua miˆn tham chiˆu [0, 1] v` I(c−) a u a o a e e a . . . + `ng biˆn v´.i c− v` c+ , t´.c l` c− ≤ c+ k´o theo I(c− ) ≤ I(c+). Mˆt c´ch ´ o a u a e o a v` I(c ) l` dˆ a a o e . ’ ’ ` a a quy nap, gia su. r˘ ng ∀x ∈ X k−1 = {x ∈ X : x c´ dˆ d`i |x| = k − 1}, ta d˜ xˆy du.ng a o o a . . . ` ´ ’ e a o a u a o du.o.c hˆ c´c khoang m`. {I(x) : x ∈ X k−1 v` |I(x)| = f m(x)} sao ch´ng l` dˆ ng biˆn e . . ˜ ’ ’ a doan [0, 1]. Khi d´, trˆn mˆi khoang m`. I(x), dˆ d`i v` tao th`nh mˆt phˆn hoach cu a . a o a o e o o o a . . . . ´ ` ’ f m(x), cua x ∈ X k−1 , nh`. t´ chˆ t (4) trong Mˆnh dˆ 2.1, ta c´ thˆ xˆy du.ng du.o.c ho o ınh a e e o e’ a . . . . ’ {I(hix) : q ≤ i ≤ p, i = 0, |I(hix)| = f m(hi x)} sao cho ch´ng l` mˆt phˆn hoach cua u a o a . . ´ ’ khoang m`. I(x). C´ thˆ thˆ y ho {I(hix) : q ≤ i ≤ p, i = 0, |I(hix)| = f m(hi x) v` o o e’ a a . ’ ’ x ∈ X k−1 } = {I(y) : y ∈ X k v` |I(y)| = f m(y)} l` mˆt phˆn hoach cua [0, 1]. C´c khoang a a o a a . . ’ n`y goi l` c´c khoang m`. m´.c k. a . a a o u o u 3.2. Dˆ tu.o.ng tu. m´.c k . . ´ ` ’ o a ` ’ Ch´ng ta c´ thˆ lˆ y c´c khoang m`. cua c´c phˆn tu. dˆ d`i k l`m dˆ tu.o.ng tu. gi˜.a c´c phˆn u o e’ a a o ’ a a a o a . . . u a ., ngh˜ l` c´c phˆn tu. m` c´c gi´ tri dai diˆn cua ch´ng thuˆc c`ng mˆt khoang m`. m´.c k l` ` ’ a a a . . e ’ ’ ’ ıa a a a a tu u o u o o u . . . ’ tu.o.ng tu. m´.c k. Tuy nhiˆn, theo c´ch xˆy du.ng c´c khoang m`. m´.c k, gi´ tri dai diˆn cua c´c u e a a . a o u a . . e ’ a . . ` u ’ ’ phˆn t`. x c´ dˆ d`i nho ho.n k luˆn luˆn l` dˆu m´t cua c´c khoang m`. m´.c k. Mˆt c´ch ho.p a o o a o o a ` a u ’ a o u o a . . . ´ ’ a e’ ıa a a u u o a a . . e a l´, khi dinh ngh˜ lˆn cˆn m´.c k ch´ng ta mong muˆn c´c gi´ tri dai diˆn nhu. vˆy phai l` diˆ m y . . . . ’ a a trong cua lˆn cˆn m´.c k. V` vˆy ta dinh ngh˜ dˆ tu.o.ng tu. m´.c k nhu. sau. Ch´ng ta luˆn luˆn u ı a ıa o u o o . . . . . u ˜ . ´ a ´ ´ ` u o ’ ’ gia thiˆt r˘ ng mˆi tˆp H − v` H + ch´.a ´ nhˆ t 2 gia tu.. X´t X k l` tˆp tˆ t ca c´c phˆn t`. dˆ e ` o a a u ıt a e a a a ’ a a . . ’ ’ d`i k. Du.a trˆn c´c khoang m`. m´.c k v` c´c khoang m`. m´.c k +1 ch´ng ta mˆ ta khˆng h` a e a o u a a o u u o ’ o ınh . ` ’ ’ th´.c viˆc xˆy du.ng mˆt phˆn hoach cua miˆn [0,1] nhu. sau: v´.i k = 1, c´c khoang m`. m´.c u e a o a e o a o u . . . . −) v` I(c+). C´c khoang m`. m´.c 2 trˆn khoang I(c−) l` I(h c− ) ≤ I(h − ` ’ ’ 1 gˆ m I(c o a a o u e a p p−1 c ) ≤ ... ≤ I(h2 c− ) ≤ I(h1 c− ) ≤ vA (c− ) ≤ I(h−1 c− ) ≤ I(h−2 c− ) ≤ ... ≤ I(h−q+1 c− ) ≤ I(h−q c− ). ` ` o Khi d´, ta xˆy du.ng phˆn hoach vˆ dˆ tu.o.ng tu. m´.c 1 gˆ m c´c l´.p tu.o.ng du.o.ng sau: o a a e . o a o . . . u − − − − − 0 W S(0) = I(hp c ); S(c ) = I(c ) [I(h−q c )(I(hpc )]; S(W ) = I(h−q c− )(I(h−q c+ ); tu.o.ng tu. . ta c´ S(c+) = I(c+)\[I(h−q c+ ) ∪ I(hp c+ )] v` S(1) = I(hpc+ ). o a ´ 0 1 W Ta thˆ y, tr`. hai diˆ m dˆu m´t vA (0) = 0 v` vA (1) = 1, c´c gi´ tri dai diˆn vA (c−), vA (W ) a u e’ ` a u a a a . . e . . . ’ . ˜. ˆ ˆ ˆ `. PHU THUO C DO N DIEU TRONG CO SO DU LIEU MO . . . . 23 ` a e’ ’ a o W a e v` vA (c+ ) dˆu l` diˆ m trong tu.o.ng u.ng cua c´c l´.p tu.o.ng tu. m´.c 1 S(c− ), S(W ) v` S(c+ ). a ´ . u .o.ng tu., v´.i k = 2, ta c´ thˆ xˆy du.ng phˆn hoach c´c l´.p tu.o.ng tu. m´.c 2. Ch˘ng ’ Tu o o e’ a a a o a . . . . u . m´.c 2, ch˘ng han, I(h c+ ) = (v (Φ h c+ ), v (Σh c+ )] v´.i hai ’ ’ han, trˆn mˆt khoang m` u e o o a o i A Φ i A i . . . . kˆ l` I(hi−1c+ ) v` I(hi+1 c+ ) ch´ng ta s˜ c´ c´c l´.p tu.o.ng du.o.ng dang sau: ` a kho`ng m` e a o a u e o a o . Φ S(hi c+ ) = I(hi c+ )\[I(hphi c+ ) ∪ I(h−q hi c+ )], S(Φhi c+ ) = I(h−q hi−1 c+ ) ∪ I(h−q hi c+ ) v` a + ) = I(h h c+ ) ∪ I(h h c+ ), v´.i i sao cho −q ≤ i ≤ p v` i = 0. B˘ ng c´ch tu.o.ng tu. ` Φ S(Φhi c o a a a p i p i . . vˆy ta c´ thˆ xˆy du.ng c´c phˆn hoach c´c l´.p tu.o.ng tu. m´.c k bˆ t k`. Tuy nhiˆn, trong ’ a ´ y o e a a a o a e nhu a . . . . u ´ ` ´ ´ ’ a o thu.c tˆ u.ng dung ch´ng ta c´ thˆ gi´.i han sˆ gia tu. t´c dˆng liˆn tiˆp lˆn phˆn tu. nguyˆn e e e a ’ u o e’ o . o e . . e ´ . − v` c+ . C´c gi´ tri kinh diˆ n v` c´c gi´ tri m`. goi l` c´ dˆ tu.o.ng tu. m´.c k nˆu c´c ´ ’ thuy c a a a . e’ a a a . o . a o o e a . . u ` m trong mˆt l´.p tu.o.ng tu. m´.c k. e ’ u u a o o gi´ tri dai diˆn cua ch´ng c`ng n˘ a . . . . . u ’ ’ ’ Lˆn cˆn m´.c k cua kh´i niˆm m`.: gia su. phˆn hoach c´c l´.p tu.o.ng tu. m´.c k l` c´c a a u a e o a a o a a . . . . u . u chı v` chı thuˆc vˆ mˆt l´.p tu.o.ng ˜ ’ ’ a ’ khoang S(x1), S(x2), ..., S(xm). Khi d´, mˆi gi´ tri m` o o a . o o ` o o . e . ., ch˘ng han d´ l` S(x ) v` n´ goi l` lˆn cˆn m´.c k cua u v` k´ hiˆu l` Ω (u). ’ ’ tu a o a a o . a a a u a y e a k i . . . . 3.3. C´c quan hˆ dˆi s´nh trong CSDL m`. a e o a o . ´ o ıa Du.a trˆn kh´i niˆm dˆ tu.o.ng tu. nhu. vˆy, c´c quan hˆ dˆi s´nh du.o.c dinh ngh˜ nhu. sau. e a e a a e o a . . . . . . ´ . . ’ ’ a a o u e e a u . a o ınh. Ta n´i o Dinh ngh˜ 3.1. [1] Gia su. t v` s l` hai bˆ d˜. liˆu trˆn tˆp v˜ tru U c´c thuˆc t´ ıa . . . . . ` ´ ’ t[Ai ] =k s[Ai ] v` goi l` ch´ng b˘ ng nhau m´.c k, nˆu mˆt trong c´c diˆu kiˆn sau xay ra: a . a u a u e o a ` e e . . ´ (1) Nˆu t[Ai ], s[Ai ] ∈ DAi th` t[Ai ] = s[Ai ]. e ı ’ ´ (2) Nˆu mˆt trong hai gi´ tri t[Ai ], s[Ai ] l` kh´i niˆm m`., ch˘ng han d´ l` t[Ai ], th` ta e o a . a a e o a o a ı . . . ’ o phai c´ s[Ai ] ∈ Ωk (t[Ai]). ´ ` a a . o (3) Nˆu ca hai gi´ tri t[Ai ], s[Ai ] dˆu l` gi´ tri m`., th` Ωk (t[Ai ]) = Ωk (s[Ai]). e ’ a . e ı ’ ´u diˆu kiˆn t[Ai ] =k s[Ai ] khˆng xay ra ta c´ biˆ u th´.c t[Ai ] =k s[Ai ]. ` ’ Nˆ e e e o o e u . ` e Mˆnh dˆ 3.1. [1] Quan hˆ =k l` quan hˆ tu.o.ng du.o.ng trˆn [0, 1]. e e e a e . . . . t v` s l` hai bˆ d˜. liˆu trˆn tˆp v˜ tru U c´c thu ˆc t´ ’ ’ Dinh ngh˜ 3.2. [1] Gia su ıa a a o u e e a u . a o ınh. Khi . . . . . d´: o ´ (1) Ta viˆt t[Ai ] ≤k s[Ai ], ho˘c t[Ai ] =k s[Ai ] ho˘c Ωk (t[Ai ]) < Ωk (s[Ai]). e a a . . ´ ´ (2) Ta viˆt t[Ai ] k s[Ai ], nˆu Ωk (t[Ai ]) > Ωk (s[Ai]). e e . so. c´c quan hˆ dˆi s´nh v`.a tr` b`y, trong phˆn tiˆp theo ch´ng tˆi nghiˆn c´.u ` ´ Trˆn co ’ a e e o a u ınh a a e u o e u . ´ . liˆu d´ l` phu thuˆc do.n diˆu trong CSDL m`.. mˆt dang phu thuˆc d˜ e o a o . o u . o e o . . . . . . . ˆ ˆ `. 4. PHU THUOC DO N DIEU TRONG CSDL MO . . . ’ o Khi ng˜. ngh˜ cua CSDL du.o.c mo. rˆng, nhu. cho ph´p lu.u gi˜. trong CSDL c´c thˆng tin u ıa ’ e u a o . . . ngh˜ cua c´c phu thuˆc d˜. liˆu c˜ng thay dˆ i, ngh˜ l` phai mo. rˆng ’ ´ ’ ’ o khˆng ch˘c th` ng˜ o a ı u ıa ’ a o u e u o ıa a . . . . . liˆu. Trong thu.c tˆ, ch´ng ta thu.`.ng g˘p c´c tri th´.c dang nhu. nˆu ´ u ´ c´c dang phu thuˆc d˜ e a . o u . o a a u e . . . e . . ’ ´ ’ ng viˆn c´ hoc h`m v` hoc vi c`ng cao th` lu.o.ng c`ng cao; nˆu mˆt tˆp thˆ T1 lao a e o a e mˆt gia o e o . a a . . a ı . . . ’ ’ ’ ’ dˆng ch˘m chı ho.n tˆp thˆ T2 th` Thu nhˆp cua tˆp thˆ T1 cao ho.n tˆp thˆ T2 . Ho˘c trong o a a e ı a ’ a e a e a . . . . . . .`.ng ho.p kh´c nˆu mˆt tˆp thˆ T1 lao dˆng khˆng ch˘m chı ho.n tˆp thˆ T2 th` Thu ’ ’ ´ ’ a e o a e a e ı mˆt tru o o o o a . . . . . . ’ a ’ T1 thˆ p ho.n tˆp thˆ T2. O. dˆy ta khˆng nh` nhˆn mˆi quan hˆ trˆn nhu. ’ ´ ´ nhˆp cua tˆp thˆ a ’ a e a a e o ın a o e e . . . . . ´ ’ l` mˆt luˆt cua mˆt co. so. tri th´.c n`o d´ m` xem nhu. l` mˆi quan hˆ gi˜.a c´c thuˆc t´ a o a ’ o u a o a a o e u a o ınh . . . . . 24 ˜ ` ˜ ˆ ´ ˆ ˆ ˆ ` NGUYEN CAT HO, NGUYEN CONG HAO ´ o a o ınh a ` a trong CSDL, d´ l` thuˆc t´ V˘n b˘ ng, Lu.o.ng, Sˆ ng`y l`m viˆc trong th´ng, T´ ky luˆt o a a e a ınh ’ a . . . .`.ng ho.p trˆn n´ tˆ n tai mˆi quan hˆ khˆng ch´ ` ´ ’ lao dˆng v` Thu nhˆp. Trong ca hai tru o o a a e o o . o e o ınh . . . . ´ e’ o ` o o a e u a . x´c nhu. mˆi quan hˆ cua c´c phu thuˆc kinh diˆ n. Do d´, cˆn c´ mˆt nghiˆn c´.u c´c dang a o e ’ a o . . . . ´ . ´ phu thuˆc d˜. liˆu nhu. thˆ dˆ u.ng dung trong viˆc ph´t hiˆn tri th´.c v` c´c qui t˘c cˆp nhˆt o u e e e’ ´ e a e u a a a a a . . . . . . . . liˆu trong CSDL m` ch´ng tˆi goi l` phu thuˆc do.n diˆu. V` phu thuˆc d˜. liˆu kinh diˆ n d˜ e u . a u o . a o e ı o u e e’ . . . . . . ’ du.o.c xem l` mˆt tru.`.ng ho.p riˆng cua phu thuˆc d˜. liˆu m`., do d´ ch´ng tˆi xem x´t phu o u o e a o o e o u e o . . . . . . . .n diˆu trong ca hai tru.`.ng ho.p kinh diˆ n v` m`.. ’ a o ’ thuˆc do o e o e . . . ’ 4.1. Phu thuˆc do.n diˆu trong CSDL kinh diˆn o e e . . . 4.1.1. Phu thuˆc do.n diˆu t˘ng o e a . . . .i X l` mˆt tˆp con cua U v` t, s l` hai bˆ t`y y trˆn U , ta viˆt t[X] ≤ s[X], nˆu v´.i ´ ´ ’ V´ o a o a a a o u ´ e e e o . . . moi A ∈ X , ta c´ t[A] ≤ s[A]. o . ` Dinh ngh˜ 4.1. Cho U l` mˆt lu.o.c dˆ quan hˆ, r l` mˆt quan hˆ trˆn U v` X, Y ⊆ U. Ta ıa a o e a o e e a . . o . . . . ’ n´i r˘ ng quan hˆ r thoa m˜n phu thuˆc do.n diˆu t˘ng X x´c dinh Y , k´ hiˆu l` X + → Y, o ` a e a o e a a . y e a . . . . . ´ trong quan hˆ r , nˆu ta c´: ∀t, s ∈ r, t[X] ≤ s[X] ⇒ t[Y ] ≤ s[Y ]. e e o . ` V´ du 4.1. Ta x´t lu.o.c dˆ quan hˆ U = {M AGV, T ENGV, SOT IET GIAN G, V U OT GIO} ı . e e . o . .i y ngh˜ M˜ sˆ gi´o viˆn (MAGV), Tˆn gi´o viˆn (TENGV), Sˆ tiˆt giang trong n˘m hoc ´ a ´ ´ ’ v´ ´ o ıa: a o e e a e o e a . .o.t gi`. (VUOTGIO). Quan hˆ Giangday x´c dinh trˆn U cho o. Bang 4.1. ` ’ ’ o e a . e (SOTIET), Tiˆn vu . e . ’ Bang 4.1. Quan hˆ Giangday e . MAGV G1 G2 G3 G4 G5 G6 G7 G8 G9 TENCN Anh ´ Hiˆu e Nhˆn a Giang ’ Hai H` a Thanh Thiˆn e . Nhˆn a SOTIETGIANG 350 450 600 300 370 360 500 650 700 VUOTGIO 120000 3000000 4000000 1000000 1400000 1300000 3500000 4500000 50000000 ´ a ´ ’ Trong quan hˆ Giangday ta thˆ y r˘ ng nˆu SOT IET GIAN G cua gi´o viˆn c`ng l´.n e a ` e a e a o . .n, hay phu thuˆc do.n diˆu t˘ng SOT IET GIAN G+ → V U OT GIO o th` V U OT GIO c`ng l´ ı a o e a . . . d´ng trong quan hˆ Giangday . Thˆt vˆy, ∀t, s ∈ Giangday ta c´ t[SOT IET GIAN G] ≤ u e a a o . . . s[SOT IET GIAN G] ⇒ t[V U OT GIO] ≤ s[V U OT GIO]. ` Goi FA l` ho c´c phu thuˆc do.n diˆu t˘ng trˆn lu.o.c dˆ quan hˆ U. Ta k´ hiˆu FA∗ l` tˆp a . a o e a e e y e a a . . . . . o . . . .n diˆu t˘ng X + → Y m` du.o.c suy dˆn t`. F . ˜ ´ tˆ t ca c´c phu thuˆc do a ’ a o e a a a u A . . . . ’ Dinh l´ 4.1. Trong CSDL v´.i tˆp v˜ tru c´c thuˆc t´ U , ho FA∗ thoa m˜n c´c tiˆn dˆ y o a u . a o ınh a a e ` e . . . . sau: ’ . (1) Phan xa: X + → X ∈ FA∗ . (2)Gia t˘ng: X + → Y ∈ FA∗ ⇒ XZ + → Y Z ∈ FA∗ , v´.i Z ⊆ U. a o ´ a (3) B˘c cˆu: X + → Y ∈ FA∗ , Y + → Z ∈ FA∗ ⇒ X + → Z ∈ FA∗ . a ` ´ C´c tiˆn dˆ (1) - (3) trong Dinh l´ 4.1 l` d´ng d˘n. a e ` e y a u a .