Một mô hình dữ liệu với các truy vấn định lượng

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

Thêm vào BST

Báo xấu

36
lượt xem 2
download

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

We extend the relational model of data to consider classes as attribute values, thereby to allow eary and convernient the representation of quantified queries. Facts regarding object classes can be stored and manipulated in the same way as facts regarding object instances. Our model is upwards compatible with the standard relational model

Chủ đề:

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

Lưu

Nội dung Text: Một mô hình dữ liệu với các truy vấn định lượng

’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.24, S.1 (2008), 42–49 ı a ` e e . . . ´ ´ ˆ ˆ INH DU. LIEU DOI VO.I CAC TRUY VAN DINH LU.O.NG ˜ ˆ ˆ ´ ´ ˆ MOT MO H` . . . . ˜ ˆ NGUYEN KIM ANH Khoa Cˆng nghˆ thˆng tin - Tru.o.ng Dai hoc B´ch khoa H` nˆi o e o ` a a o . . . . Abstract. We extend the relational model of data to consider classes as attribute values, thereby to allow eary and convernient the representation of quantiﬁed queries. Facts regarding object classes can be stored and manipulated in the same way as facts regarding object instances. Our model is upwards compatible with the standard relational model. ´ ’ o e a o T´m t˘t. Ch´ ng tˆi mo. rˆng mˆ h` d˜. liˆu quan hˆ dˆ cho ph´p c´c l´.p nhu. c´c gi´ tri thuˆc o a u o o ınh u e e e a a . o . . . ’ . ’ ˜ a ˜ a ´ . ’.i vˆy, cho ph´p biˆu diˆn c´c truy vˆn dinh lu.o.ng mˆt c´ch dˆ d`ng v` thuˆn tiˆn ho.n. t´ v` bo a ınh a e e e a o a e a a e . . . . . ’ ´ ´ o C´c su. kiˆn xem x´t c´c l´.p dˆi tu.o.ng c´ thˆ du.o.c lu.u tr˜. v` thao t´c giˆng nhu. c´c su. kiˆn xem a . e e a o o e u a a o a . e . . . . ’ . ’ ´ x´t c´c thˆ hiˆn dˆi tu.o.ng. Mˆ h` cua ch´ ng tˆi l` tu.o.ng th´ v´.i mˆ h` quan hˆ chuˆ n. e a e e o o ınh ’ u o a ıch o o ınh e a . . ˆ ´. 1. GIO I THIEU . ´ ’ Ph´p chia l` mˆt ph´p to´n cua dai sˆ quan hˆ thu.c hiˆn mˆt thao t´c kiˆ m tra ch´.a e a o e a e . e o a e’ u . . o . . . . dˆy, mˆt tˆp biˆ u diˆn mˆt nh´m c´c bˆ. Ph´p chia tˆ ng qu´t [5] mo. rˆng ’ ˜ ` ’ o tˆp nhiˆu-mˆt, o a a e o ’ o a e’ e o o a o e o a . . . . . . . .`.ng v´.i viˆc thu.c hiˆn c´c thao t´c kiˆ m tra ch´.a tˆp nhiˆu-nhiˆu. Ph´p to´n ` ` ph´p chia thu o e o e e a a e’ u a e e e a . . . . .o.ng tu. nhu. ph´p kˆt nˆi ch´.a tˆp dˆi v´.i c´c co. so. d˜. liˆu quan hˆ (CSDL) ´ ´ ´ ’ u e e e o u a e n`y c˜ng tu a u o o a . . . . ’ ’. dang chuˆ n 1. Hiˆn tai, khˆng mˆt ph´p chia n`o du.o.c c`i d˘t tu.`.ng minh trong khˆng o . o a e . o o e a o . . . a a . ´ ` ´ e ’ c´c hˆ quan tri CSDL (DBMS), m˘c d` c´c ph´p to´n n`y giai quyˆt nhiˆu vˆ n dˆ u.ng dung a e ’ a u a e a a e e a ` ´ . . . . .c tiˆn. Nhu. ch´ng ta d˜ biˆt, c´c truy vˆ n dinh lu.o.ng, t´.c ´ ´ quan trong c´ y ngh˜ trong thu ˜ o´ ıa e u u a e a a . . . . .i lu.o.ng t`. hay han chˆ sˆ dˆu d`i hoi phai thu.c hiˆn mˆt ph´p chia c`ng ´ ´ ´ e o ’ ’ l` c´c truy vˆ n v´ a a a o u e o ` e o e u . . . . . .i mˆt ph´p kˆt tˆp n`o d´. Nh˜.ng ngu.`.i su. dung b` thu.`.ng hay khˆng chuyˆn nghiˆp ´ . o e e a a o o ’ . ınh o o e e v´ o u . . .`.ng rˆ t kh´ kh˘n v` vˆ t va khi phai biˆ u diˆn c´c truy vˆ n dinh lu.o.ng. Ch´ng tˆi cho ’ ˜ a ´ ´ ´ ’ thu o a o a a a ’ e e a . u o . ` ´ r˘ ng, c´c u.ng dung quan tˆm dˆn lu.o.ng t`. s˜ ng`y c`ng t˘ng lˆn trong mˆt tu.o.ng lai khˆng a a ´ a u e a a a e o o e . . . ´ ’ o xa. B`i b´o n`y dˆ cˆp dˆn viˆc mo. rˆng mˆ h` d˜. liˆu quan hˆ cho ph´p c´c l´.p nhu. c´c a a a ` a e e . e o ınh u e e e a o a . . . . .i vˆy, cho ph´p biˆ u diˆn c´c truy vˆ n dinh lu.o.ng mˆt c´ch dˆ d`ng ˜ a ˜ a ´ gi´ tri thuˆc t´ v` bo a a . o ınh a ’ . e e’ e a . o a e . . . .n. v` thuˆn tiˆn ho a a e . . . phˆn cˆ p du.o.c xem nhu. mˆt k˜ thuˆt cˆ u tr´c d˜. liˆu rˆ t phˆ biˆn. C´c cˆ u tr´c ’ ´ ´ ´ ´ Su a a o y a a u u e a o e a a u . . . . ´ . . ngh˜ dˆi v´.i viˆc quan l´ c´c thˆng tin ph´.c ˜ ´ ´ ’ y a cˆy cung cˆ p mˆt k˜ thuˆt biˆ u diˆn gi`u ng˜ a a o y a e’ e a u ıa o o e o u . . . . phˆn cˆ p c˜ng d˜ du.o.c dˆ nghi trong ng˜. canh thiˆt kˆ CSDL nhu. mˆt k˜ thuˆt ´ ´ ´ tap. Su a a u a e u ’ e e o y a . . . ` . . . ’u diˆn tri th´.c thˆ gi´.i thu.c. Trong b`i b´o n`y, ch´ng tˆi cˆ g˘ng du.a kh´i niˆm phˆn ˜ ´ ´ ´ biˆ e e u e o a a a u o o a a e a . . ´ cˆ p l´.p v`o mˆ h` quan hˆ thˆng qua viˆc cho ph´p c´c l´.p du.o.c su. dung nhu. c´c gi´ tri a o a o ınh e o e e a o a a . . . . ’ . .a v`o kh´i niˆm kh˘ng dinh ˆm ’ thuˆc t´ trong mˆt quan hˆ. D˘c biˆt, ch´ng tˆi c˜ng du a o ınh o e a e u o u a e a . . . . . . . a ’ dˆ cho ph´p c´c ngoai lˆ du.o.c xay ra. Hai ph´p to´n m´.i du.o.c yˆu cˆu l`: ph´p nh´m dˆ e’ e a e e a o e ` a a e o e’ . . . . ´ ´ ˆ ˆ INH DU. LIEU DOI VO.I CAC TRUY VAN DINH LU.O.NG ˜ ˆ ˆ ´ ´ ˆ MOT MO H` . . . . 43 ` ’ e’ gˆp nhiˆu bˆ cua quan hˆ v`o mˆt v`i bˆ do.n v` ph´p mo. nh´m dˆ thu du.o.c mˆt thˆ hiˆn o e o ’ e a o a o a e o o e’ e . . . . . . . . . liˆu thu du.o.c l` tu.o.ng th´ v´.i mˆ h` quan hˆ chuˆ n. ’ ` ’ ’ a ıch o o ınh e a dˆy du cua quan hˆ. Mˆ h` d˜ e a e o ınh u . . . . ` ´ ’ . C´c CSDL dang tˆ n tai c´ thˆ tiˆp tuc du.o.c su. dung theo mˆ h` cua ch´ng tˆi v` y ngh˜ a o . o e’ e . o ınh ’ u o a´ ıa . .`.ng khˆng hˆ thay dˆ i. ’ ` ’ a cua c´c ph´p to´n quan hˆ thˆng thu o e a e o o e o . .u thˆ c´ thˆ dat du.o.c nh`. viˆc khai th´c su. phˆn cˆ p trong biˆ u diˆn d˜. liˆu [1]. ˜ u e ´ ´ ` e o e’ . o e a . a a e’ e Nhiˆu u e . . . ’ lu.u tr˜. chı mˆt bˆ do.n v´.i tˆn cua l´.p dˆ thay thˆ cho nhiˆu bˆ v´.i c´c ’ ´ ` ’ o Ch´ng ta c´ thˆ u o e u ’ o o o e e e e o o a . . . ’ ´ th`nh viˆn cˆ u th`nh nˆn l´.p d´. Mˆ h` d˜. liˆu du.o.c tr` b`y trong b`i b´o n`y c´ thˆ a e a a e o o o ınh u e ınh a a a a o e . . ’ ´ o e a a a a o o ınh e a o . xem nhu. mˆt giao diˆn cung cˆ p c´c thao t´c bˆc cao so v´.i mˆ h` quan hˆ chuˆ n v´.i su. . . . . . cua phˆn cˆ p c´c l´.p dˆi tu.o.ng. Viˆc cung cˆ p c´c thao t´c bˆc cao cho ph´p ngu.`.i ˜ ´ ´ ´ hˆ tro ’ o . a a a o o e a a a a e o . . . .n gian ho.n v´.i ´ thao t´c ho.n v` ho.n n˜.a, ˜ a ´ ’ d`ng c´ thˆ biˆ u diˆn c´c truy vˆ n mˆt c´ch do u o e’ e’ e a o a o ıt a a u . .o.c d´nh gi´ hiˆu qua ho.n. ´ ’ a e c´c truy vˆ n du . a a a . .o.c tr` b`y nhu. sau: phˆn 2 mo. dˆu v´.i mˆt sˆ kh´i niˆm co. ban ` ’ ` ’ Nˆi dung b`i b´o du . o a a ınh a a a o o o a e . ´ . . . liˆu mo. rˆng dˆi v´.i CSDL quan hˆ. Phˆn 3 tr` b`y c´c ´ ` ’ o v` dinh ngh˜ mˆt mˆ h` d˜ e a . ıa o o ınh u . o o e a ınh a a . . . ’ ˜ a ´ dˆi v´.i mˆ h` d˜. liˆu mo. rˆng v` phˆn 4 biˆ u diˆn c´c truy vˆ n dinh ´ o ` ´ . ’ o ph´p to´n dai sˆ o e a o ınh u e a a e e a . o . . ´ ´ ` ’ . ’ o lu.o.ng su. dung c´c ph´p to´n dai sˆ cua mˆ h` d˜. liˆu mo. rˆng. Cuˆi c`ng, phˆn 5 du.a ra a e a o ınh u e o u a . . o ’ . . ´ a mˆt v`i d´nh gi´ v` kˆt luˆn. o a a a a e . . ’ ˆ INH DU. LIEU MO. RONG ˜ ˆ ˆ 2. MO H` . . ´ ´ ’ Tru.´.c tiˆn, ch´ng tˆi nh˘c lai ng˘n gon mˆt sˆ kh´i niˆm co. ban. Cho mˆt tˆp c´c o e u o a . a o o e o a a . . ´ a . . . ˜i thuˆc t´ Ai du.o.c kˆt ho.p v´.i mˆt miˆn Di v´.i ´ . ` thuˆc t´ N = {A1, A2, ..., An}, mˆ o ınh o o ınh e o o e o . . . . ` i = 1...n. K´ hiˆu D ∗ l` t´ Dˆ-c´c cua c´c miˆn. Mˆt quan hˆ x´c dinh trˆn tˆp thuˆc t´ ı e a ıch ` a ’ a e e o e a . e a o ınh . . . . . {A1 , A2 , ..., An} l` mˆt tˆp con n`o d´ cua D ∗ v` mˆt bˆ cua quan hˆ l` mˆt ´nh xa t`. N a o a a o ’ a o o ’ e a o a . . . . . . . u ∗. ´ dˆn D e ´ ’ ’ a Dˆi v´.i mˆt sˆ miˆn cua thuˆc t´ o o o o ` o ınh, d˘c biˆt l` miˆn cua c´c thuˆc t´ kh´a hay c´c a e a ` e o ınh o a . ´ e . . . . .o.ng, ch´ng tˆi x´c dinh mˆt tˆp c´c miˆn con cua n´ u.ng v´.i ´ ` ’ thuˆc t´ dinh danh dˆi tu . o ınh . o u o a . o a a e o ´ o . . . . phˆn nh´m c´c dˆi tu.o.ng du.o.c x´c dinh b´.i thuˆc t´ n`y v` xˆy du.ng mˆt cˆ u ´ ´ mˆt su o . a o a o a . o o ınh a a a o a . . . . . . ´ ´ ` ´ tr´c phˆn cˆ p dˆi v´.i c´c miˆn con hay c´c l´.p dˆi tu.o.ng n`y. Mˆt l´.p, theo ch´ng tˆi, l` u a a o o a e a o o a o o u o a . . .n gian l` ´ ’ a ’ mˆt tˆp C sao cho C ⊆ D(D l` miˆn cua thuˆc t´ o a a ` e o ınh). Ch´ng tˆi s˜ viˆt ∀C hay do u o e e . . . . gi´ tri cua thuˆc t´ n`y trong mˆt bˆ, diˆu n`y c´ ngh˜ l` quan hˆ phai ch´.a moi ’ C nhu a . ’ o ınh a o o ` e a o ıa a e u . . . . . .ng v´.i mˆi gi´ tri x m` x ∈ C v´.i c´c gi´ tri trˆn c´c thuˆc t´ kh´c vˆn gi˜. nguyˆn. ˜ ˜ bˆ u o´ o o a . a o a a . e a o ınh a a u e . . ´ ´ ´ ` ´ Cˆ u tr´c phˆn cˆ p dˆi v´.i mˆt miˆn D l` mˆt cˆ u tr´c cˆy v´.i gˆc cua cˆy ch´ l` miˆn D a u a a o o o e a o a u a o o ’ a ınh a ` e . . ´ . mˆt l´.p tˆ ng qu´t ho.n dˆn c´c l´.p d˘c biˆt ho.n cua n´. C´c gi´ tri thuˆc ’ ´ a o ’ o a v` c´c canh di t` o o o a a . u . a e a e a . o . . . ´ o o ´ ’ o D l` c´c l´.p chı c´ duy nhˆ t mˆt dˆi tu.o.ng v` du.o.c d˘t o. c´c n´t l´ cua cˆy. a a o a a a ’ a u a ’ a . . . . ’ ´ ´ ´ ´ ´ ´ ´ a Bˆ t kˆ mˆt cˆ g˘ng n`o dˆi v´.i viˆc tˆ ng qu´t h´a tri th´.c thˆ gi´.i thu.c tˆ t s˜ thˆ y cˆn a e’ o o a a o o e o a o u e o . . . a e a ` .a v`o c´c ngoai lˆ. Mˆ h` d˜. liˆu cua ch´ng tˆi c˜ng cho ph´p mˆt dang ngoai lˆ thˆng ’ du a a o ınh u e u o u e o . . e . . . . e o . .p mˆi bˆ v´.i mˆt gi´ tri chˆn l´. Mˆt bˆ du.o.c goi l` bˆ du.o.ng hay kh˘ng ˜ . ’ ´ qua viˆc kˆt ho e e . o o o o a . a y o o a o a . . . . . . . .o.ng nˆu gi´ tri chˆn l´ cua bˆ l` ‘true’ (d´ng), ngu.o.c lai, bˆ v´.i gi´ tri chˆn l´ ‘false’ ´ dinh du e a . a y ’ o a u o o a . a y . . . . . .o.c goi l` bˆ ˆm hay kh˘ng dinh ˆm. Tˆ t nhiˆn, c´c kh˘ng dinh ˆm u.ng v´.i c´c ’ ’ ´ (sai) s˜ du . e a a e a a o a . a oa . . a . a ´ . kiˆn khˆng tˆ n tai trong CSDL. V´.i su. c´ m˘t cua c´c kh˘ng dinh ˆm, mˆt bˆ x v´.i c´c ` . ’ ’ a su e o o o . o a a o o o a . . . . a . . ` ´ ’ gi´ tri nguyˆn tˆ du.o.c ch´.a trong mˆt bˆ du.o.ng cua quan hˆ chı l` d´ng khi khˆng tˆ n tai a . e o u o o e ’ a u o o . . . . . 44 ˜ ˆ NGUYEN KIM ANH ’ ’ u ıa o a a e mˆt kh˘ng dinh ˆm ch´.a x. Ch´ng ta c´ thˆ du.a ra mˆt dinh ngh˜ tˆ ng qu´t cho kh´i niˆm o a u o e’ o . . a . . . . liˆu mo. rˆng nhu. sau. ’ o quan hˆ nh´m trong mˆ h` d˜ e e o o ınh u . . . ˜ Dinh ngh˜ 1. Cho mˆt tˆp c´c thuˆc t´ N = {A1, A2, ..., An}, mˆi thuˆc t´ Ai du.o.c ıa o a a o ınh o o ınh . . . . . . ` ´ o o a ´ ´ ´t ho.p v´.i mˆt miˆn Di v` c´ thˆ c´ mˆt cˆ u tr´c phˆn cˆ p HDi v´.i i = 1..n. K´ hiˆu o o e a o e u a a o ı e kˆ . e . . . + + ´t ca c´c n´t cua HDi dˆi v´.i c´c thuˆc t´ Ai c´ cˆ u tr´c phˆn cˆ p, Di = Di ´ o a ´ ´ ’ a u ’ Di l` tˆp tˆ a a a o o ınh o a u a a . . ´ ´ ´ dˆi v´.i c´c thuˆc t´ Ai khˆng c´ cˆ u tr´c phˆn cˆ p, T F = { true , f alse } v` k´ hiˆu D∗ o o a o ınh o o a u a a a ı e . . + ` l` t´ Dˆ-c´c cua c´c miˆn Di v` T F . Mˆt quan hˆ nh´m R x´c dinh trˆn tˆp thuˆc t´ a ıch ` a ’ a e e a o e o a . e a o ınh . . . . a o o ’ e a o a {A1 , A2 , ..., An, T } l` mˆt tˆp con n`o d´ cua D ∗ v` mˆt bˆ cua quan hˆ l` mˆt ´nh xa t`. a o a a o ’ . . . . . u . . ∗ v´.i T ∈ N l` tˆn cua thuˆc t´ ’ sung dˆ lu.u tr˜. gi´ tri chˆn l´ cua bˆ. ’ ´ N ∪ T dˆn D o e a e ’ o ınh bˆ o e u a . a y ’ o . . ´ ´ ’ ´ ´ ´ ˆ ˆ ´. ˆ INH DU. LIEU MO. RONG ˜ ˆ ˆ 3. CAC PHEP TOAN DAI SO DOI VO I MO H` . . . ` ’ Trong phˆn tru.´.c, ch´ng ta d˜ du.a ra kh´i niˆm quan hˆ nh´m, mˆt su. mo. rˆng cua kh´i a o u a a e e o o . ’ o a . . . . .`.ng ho.p tˆ t ca c´c thuˆc t´ cua mˆt quan hˆ nh´m dˆu ` ´ e’ e niˆm quan hˆ kinh diˆ n. Trong tru o e e a ’ a o ınh ’ o e o . . . . . . ´ u ´ khˆng c´ cˆ u tr´c phˆn cˆ p v` gi´ tri chˆn l´ cua moi bˆ trong quan hˆ dˆu l` ’true’ th` quan o o a a a a a . a y ’ o e ` a e ı . . . .i viˆc bˆ sung thˆm thuˆc t´ T nhˆn gi´ tri ’ e o e o ınh a a . hˆ nh´m n`y ch´ l` quan hˆ kinh diˆ n v´ e o a ınh a e e’ o . . . . . .i moi bˆ cua quan hˆ. Ch´ng tˆi goi quan hˆ nh´m n`y l` quan hˆ nh´m nguyˆn ´ ’true’ dˆi v´ o o e u o . e o a a e o e . o ’ . . . . ´ v` quan hˆ nh´m nguyˆn tˆ sau khi bo di thuˆc t´ T l` quan hˆ nguyˆn tˆ. Nhu. vˆy, c´ ´ ´ ’ a o tˆ a o e o e o o ınh a e e o . . . . ’ xem quan hˆ kinh diˆ n l` mˆt tru.`.ng ho.p d˘c biˆt cua quan hˆ nh´m tˆ ng qu´t. Trong ’ a o ’ ’ thˆ e e e o a e e o o a . . . . . . ` ´ phˆn n`y, ch´ng tˆi s˜ du.a ra c´c ph´p to´n dai sˆ trˆn mˆ h` mo. rˆng n`y. Hai ph´p to´n a a u o e a e a o e o ınh ’ o a e a . . .i: ph´p nh´m v` ph´p mo. nh´m l` cˆn thiˆt dˆ dinh ngh˜ c´c ph´p to´n dai sˆ trˆn c´c ´ ´ ’ m´ o e o a e o a ` a e e’ . ıa a e a . o e a .o.ng du.o.ng v´.i mˆt quan hˆ nguyˆn ˜ ’ quan hˆ nh´m. Ch´ y r˘ ng, mˆi quan hˆ nh´m phai tu e o u´ ` a o e o o o e e . . . . .i c´c cˆ u tr´c phˆn cˆ p d˜ cho. C´ ngh˜ l`, c´ mˆt mˆ h` duy nhˆ t v´.i ´ ´ ´ ´ ´ ´ tˆ duy nhˆ t dˆi v´ a a o a o o u a a a o ıa a o o o ınh a o . ´ (c´c gi´ tri thuˆc miˆn gˆc cua thuˆc t´ ` ´ ’ ’ c´c gi´ tri nguyˆn tˆ a a a . e o a . o e o o ınh) thoa m˜n quan hˆ d˜ cho. a e a . . . ’ o ´t kˆ n´ du.o.c thu.c hiˆn e Mˆt ph´p to´n n`o d´ trˆn c´c quan hˆ nh´m s˜ c´ c`ng t´c dˆng bˆ e o e a a o e a e o e o u a o a . . . . . . ´ trˆn c´c quan hˆ nh´m hay trˆn c´c quan hˆ nguyˆn tˆ tu.o.ng du.o.ng. Theo ngh˜ n`y, ng˜. e a e o e a e e o ıa a u . . .`.ng ho.p v´.i c´c quan ’ ’ ngh˜ cua c´c ph´p to´n quan hˆ l` khˆng bi thay dˆ i ngay ca trong tru o ıa ’ a e a e a o o o a . . . hˆ nh´m. e o . Dˆ tr` b`y c´c ph´p to´n trˆn c´c quan hˆ nh´m, tru.´.c tiˆn, ch´ng tˆi tr` b`y mˆt e’ ınh a a e a e a e o o e u o ınh a o . . .n gian cho ph´p dich mˆt tˆp c´c gi´ tri trong mˆt D+ v´.i HD tu.o.ng u.ng ’ thuˆt to´n kh´ do a a a e . o a a a . o o ´ . . . . ’ ’ cua mˆt thuˆc t´ A n`o d´ th`nh c´c l´.p tˆ ng qu´t ho.n trong HD v` cho ph´p c´ ngoai o o ınh a o a a o o a a e o . . . .i c´c loai cˆu truy vˆ n dinh lu.o.ng kh´c nhau, ch´ng ta c´ thˆ su. dung c´c thuˆt to´n ’ ’ . ´ . a a u o e a a a lˆ. V´ a e o . . a . . .i c´c tiˆu ch´ nh´m kh´c nhau. O. dˆy, ch´ng tˆi chı quan tˆm dˆn c´c truy ’ a ´ a ’ dich kh´c nhau v´ a e a o ı o a u o a e . ´ ´ ’ vˆ n v´.i lu.o.ng t`. ∀ v` bo.i vˆy, tiˆu ch´ nh´m cua ch´ng tˆi l` nh´m tˆ t ca c´c n´t du.o.ng a o u a ’ a e ı o u o a o a ’ a u . . ´ ´ ’ ’ c´ c`ng cha lai khi sˆ c´c ngoai lˆ hay c´c n´t ˆm cua ch´ng l` nho ho.n. Trong thu.c tˆ, v´.i o u o a a u a u a . . e . . e o . phˆn nh´m c´c dˆi tu.o.ng ho.p l´, sˆ c´c ngoai lˆ thu.`.ng l` kh´ nho hay thu.c chˆ t l` ´ ´ ´ ’ mˆt su a o . o a o o a a a a . . . y o a . e . . ’. khˆng d´ng kˆ o a e ´ ` ´ Cho mˆt thuˆc t´ A du.o.c kˆt ho.p v´.i miˆn D c´ mˆt cˆ u tr´c phˆn cˆ p HD v` S ⊂ D+ o o ınh e o o a a a a . . . e . o . ´ u .i D+ - k´ hiˆu tˆp tˆ t ca c´c n´t cua HD . v´ o ı e a a ’ a u ’ . . ´ ’ Thuˆt to´n 1. T´ c´c l´.p tˆ ng qu´t cua S ⊂ D+ v` c´c ngoai lˆ. a a ınh a o o a ’ a a . e . . ´ ´ ˆ ˆ INH DU. LIEU DOI VO.I CAC TRUY VAN DINH LU.O.NG ˜ ˆ ˆ ´ ´ ˆ MOT MO H` . . . . 45 ` ´ ´ V`o: Thuˆc t´ A, miˆn D, cˆ u tr´c phˆn cˆ p HD v` S ⊂ D+ . a o ınh e a u a a a . .p (S) v` N gL(S). Ra: T´ L´ ınh o a C´ch t´ a ınh: ´ ´ ’ o o • T` n´t cha chung nho nhˆ t cua S dˆi v´.i HD v` k´ hiˆu n´t n`y l` Rt. ım u a ’ a ı e u a a . ´ a ’ a HD v´.i n´t gˆc l` Rt v` c´c n´t l´ l` c´c n´t ho˘c thuˆc S ho˘c l` c´c • K´ hiˆu cˆy con cu ı e a o u o a a u a a a u a o a a a . . . . ’ a u n´t anh em cua c´c n´t trong S l` T. u a ´ a a a u a o a • D´nh dˆ u c´c n´t l´ thuˆc S l` + . ´ • D´nh dˆ u c´c n´t l´ khˆng thuˆc S l` − a a a u a o o a . + ˜ ´ ´ ’ ’ o o o u ı e a o . a a ı e a • Dˆi v´.i mˆi n´t trong N cua T , k´ hiˆu cˆy con cua T gˆc tai N l` TN v` k´ hiˆu SN l` . . .o.c d´nh dˆ u +, S − l` tˆp c´c n´t l´ du.o.c d´nh dˆ u - dˆi v´.i T . T´ ´ ´ ´ tˆp c´c n´t l´ du . a a u a a a a a o o N ınh . . a u a . N a a + − .o.c goi l` n´t tˆt, ngu.o.c lai du.o.c goi l` n´t ´ x = |SN | v` y = |SN |. Mˆt n´t N c´ x > y du . a o u o . . a u o . . . . a u ` tˆ i. o + − ’ . • D˘t N := Rt. Goi thu tuc Chon (N, TN , SN , SN ) a . . . + − ’ . • Thu tuc chon n´t Chon (N, TN , SN , SN ): . u . + + ´ ´ a ı o 1) Nˆu N l` n´t l´ v` du.o.c d´nh dˆ u + th` L´.p(SN ) = N, N gL(SN ) = ∅ e a u a a . a ’ ´ ´ ´ ´ 2) Nˆu N l` n´t tˆt c´ m con tru.c tiˆp l` N1, N2, ...., Nm v` khˆng mˆ t t´ tˆ ng qu´t, e a u o o e a a o a ınh o a . . N , N , ...., N l` c´c n´t tˆ i v` N , N , ...., N l` c´c n´t tˆt. ` a k+1 2 ´ ’ ’ gia su 1 2 u o u o k a a m a a k k .i x = |S + | v` y = |S − | th` L´.p(S + ) = N, N gL(S +) = ´ ı o Nˆu 1+ 1 yi < m−k+ 1 xi v´ i e o Ni a i Ni N N − ´t th´c. SN v` kˆ a e u + − + Ngu.o.c lai, thu.c hiˆn Chon (Ni, TN i, SN i, SN i) v´.i i = 1..m v` d˘t L´.p(SN ) = ∪m e o a a o . . . . . . 1 + + + L´.p(SN i), N gL(SN ) = ∪m N gL(SN i). o 1 + − ` ´ ´ e 3) Nˆu N l` n´t tˆ i c´ m con tru.c tiˆp l` N1 , N2, ...., Nm, thu.c hiˆn Chon(Ni, TN i, SN i, SN i) e a u o o . e a . . . + + + + v´.i i = 1..m v` d˘t L´.p(SN ) = ∪m L´.p(SN i), N gL(SN ) = ∪m N gL(SN i). o a a o o . 1 1 + + • D˘t L´.p(S) = L´.p(SRt) v` N gL(S) = N gL(SRt) a o o a . ` ´ ` ´ Mˆnh dˆ 1. Cho mˆt thuˆc t´ A du.o.c kˆt ho.p v´.i miˆn D c´ mˆt cˆ u tr´c phˆn cˆ p e e o o ınh e . o e o o a u a a . . . . ´ . + . K´ hiˆu DTu.o.ng (S) l` tˆp tˆ t ca c´c dˆ i tu.o.ng thuˆc c´c l´.p trong S th` ´ a a a ’ a o o a o ı HD v` S ⊂ D a ı e . . ´ . . . .o.ng (S) = DTu.o.ng (L´.p(S)) \ DTu.o.ng (NgL(S)). DTu . o . . .ng minh. Dˆ thˆ y, do cˆ u tr´c phˆn cˆ p H , tˆp tˆ t ca c´c dˆi tu.o.ng thuˆc mˆt l´.p ˜ a ´ ´ ´ ´ Ch´ u e ´ a u a a a a ’ a o o o o D . . . . .p cua tˆp tˆ t ca c´c dˆi tu.o.ng thuˆc c´c l´.p con cua n´. Bo.i vˆy, ch´ng ta c´ ´ ´ ’ a a ’ a o ’ ’ a ch´ l` ho ınh a . o a o o u o . . . . .o.ng (L´.p(S )) = DTu.o.ng (S ) ∪DTu.o.ng (N gL(S)). Ho.n n˜.a, DTu.o.ng (S) v` DTu.o.ng DTu . o u a . . . . ’ (N gL(S)) l` r`.i nhau. Do vˆy, ta c´ diˆu phai ch´.ng minh. a o a o ` e u . . nh´m: Cho quan hˆ nh´m R(X, Y, T ) v´.i c´c thuˆc t´ A ∈ Y du.o.c kˆt ho.p v´.i ´ ’ Ph´p mo e o e o o a o ınh o . . . e . .o.c kˆt ` ´ ´ mˆt miˆn D v` c´ mˆt cˆ u tr´c phˆn cˆ p HD v` c´c thuˆc t´ thuˆc X khˆng du . o e a o o a u a a a a o ınh o o e . . ´ . . .p v´.i mˆt cˆ u tr´c phˆn cˆ p n`o. X ho˘c Y c´ thˆ b˘ ng ∅ nhu.ng XY = ∅. ’ ` ´ ho o o a u a a a a o e a . . ´ . . Y = {A , A , ..., A }, v[Y ] = (C , C , ..., C ) v` mˆt bˆ nguyˆn tˆ t[Y ] = ´ ’ ’ Gia su a o o e o 1 2 k 1 2 k . . .i c ∈ D - miˆn cua A . Ch´ng ta viˆt t[Y ] ∈ v[Y ] nˆu v´.i i = 1..k th` ` ´ ´ o ’ (c1 , c2 , ..., ck) v´ i o e u e e ı i i ´ o ’. nh´m dˆi v´.i quan hˆ nh´m R, k´ hiˆu l` Mo.Nh´m(R) du.o.c dinh ngh˜ ’ o ci ∈ Ci . Ph´p mo e o o e o ı e a ıa . . . . nhu. sau: ’ o Mo.Nh´m(R) = {t[XY ]/∃v ∈ R(t[X] = v[X] ∧ t[Y ] = y ∧ y ∈ v[Y ] ∧ v[T ] = ‘true ∧ ∃v ∈ 46 ˜ ˆ NGUYEN KIM ANH R (v [X] = v[X] ∧ v [T ] = ‘f alse ∧ y ∈ v [Y ]))}. ´ ´ ’ ’ . e ’ a o Ch´ ´: Ph´p mo. nh´m tra lai kˆt qua l` mˆt quan hˆ nguyˆn tˆ thˆng thu.`.ng, quan hˆ chı uy e o e e o o o e ’ . . . .a c´c gi´ tri nguyˆn tˆ v` khˆng ch´.a thuˆc t´ T lu.u gi´ tri chˆn l´ cua bˆ. Ho.n n˜.a, ´ ch´ a u a . e o a o u o ınh a . a y ’ o u . . .Nh´m dam bao mˆi quan hˆ nh´m l` tu.o.ng du.o.ng v´.i mˆt quan hˆ nguyˆn tˆ ˜ ´ ’ ’ ’ ph´p to´n Mo o e a o e o a o o e e o . . . .i c´c cˆ u tr´c phˆn cˆ p d˜ cho. ´ ´ ´ ´ duy nhˆ t dˆi v´ a a a o o u a a a Ph´p nh´m: Cho mˆt quan hˆ nh´m R x´c dinh trˆn tˆp thuˆc t´ U v´.i mˆt thuˆc t´ e o o e o a . e a o ınh o o o ınh . . . . . . ´ ` ´ ´ e . o o e a o o a u a a ı e A ∈ U n`o d´ du.o.c kˆt ho.p v´.i mˆt miˆn D v` c´ mˆt cˆ u tr´c phˆn cˆ p HD . K´ hiˆu R+ a o . . . . ’ ’ l` tˆp c´c bˆ du.o.ng cua R v` R l` tˆp c´c bˆ ˆm cua R. Ph´p nh´m quan hˆ nh´m R theo a a a o a a a a oa e o e o . . . . . ıa thuˆc t´ A, k´ hiˆu l` Nh´mA (R) du.o.c dinh ngh˜ nhu. sau: o ınh ı e a o . . . . Nh´mA (R+ ) = {t/(v ∈ R+ (t[U \T A] = v[U \T A] ∧ ((t[A] = {C/∃C ∈ L´.p (S)} ∧ t[T ] = o o .i c´c v ∈ R+ thoa ’ ‘true ) ∨ (t[A] = {C/∃C ∈ N gL(S)} ∧ t[T ] = ‘f alse )) ∧ S = ∪v[A] v´ a o t[U \A] = v[U \A])}. Nh´mA (R) = Nh´mA (R+ ) ∪ R− . o o ´ ´ ` ´ Ch´ ´: Trong qu´ tr` nh´m, ch´ng ta luˆn cˆ g˘ng nh´m nhiˆu nhˆ t c´ thˆ c´c l´.p con uy a ınh o u o o a o e a o e’ a o .o.ng th`nh mˆt l´.p tˆ ng qu´t ho.n v´.i viˆc chˆ p ’ ´ e ´ ’ a o xuˆ t hiˆn trong thuˆc t´ A cua c´c bˆ du a o ınh a o o o a o e a . . . . . ’ e a a o ´ ngoai lˆ khˆng d´ng kˆ nˆn tˆp c´c bˆ thuˆc Nh´mA (R+ ) v` R− l` r`.i nhau. nhˆn mˆt sˆ a o o a e o o a a o . . . e o . . . . ` ` ’ ’ Mˆnh dˆ 2. Ph´p to´n Nh´m bao to`n nˆi dung thˆng tin cua quan hˆ nh´m ban dˆu. e e e a o a o o e o a . . . ´ ´ C´ ngh˜ l` v´.i mˆt quan hˆ nh´m R v` mˆt thuˆc t´ A c´ mˆt cˆ u tr´c phˆn cˆ p th` o ıa a o o e o a o o ınh o o a u a a ı . . . . . .Nh´m(Nh´mA(R)) = Mo.Nh´m(R). ’ ’ o Mo o o ´ ’ ’ o Ch´.ng minh. Theo dinh ngh˜ cua c´c ph´p to´n Mo.Nh´m, Nh´m v` t´ d´ng d˘n cua u ıa ’ a e a o a ınh u a . .o.c kh˘ng dinh trong mˆnh dˆ 1, mˆi bˆ x v´.i c´c gi´ tri nguyˆn tˆ thuˆc ˜ o ’ ´ ` a a . e o o Thuˆt to´n 1 du . a a e e o . o a . . . . ’.Nh´m(Nh´mA (R)) c˜ng thuˆc Mo.Nh´m(R) v` ngu.o.c lai. ’ o Mo o o u o a . . . ´ ’ Hˆ qua 1. Cho R l` quan hˆ nh´m nguyˆn tˆ v` mˆt thuˆc t´ A c´ mˆt cˆ u tr´c phˆn e a e o e o a o o ınh o o a u a . . . . ´ . .i R th` Mo.Nh´m(Nh´mA(R)) = R’. ´ ´ ´ cˆ p. Goi R’ l` quan hˆ nguyˆn tˆ dˆi v´ a a e e o o o ı ’ o o . . ´ ` e u e Hˆ qua 1 du.o.c suy ra tru.c tiˆp t`. Mˆnh dˆ 2. e ’ e . . . . ´ ´ Ph´p kˆt nˆi tu. nhiˆn: Cho hai quan hˆ nh´m R(U ) v` S(V ) v´.i U ∩ V = Y Z v` Y = e e o . e e o a o a . .o.c kˆt ho.p v´.i mˆt miˆn Di v` c´ mˆt cˆ u tr´c ´ . ` ´ {A1 , A2 , ..., Ak}. C´c thuˆc t´ Ai ∈ Y du . e a o ınh o o e a o o a u . . . ´ ´ ´ phˆn cˆ p HDi, i = 1..k. C´c thuˆc t´ thuˆc Z khˆng du.o.c kˆt ho.p v´.i mˆt cˆ u tr´c phˆn a a a o ınh o o e . o o a u a . . . . ´ ´ ´ cˆ p n`o. Z c´ thˆ b˘ ng ∅ v` k c´ thˆ b˘ ng 0. Ph´p kˆt nˆi tu. nhiˆn cua 2 quan hˆ nh´m R a a o e’ ` a a o e’ ` a e e o . e ’ e o . .o.c dinh ngh˜ nhu. sau: v` S , k´ hiˆu l` R ∗ S du . . a ı e a ıa . R ∗ S = {t[U V ]/∃u ∈ R∃v ∈ S(t[U \Y T ] = u[U \Y T ] ∧ t[V \Y T ] = v[V \Y T ] ∧ (t[Ai ] = ’ a u[Ai ] ∩ v[Ai], i = 1..k) ∧ t[T ] = u[T ] ∗ v[T ]}, o. dˆy ‘true ∗ ‘true = ‘true v` ‘true ∗ ‘f alse = a ‘f alse ∗ ‘true = ‘f alse . ´ ´ Ph´p chiˆu: Cho quan hˆ nh´m R(X, Y, T ) v´.i c´c thuˆc t´ A ∈ Y du.o.c kˆt ho.p v´.i mˆt e e e o o a o ınh o o . . . e . . .o.c kˆt ho.p v´.i ` ´ ´ ´ miˆn D v` c´ mˆt cˆ u tr´c phˆn cˆ p HD v` c´c thuˆc t´ thuˆc X khˆng du . e . e a o o a u a a a a o ınh o o o . . . ´ a ´ mˆt cˆ u tr´c phˆn cˆ p n`o. X v` Y c´ thˆ b˘ ng ∅. Ch´ng tˆi dinh ngh˜ hai ph´p chiˆu o a u a a a o e’ ` a u o . ıa e e . ´ ´u: Π0 l` ph´p chiˆu v´.i tˆp thuˆc ´ o a trˆn quan hˆ nh´m R phu thuˆc v`o tˆp thuˆc t´ chiˆ e e o o a a o ınh e a e e o . . . . . . . ´u chı liˆn quan dˆn c´c thuˆc t´ khˆng c´ cˆ u tr´c phˆn cˆ p v` Π1 l` ph´p chiˆu ´ a ´ ´ a ´ ’ e t´ chiˆ ınh e e o ınh o o a u a a a e e . ´ ´ ´ ´ v´.i tˆp thuˆc t´ chiˆu c´ liˆn quan dˆn c´c thuˆc t´ c´ cˆ u tr´c phˆn cˆ p. o a o ınh e o e e a o ınh o a u a a . . .