Truy vấn cơ sở dữ liệu quan hệ sử dụng đồ thị khái niệm.

Chia sẻ: Bút Màu | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

63
lượt xem 5
download

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

Truy vấn cơ sở dữ liệu quan hệ sử dụng đồ thị khái niệm. Và khi hệ thống vận hành, thay đổi thì điều khiển học dùng các khái niệm của mình là sự phát triển, tự tổ chức, sự tăng trưởng, xuất hiện mới (emergence), sự học tập, sự thích nghi và tiến hóa....

Chủ đề:

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

Lưu

Nội dung Text: Truy vấn cơ sở dữ liệu quan hệ sử dụng đồ thị khái niệm.

. . a ` e e’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.22, S.3 (2006), 275—281 ı . ´ ˆ ´ . ’ . ˜. ˆ ˆ TRUY VAN CAC CO SO DU LIEU QUAN HE . . ’. DUNG DO THI KHAI NIEM SU . ` ˆ ´ ˆ . . ˜ ˆ NGUYEN KIM ANH Khoa Cˆng nghˆ thˆng tin, Tru.`.ng Dai hoc B´ch khoa H` Nˆi o e o . o . . a a o. Abstract. This paper presents a formalism, called conceptual graphs, that can represent relational database schemas and queries according to the user’s view and access data according to the system’s view. T´m t˘t. B`i b´o tr` b`y mˆt hˆ h` th´.c, du.o.c goi l` dˆ thi kh´i niˆm, n´ c´ kha n˘ng biˆ u o ´ a a a ınh a o e ınh u . . . ` . a o . a e . o o ’ a e’ ˜ a e . dˆ co. so. d˜. liˆu quan hˆ v` c´c truy vˆ n trˆn co. so. d˜. liˆu n`y ph` ho.p v´.i c´ch nh` diˆn c´c so o ` ’ u e e a a ´ a e ’ u e a u . o a ın . . . cua ngu.`.i d`ng v` truy nhˆp d˜. liˆu ph` ho.p v´.i c´ch nh` cua hˆ thˆng. ’ o u a a u e . . u . o a ın ’ e o . ´ ´. ˆ 1. GIO I THIEU . Trong lich su., c´c hˆ co. so. d˜. liˆu quan hˆ (CSDLQH) du.o.c biˆt l` mˆt hˆ hˆ tro. mˆt . ’ a e . ’ u e . e. . ´ . . ˜ e a o e o . o . mˆ h` d˜ e o ınh u . . liˆu do.n gian ho.n so v´.i c´c mˆ h` d˜. liˆu kh´c v` c´ kha n˘ng cho ph´p do.n ’ o a o ınh u e a a o ’ a e . gian h´a giao diˆn ngu.`.i su. dung. C´c quan hˆ l` mˆt giao diˆn tˆt dˆi v´.i c´c nh` lˆp tr` ’ o e . o ’ . a e a o . . . ´ ´ e o o o a a a. ınh chuyˆn nghiˆp v` c˜ ng c´ thˆ e e a u . o e ’ du.o.c su. dung bo.i nh˜.ng ngu.`.i d`ng khˆng chuyˆn quen thuˆc . ’ . ’ u o u o e o. v´.i c´c quy u.´.c v` c´ch biˆu diˆn d˜. liˆu cua c´c CSDLQH. Mˆt sˆ ngˆn ng˜. truy vˆ n, o a o a a e’ ˜ u e e . ’ a o o o . ´ u ´ a ch˘ ng han nhu. SQL hay QBE, d˜ du.o.c thiˆt kˆ cho nh˜.ng ngu.`.i d`ng khˆng chuyˆn du.o.c a’ . a . ´ ´ e e u o u o e . d`o tao dˆ a . e ’ khai th´c CSDL. Tuy nhiˆn, nh˜.ng ngu.`.i su. dung b` thu.`.ng khˆng phai nh` a e u o ’ . ınh o o ’ a lˆp tr` c˜ng khˆng biˆt c´c quy u.´.c v` c´ch biˆ u diˆn d˜. liˆu trong CSDLQH s˜ cˆn mˆt a . ınh u o ´ e a o a a e’ ˜ u e e . e ` a o. th`.i gian huˆ n luyˆn m´.i c´ thˆ khai th´c du.o.c c´c CSDL quan hˆ. o a´ e . o o e ’ a . a e . Trong [5], J. F. Sowa d˜ dˆ cˆp dˆn kha n˘ng su. dung CG dˆ hˆ tro. mˆt giao diˆn tu. a ` a e e . ´ ’ a ’ . ’ ˜ e o . o . e . . .`.i d`ng, tuy nhiˆn, han chˆ cua CG l` chı v´.i mˆt sˆ cˆu truy ´ nhiˆn v` thˆn thiˆn cho ngu o u e a a e . e . e ’ a ’ o . ´ o o a vˆ n v´.i lu.o.ng t`. ngˆm dinh l` ‘tˆ n tai’. Trong thu.c tˆ, dˆi v´.i mˆt CSDL quan hˆ, c´c cˆu ´ a o . u ` a . a o . ` ´ ´ . e o o o . e a a . a´ truy vˆ n thu o .`.ng kh´ da dang v` ph´.c tap v´.i su. xuˆ t hiˆn cua c´c lu.o.ng t`. ‘tˆ n tai’, ‘moi’ a a u . o . a´ e ’ a u o .` . . . . v` c´c tˆp gi´ tri cu thˆ cua mˆt thˆng tin n`o d´ trong CSDL. Mo. rˆng v` ph´t triˆ n mˆt a a a . a . . e ’ ’ o . o a o ’ o. a a e’ o. sˆ y tu.o.ng t`. [2, 3, 5], ch´ng tˆi du.a ra c´c dinh ngh˜ mo. rˆng cho CG, c´c luˆt thiˆt lˆp ´ o´ ’ u u o a . ıa ’ o . a a. ´ . e a CG d´ng d˘n, ph´p dich mo. rˆng c´c CG du.´.i dang logic vi t`. cˆ p mˆt (FOL) dˆ hˆ tro. u ´ a e . ’ o . a o . . u a ´ o . ’ ˜ e o . . e’ ˜ a . e a o e ` ´ ’ a viˆc biˆ u diˆn c´c dang truy vˆ n c´ thˆ b˘ ng CG. Nˆi dung b`i b´o: Muc 2 l` mˆt sˆ kh´i e o. a a . . ´ a o o a niˆm co ’ . ban du.o.c su. dung trong b`i b´o, Muc 3 l` c´c mo. rˆng dˆi v´.i CG v´.i kha n˘ng ´ o e. . ’ . a a . a a ’ o . o o ’ a truy vˆ n mˆt CSDL quan hˆ, Muc 4 tr` b`y ph´p dich mo. rˆng c´c CG du.´.i dang logic vi a´ o. e . . ınh a e . ’ o. a o . . t`. cˆ p mˆt. Muc 5 du.a ra mˆt sˆ v´ du minh hoa, cuˆi c`ng Muc 6 du.a ra c´c kˆt luˆn cua u a ´ o . . . ´ o o ı . . ´ o u . a e ´ a ’ . b`i b´o. a a
276 ˜ ˆ NGUYEN KIM ANH ˆ ´ ˆ ´ ˆ . ’ 2. MOT SO KHAI NIEM CO BAN . . 2.1. So. dˆ thu.c thˆ - liˆn kˆt ` o . e’ e ´ e Trong thu.c tˆ, khi thiˆt kˆ CSDLQH cho mˆt x´ nghiˆp, ch´ ng ta . ´ e ´ e ´ e o . ı e . u thu o .`.ng su. dung mˆt so. dˆ thu.c thˆ - liˆn kˆt biˆ u diˆn cˆ u tr´c logic tˆ ng thˆ cua CSDL ’ . o ` o . e’ e e ´ e ’ ˜ a e ´ u o’ e’ ’ . dˆi v´.i x´ nghiˆp n`y. C´c th`nh phˆn co. ban cua mˆt so. dˆ thu.c thˆ - liˆn kˆt l` c´c thu.c ´ o o ı e a . a a ` a ’ ’ o . ` o . e’ e e a a ´ . thˆ , c´c thuˆc t´ v` c´c liˆn kˆt. Mˆt tˆp thu.c thˆ (goi do.n gian l` thu.c thˆ) k´ hiˆu mˆt ’ e a o ınh a a e e . ´ o a . . . ’ e . ’ a . ’ e y e . o. tˆp c´c dˆ a a o . ´i tu.o.ng c´ c´c t´ chˆ t chung v` du.o.c g´n mˆt tˆn goi l` mˆt danh t`.. C´c tˆp . o a ınh a ´ a . a o e . a o . . u a a . thu.c thˆ du.o.c x´c dinh thˆng qua mˆt tˆp c´c t´ chˆ t, du.o.c goi l` c´c thuˆc t´ . e’ . a . o o a a ınh a . . ´ . . a a o ınh, dˆ phan . e’ ’ ´nh c´c d˘c tru a a a .ng cua tˆp thu.c thˆ. Mˆ i mˆt thuˆc t´ du.o.c g´n mˆt tˆn goi c˜ng l` mˆt ’ a e’ ˜ o o o ınh . . . . . . a o e . u . a o. danh t`.. Mˆt tˆp liˆn kˆt (goi do.n gian l` liˆn kˆt) k´ hiˆu mˆt tˆp c´c bˆ m` mˆi bˆ biˆ u u o a e e . . ´ . ’ a e e ´ y e . o a a o a o o e . . . ˜ . ’ diˆn mˆt su. kˆt ho.p gi˜.a c´c thu.c thˆ du.o.c k´o theo bo.i liˆn kˆt n`y. Mˆi liˆn kˆt du.o.c g´n ˜ e o . e . . ´ u a . e’ . e ’ e e a´ ˜ o e e ´ . a mˆt tˆn goi l` mˆt dˆng t` o e . a o o u.. . . . ` 2.2. Dˆ thi kh´i niˆm o . a e . Mˆt CG ([3, 5]) l` mˆt dˆ thi c´ hu.´.ng hai phˆn h˜.u han v´.i c´c n´t kh´i niˆm v` c´c o . a o o . o o . ` `a u . o a u a e . a a n´t quan hˆ kh´i niˆm. Trong c´c dˆ thi n`y, c´c n´t kh´i niˆm biˆ u diˆn c´c thu.c thˆ , c´c u e a e . . ` a o . a a u a e . e’ ˜ a e . ’ e a o ınh a ’ a e e . ´ o a u thuˆc t´ v` ca c´c liˆn kˆt, c`n c´c n´t quan hˆ kh´i niˆm chı ra c´c n´t kh´i niˆm c´ e a e . . ’ a u a e . o quan hˆ v´e o .i nhau nhu. thˆ n`o, thˆng thu.`.ng c´c n´t n`y x´c dinh c´c quan hˆ hay vai tr` e’ a o o a u a a . a e o . . ng˜. ngh˜ cua mˆt n´t kh´i niˆm n`y dˆi v´.i n´t kh´i niˆm kia. Mˆi n´t kh´i niˆm du.o.c v˜ u ıa ’ o u . a e . ´ a o o u a e . ˜ o u a e . . e trong mˆt hˆp v` du . a o o a .o.c g´n nh˜n bo.i mˆt c˘p gˆ m kiˆu kh´i niˆm v` tham chiˆu kh´i niˆm. a ’ o a o ` e’ a e a ´ e a e . . . . . . Mˆ i n´t quan hˆ kh´i niˆm du.o.c v˜ trong mˆt h` tr`n du.o.c g´n nh˜n bo.i mˆt kiˆu quan ˜ o u e a e . . . e o ınh o . . a a ’ o e . ’ ’. a u o ’ e a hˆ kh´i niˆm. O dˆy, ch´ ng tˆi chı x´t c´c quan hˆ kh´i niˆm l` c´c quan hˆ hai ngˆi. Trong e a e e a e a a e o . . . . . dang biˆu diˆn v˘n ban, c´c kh´i niˆm v` quan hˆ kh´i niˆm c´ thˆ du.o.c biˆu diˆn mˆt c´ch . e ’ ˜ a e ’ a a e . a e a e . . o e ’ . e’ ˜ e o a . tu .o.ng u.ng trong c´c c˘p ngo˘c vuˆng v` ngo˘c tr`n. ´ a a a o a a o . . . Tru.`.ng tham chiˆu kh´i niˆm ([4]) c´ thˆ nhˆn mˆt trong c´c gi´ tri sau: o e´ a e . ’ . o e a o . a a . o a . ´ . ’ ˜ e ’ o a e a o . o . e’ ’ • Mˆt d´nh dˆ u k´ hiˆu ∗ hay ∃ biˆu diˆn mˆt c´ thˆ n`o d´ thuˆc kiˆu cua kh´i niˆm. a y e e a e . . ´ ’ ’ ˜ e ’ o a e . e . ’ o . e’ ’ • Mˆt d´nh dˆ u c´ thˆ biˆu diˆn mˆt c´ thˆ cu thˆ thuˆc kiˆ u cua kh´i niˆm. o a a a e e a e . o a . ´ . ’ ’ ˜ e o a a a e a . . . ’ o. e’ ’ • Mˆt d´nh dˆ u tˆp c´ thˆ biˆu diˆn mˆt tˆp c´c c´ thˆ x´c dinh thuˆc kiˆ u cua kh´i niˆm. a a a e e a e . o a . ´ a y e . e’ ˜ e o a o . . ` o a. ` a e a o e ’ • Mˆt d´nh dˆ u k´ hiˆu {∗} biˆu diˆn mˆt tˆp gˆ m khˆng ho˘c nhiˆu c´ thˆ n`o d´ thuˆc o . ’ ’ kiˆu cua kh´i niˆm. e a e . . ´ a y e . e’ ˜ a a ’ a a e e . ´ ’ o . e’ ’ • Mˆt d´nh dˆ u k´ hiˆu ∀ biˆu diˆn tˆp tˆ t ca c´c c´ thˆ thuˆc kiˆ u cua kh´i niˆm. o a a e . 2.3. Su. phˆn cˆp kiˆ u kh´i niˆm . a a ´ e’ a e . C´c kiˆu kh´i niˆm du.o.c du.a v`o trong mˆt d`n m` quan hˆ th´. tu. bˆ phˆn ( {tˆp con kh´c rˆ ng c´c c´ thˆ a´ a a a e ’ a a o ˜ a a e ’ . . . ’ a a e ’ cua tˆp c´ thˆ}> ∃(∗) > {∗}. .
´ . ’ . ˜. ˆ ˆ ’. . ` ˆ ´ . ˆ . ´ ˆ TRUY VAN CAC CO SO DU LIEU QUAN HE SU DUNG DO THI KHAI NIEM . . 277 ’. ˆ ´ ˆ ´. ˆ ´ ˆ ´ 3. MO RONG CG DOI VO I VIEC TRUY VAN CAC CSDLQH . . 3.1. So. dˆ kh´i niˆm (SDKN) ` a o e . .c tˆ, khˆng phai tˆt ca c´c tˆ ho.p cua c´c kh´i niˆm v` quan hˆ kh´i niˆm dˆu c´ ’ Thu e. ´ o ´ ’ a ’ a o . ’ a a e . a e a e . . ` o e ngh˜ do vˆy, ban dˆu, ngu.`.i thiˆt kˆ CSDL phai c´ c´ch khai b´o c´c tˆ ho.p nhˆ t dinh ıa, a . ` a o ´ ´ e e ’ o a a a o . ’ ´ a . du.o.c thiˆt lˆp tˆt. C´c CG du.o.c thiˆt lˆp tˆt (CG-TLT) c˜ng giˆng nhu. c´c cˆng th´.c . ´ . e a o ´ a . ´ . e a o ´ u ´ o a o u .o.c thiˆt lˆp tˆt trong logic k´ hiˆu hay c´c cˆu d´ng v˘n pham trong ngˆn ng˜. tu. nhiˆn. du . ´ a o e . ´ y e a a u a o u . e . . Trong phˆn n`y, ch´ng tˆi s˜ chı ra r˘ ng, c´c ng˜. ngh˜ du.o.c phan ´nh trong so. dˆ thu.c `a a u o e ’ ` a a u ıa . ’ a ` . o thˆ - liˆn kˆt d˜ o. dang chuˆn 3 c´ thˆ du.o.c n˘m b˘t trong SDKN thˆng qua mˆt ph´p e’ ´ e e a ’ . a’ o e ’ . ´ a ´ a o o . e dich t`. so. dˆ thu.c thˆ - liˆn kˆt th`nh c´c CG-TLT. . u ` o . e’ e e ´ a a SDKN bao gˆ m mˆt tˆp c´c CG-TLT du.o.c suy ra t`. mˆt so. dˆ thu.c thˆ - liˆn kˆt S o` o a a . . . u o . ` . o e’ e e ´ nhu . sau: • V´.i mˆi c˘p c´c kiˆ u thu.c thˆ E, F sao cho E l` mˆt F trong S, ch´ng ta c´ kh˘ng dinh: o ˜ . o a a e’ . e’ a o . u o a ’ . E < F. • V´.i mˆi thu.c thˆ E c´ c´c thuˆc t´ A1 , A2 , ..., Ak , ch´ng ta c´ mˆt CG-TLT, trong d´ o ˜ o . e’ o a o ınh . u o o . o v´ o .i mˆi mˆt thuˆc t´ Ai , CG-TLT n`y c´ c´c n´t v` canh c´ hu.´.ng sau: ˜ o o o ınh a o a u a . o o . . [E] → (C´ Ai ) → [Ai ]. o • V´.i mˆi liˆn kˆt n-ngˆi R gi˜.a n thu.c thˆ E1 , ..., En v` c´ m thuˆc t´ liˆn kˆt T1 , ..., Tm , ˜ o o e e ´ o u . e’ a o o ınh e e . ´ ch´ng ta c´ mˆt CG-TLT, trong d´ v´ u o o o o .i mˆi mˆt thu.c thˆ Ei hay v´.i mˆi mˆt thuˆc t´ ˜ o o e’ o ˜ o o o ınh . . . . . Tj , CG-TLT n`y c´ c´c n´t v` canh c´ hu.´.ng sau: a o a u a . o o [R] → (Vai tr` ng˜. ngh˜ cua Ei ) → [Ei ] hay [R] → (C´ Tj ) → [Tj ]. o u ıa ’ o Dˆi v´.i c´c CG-TLT n`y, [C] → (r) → [C ] phan ´nh mˆt phu thuˆc h`m trong S: ´ o o a a ’ a o . . o a . ` C → C v` [C] ngˆm dinh l` [C : ∗] a a . a 3.2. Dˆ thi kh´i niˆm mo. rˆng ` o . a e . ’ o . Dˆ phˆn biˆt c´c kh´i niˆm biˆu diˆn c´c thu.c thˆ, c´c thuˆc t´ hay c´c liˆn kˆt, cˆn ’ e a e a . a e . e’ ˜ a e . ’ e a o ınh . a e e ` ´ a ’ o phai bˆ ’ sung mˆt thˆng tin vˆ c´c kh´i niˆm l` kiˆ u kh´i niˆm cua n´ l` mˆt danh t`. hay o . o ` a e a e a e . ’ a e . ’ o a o . u dˆng t`.. o . u Sau dˆy, ch´ng tˆi s˜ du.a ra mˆt dinh ngh˜ mo. rˆng cho CG: a u o e o . . ıa ’ o . Dinh ngh˜ 3.1. Mˆt CG mo o ıa o . rˆng (ECG) G = (R, C, E Lab, Ca) l` mˆt dˆ thi c´ hu.´.ng ’ . R, E, ` a o o . o o . . . ` hai phˆn h˜a u .u han v´.i C = φ. R v` C k´ hiˆu c´c n´t quan hˆ v` c´c n´t kh´i niˆm cua n´. o a y e a u e a a u a e ’ o . . . . E l` tˆp c´c canh c´ hu o a a a . o .´.ng cua G. Ca l` mˆt h`m t`. C dˆn {DT, DT } cho biˆt pham tr` ’ a o a u ´ e ´ e u . . . cua mˆt n´t kh´i niˆm. Mˆi n´t kh´i niˆm trong ECG c´ mˆt nh˜n du.o.c dinh ngh˜ bo.i ’ o u . a e . ˜ o u a e . o o . a . . ıa ’ ´nh xa Lab. Mˆt nh˜n cua mˆt kh´i niˆm C ∈ C du.o.c k´ kiˆu l` Lab(C) = (c, m(c)) v´.i a . o. a ’ o. a e . . ı e a . o m(c) l` tham chiˆu cua c. a ´ ’ e V´.i mˆt n´t kh´i niˆm C ∈ C , nˆu Ca(C) = DT th` n´t d´ c´ thˆ biˆu diˆn mˆt thuˆc o o u . a e . e´ ı u o o e e ’ ’ ˜ e o . o. t´ ho˘c mˆt thu ınh a o .c thˆ , nˆu Ca(C) = DT th` c´ ngh˜ l` n´t d´ biˆu diˆn mˆt liˆn kˆt. e’ e ´ ı o ıa a u o e ’ ˜ e o e e ´ . . . . Gia su. hai n´t C1 v` C2 v´.i nh˜n tu.o.ng u.ng [c1 : m1 ] v` [c2 : m2 ], ph` ho.p v´.i d`n ’ ’ u a o a ´ a u . o a kiˆe’u kh´i niˆm, d`n d´nh dˆu v` c´c d´nh dˆ u cua mˆt kiˆu kh´i niˆm phai ph` ho.p v´.i a e . a a a´ a a a a´ ’ o. e’ a e . ’ u . o e’ a e . o o ´ e a ’ e kiˆu kh´i niˆm d´, ta c´ Lab(C1 ) Lab(C2 ) nˆu v` chı nˆu c1 c2 v` m1 m2 . D˘c biˆt, ´ a a . e . o ´ ta n´i Lab(C1 ) = Lab(C2 ) nˆu c1 = c2 v` m1 = m2 . e a Dˆ thˆ y, ch´ng ta c´ thˆ dinh ngh˜ c´c SDKN du.´.i dang mˆt tˆp c´c ECG-TLT. ˜ a e ´ u o e . ’ ıa a o . o a a . .
278 ˜ ˆ NGUYEN KIM ANH 3.3. C´c luˆt thiˆt lˆp mo. rˆng dˆi v´.i ECG a a. ´ . e a ’ o . ´ o o Dˆ x´c dinh du.o.c c´c ECG-TLT, ch´ng ta cˆn x´c dinh mˆt tˆp c´c luˆt thiˆt lˆp cho ’ e a . . a u `a a . o a a . . a . ´ . e a e ’ ph´p san sinh ra c´c ECG-TLT t` o a a a . mˆt tˆp c´c ECG-TLT ban dˆu. Sau dˆy, ch´ng tˆi s˜ u . . `a a u o e du .a ra c´c luˆt thiˆt lˆp mo. rˆng cho c´c ECG: a a ´ a e . ’ o a . . o ’ . ınh a ’ 1) Sao ch´p: Mˆt ban sao ch´ x´c cua mˆt ECG-TLT l` mˆt ECG-TLT. e o. a o . 2) X´a: X´a di mˆt quan hˆ kh´i niˆm n`o d´ t` o o o o e a e a o u . . mˆt ECG-TLT s˜ thu du.o.c mˆt ECG-TLT. e o . . . . . 3) Han chˆ . ´: Nˆu C l` mˆt n´t kh´i niˆm trong mˆt ECG-TLT th` thay thˆ C bo.i C v´.i e ´ e a o u . a e . o . ı e’ ’ o Lab(C ) Lab(C) s˜ thu du . e .o.c mˆt ECG-TLT. o . 4) Kˆt nˆi: Gia su. C l` mˆt n´t kh´i niˆm trong mˆt ECG-TLT G v` C l` mˆt n´t kh´i niˆm ´ ´ e o ’ ’ a o u . a e . o . a a o u . a e . trong mˆt ECG-TLT G , o. dˆy G v` G c´ thˆ l` c`ng mˆt dˆ thi. Nˆu Lab(C) = Lab(C ) o. ’ a a o e a u ’ o o . e . ` ´ v` Ca(C) = Ca(C ) = DT th` G v` G c´ thˆ du.o.c kˆt nˆi dˆ h` th`nh mˆt ECG-TLT a ı a o e ’ ´ ´ ’ . e o e ınh a o. b˘ ng c´ch x´a C t`. G v` g˘n v`o C tˆt ca c´c m´c nˆi cua c´c quan hˆ kh´i niˆm trong ` a a o u a a a ´ ´ a ’ a o o ’ a ´ e a e . . G m` tru.´.c dˆy du.o.c g˘n v`o C. a o a . a a ´ Trong tru.`.ng ho.p n´t C v` C d´ biˆu diˆn mˆt liˆn kˆt (Ca(C) = Ca(C ) = DT ), ch´ng o . u a o e ’ ˜ e o e e . ´ u ’ ta phai mo o . rˆng phˆn chung cua hai ECG-TLT G v` G b˘ ng c´ch thˆm c´c quan hˆ kh´i ’ . `a ’ a ` a a e a e a . niˆm v` c´c kh´i niˆm kˆ v´.i hai n´t kh´i niˆm C v` C d´ trong G v` G . Nˆu liˆn kˆt R e . a a a e . ` o e u a e . a o a ´ e e e ´ .o.c biˆu diˆn bo.i C v` C k´o theo k thu.c thˆ E , ..., E o. trong G v` G th` G v` G chı ’ ˜ ’ ’ du . e e a e . e 1 k ’ a ı a ’ c´ thˆ o e ’ du.o.c kˆt nˆi nˆu G v` G c`n ch´.a k − 1 n´t kh´i niˆm chung (c´ nh˜n giˆng nhau) . e o e ´ ´ ´ a o u u a e . o a ´ o tu.o.ng u.ng v´.i k − 1 thu.c thˆ k´o theo trong liˆn kˆt, khˆng mˆ t t´ tˆ ng qu´t, gia su. l` ´ o . ’ e e e e ´ o ´ a ınh o ’ a ’ ’ a E1 , ..., Ek−1 , v` khˆng ch´ a o u .a mˆt n´t kh´i niˆm n`o tu.o.ng u.ng v´.i mˆt thuˆc t´ cua liˆn o u a e a ´ o o o ınh ’ e . . . . kˆt du.o.c biˆu diˆn bo.i C. Dˆi v´.i thu.c thˆ Ek , gia su. trong G c´ [C] → (Rk ) → [Ek : A] e´ . e’ ˜ e ’ ´ o o . e’ ’ ’ o v` trong G c´ [C ] → (Rk ) → [Ek : A ], o. dˆy A v` A l` mˆt dang d´nh dˆu n`o d´ cua a o ’ a a a o . . a a´ a o ’ tru.`.ng tham chiˆu dˆi v´.i Ek . Khi d´, G v` G c´ thˆ du.o.c kˆt nˆi dˆ h` th`nh mˆt o ´ o o e ´ o a o e ’ . ´ ´ ’ e o e ınh a o . ECG-TLT nhu . sau: Tru.´.c tiˆn, ´p dung luˆt kˆt nˆi o. trˆn dˆi v´.i k − 1 n´t kh´i niˆm o e a a e o ’ e ´ ´ ´ o o u a e . . . chung tu.o.ng u.ng v´.i E1 , ..., Ek−1 , ch´ng ta du.o.c mˆt ECG, k´ hiˆu l` G . Sau d´, x´a c´c ´ o u . o . y e a . o o a quan hˆ kh´i niˆm kˆ v´.i C v` tˆt nhiˆn x´a [C] → (Rk ) → [Ek : A] t`. G v` thay thˆ n´t e a e . . ` o e a a ´ e o u a ’ e u kh´i niˆm [Ek : A ] bo a e . ’.i [Ek : A ∪ A ]. T`. c´c luˆt thiˆt lˆp co. ban trˆn, ch´ng ta c´ thˆ dinh ngh˜ mˆt sˆ ph´p to´n c´ y u a a . ´ . e a ’ e u o e . ’ ıa o o . ´ e a o ´ ngh˜ dˆi v´ e ıa o o ´ .i viˆc biˆu diˆn v` tra l`.i c´c cˆu truy vˆ n dˆi v´.i mˆt CSDL quan hˆ. e’ ˜ a ’ o a a e ´ ´ a o o o e . . . Dinh ngh˜ 3.2. Mˆt ph´p chiˆu Π t`. mˆt ECG G = (R, C, E Lab, Ca) dˆn mˆt ECG . ıa o . e ´ e u o . R, E, ´ e o. G = (R , C , E , Lab , Ca ) l` mˆt c˘p c´ th´ . R a o a o u . tu. hai ´nh xa Π = (f, g) v´.i f : R → R v` a o a . . . g : C → C sao cho: 1) V´.i mˆ i e : (r) → [c] hay e : [c] → (r) thuˆc E th` c´c canh (f (r)) → [g(c)] hay o ˜ o o . ı a . [g(c)] → (f (r)) phai thuˆc E . ’ o . 2) ∀r ∈ R , Lab(r) = Lab (f (r)) 3) ∀c ∈ C, Lab(c) Lab (g(c)) v` Ca(c) = Ca (g(c)) a Ch´ng ta s˜ goi dˆ thi con cua G ch´.a c´c n´t v` c´c canh du.o.c chiˆu t`. G xuˆng l` u e . o . ` ’ u a u a a . . ´ e u ´ o a gˆ o´c chiˆu cua G trong G v` G l` chiˆu cua G . ´ ’ e a a ´ ’ e . ` ´ o . a ´ e ’ Mˆnh dˆ 3.1. Nˆu mˆt ECG G l` chiˆu cua mˆt ECG-TLT G’ th` G c˜ng l` ECG-TLT. e e e o . ı u a Ch´.ng minh: Theo Dinh ngh˜ 3.2, nˆu G l` chiˆu cua G th` G c´ thˆ du.o.c suy ra t`. G v´.i u . ıa ´ e a ´ e ’ ı o e ’ . u o .´.c sau: Tru.´.c tiˆn, thu.c hiˆn luˆt x´a c´c quan hˆ kh´i niˆm trong G dˆ h` th`nh c´c bu o a o e e a o a e a e e’ ınh a . . . . . ´ o e´ ’ o´ ´ e a a o o . . ` e o ’ gˆc chiˆu cua G trong G . Do gˆc chiˆu n`y l` mˆt dˆ thi con liˆn thˆng cua G nˆn n´ phai e o ’
´ . ’ . ˜. ˆ ˆ ’. . ` ˆ ´ . ˆ . ´ ˆ TRUY VAN CAC CO SO DU LIEU QUAN HE SU DUNG DO THI KHAI NIEM . . 279 l` mˆt ECG-TLT. Sau d´, thu.c hiˆn mˆt d˜y c´c luˆt han chˆ trˆn c´c kh´i niˆm cua gˆc a o . o . e . o a a . a . . ´ e e a a e . ’ o´ ´ e e ’ ´ a ’ a a a . . ` e ’ ’ e´ ’ a o chiˆu dˆ suy ra G. Do tˆ t ca c´c luˆt ´p dung dˆu dam bao kˆt qua l` mˆt ECG-TLT nˆn . e kˆ e´t qua cuˆi c`ng G l` mˆt ECG-TLT. ’ o ´ u a o . Dˆ kh˘ng dinh liˆu c´c luˆt thiˆt lˆp du.a ra o. trˆn c´ dam bao chı sinh ra c´c ECG-TLT ’ ’ e a . e a . a. ´ . e a ’ e o ’ ’ ’ a d´ng d˘ u ´n khˆng, ch´ng tˆi s˜ du.a ra ph´p dich ng˜. ngh˜ cua c´c ECG du.´.i dang FOL v` a o u o e e . u ıa ’ a o . a su. dung ch´ng dˆ kiˆm tra t´ d´ng d˘n cua c´c luˆt thiˆt lˆp trˆn. ’ . u ’ ’ e e ınh u ´ a ’ a a. ´ . e a e ˆ ´ . ´. 4. THONG DICH CAC ECG DU O I DANG FOL . . Dinh ngh˜ 4.1. Cho G = (R, C, E Lab, Ca) l` mˆt ECG khˆng ch´.a d´nh dˆ u {∗}. Kˆt . ıa R, E, a o . o u a a´ e´ .p v´.i mˆi kiˆu kh´i niˆm mˆt vi t`. mˆt ngˆi v` du.o.c k´ hiˆu c`ng tˆn. Tu.o.ng tu., ch´ng ho o o ˜ e ’ a e o . u o o a . . . . . y e u . e . u tˆi kˆt ho.p v´.i mˆ i quan hˆ hai ngˆi mˆt vi t`. hai ngˆi du.o.c k´ hiˆu c`ng tˆn. Cuˆi c`ng, o e .´ o ˜ o e . o o . u . o . y e u . e ´ o u tˆt ca c´c d´nh dˆ u c´ thˆ du.o.c xu. l´ nhu. c´c h˘ ng cua FOL. Ch´ng tˆi phˆn biˆt 4 tˆp ´ a ’ a a ´ a a e ’ . ’ y a ` a ’ u o a e . a. biˆn X, Y, Z, V mˆt c´ch th´ ho.p v` k´ hiˆu M l` tˆp tˆt ca c´c d´nh dˆ u c´ thˆ, S l` ´ e o a . ıch . a y e . a a a ’ a a . ´ ´ a a e ´ a ´ . tˆp c´c d´nh dˆ u tˆp c´ thˆ, gia su a a a a a a e ´ ’ ’ . S = {A , ..., A } . 1 n 1) V´.i mˆi n´t kh´i niˆm [C] ∈ C , ph´p dich kh´i niˆm l`: o ˜ o u a e . e . a e a . • C(x) v´.i x ∈ X l` mˆt biˆn m´.i nˆu tham chiˆu cua C l` ∀; o a o . ´ e o e ´ ´ ’ e a • C(y) v´.i y ∈ Y l` mˆt biˆn m´.i nˆu tham chiˆu cua C l` ∃ hay ∗ v` G khˆng ch´.a o a o . ´ e o e ´ ´ ’ e a a o u [C] → (r) → [C : Ai ] hay [C] → (r) → [C : ∀]; • C(v) v´.i v ∈ V l` mˆt biˆn m´.i nˆu tham chiˆu cua C l` ∃ hay ∗ v` G ch´.a [C] → o a o . e´ o e ´ ´ ’ e a a u (r) → [C : Ai ] hay [C] → (r) → [C : ∀] v´ o.i C n`o d´; a o • C(a) v´.i n´t [C : a] v` a l` mˆt d´nh dˆu c´ thˆ; o u a a o a . ´ a a e ’ • C(z) v´ o .i z ∈ Z l` mˆt biˆn m´.i nˆu tham chiˆu cua C l` tˆp c´ thˆ; a o ´ e o e ´ ´ ’ e a a a e ’ . . ’ Ta k´ hiˆu ph´p dich cua [C] trong FOL bo y e e . ’.i C(t), o. dˆy, t c´ thˆ l` mˆt biˆn hay mˆt ’ a o e ’ a o ´ e o . . . ` h˘ ng. a 2) V´.i mˆi n´t quan hˆ hai ngˆi (r) ∈ R , ch´ng tˆi kˆt ho.p mˆt cˆng th´.c τ (r) nhu. o ˜ o u e . o u o e ´ . o o . u sau: nˆu C1 v` C2 l` hai n´t kh´i niˆm kˆ v´.i n´t quan hˆ r n`y, c´ ngh˜ l` G ch´.a e´ a a u a e . ` o u e e. a o ıa a u [C1 : m1 ] → (r) → [C2 : m2 ] th` τ (r) = ∧ti∈Y ∪Z∪M∪V Ci (ti ) ∧tj ∈X [Cj (tj ) → r(t1 , t2 )] nˆu c´ ı ´ e o . ´ mˆt tj ∈ X, nˆu khˆng τ (r) = C1 (t1 ) ∧ C2 (t2 ) ∧ r(t1 , t2 ). o e o e . ’ 3) Ph´p dich cua ECG trong FOL l`: a Φ(G) = ∃y1 ...yk ∀z1 ∈ A1 , ...∀zn ∈ An ∀x1 ...∀xh ∃v1 ...∃vm ∧r∈R τ (r). Ch´ y r˘ ng tˆt ca c´c n´t cˆ lˆp luˆn c´ mˆt ph´p dich do.n gian l` C(a), ∀x C(x), u ´ a ` ´ a ’ a u o a . o o o . e . ’ a ∀z ∈ A C(z) ho˘c ∃yC(y). a. Thˆng qua ph´p dich c´c ECG th`nh mˆt biˆu th´.c FOL, ch´ng ta c´ thˆ nhˆn thˆ y, o e . a a o . e ’ u u o e ’ a . ´ a ` ’ a ’ c´c dˆ thi kh´i niˆm c´ kha n˘ng biˆu diˆn c´c so o a o . a e o e ˜ a e . dˆ co. so. d˜. liˆu quan hˆ v` c´c truy vˆ n ` ’ u e e a a a´ . . . trˆn co e . so. d˜. liˆu n`y ph` ho.p v´.i c´ch nh` cua ngu.`.i d`ng v` truy nhˆp d˜. liˆu ph` ho.p ’ u e a u . o a ın ’ o u a a u e u . . . . v´.i c´ch nh` cua hˆ thˆng. o a ın ’ e o . ´ Dinh l´ 4.1. Mˆ . y ˜i ECG-TLT du.o.c sinh ra bo.i viˆc ´p dung c´c luˆt thiˆt lˆp co. ban: sao o . ’ e a . . a a . ´ . e a ’ ch´p, xo´, han chˆ v` kˆt nˆi trˆn c´c ECG-TLT dˆu du.o.c suy diˆn logic t`. c´c ECG-TLT e a . ´ ´ ´ e a e o e a `e . ˜ e u a sinh ra n´.o Ch´.ng minh: Dˆ thˆ y, v´.i c´c luˆt thiˆt lˆp co. ban: sao ch´p, xo´, han chˆ v` kˆt nˆi u ˜ a e ´ o a a . ´ . e a ’ e a . ´ e a e o ´ ´ v´ o.i Ca(C) = Ca(C ) = DT , c´c ECG-TLT du.o.c sinh ra dˆu du.o.c suy diˆn logic t`. c´c a `e ˜ e u a . . ECG-TLT sinh ra n´. Ta s˜ ch´.ng minh cho tru.`.ng ho.p kˆt nˆi v´.i Ca(C) = Ca(C ) = o e u o . ´ ´ e o o
280 ˜ ˆ NGUYEN KIM ANH ’ ` a e’ ´ DT . Chı cˆn kiˆm tra, nˆu c´ [C] → (Rk ) → [Ek : A] v` [C ] → (Rk ) → [Ek : A ] th` e o a ı [C ] → (Rk ) → [Ek : A ∪ A ]. X´t c´c tru.`.ng ho.p: e a o . • Nˆu mˆt trong A v` A l` ∀ th` du.o.ng nhiˆn A ∪ A = ∀ v` do vˆy ´ e o . a a ı e a a . [C ] → (Rk ) → [Ek : A ∪ A ] l` d´ng. a u • Nˆu A v` A l` c´c tˆp c´ thˆ, ´p dung Dinh ngh˜ 4.1, t`. [C] → (Rk ) → [Ek : A], ´ e a a a a a e a . ’ . . ıa u ta c´ ∀z1 ∈ A ∃v1 C(v1 ) ∧ Ek (z1 ) ∧ Rk (v1 , z1 ) v` t` o a u . [C ] → (R ) → [E : A ], ta c´ o k k ∀z1 ∈ A ∃v1 C (v1 ) ∧ Ek (z1 ) ∧ Rk (v1 , z1 ). Do C = C nˆn ta c´: e o ∀z1 ∈ A ∪ A ∃ v1 C (v1 ) ∧ Ek (z1 ) ∧ Rk (v1 , z1 ) v` vˆy [C ] → (Rk ) → [Ek : A ∪ A ] l` d´ng. ı a. a u V` vˆy, mˆ ı a . ˜i ECG du.o.c sinh ra bo.i viˆc ´p dung c´c luˆt thiˆt lˆp co. ban: sao ch´p, xo´, o . ’ e a . . a a . ´ . e a ’ e a han chˆ v` kˆt nˆi trˆn c´c ECG-TLT dˆu du.o.c suy diˆn logic t`. c´c ECG-TLT sinh ra n´. . ´ ´ ´ e a e o e a `e . ˜ e u a o Dˆi v´.i mˆt hˆ CSDL c´ hˆ tro. kha n˘ng truy vˆ n CSDL su. dung ECG, truy vˆn ban ´ o o o e . . ˜ o o . ’ a a´ ’ . a´ ` dˆu cua ngu o ’ . a ’ .`.i su. dung s˜ du.o.c dich th`nh mˆt dˆ thi truy vˆn v` hˆ s˜ sinh ra mˆt dˆ thi e a o o ` . ´ a a e e o o . ` . . . . . ’ o tra l` .i thˆng qua viˆc ´p dung l˘p lai c´c luˆt thiˆt lˆp trˆn c´c ECG-TLT ban dˆu. Phˆn o e a a . a a ´ . e a e a ` a ` a . . . . .o.t qu´ pham vi cua b`i b´o nˆn khˆng du.o.c dˆ cˆp dˆn o. dˆy. n`y vu . a a . ’ a a e o . ` a e ’ a e . ´ 5. CAC V´ DU MINH HOA ´ I . . ´ e a e . ’ V´ du 1: Cho biˆt c´c sinh viˆn hoc ca hai mˆn CSDL1v` CSDL2 ı . o a [SinhViˆn: ?] ← (Rcpt) ← [Hoc] → (Obj) → [Mˆn: {CSDL1, CSDL2}]. e . o V´ du 2: Cho biˆ a ı . ´t c´c giang viˆn day tˆ t ca c´c mˆn e ’ e . a´ ’ a o ’ [GiangViˆn: ?] ← (Agnt) ← [Day] → (Obj) → [Mˆn: ∀]. e . o V´ du 3: Cho biˆt c´c giang viˆn c´ day mˆt mˆn n`o d´ m` sinh viˆn n˘m th´. nhˆ t phai ı . ´ e a ’ e o . o . o a o a e a u ´ a ’ hoc: . ’ [GiangViˆn: ?] ← (Agnt) ← [Day] → (Obj) → [Mˆn: ∃] ← (Obj) ← [Hoc] → (Rcpt) → e . o . [SinhViˆn:∗] → (C´N˘mHoc) → [N˘m: Th´. nhˆ t]. e o a . a u ´ a (Dˆ u ? dˆ d´nh dˆu c´c thˆng tin cˆn tra c´.u v` cˆn du.o.c du.a ra, Agnt l` t´c nhˆn, ´ a ’ e a ´ a a o ` a u a `a . a a a Obj l` dˆi tu.o.ng chiu t´c dˆng v` Rcpt l` dˆi tu.o.ng nhˆn t´c dˆng). a o ´ . . a o . a a o´ . a a o . . ´ ˆ ˆ 6. KET LUAN . C´c dˆ thi kh´i niˆm (CG) cung cˆp mˆt c´ch k´ hiˆu h` th´.c m` m´y t´ c´ thˆ a o . a e` . ´ a o a . y e ınh u . a a ınh o e ’ ’ e a ’ hiˆu v` xu y a . l´. C´c CG du.o.c dinh ngh˜ trong b`i n`y khˆng c´ y dinh nhu. mˆt phu.o.ng tiˆn ıa a a o o´ . o e . . . . lu.u tr˜. d˜. liˆu m` chı l` mˆt phu.o.ng tiˆn mˆ ta d˜. liˆu v` c´c mˆi quan hˆ gi˜.a ch´ng. u u e a ’ a o e o ’ u e a a ´ o e u u . . . . . Nhu. mˆt phu.o.ng ph´p mˆ ta h` th´.c, CG c´ ba u.u diˆm ch´ sau: o. a o ’ ınh u o e ’ ınh ˜ + Hˆ tro o a o . . . mˆt ´nh xa tru.c tiˆp v`o mˆt CSDL quan hˆ. ´ e a o e . . . . .o.c su. dung nhu. mˆt c´ch biˆu diˆn ng˜. ngh˜ c´c cˆu truy vˆ n tu. nhiˆn. + Du . ’ . o a e’ ˜ e u ıa a a ´ a . e . ’ a + C´ kha n˘ng hˆ . a o ˜ tro. c´c suy diˆn tu. dˆng dˆ x´c dinh c´c mˆi quan hˆ khˆng du.o.c nh˘c o ˜ . o e . e’ a . a ´ o e o . . ´ a e´ dˆn mˆt c´ch tu o o a .`.ng minh trong c´c yˆu cˆu truy vˆ n cua ngu.`.i d`ng a e ` a ´ ’ a o u . Mˆt hˆ CSDL c´ hˆ tro a o e o o .˜ . c´c truy vˆ n tu. nhiˆn s˜ khˆng ho`n to`n tu. nhiˆn nˆu n´ d`i ´ a . e e o a a . ´ e e o o . . .`.i su. dung phai biˆt d˜. liˆu du.o.c biˆu diˆn nhu. thˆ n`o trong CSDL. C´c CG c´ hoi ngu o ’ . ’ ’ ´ u e e e’ ˜ e e’ a a o . . thˆ hˆ tro. mˆt giao diˆn cho ph´p ngu.`.i su. dung truy vˆ n c´c CSDLQH cua ho thˆng qua ’ ˜ e o . o . e. e o ’ . ´ a a ’ . o c´c thuˆt ng˜. quen thuˆc m` khˆng cˆn hoc c´c ngˆn ng˜. truy vˆn d˘c biˆt v` biˆt c´c a a. u o . a o `a . a o u a´ a. e a e a . ´ quy u.´.c vˆ m´y t´ o ` a ınh. Ch´ng tˆi hy vong r˘ ng, c´ch mo. rˆng c´c CG v` c´c luˆt thiˆt lˆp e u o . ` a a ’ o . a a a a. ´ . e a
´ . ’ . ˜. ˆ ˆ ’. . ` ˆ ´ . ˆ . ´ ˆ TRUY VAN CAC CO SO DU LIEU QUAN HE SU DUNG DO THI KHAI NIEM . . 281 trong b`i n`y c´ thˆ du.o.c ´p dung dˆ xˆy du.ng c´c hˆ CSDLQH cho ph´p truy vˆ n CSDL a a o e ’ . a . ’ e a . a e . e ´ a ’ e o cua hˆ thˆng qua c´c CG. . a ` ˆ ’ TAI LIEU THAM KHAO . [1] Androutsopoulos, Interfacing a Natural Language front-End to Relational Database, Tech. Paper no.11, Dept.of AI, Univ. of Edingburgh, 1993. [2] P. N. Creasy and B. Moulin, Adding semantics to semantic data models, Current Direc- tions in Conceptual Graphs Research, Nagle et al. (Eds), 1992 (189—200). [3] B. Moulin and P. N. Creasy, Extending the conceptual graph aproach for data conceptual modelling, Data & Knowledge Engineering 8 (1992) 223—248. [4] J. Farques, M. C. Landau, A. Dugourd, and L. Catach, Conceptual graphs for semantics and knowledge processing, IBM J. Res. Develop 30 (1) (1986). [5] J. F. Sowa, Conceptual graphs for a data base interface, IBM J. Res. Develop 20 (4) (1976). [6] M. Wermelinger, Conceptual graphs and ﬁrst-order logic, Proc.ICC’95, LNCS 954, 1995. Nhˆn b`i ng`y 9 - 1 - 2006 a a . a