Một cách tiếp cận đối với phép dịch các câu truy vấn ngôn ngữ tự nhiên thành dạng logic.

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

Thêm vào BST

Báo xấu

52
lượt xem 5
download

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

Một cách tiếp cận đối với phép dịch các câu truy vấn ngôn ngữ tự nhiên thành dạng logic. Điều khiển và Truyền thông trong Sinh vật và Máy móc" về Các vòng nhân quả và Cơ chế phản hồi của Wiener được xuất bản lần đầu tiên cùng lúc tại Mỹ, Anh, Pháp... Trong cuốn sách, điều khiển học được nhấn mạnh là không chỉ điều khiển và truyền thông bên trong các hệ nhân tạo được thiết kế mới mà cả trong sự phát triển của các hệ thống của tự nhiên, như sinh vật, xã hội....

Chủ đề:

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

Lưu

Nội dung Text: Một cách tiếp cận đối với phép dịch các câu truy vấn ngôn ngữ tự nhiên thành dạng logic.

. . a ` e e’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.21, S.3 (2005), 271—279 ı . ˆ ´ ˆ´ ˆ ´ ˆ ´. ´ MOT CACH TIEP CAN DOI VO I PHEP DICH . . . ´ CAU TRUY VAN NGON NGU. TU. NHIEN THANH DANG LOGIC CAC ˆ ´ ˆ ˆ ˜ . ˆ ` . ˜ ˆ 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. For most natual language processing tasks, an interpreter that translates the natural language sentences into a semantic representation is signiﬁcantly more useful than a parser that simply recognizes syntactically well-formed strings. In this paper, we focus on the task of translating database queries directly into an executable logical form. T´m t˘t. Dˆi v´.i hˆu hˆt c´c nhiˆm vu xu. l´ ngˆn ng˜. tu. nhiˆn, mˆt bˆ thˆng dich nh˘ m dich o ´ a ´ o o ` a e a´ e . . ’ y o u . e o o o . . . ` a . c´c cˆu ngˆn ng˜ . a a o u. tu. nhiˆn th`nh mˆt biˆ u diˆn ng˜. ngh˜ c´ ´ ho.n mˆt bˆ phˆn t´ c´ ph´p chı e a o e’ ˜ e u ıa o ıch o o a ıch u a ’ . . . do.n gian nhˆn biˆt vˆ c´ ph´p c´c xˆu dˆu v`o du.o.c thiˆt lˆp tˆt. Trong b`i b´o n`y, ch´ ng tˆi ’ a . e ` u a a a ` ´ e a a . ´ . e a o ´ a a a u o tˆp trung v`o nhiˆm vu dich c´c cˆu truy vˆ n co. so. d˜. liˆu th`nh mˆt dang logic c´ thˆ thu.c hiˆn a . a e. . . a a ´ a ’ u e . a o . . o e ’ . e. du.o.c. . ´. ˆ 1. GIO I THIEU . Gi´p m´y t´ dˆ su. dung ho.n, gˆn g˜i v´.i con ngu.`.i ho.n l` diˆu m` c´c nh` lˆp tr` u a ınh ˜ ’ . e ` u o a o a ` e a a a a . ınh v` nghiˆn c´ a e u .u m´y t´ d˜, dang v` s˜ tiˆp tuc cˆ g˘ ng thu.c hiˆn. Ngˆn ng˜. n´i l` mˆt a ınh a ´ a e e . o a ´ ´ e o u o a o . . . trong nh˜.ng c´ch giao tiˆp thˆng dung v` tu. nhiˆn nhˆt cua con ngu.`.i. Dˆ gi´p m´y t´ u a e´ o . a . e ´ a ’ o ’ e u a ınh giao tiˆp du.o.c v´.i con ngu.`.i thˆng qua ngˆn ng˜. n´i, ch´ng ta cˆn c´ c´c th`nh phˆn xu. l´ ´ e . o o o o u o u ` o a a a `a ’ y ngˆn ng˜ . o u . tu. nhiˆn (NLP). Muc d´ ch´ cua c´c th`nh phˆn NLP n`y l` t`. mˆt cˆu tiˆng e ’ a ` ´ . ıch ınh a a a a u o a . e Viˆt (ho˘c mˆt ngˆn ng˜ a y e e a o o . bˆ t k`) s˜ du.o.c thˆng dich bo.i m´y t´ v` mˆt h`nh dˆng tu.o.ng u ´ o ’ a ınh a o a o . . . . . . . u ´ .ng s˜ du.o.c thu.c hiˆn. Do t´ mˆp m`., da ngh˜ trong ngˆn ng˜. n´i nˆn cho dˆn nay, c´c e e ınh a o ıa o u o e ´ e a . . . . hˆ thˆng NLP xˆy du.ng du.o.c dˆu bi gi´.i han trong mˆt miˆn nho v` chı thˆng dich du.o.c e o . ´ a . . ` e . o . o. ` e ’ a ’ o . . . ´ mˆt sˆ loai cˆu nhˆt dinh. o o . a ´ a . Mˆt l˜ vu.c m` c´c hˆ thˆng NLP c´ thˆ ´p dung hiˆu qua l` c´c hˆ truy vˆ n co. so. d˜. o ınh . . a a e o . ´ o ea ’ . e. ’ a a e . ´ a ’ u liˆu (CSDL). L´ do l` c´c CSDL thu o e y a a .`.ng phu mˆt miˆn du nho nˆn nh˜.ng cˆu truy vˆ n tiˆng ’ o `e ’ ’ e u a a´ e ´ . . Viˆt vˆ d˜. liˆu c´ thˆ phˆn t´ du.o.c bo.i mˆt hˆ thˆng NLP. Dˆi v´.i hˆu hˆt c´c nhiˆm vu e ` u e o e a ıch . e . ’ . ’ o e o . . ´ o o ` ´ a e a ´ e . . xu. l´ ngˆn ng˜. tu. nhiˆn, mˆt bˆ thˆng dich nh˘ m dich c´c cˆu dˆu v`o th`nh mˆt biˆ u diˆn ’ y o u . e o o o . . . ` a . a a ` a a a o e . ’ ˜ e ng˜. ngh˜ c´ ´ ho.n mˆt bˆ phˆn t´ c´ ph´p chı do.n gian nhˆn biˆt vˆ c´ ph´p c´c xˆu u ıa o ıch o o a ıch u a . . ’ ’ a. e ` u a a a ´ e dˆu v`o du.o.c thiˆt lˆp tˆt. Tuy nhiˆn, theo ch´ng tˆi, mˆt sˆ c´ch tiˆp cˆn dich c´c cˆu truy ` a a . ´ . ´ e a o e u o . ´ o o a ´ . e a . a a vˆ ´n ngˆn ng˜. tu. nhiˆn th`nh dang logic trong [2] v` [7] chu.a khai th´c tˆt c´c tri th´.c miˆn, a o u . e a . a a o ´ a u `e ’ cu thˆ l` c´c ng˜ e a a u . ngh˜ du.o.c biˆt vˆ CSDL m` ch´ng ta dang xem x´t khi giai quyˆt c´c ıa e ` ´ e a u e ’ ´ e a . . ` ’ ´ a ’ a a nhˆp nh˘ ng v` kiˆm tra t´ nhˆ t qu´n cua c´c cˆu truy vˆ n dˆu v`o. B`i b´o n`y dˆ cˆp a . a a e ınh a a ` ´ a a a a a ` a e . ´ ´ . dˆn mˆt c´ch tiˆp cˆn cho ph´p dich c´c cˆu truy vˆ n ngˆn ng˜ . e o a e a e . a a a´ o u. tu. nhiˆn tiˆng Viˆt th`nh e ´ e e a . . mˆt dang logic c´ thˆ . o . . o e ’ thu.c hiˆn du.o.c. Nˆi dung b`i b´o du.o.c tr`nh b`y nhu. sau: phˆn 2 e. . o . a a . ı a ` a mo. dˆu v´.i mˆt sˆ kh´i niˆm co. ban liˆn quan dˆn viˆc x´c dinh v` biˆ u diˆn ng˜. ngh˜ cua ’ ` o o o a e a . ´ . ’ e ´ e e a . . a e ’ ˜ e u ıa ’
272 ˜ ˆ NGUYEN KIM ANH CSDL quan hˆ. Muc 3 tr`nh b`y mˆt kiˆn tr´c ph´c thao cua hˆ thˆng l`m co. so. cho ph´p e. . ı a o e . ´ u a ’ ’ e o . ´ a ’ e dich c´c cˆu truy vˆ n tu a a ´ a . . nhiˆn. Muc 4 tr` b`y c´c bu.´.c ch´ dˆ dich c´c cˆu truy vˆ n tu. e ınh a a o ınh e . ’ a a ´ a . . . nhiˆn tiˆng Viˆt th`nh dang logic c´ thˆ thu.c hiˆn du.o.c. Cuˆi c`ng, Muc 5 tr` b`y mˆt e ´ e e. a . o e . ’ e. . ´ o u . ınh a o. ´ sˆ v´ du minh hoa v` Muc 6 du o ı . a . .a ra mˆt v`i d´nh gi´ v` kˆt luˆn. o a a a a e ´ a . . . ˆ ´ ˆ ´ ˆ . ’ 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ˆ co. so. d˜. liˆu quan hˆ cho mˆt x´ nghiˆp, ch´ng ta thu.`.ng su. . e ´ ´ ´ e e ’ u e . e . o ı . e . u o ’ dung mˆt so oo . dˆ thu.c thˆ - liˆn kˆt biˆu diˆn cˆ u tr´c logic tˆ ng thˆ cua CSDL dˆi v´.i dˆi ` . e’ e e ´ e ’ ˜ a e ´ u o’ e’ ’ o´ o o ´ . . tu.o.ng 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 thˆ , c´c . a a a `a ’ ’ o . ` o . e ’ e e a a´ . ’ e a thuˆc t´ v` c´c liˆn kˆ o ınh a a e e . ´t. Mˆt tˆp thu.c thˆ (goi do.n gian l` thu.c thˆ ) k´ hiˆu mˆt tˆp c´c o a . . . e’ . ’ a . e’ y e . o a a . . x´ nghiˆp 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 thu.c thˆ ı e o a ınh a . ´ a . a o e . a o . . u a a . . e’ .o.c x´c dinh thˆng qua mˆt tˆp c´c t´nh chˆ t, du.o.c goi l` c´c thuˆc t´nh, dˆ phan ´nh c´c du . a . o o a a ı a´ ’ ’ a . . . . a a o ı . e a d˘c tru.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 danh t`.. a. ’ a . . e’ ˜ o o . o ınh . . a o e . u . a o . u Mˆt tˆp liˆn kˆt (goi do o a e e ´ .n gian l` liˆn kˆt) k´ hiˆu mˆt tˆp c´c bˆ m` mˆi bˆ biˆu diˆn mˆt ’ a e e ´ y e o a a o a o . ˜ o e ’ ˜e o . . . . . . . . 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 mˆt tˆn . ´ e . u a . e’ . e ’ e e a ´ ˜ o e e ´ . a o e . goi l` mˆt dˆng t`.. Thˆng thu.`.ng, ng˜. ngh˜ cua c´c thu.c thˆ, c´c thuˆc t´ v` c´c liˆn . a o o . . u o o u ıa ’ a . ’ e a o ınh a a e . kˆt d˜ phˆn n`o du.o.c phan ´nh thˆng qua tˆn goi cua ch´ng. Do vˆy, so. dˆ thu.c thˆ - liˆn e a ` ´ a a . ’ a o e . ’ u a. ` o . e’ e ´ ´ kˆt dˆi v´ o ı e o o .i mˆt x´ nghiˆp c´ mˆt y ngh˜ quan trong nhˆ t dinh dˆi v´.i bˆ phˆn t´ c´ ph´p e o o ´ ıa ´ a . ´ o o o a ıch u a . . . . . c˜ng nhu. bˆ thˆng dich ng˜. ngh˜ dˆ hiˆu ngh˜ cua c´c cˆu truy vˆ n dˆi v´.i CSDL cua x´ u o o . . u ıa e e ’ ’ ıa ’ a a ´ ´ a o o ’ ı nghiˆp n`y v` dˆi v´ e a a o o ´ .i ch´ng tˆi, so. dˆ thu.c thˆ - liˆn kˆt dˆi v´.i mˆt x´ nghiˆp c´ thˆ du.o.c u o ` o . e’ e e o o o ı ´ ´ e o e ’ . . . . xem nhu a u . l` nh˜.ng tri th´.c vˆ ng˜. ngh˜ d˜ du.o.c biˆt vˆ CSDL m` ch´ng ta dang xem x´t. u e ` u ıa a ´ ` e e a u e . o ’ 2.2. Logic mˆ ta CIFR [4] C´c logic mˆ ta l` c´c hˆ h` th´.c cho ph´p biˆ u diˆn v` lˆp luˆn trˆn c´c l´.p dˆi tu.o.ng a o ’ a a e ınh u . e e’ ˜ a a e . a . e a o o ´ . ph´ .u.c tap (du.o.c goi l` c´c kh´i niˆm) v` c´c mˆi quan hˆ gi˜.a ch´ng (thu.`.ng du.o.c biˆ u diˆn ´ ’ ˜ . . a a a e . a a o e u . u o . e e bo.i c´c quan hˆ hai ngˆi v` c˜ng c`n du.o.c goi l` c´c vai tr`). ’ a e . o a u o . . a a o Mˆt co. so. tri th´.c cua logic mˆ ta gˆ m c´ hai th`nh phˆn: o . ’ u ’ o ’ o ` o a ` a + TBoxes ch´ u.a mˆt tˆp c´c mˆ ta kh´i niˆm v` biˆ u diˆn cho so. dˆ chung mˆ h` h´a o a a o ’ a e a e ’ ˜ e ` o o ınh o . . . ` miˆn quan tˆm. e a + ABoxes l` mˆt su. thˆ hiˆn bˆ phˆn cua so. dˆ n`y bao gˆ m mˆt tˆp c´c kh˘ng dinh a o . e e o a . ’ . . . ’ ` o a o` o a a . . ’ a . liˆn quan dˆn c´c c´ thˆ cua c´c l´.p hay c´c c´ thˆ c´ quan hˆ v´.i nhau thˆng qua c´c mˆi e ´ e a a e ’ a o ’ a a e o ’ e o . o a ´ o quan hˆ gi˜e u .a ch´ ng. u . CIFR l` mˆt su. mo. rˆng kh´ tu. nhiˆn cua CIF v´.i muc d´ biˆu diˆn tru.c tiˆp c´c quan a o . ’ o . . a . e ’ o . ıch e ’ ˜ e . ´ e a hˆ n - ngˆi m` d˘c biˆt c´ y ngh˜ trong ng˜ ’ e o a a e o´ ıa u. canh cua ch´ng tˆi, biˆ u diˆn c´c truy vˆn dˆi ’ u o e’ ˜ a e ´ ´ a o . . . v´ o o .i mˆt co. so. d˜. liˆu quan hˆ. ’ u e e . . . Gia su. ch´ng ta c´ mˆt tˆp h˜.u han c´c kh´i niˆm nguyˆn tˆ k´ hiˆu bo.i A, c´c vai tr` ’ ’ u o o a u . . . a a e . ´ e o y e . ’ a o ´ nguyˆn tˆ k´ hiˆu bo e o y e ’.i P v` c´c quan hˆ n-ngˆi k´ hiˆu bo.i R . Ch´ng tˆi su. dung R k´ hiˆu a a e o y e ’ u o ’ . y e . . . . c´c vai tr` t`y y, C k´ hiˆu c´c kh´i niˆm t`y y v` T l` kh´i niˆm dınh, ⊥ l` kh´i niˆm d´y, a o u ´ y e a . a e u ´ a . a a e . ’ a a e . a Π l` ph´p giao v` l` ph´p ho.p. C´c kh´i niˆm v` vai tr` du.o.c xˆy du.ng ph` ho.p v´.i c´ a e a a e . a a e . a o . a . u . o u ph´p sau: a C ← T |⊥|A|C1 C2 |C1 C2 |¬C|∀R.C|∃R.C|( 1P )|( 1P − ), |( 1R[U ])∀R[U ].T1 : C1 , ..., Tm : Cm |∃R[U ].T1 : C1 , ..., Tm : Cm ,
ˆ ´ ´ ˆ ˆ ´ ˆ ´. ´ MOT CACH TIEP CAN DOI VO I PHEP DICH... . . . 273 R ← P |R[U, U ]|R1 R2 |R1 ◦ R2 |R− |id(C). Ng˜. ngh˜ cua CIFR, nhu. thˆng thu.`.ng, du.o.c cho thˆng qua h`m diˆn dich I = ( I,.I , ). u ıa ’ o o . o a ˜ . e a . e . ´ e a o . e . o a a a . o ’ o a D˘c biˆt, nˆu R l` mˆt quan hˆ n-ngˆi m` tˆp c´c r-vai tr` cua n´ l` rol (R) = {U1 , ..., Un } th` RI l` mˆt tˆp c´c bˆ du.o.c g´n nh˜n c´ dang U1 : d1 , ..., Un : dn , o. dˆy d1 , ..., dn ∈ I . ı a o a a o . . . . a a o . ’ a Ch´ng ta viˆ u ´t r[U ] k´ hiˆu gi´ tri du.o.c kˆt ho.p v´.i U -th`nh phˆn cua bˆ r. e y e . a . . e ´ . o a ` a ’ o . C´c cˆ u tr´c m´.i du.o.c diˆn dich nhu. sau: a a ´ u o . ˜ . e R[U ]I = {(d, r) ∈ I × RI |d = r[U ]} R[U, U ]I = {(d, d) ∈ I × I |∃r ∈ RI .d = r[U ] ∧ d = r[U ]} ( 1R[U ])I = {d ∈ I |ton tai nhieu nhat mot r ∈ RI |sao cho r[U ] = d}, (∀R[U ])T1 : C1 , ..., Tm : Cm )I = {d ∈ I |∀r ∈ RI .r[U ] = d → (r[T1 ] ∈ C1 , ..., r[Tm ] ∈ Cm )}, I I (∃R[U ])T1 : C1 , ..., Tm : Cm )I = {d ∈ I |∃r ∈ RI .r[U ] = d ∧ r[T1 ] ∈ C1 ∧, ..., ∧r[Tm ] ∈ Cm )}. I I CIFR-TBoxes du.o.c dinh ngh˜ l` mˆt tˆp h˜.u han c´c kh˘ng dinh bao h`m C1 ⊆ C2 , o. . . ıa a o a u. . . a ’ a . a ’ dˆy C1 , C2 l` c´c kh´i niˆm t` y y cu a a a a e . u ´ ’ a CIFR. CIFR-ABoxes du.o.c dinh ngh˜ l` mˆt tˆp h˜.u han c´c kh˘ng dinh A(a) v´.i a l` mˆt thˆ . . ıa a o a u . . . a ’ a . o a o. e’ hiˆn cu e . ’ a kh´i niˆm nguyˆn tˆ A, c´c kh˘ng dinh P (a, b) v´.i (a, b) l` mˆt thˆ hiˆn cua vai tr` a e . e o ´ a a’ . o a o . ’ e ’ e . o nguyˆn tˆ P v` c´c kh˘ng dinh R(U1 : d1 , ..., Un : dn ) v´.i U1 : d1 , ......, Un : dn . l` mˆt thˆ e o ´ a a ’ a . o a o. e’ e ’ hiˆn cua quan hˆ n-ngˆi R. . e . o T´ thoa m˜n cua kh´i niˆm c˜ng nhu. ph´p k´o theo logic trong CIFR-TBoxes du.o.c ınh ’ a ’ a e . u e e . dinh ngh˜ nhu o ıa . thˆng thu.`.ng nˆn ch´ ng tˆi khˆng dˆ cˆp dˆn trong phˆn n`y n˜.a. o e u o o ` a e e . ´ ` a a u . ´ ˆ ´ ˆ ´ ˆ 3. KIEN TRUC HE THONG . Câu truy v n ngôn ng t nhiên Các module ph thu c mi n T i n t v ng và B phân tích cú pháp các lu t cú pháp Cây cú pháp B thông d ch ng nghĩa T i n ng nghĩa Truy v n d ng logic Sơ CSDL quan h và B d ch LQL thành SQL các ràng bu c toàn v n Truy v n SQL DBMS quan h CSDL quan h K t qu truy v n B sinh câu tr l i Tr l i ı ´ e . ´ H`nh 1. Kiˆn tr´c hˆ thˆng u e o
274 ˜ ˆ NGUYEN KIM ANH Trong phˆn n`y, ch´ng tˆi s˜ tr` b`y mˆt kiˆn tr´c ph´c thao dˆi v´.i hˆ truy vˆ n ngˆn ` a a u o e ınh a o e . ´ u a ’ o o e ´ . a´ o ng˜ .u. tu. nhiˆn v` mˆt sˆ phˆn t´ liˆn quan dˆn ph´p dich c´c cˆu truy vˆn ngˆn ng˜. tu. e a o o a ıch e ´ ´ e e . a a a´ o u . . nhiˆn th`nh dang logic. e a . Theo kiˆn tr´c trong H` 1, cˆu truy vˆ n ngˆn ng˜. tu. nhiˆn tru.´.c tiˆn du.o.c phˆn t´ ´ e u ınh a ´ a o u . e o e . a ıch ’.i bˆ phˆn t´ c´ ph´p. Bˆ phˆn t´ c´ ph´p tham chiˆu dˆn t`. diˆn t`. vu.ng dˆ phˆn bo o a ıch u a . o a ıch u a . ´ e u e u . e ´ ’ e’ a t´ch c´c t` o a a u . c´ ngh˜a trong cˆu truy vˆ n tu. nhiˆn, x´c dinh loai t`. v` t`.ng bu.´.c tao nˆn cˆy ı a ´ a . e a . . u a u o . e a c´ ph´p dˆ o a u a o ´i v´.i cˆu truy vˆ n thˆng qua mˆt tˆp c´c luˆt c´ ph´p. Tiˆp sau d´, cˆy phˆn ´ a o o a a . . a u a . ´ e o a a t´ c´ ph´p kˆt qua du.o.c xu. l´ bo.i bˆ thˆng dich ng˜. ngh˜ dˆ hiˆ u ngh˜ cua cˆu truy vˆ n ıch u a e ´ ’ . ’ y ’ o o . . u ıa e e ’ ’ ıa ’ a ´ a v` sinh ra cˆu truy vˆ a a a´n dang logic. Ngˆn ng˜. du.o.c lu.a chon dˆ biˆu diˆn c´c cˆu truy vˆ n . o u . . . e’ e ’ ˜ a a e ´ a logic phai c´ kha n˘ng mˆ ta hay dinh ngh˜ du.o.c c´c t´ chˆ t hay c´c diˆu kiˆn tr´ r´ t ’ o ’ a o ’ . ıa . a ınh a ´ a ` e e. ıch u du.o.c t`. cˆu truy vˆ n dˆu v`o. Ch´ng tˆi dˆ nghi su. dung mˆt logic mˆ ta nhu. mˆt ngˆn . u a ´ a a a ` u o ` e . ’ . o . o ’ o . o ng˜. trung gian dˆ biˆu diˆn c´c truy vˆ n logic du.´.i dang mˆt biˆ u th´.c logic mˆ ta. Tiˆp u ’ ’ e e ˜ a e ´ a o . o. e’ u o ’ ´ e a´ theo, cˆu truy vˆ n logic n`y s˜ du . . a a e .o.c dich th`nh mˆt truy vˆ n SQL m` c´ thˆ du.o.c thu.c hiˆn a o a´ a o e ’ e . . . . bo.i mˆt phˆn mˆm hˆ quan tri CSDL quan hˆ n`o d´ c´ hˆ tro. SQL. Bˆ sinh cˆu tra l`.i su. ’ o . `a `e e. ’ . e a o o o . . ˜ o . a ’ o ’ dung c´c kˆt qua cua truy vˆ n SQL dˆ du.a ra cˆu tra l`.i cho ngu.`.i su. dung. . a e ´ ’ ’ a´ e’ a ’ o o ’ . Dˆ gi´p cho bˆ phˆn t´ c´ ph´p c´ thˆ tao ra du.o.c cˆy phˆn t´ c´ ph´p dˆi v´.i cˆu ’ e u o a ıch u a o e . . ’ . a a ıch u a o o a ´ a ` ´ a a u truy vˆ n dˆu v`o, t` e . diˆn t`. vu.ng cua hˆ cˆn phai liˆt kˆ dˆy du tˆ t ca c´c dang t`. c´ thˆ ’ u . ’ e ` ’ e e ` ´ ’ a ’ a . ’ . a . a u o e ´ e xuˆ t hiˆn trong c´c cˆu truy vˆ n cua ngu o ’ . a a a ´ a ’ .`.i su. dung. Do vˆy, t`. diˆn t`. vu.ng phai ch´.a tˆ t a u e u . ’ ’ u a ´ . . ’ a ca c´c thˆng tin du . o .o.c biˆt vˆ CSDL quan hˆ nhu. tˆn c´c thu.c thˆ, c´c thuˆc t´ cua thu.c e ` ´ e e e a e’ a o ınh ’ . . . . thˆ v` c´c liˆn kˆt gi˜.a c´c thu.c thˆ du.o.c lu.u tr˜. trong CSDL n`y. Mˆt sˆ nh˜.ng thˆng ’ e a a e e ´ u a . e’ . u a o o u . ´ o tin cˆn thiˆt kh´c nhu. c´c t`. dˆ ng ngh˜ cua mˆt t`. vu.ng trong t`. diˆn v` tˆ t ca c´c gi´ ` a ´ e a a u o ` ıa ’ o u . . ’ u e a a ’ a ´ a tri miˆn dˆi v´.i c´c thuˆc t´ c˜ng cˆn du.o.c lu.u tr˜. trong t`. diˆ n t`. vu.ng. Ngo`i ra, mˆt . `e o o a ´ o ınh u . `a . u u e u . ’ a o. sˆ c´c ph´p to´n xuˆ t hiˆn trong c´c cˆu truy vˆ n nhu. c´c ph´p to´n so s´nh (l´.n ho.n, nho ´ o a e a ´ e a . a a a´ a e a a o ’ ho .n,....) v` c´c ph´p to´n logic (v`, ho˘c/hay, khˆng) c˜ng cˆn du.o.c du.a v`o trong t`. diˆ n a a e a a a o u ` a a u e ’ . . t`. vu.ng. D˘c biˆt, t`. diˆn n`y khˆng chı do.n gian lu.u tr˜. thˆng tin vˆ loai t`. (danh t`., t´ u . a . e u e a . ’ o ’ ’ u o ` . u e u ınh t`., dˆng t`.,...) m` lu.u ca c´c thˆng tin vˆ tˆ ho.p c´c tri th´.c liˆn quan dˆn t`. vu.ng. N´i u o . u a ’ a o e ’ ` o . a u e ´ e u . o a a u ’ c´ch kh´c, t` e . diˆn khˆng chı lu.u thˆng tin mˆt c´ch do.n gian vˆ t`. loai m` ca ngh˜ loai v` o ’ o o a ’ ` u . e a ’ ıa . a . c´c thˆng tin liˆn quan kh´c khi cˆn thiˆt. Dˆy l` nguˆ n d˜. liˆu chu yˆu vˆ thˆng tin thuˆc a o e a `a e´ a a ` o u e . ’ e ` o ´ e o. ınh ’ u t´ cua t` . . vu.ng phuc vu cho muc d´ phˆn t´ c´ ph´p c´c dang cˆu truy vˆ n c´ thˆ t`. ıch a ıch u a a . a ´ a o e u ’ . . . ngu.`.i su. dung v` cˆy phˆn t´ c´ ph´p kˆt qua cˆn ch´.a dˆy du nh˜.ng thˆng tin cˆn thiˆt o ’ . a a a ıch u a e ´ ’ ` a u ` a ’ u o `a e´ gi´p cho bˆ thˆng dich ng˜. ngh˜ c´ thˆ hiˆu du.o.c ngh˜ cua cˆu truy vˆ n dˆu v`o. u o o . . u ıa o e e ’ ’ . ıa ’ a ´ a a ` a T` e u . diˆn ng˜. ngh˜ cua hˆ gi´p cho bˆ thˆng dich ng˜. ngh˜ c´ thˆ hiˆu du.o.c cˆu truy ’ u ıa ’ e u o o u ıa o e e ’ ’ . . . . a a ` ´ a a vˆ n dˆu v`o. Do vˆy, y ngh˜ cua mˆi t` e e a ´ ıa ’ ˜ o u . . liˆt kˆ trong t`. diˆ n t`. vu.ng cˆn du.o.c mˆ ta y u e u . ’ ` a o ’ ´ . . ngh˜ trong t` e ıa u . diˆn ng˜. ngh˜ du.´.i dang mˆt vi t`. logic. Ch´ng tˆi c˜ng su. dung c`ng mˆt ’ u ıa o . o . u u o u ’ . u o . . logic mˆ ta du.o.c lu.a chon biˆu diˆn cˆu truy vˆ n logic dˆ mˆ ta c´c t`. vu.ng trong t`. diˆ n o ’ . . . e ’ ˜ a e ´ a ’ e o ’ a u . u e ’ t`. vu.ng. Bˆ thˆng dich ng˜. ngh˜ su. dung c´c vi t`. logic n`y dˆ h` th`nh nˆn cˆu truy u . o o . . u ıa ’ . a . u a e ınh a ’ e a ´ e ’ ´ ıa ’ vˆ n logic biˆ u thi y ngh˜ cua truy vˆ n dˆu v`o. Hai t` e a a a ´ a a ` a . diˆ n n`y v` so. dˆ CSDL quan hˆ l` u ’ o` e a . . `e a ` .o.c xˆy du.ng mˆi khi hˆ thˆng du.o.c c`i d˘t cho ˜ c´c module phu thuˆc miˆn v` cˆn phai du . a a . o. a ’ . o . ´ e o . a a . mˆt CSDL m´.i hay mˆt miˆn tri th´.c m´.i. Tuy nhiˆn, vˆ co. ban, hai t`. diˆn n`y c´ thˆ o . o o . `e u o e `e ’ u e ’ a o e ’ .o.c tao lˆp mˆt c´ch b´n tu. dˆng v´.i su. can thiˆp nhˆ t dinh t`. ngu.`.i quan tri hˆ thˆng. ´ du . . a . o a . a . o . o . e . a . u o ’ . e o . ´ ` o e a ` ’ ´ a .c hiˆn khi thiˆt Qua phˆn tr` b`y trˆn, c´ thˆ thˆ y r˘ ng, trong c´c nhiˆm vu cˆn thu a ınh a e a e. . ` a . e . e´ ´ kˆ v` c`i d˘t mˆt giao diˆn truy vˆn ngˆn ng˜ . e a a a o e ´ a o u . tu. nhiˆn dˆi v´.i c´c CSDL, nhiˆm vu thˆng e o o a ´ e . . . . . o dich ng˜. ngh˜ nh˘ m dich c´c cˆu truy vˆ n dˆu v`o th`nh mˆt biˆu diˆn ng˜. ngh˜ cˆu truy . u ıa ` a . a a a ` a ´ a a o e . ’ ˜e u ıa a
ˆ ´ ´ ˆ ˆ ´ ˆ ´. ´ MOT CACH TIEP CAN DOI VO I PHEP DICH... . . . 275 vˆ n l` quan trong ho.n ca nhˆ t l` khi c´c truy vˆ n tu. nhiˆn du.o.c ph´t ra kh´ tu. do t`. nh˜.ng ´ a a . ´ ’ a a a ´ a . e . a a . u u .`.i su. dung khˆng chuyˆn vˆ tin hoc, khˆng c´ nh˜.ng hiˆu biˆt dˆy du v` nhˆ t dinh vˆ ngu o ’ . o e ` e o o u e ’ ´ a e ` ’ a a . ´ `e . CSDL cˆ ` n tra c´.u. Do vˆy, trong phˆn tiˆp theo, ch´ng tˆi ch´ trong v`o nhiˆm vu dich c´c a u a . ` a e ´ u o u . a e . . . a cˆu truy vˆ n tu. nhiˆn th`nh dang logic c´ thˆ thu.c hiˆn du.o.c. a ´ a . e a . o e .’ e . . ˆ ˆ´ . ˆ ` 4. DICH CAU TRUY VAN TU NHIEN THANH DANG LOGIC . . . Dˆ biˆu diˆn y ngh˜ cua c´c t`. vu.ng trong t`. diˆ n t`. vu.ng, ch´ng tˆi su. dung mˆt logic ’ ’ e e ˜ ´ e ıa ’ a u . u e u .’ u o ’ . o . mˆ ta a o ’ d˘c biˆt, CIFR, d˜ du.o.c gi´.i thiˆu trong Muc 2.2. . e . a . o e. . 4.1. Dich so. dˆ thu.c thˆ - liˆn kˆt th`nh CIFR-TBoxes . o` . e ’ e ´ e a 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ˆ e’ - liˆn kˆt c´ thˆ du.o.c n˘m b˘t trong CIFR thˆng qua mˆt ph´p dich t`. so. dˆ thu.c thˆ e e o e ´ ’ . a ´ ´ a o o. e . u ` o . e’ e e ´ - liˆn kˆt th`nh CIFR-TBoxes. a Co ’. so. tri th´.c CIFR-TBoxes du.o.c suy ra t`. mˆt so. dˆ thu.c thˆ - liˆn kˆt S du.o.c x´c u u o ` o . e’ e e ´ . . . a dinh nhu . sau: . + Co. so. tri th´.c n`y ch´.a mˆt kh´i niˆm nguyˆn tˆ A dˆi v´.i mˆ i miˆn gi´ tri thuˆc ’ u a u o . a e . e o ´ ´ o o ˜ o ` e a . o. t´ hay mˆ ınh o˜i thu.c thˆ A, mˆt vai tr` nguyˆn tˆ P dˆi v´.i mˆi thuˆc t´ P v` mˆt quan hˆ . e’ o. o e o ´ ´ o o o ˜ o ınh . a o . e . n + m-ngˆi R dˆi v´.i mˆi liˆn kˆt R n-ngˆi (k´o theo n thu.c thˆ) c´ m thuˆc t´ liˆn kˆt. o ´ o o o e e ˜ ´ o e . ’ e o o ınh e e . ´ Tˆp c´c kh˘ng dinh bao h`m cua co. so. tri th´.c du.o.c x´c dinh nhu. sau: a a . ’ a . a ’ ’ u . a . + V´.i mˆ i c˘p c´c 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’ a o . u o a ’ . E ⊆ F v´ o .i E v` F l` c´c kh´i niˆm nguyˆn tˆ u.ng v´.i c´c thu.c thˆ E v` F. a a a a e e o´ ´ o a e’ a . . + V´.i mˆ i thu.c thˆ E c´ c´c thuˆc t´ A1 , A2 , ....., Ak v´.i c´c miˆn D1 , D2 , ....., Dk o o˜ . e’ o a o ınh . o a ` e tu .o.ng u.ng, ch´ng ta c´ kh˘ng dinh: ´ u o a ’ . E ⊆ ∀A1 .D1 Π........Π∀Ak .Dk Π( 1A1 )Π......Π( 1Ak ). + V´.i mˆ i liˆn kˆt n-ngˆi R gi˜.a n thu.c thˆ E1 , ...., En c´ m thuˆc t´ liˆn kˆt T1 , ..., Tm ˜ o o e e ´ o u . e’ o o ınh e e . ´ o.i c´c miˆn D , D , ....., D , tu.o.ng u.ng, ch´ng ta c´ kh˘ng dinh: v´ a `e ´ u o a ’ 1 2 m . Ei ⊆ ∀R[Ei ].T1 : D1 , ....., Tm : Dm . . . ’ 4.2. Dich nˆi dung cua CSDL quan hˆ th`nh CIFR-ABoxes o e a . V´ o.i mˆi miˆn D ch´.a c´c gi´ tri r`.i rac v` h˜.u han, ch´ng ta c´ kh˘ng dinh: D(d) v´.i ˜ o ` e u a a . o . a u u o a ’ o . . ’ . e e ’ d l` mˆt thˆ hiˆn cua D. a o . 4.3. Phˆn t´ c´ ph´p cˆu truy vˆ n ngˆn ng˜. tu. nhiˆn a ıch u a a a´ o u . e Tru.´.c tiˆn, bˆ phˆn t´ c´ ph´p tra c´.u t`. diˆn t`. vu.ng dˆ phˆn t´ch c´c t`. c´ ngh˜ o e o a ıch u a . u u e u . ’ ’ e a a a u o ıa trong cˆu truy vˆ o a ´n dˆ ng th`.i x´c dinh loai t`. c˜ng nhu. nh˜.ng thˆng tin cˆn thiˆt kh´c c´ a ` o a . . u u u o ` a ´ e a o liˆn quan dˆn t`. du.o.c lu.u tr˜. trong t`. diˆ n t`. vu.ng. Du.a trˆn nh˜.ng thˆng tin n`y v` mˆt e ´ e u . u u e u .’ . e u o a a o . . . o a ıch u a e a . . a´ tˆp c´c luˆt c´ ph´p, bˆ phˆn t´ c´ ph´p s˜ x´c dinh cˆ u tr´c c´ ph´p cua cˆu truy vˆ n a a a u a u u a ’ a ´ a dˆu v`o v` d˘c biˆt, x´c dinh dang cua cˆu truy vˆn (cˆu c´ t`. dˆ hoi, cˆu nghi vˆ n, cˆu ` a a a a . e . a . . ’ a a´ a o u e ’ a ’ a´ a .c v´.i h`m y yˆu cˆu,...). Trong ng˜. canh cua ch´ ng tˆi, dˆ bˆ phˆn t´ c´ mˆnh lˆnh th´ o a ´ e a e e u ` u ’ ’ u ’ o a ıch u o e . . . ph´p c´ thˆ phˆn t´ cˆu truy vˆ n dˆu v`o mˆt c´ch hiˆu qua v` x´c dinh du.o.c dang cˆu ’ a o e a ıch a a ` ´ a a o a . e . ’ a a . . . a ´ truy vˆn, mˆt tˆp c´c luˆt c´ ph´p du . a a o a a a u a .o.c xˆy du.ng du.a trˆn viˆc liˆt kˆ c´c dang cˆu truy e e e e a . a . . . . . . . vˆ n c´ thˆ t`. ngu.`.i su. dung cˆn du.o.c bˆ sung v`o tˆp c´c luˆt c´ ph´p cua hˆ thˆng. Cˆ u ´ a o e u ’ o ’ . ` a . ’ o . a a a. a u a ’ e o . . ´ ´ a
276 ˜ ˆ NGUYEN KIM ANH tr´c c´ ph´p kˆt qua cua cˆu truy vˆ n dˆu v`o s˜ du.o.c xu. l´ tiˆp bo.i bˆ thˆng dich ng˜. u u a e ´ ’ ’ a a ` ´ a a e . ’ y e ´ ’ o o. . u ngh˜ıa. 4.4. Dich cˆy phˆn t´ c´ ph´p th`nh cˆu truy vˆn logic . a a ıch u a a a ´ a Dˆ thˆng dich ng˜. ngh˜ c´c cˆu truy vˆ n tu. nhiˆn dˆi v´.i mˆt CSDL quan hˆ, ch´ ng tˆi ’ e o . u ıa a a ´ a . e o o o ´ . e . u o ’ bˆ sung v`o tˆp c´c kh´i niˆm nguyˆn tˆ cua CIFR mˆt tˆp dˆm du . a o a a a a e e o ’ ´ o a e ´ .o.c c´c kiˆ u co. so. , du.o.c e’ ’ . . . . . k´ hiˆu l` B v´ y e a o .i B = {Int, Real, String, Bool, Date, d1 , d2 }, o. dˆy, c´c d k´ hiˆu c´c phˆn ’ a a k y e a `a . . tu. cua Int ∪ Real ∪ String ∪ Bool ∪ Date. Ngo`i ra, dˆ thˆng dich du.o.c c´c ph´p so s´nh, ’ ’ a ’ e o . . a e a ch´ng tˆi bˆ u o o ’ sung v`o tˆp c´c vai tr` nguyˆn tˆ cua CIFR mˆt vai tr` nguyˆn tˆ L´.nHo.n v` a a a . o e o ´ ’ o. o e o ´ o a dinh ngh˜ c´c vai tr` sau: B˘ ng = id(Int ∪ Real), L´.nHo.nHo˘cB˘ ng = L´.nHo.n . ıa a o ` a o a ` . a o ` B˘ ng, a NhoHo.n = L´.nHo.n, NhoHo.nHo˘cB˘ ng = NhoHo.n ’ o ’ a ` . a ’ ` B˘ ng. a Muc d´ cua bˆ thˆng dich ng˜. ngh˜ c˜ng nhu. c´c giao diˆn truy vˆ n ngˆn ng˜. tu. . ıch ’ o o . . u ıa, u a e . a´ o u . e a ` nhiˆn kh´c, cˆn phai tr´ ra nh˜ a ’ ıch u .ng thˆng tin cˆn thiˆt t`. cˆu truy vˆ n tu. nhiˆn cua ngu.`.i o `a ´ e u a ´ a . e ’ o ’. dung dˆ c´ thˆ ph´t biˆ u du.o.c mˆt cˆu truy vˆ n c´ thˆ thu.c hiˆn du.o.c dˆi v´.i mˆt CSDL su . e’ o e a e ’ ’ o a ´ a o e ’ . e ´ . . . . o o o . quan hˆ. Do vˆy, dˆi v´.i mˆ i cˆu truy vˆ n tu. nhiˆn, ch´ng ta cˆn x´c dinh du.o.c ba phˆn: e. a. ´ o o ˜ o a ´ a . e u `a a . . `a danh s´ch c´c thuˆc t´ cˆn du a a o ınh ` a .a ra, c´c thu.c thˆ c´ liˆn quan v` c´c diˆu kiˆn r`ng buˆc a e ’ o e a a ` e e a o . . . . cua truy vˆ n. Sau khi phˆn t´ c´ ph´p cˆu truy vˆ n, ch´ng ta d˜ x´c dinh du.o.c dang cˆu ’ ´ a a ıch u a a ´ a u a a . . . a truy vˆ n v` cˆ u tr´ c c´ ph´p cua cˆu. Tuy nhiˆn, dˆ hiˆ u du.o.c cˆu truy vˆ n n`y, ch´ng ta ´ a a a ´ u u a ’ a e ’ ’ e e . a ´ a a u cˆn biˆt y ngh˜ cua mˆi t`. hay cum t`. c´ ngh˜ trong cˆu truy vˆ n dˆu v`o. Mˆ i t`. hay `a ´ e ´ ıa ’ ˜ o u . u o ıa a ´ a a a ` ˜ o u cum t`. n`y c´ thˆ l` tˆn cua mˆt thu.c thˆ , mˆt thuˆc t´ . u a o e a e ’ ’ o . . ’ e o . o ınh, mˆt liˆn kˆt, mˆt gi´ tri thuˆc . o e e . ´ o a . . o . t´ ınh, mˆt ph´p so s´nh hay ph´p to´n logic. Kh´ kh˘n cu o . e a e a o a ’ a nhiˆm vu thˆng dich l` nh˜.ng y e . . o . a u ´ dinh cua ngu.`.i su. dung c´ thˆ biˆ u thi mˆt c´ch khˆng tru.c tiˆp v` tiˆm t`ng nhiˆu nhˆp . ’ o ’ . o e e ’ ’ . o a . o . e a ` ´ e a `e a . nh˘ ` ng trong cˆu truy vˆ n du.a v`o. V` vˆy, nh˜.ng thˆng tin tr´ r´ t ra du.o.c t`. cˆu truy a a ´ a a ı a . u o ıch u . u a vˆ n du.a v`o c´ thˆ l` khˆng dˆy du v` khˆng r˜ r`ng. ´ a a o e a o ’ `a ’ a o o a Thˆng thu o o .`.ng, viˆc x´c dinh y ngh˜ cua c´c t`. hay cum t`. c´ ngh˜ khˆng phai luˆn e a . ´ ıa ’ a u u o ıa o ’ o . . luˆn tˆ o a ` m thu.`.ng. Trong qu´ tr` thˆng dich, bˆ thˆng dich phai tham chiˆu dˆn t`. diˆ n o a ınh o . o o . . ’ ´ e u e e ´ ’ . ngh˜ hay su. dung c´c tri th´.c cua hˆ dˆ x´c dinh y ngh˜ ph` ho.p nhˆ t dˆi v´.i cho c´c ng˜ u ıa ’ . a u ’ e e a . ´ . ’ ıa u . ´ ´ a o o a t` u . hay cum t`. . u . Danh s´ch thuˆc t´ cˆn du.a ra dˆi v´.i truy vˆ n cua ngu.`.i su. dung phu thuˆc v`o nh˜.ng a o ınh ` . a ´ o o ´ a ’ o ’ . . o a . u thuˆc t´ n`o ngu.`.i su. dung muˆn du.a ra trong cˆu tra l`.i. Hˆ thˆng cua ch´ng tˆi x´c o ınh a . o ’ . ´ o a ’ o e o . ´ ’ u o a dinh hai loai truy vˆ n v`o: loai th´. nhˆ t c´ danh s´ch thuˆc t´nh du.a ra tu.`.ng minh v` loai . . ´ a a . u a o ´ a o ı . o a . th´. hai khˆng c´ danh s´ch thuˆc t´ du.a ra. u o o a o ınh . 1. C´c dang cˆu truy vˆn thuˆc loai th´. nhˆ t: a . a ´ a o . . u a ´ + Cˆu truy vˆ n v´ o a ´ a o . .i dˆng t`. h`m y ‘yˆu cˆu’ d´.ng dˆu. C´c dˆng t`. h`m y ‘yˆu cˆu’ nhu.: u a ´ e ` a u ` a a o u a ´ e ` a . liˆt kˆ, cho biˆ e e . ´t, du.a ra,... luˆn luˆn du.o.c su. dung dˆ ph´t ra mˆt yˆu cˆu tra c´.u thˆng tin e o o . ’ . e’ a o e a . ` u o trong mˆt CSDL. C´c dˆng t`. n`y khˆng chuyˆn h`nh dˆng. Do vˆy, ch´ ng ta khˆng cˆn o. a o . u a o e’ a o . a . u o `a ´t ho.p n´ v´.i mˆt vi t`. biˆu diˆn liˆn kˆt n`o ca. Tuy nhiˆn, nh˜.ng danh t`. d´.ng ngay kˆ . e o o o . u e . ’ ˜ e e a ’ e ´ e u u u sau nh˜.ng dˆng t`. n`y cho ph´p x´c dinh du.o.c nh˜.ng thuˆc t´ hay thu.c thˆ cˆn du.a ra u o. u a e a . . u o ınh . . ’ a e ` trong cˆu tra l` a ’ o .i cho ngu.`.i su. dung. o ’ . + Cˆu truy vˆ o u e ’ a a´n c´ t`. dˆ hoi. Bˆ thˆng dich x´c dinh c´c thuˆc t´ du.o.c nh˘c t´.i bo.i ’ o o . . a . a o ınh . . ´ a o ’ .`.i su. dung, cu thˆ d´ l` nh˜.ng thuˆc t´ c´ xuˆ t hiˆn trong cˆu du.a v`o nhu.ng khˆng ngu o ’ . ’ ´ e . e o a u o ınh o a . . a a o tham gia v`o viˆc x´c dinh c´c diˆu kiˆn truy vˆ n. Nh˜ a e a . a ` e e a´ u.ng thuˆc t´ n`y s˜ du.o.c du.a v`o o ınh a e a . . . . danh s´ch thuˆc t´ cˆn du.a ra mˆt c´ch tu. dˆng. Ch´ng tˆi cho r˘ ng, c´c thuˆc t´nh du.o.c a o ınh ` . a o a . . . o u o ` a a o ı . .
ˆ ´ ´ ˆ ˆ ´ ˆ ´. ´ MOT CACH TIEP CAN DOI VO I PHEP DICH... . . . 277 su. dung trong c´c diˆu kiˆn truy vˆn d˜ c´ gi´ tri v` nh˜.ng thuˆc t´ khˆng thuˆc diˆu kiˆn ’ . a ` e e . ´ a a o a . a u o ınh o . o ` . e e . truy vˆ n cˆn phai tra c´ a ` a ` ´ a ’ u .u v` cˆn du.o.c du.a ra. a . 2. C´c dang cˆu truy vˆ a . a a´n thuˆc loai th´. hai: Dˆi v´.i c´c cˆu truy vˆ n thuˆc loai n`y, hˆ s˜ o. . u ´ o o a a a´ o. . a e e . du .a ra c´c thuˆc t´ ngˆm dinh dˆi v´.i thu.c thˆ du.o.c nh˘c t´.i bo.i ngu.`.i su. dung. C´ thˆ a o ınh ` a ´ o o e’ ´ a o ’ o ’ . o e ’ . . . . thˆ a a´y r˘ ng, phˆn thˆng tin cˆn thiˆt v` quan trong nhˆ t cˆn tr´ r´t t`. cˆu truy vˆ n dˆu ` ` a o ` a ´ a e . ´ ` a a ıch u u a ´ ` a a v`o l` c´c diˆu kiˆn r`ng buˆc cua truy vˆ n do c´c thu.c thˆ c´ liˆn quan d˜ du.o.c x´c dinh a a a ` e e a . o ’ . a´ a . ’ e o e a . a . e ’ ` a ’ ˜ ` tiˆm ˆ n khi biˆu diˆn diˆu kiˆn r`ng buˆc cua truy vˆn. e e e e a . o ’ . a´ Dˆng t`. d´ng mˆt vai tr` rˆ t quan trong trong viˆc thˆng dich ng˜. ngh˜ cˆu truy vˆ n. o. u o o . o a ´ . e. o . u ıa a a´ Do vˆy, bˆ thˆng dich ng˜ a o o u. ngh˜ cua ch´ng tˆi lˆy dˆng t`. l`m th`nh phˆn trung tˆm cua ıa ’ u o a ´ o u a a ` a a ’ . . . . cˆu dˆ x´c dinh c´c chu thˆ v` dˆi tu.o.ng c´ liˆn quan dˆn dˆng t`. hay x´c dinh c´c vai tr` a e a . ’ a ’ e a o ’ ´ . o e ´ . e o u a . a o ng˜ u . ngh˜ cua dˆng t`.. Tiˆp theo, ch´ng ta s˜ lˆn lu.o.t x´t c´c dˆng t`. xuˆ t hiˆn trong cˆy ıa ’ o u e´ u e ` a ´ e . . e a o . u a . a a ıch u a e a . ’ phˆn t´ c´ ph´p dˆ x´c dinh diˆu kiˆn r`ng buˆc cua truy vˆ n. ` e e a . o ’ . a´ a. Dˆng t`. dang x´t tu.o.ng u.ng v´.i mˆt quan hˆ n-ngˆi trong co. so. tri th´.c cua hˆ. o. u e ´ o o . e. o ’ u ’ e . + Dich dˆng t` a o u . th`nh quan hˆ n-ngˆi tu.o.ng u.ng dˆ ng th`.i x´c dinh c´c cum danh t`. hay e o ´ ` o o a . a . u . . . mˆnh dˆ d´ng vai tr` chu thˆ v` dˆi tu.o.ng cua dˆng t`. tu.o.ng u.ng v´.i c´c thu.c thˆ tham e . ` o e o ’ e a o ’ ´ . ’ o . u ´ o a . e’ gia v`o liˆn kˆt du.o.c biˆu diˆn bo.i quan hˆ n - ngˆi n`y. Ngo`i ra, doan trang ng˜. cua cˆu a e e ´ . e’ ˜ e ’ e. o a a . . u ’ a s˜ du.o.c dich th`nh thuˆc t´ cua liˆn kˆt d˜ x´c dinh. e . . a o ınh ’ e e a a . . ´ + Dich c´c danh t`. d´.ng dˆu cum danh t`. th`nh c´c kh´i niˆm tu.o.ng u.ng v´.i c´c thu.c . a u u `a . u a a a e . ´ o a . thˆ d˜ x´c dinh. Thˆng thu.`.ng, c´c cum danh t`. n`y c´ thˆ c´ mˆt sˆ dinh ng˜. bˆ ngh˜ ’ e a a . o o a . u a o e o o o . ’ . ´ u o ’ ıa cho danh t` u u. d´.ng dˆu. C´c dinh ng˜. n`y c´ thˆ l` c´c danh t`., t´ t`. hay mˆt mˆnh dˆ. `a a . u a o e a a ’ u ınh u o e `e . . Tra c´ u e u .u t`. diˆ n ng˜. ngh˜ dˆi v´.i c´c danh t`. v` t´ t`., ch´ng ta c´ thˆ x´c dinh du.o.c c´c ’ u ıa o ´ o a u a ınh u u o e ’ a . . a dinh ng˜. n`y tu.o.ng u.ng v´.i thuˆc t´ v`/hay gi´ tri thuˆc t´ cua thu.c thˆ d˜ x´c dinh. . u a ´ o o ınh a . a . o ınh ’ . . ’ e a a . Dich c´c dinh ng˜. n`y th`nh c´c r`ng buˆc gi´ tri dˆi v´.i c´c vai tr` tu.o.ng u.ng. . a . u a a a a o . a . o o a ´ o ´ Tru.`.ng ho.p bˆ ng˜. cua dˆng t`. hay dinh ng˜. cua danh t`. l` mˆnh dˆ s˜ du.o.c x´t tiˆp o . ’ o u ’ o . u . u ’ u a e . ` e e . e e ´ sau dˆy. a b. Dˆng t`. dang x´t khˆng tu.o.ng u.ng v´.i mˆt quan hˆ n-ngˆi trong co. so. tri th´.c cua hˆ. o. u e o ´ o o . e. o ’ u ’ e . Trong tru o .`.ng ho.p n`y, dˆng t`. dang x´t khˆng chuyˆn h`nh dˆng m` chı mˆ ta mˆt thuˆc a o u e o ’ e a o a ’ o ’ o o . . . . . t´ cua thu.c thˆ d´ng vai tr` chu thˆ cua dˆng t`. v` bˆ ng˜. cua dˆng t`. c´ thˆ danh ınh ’ . ’ e o o ’ e ’ ’ o. u a o u ’ ’ o . u o e ’ t`./t´ t`. hay mˆt cum danh t`.. u ınh u o . . u + Bˆ u a o ’ ng˜. l` danh t`./t´ t`.: Tra c´.u t`. diˆ n ng˜. ngh˜ dˆ x´c dinh danh t`./t´ t`. u ınh u u u e ’ u ıa e a . ’ u ınh u a a a . ’ n`y l` gi´ tri cua thuˆc t´ n`o dˆi v´ o ınh a o o ´ .i thu.c thˆ d˜ x´c dinh. Dich bˆ ng˜. n`y th`nh r`ng ’ e a a . ’ o u a a a . . . buˆc gi´ tri dˆi v´ a o a . o o ´ .i c´c vai tr` tu.o.ng u.ng o ´ . + Bˆ ng˜. l` cum danh t`.: Dich danh t`. d´.ng dˆu th`nh vai tr` tu.o.ng u.ng v´.i mˆt thuˆc ’ o u a . u . u u `a a o ´ o o . o . ınh ’ t´ cua thu .c thˆ d˜ x´c dinh v` dich dinh ng˜. cua danh t`. d´.ng dˆu th`nh r`ng buˆc gi´ ’ e a a . a . u ’ u u `a a a o a . . . tri dˆ o . o ´i v´.i vai tr` d˜ x´c dinh (c´ thˆ thˆng qua mˆt ph´p to´n so s´nh). o a a . o e ’ o o . e a a c. Dich c´c t`. chı quan hˆ ‘v`’, ‘ho˘c/hay’ th`nh c´c ph´p to´n , trong CIFR tu.o.ng u.ng. . a u ’ e a . a . a a e a ´ d. Dich t` ’ u. chı phu dinh ‘khˆng’ th`nh ph´p ¬ trong CIFR tu.o.ng u.ng. ’ . o a e ´ . e. C´c dang truy vˆn d˘c biˆt: a . ´ . a a e . + Cˆu truy vˆ n o. dang nghi vˆ n v´.i dˆng t`. ‘l`’: Dˆng t`. ‘l`’ l` dˆng t`. liˆn hˆ thu.`.ng a ´ a ’ . ´ a o o . u a o. u a a o . u e e . o du ..o.c su. dung dˆ mˆ ta chu thˆ cua dˆng t`.. C´c dˆng t`. n`y khˆng chuyˆ n h`nh dˆng. Do ’ . e’ o ’ ’ e ’ o ’ u a o u a o e’ a o . . . vˆy, ch´ng ta khˆng cˆn kˆt ho.p n´ v´.i mˆt vi t`. biˆu diˆn liˆn kˆt n`o ca. a . u o ` e . a ´ o o o . u e . ’ ˜ e e a ’ e ´ + Cˆu truy vˆ n o. dang so. h˜.u: ch´ y r˘ ng, mˆt sˆ liˆn kˆt c´ thˆ du.o.c truy vˆ n du.´.i a ´ a ’ . ’ u u´ ` a . ´ o o e e o e ´ ’ . a´ o dang so u ’. h˜.u nhu. ‘h˜y liˆt kˆ c´c A cua B’. Trong tru.`.ng ho.p n`y, khˆng c´ dˆng t`. n`o a e e a ’ o a o o o u a . . . .
278 ˜ ˆ NGUYEN KIM ANH xuˆ t hiˆn trong cˆu truy vˆ n tu. nhiˆn v` do vˆy khˆng thˆ x´c dinh du.o.c c´c liˆn kˆt cˆn ´ e a . a ´ a . e a a . o ’ e a . . a e e ` ´ a e u . cˆu dˆu v`o dˆ dich cˆu truy vˆ n n`y th`nh dang logic c´ thˆ thu.c hiˆn du.o.c. Dˆi thiˆt t` a ` a e . ´ a ’ a ´ a a a o e .’ e o´ . . . .i c´c cˆu truy vˆ n dang n`y, trong qu´ tr`nh dich, tru.´.c tiˆn, hˆ s˜ dich c´c cum danh t`. v´ a a o ´ . a a a ı o e e e . a . u . . (A v` B) th`nh c´c kh´i niˆm/vai tr` tu.o.ng u.ng. Tiˆp sau d´, du.a trˆn co. so. tri th´.c cua a a a a e . o ´ ´ e o . e ’ u ’ hˆ, hˆ s˜ suy diˆn dˆ thiˆt lˆp c´c du.`.ng dˆ n c´ thˆ gi˜.a c´c kh´i niˆm/vai tr` n`y v` cho e e e . . ˜ e e ’ ´ . e a a o ˜ a o e u a ’ a e . o a a o ’ ´ ´ ’ ph´p mˆ ta chi tiˆt cˆu truy vˆ n logic c´ thˆ thu e e a a o e . .c hiˆn du.o.c. Trong tru.`.ng ho.p tˆ n tai nhiˆu e o ` ` . . . o . e .`.ng dˆ n c´ thˆ, ngu.`.i su. dung s˜ du.o.c hoi dˆ kh˘ng dinh mˆt du.`.ng dˆn ph` ho.p v´.i y du o ˜ a o e ’ o ’ . e ’ e ’ a ’ o o ˜ a u . o ´ . . . dinh cua ngu.`.i su. dung. . ’ o ’ . ˆ ´ 5. MOT SO V´ DU MINH HOA ˆ I . . . Cˆu 1. H˜y du.a ra tˆn c´c sinh viˆn o. H` Nˆi v` sinh sau n˘m 85: TˆnSV l` thuˆc t´ a a e a e ’ a o a . a e a o ınh . ` cˆn du a .a ra v` biˆu th´.c logic mˆ ta l`: ∃ DiaChı◦H`Nˆi ∃ N˘mSinh◦L´.nHo.n◦85. a e ’ u o ’ a ’ a o a o . . Cˆu 2. Cho biˆt c´c giang viˆn chı day mˆn Co. so. d˜. liˆu hay mˆn Hˆ quan triCSDL: a ´ e a ’ e ’ . o ’ u e . o e ’ . . ∀ Day[GV, MˆnHoc]◦TˆnMˆn◦(Co ’ u e o . e o . so. d˜. liˆu Hˆ quan tri CSDL). e ’ . . . . ´ e ’ Cˆu 3. Cho biˆt c´c sinh viˆn cua giang viˆn A: a e a ’ e Hˆ x´c dinh du . e a . .o.c 2 du.`.ng dˆn gi˜.a SV v` GV l`: o ˜ a u a a . 1. SV Hoc MˆnHoc Day GV v` . o . . a 2. SV Hu o .´.ngDˆn GV. ˜ a .`.i su. dung s˜ du.o.c hoi dˆ lu.a chon du.`.ng dˆn ph` ho.p: Ngu o ’ . e ’ ’ e . o ˜ a u . . . 1. ∃ Hoc[SV, MˆnHoc]◦Day[MˆnHoc, GV]◦TˆnGV◦A. . o . . o . e 2. ∃ Hu o .´.ngDˆn [SV, GV]◦ TˆnGV◦ A a˜ e ´ ´ ` ˆ ´ ˆ 6. DANH GIA VA KET LUAN . Ch´ ng tˆi d˜ tiˆn h`nh c`i d˘t thu. nghiˆm mˆt hˆ truy vˆ n ngˆn ng˜. tu. nhiˆn tiˆng Viˆt u o a e a ´ a a . ’ e . o e . . a´ o u . e e ´ e. ´ .i CSDL Quan l´ hoc tˆp mˆt kho´ cua tru.`.ng Dai hoc B´ch khoa H` Nˆi. Hˆ thˆng dˆi v´ o o ’ y . a . o . a ’ o . . a a o . . ´ e o c`i d˘t d˜ d´p u.ng du.o.c c´c yˆu cˆu v` muc tiˆu dˆ ra dˆi v´.i mˆt hˆ thˆng truy vˆ n ngˆn a a a a ´ . . a e ` a . a e ` e ´ o o o e o . . ´ ´ a o . tu. nhiˆn. Tuy nhiˆn, hiˆu qua cua hˆ thˆng phu thuˆc rˆ t nhiˆu v`o vˆn t`. vu.ng m` ta ng˜ . u e e e. ’ ’ e o . ´ . . ´ o a ` a o u . e ´ a du.a v`o. Dˆy ch´ l` kh´ kh˘n l´.n nhˆ t v` c˜ng l` vˆ n dˆ co. ban cua bˆ t k` hˆ thˆng xu. a a ınh a o a o ´ a a u a a `´ e ’ ´ ’ a y e o . ´ ’ l´ ngˆn ng˜ . y o u. tu. nhiˆn n`o - su. hiˆ u biˆt cua n´ vˆ CSDL cu thˆ. e a ’ e ’ o ` ´ ’ . e e . e Theo d´nh gi´ cua ch´ng tˆi, c´ch tiˆp cˆn dich c´c cˆu truy vˆ n tu. nhiˆn tiˆng Viˆt a a ’ u o a ´ . e a . a a ´ . a e ´ e e. du.o.c gi´.i thiˆu trong b`i n`y th`nh mˆt biˆ u th´.c logic mˆ ta l` rˆ t c´ triˆ n vong. Cˆu truy . o e . a a a o e . ’ u ´ o ’ a a o e . ’ a vˆ n o. dang logic n`y kh´ tu. nhiˆn v` rˆt gˆn v´.i cˆu truy vˆn tu. nhiˆn. Ho.n n˜.a, su. dung ´ a ’ . a a . e a a ` ´ a o a ´ a . e u ’ . kha a’ n˘ng lˆp luˆn cua hˆ logic mˆ ta, ch´ng ta c´ thˆ dich du.o.c c´c truy vˆ n khˆng dˆy du a . a. ’ e . o ’ u o e ’ . . a ´ a o ` a ’ o o a e’ ınh a ´ a ’ a thˆng tin, khˆng r˜ r`ng, kiˆm tra t´ nhˆ t qu´n cua cˆu truy vˆ n dˆu v`o v` d˘c biˆt c´ o a ` ´ a a a a . e o . thˆ a e’ ´p dung c´c k˜ thuˆt tˆi u.u ho´ vˆ ng˜. ngh˜ dˆi v´.i c´c cˆu truy vˆ n ph´.c tap. C´ch . a y a o . ´ a e u ` ıa o ´ o a a a´ u . a tiˆp cˆn n`y d˘c biˆt ph` ho.p v´.i c´c truy vˆn tra c´.u thˆng tin vˆ mˆt kh´i niˆm - mˆt ´ . e a a a . e. u . o a ´ a u o ` o e . a e . o. . ´ dang truy vˆ n phˆ e o o a e a ’ biˆn dˆi v´.i c´c hˆ CSDL quan hˆ. o ´ ´ . e . Cuˆi c`ng, ch´ng tˆi hy vong r˘ ng hˆ thˆng c`i d˘t s˜ du.o.c cai tiˆn v` ph´t triˆn ho`n ´ o u u o . ` a . ´ e o a a e. . ’ e a a ´ e’ a e .n n˜.a dˆ d´p u.ng dˆy du c´c yˆu cˆu cua mˆt hˆ truy vˆ n ngˆn ng˜. tu. nhiˆn tiˆng thiˆn ho u e a ´ ’ ` a ’ a e ` a ’ o e a´ o u . e ´ e . . . Viˆt v` thu.c su. cho ph´p nh˜.ng ngu.`.i su. dung khˆng du.o.c d`o tao vˆ Tin hoc c´ thˆ khai e a . . . e u o ’ . o . a . ` e . o e ’ ´ th´c tˆt c´c CSDL. a o a
ˆ ´ ´ ˆ ˆ ´ ˆ ´. ´ MOT CACH TIEP CAN DOI VO I PHEP DICH... . . . 279 ` ˆ ’ TAI LIEU THAM KHAO . [1] S. Abiteboul, R. Hull, IFO, A formal semantic database model, ACM TODS 12 (4) (1987) 525—565. [2] I. Androutsopoulos, “Interfacing a natural language front-end to relational database”, Tech. Paper no.11, Dept.of AI, Univ. of Edingburgh, 1993. [3] D. Calvanese, M. Lenzerini, D. Nardi, Logics for Databases and Information Systems, Kluwer, 1998. [4] G. D. Giacomo, M. Lenzerini, Description logic with inverse roles, functional restrictions, and n-ary relations, Proc. of the 4th European Workshop on Logic in AI (1994) 332—346. [5] G. G. Hendrix, et.all, Developing a nature language interface to complex data, ACM TODS 3 (3) (1978) 105—147. [6] J. S. Kaplan, Designing a portable nature language database query system, ACM TODS 9 (1) (1984) 1—19. [7] C. A. Thompson, R. S. Mooney, and L. R. Tang, Learning to parse natural language data- base queries into logical form, Workshop on Automata Induction, Grammatical Inference and Language Acquisition, 1997. [8] D. L. Waltz, An English language question answering system for a large relational data- base, Comm. ACM 21 (7) (1978) 526—539. Nhˆn b`i ng`y 18 - 5 - 2005 a a . a ’ Nhˆn lai sau su a . .a ng`y 17 - 10 -2005 a .