B GIÁO DC VÀ ĐÀO TO
ĐI HC ĐÀ NNG
NGUYN VĂN PHONG
BIU DIN D LIU M
BNG XML VÀ NG DNG
Chuyên ngành: KHOA HC MÁY TÍNH
Mã s: 60.48.01
TÓM TT LUN VĂN THC SĨ K THUT
Đà Nng – Năm 2012
1
Công trình ñưc hoàn thành ti
ĐI HC ĐÀ NNG
Ngưi hưng dn khoa hc: PGS.TS Võ Trung Hùng
Phn bin 1: PGS.TSKH. Trn Quc Chin
Phn bin 2: PGS.TS. Đoàn Văn Ban
Lun văn ñã ñưc bo v trưc Hi ñng chm Lun
văn tt nghip thc sĩ k thut hp ti Đi hc Đà Nng
vào ngày 04 tháng 03 năm 2012
Có th tìm hiu lun văn ti:
- Trung tâm Thông tin – Hc liu, Đi hc Đà Nng.
- Trung tâm Hc liu, Đi hc Đà Nng.
2
M ĐU
1. Lý do chn ñ tài
Theo hiu bit ca chúng tôi, hu ht các nghiên cu v cơ s d
liu m ch! xây d"ng trên mô hình lý thuyt ho#c ñưc cài ñ#t trên
các mô hình quan h c$ ñin mà chưa có mt mô hình CSDL m
th"c s" ñưc cài ñ#t trên máy tính. Do ñó ít nhiu hn ch vic ng
d%ng các kt qu lý thuyt thu ñưc. Vì vy trong lun văn này,
chúng tôi ñ xut mt cách biu di&n cơ s d liu m b'ng XML,
mô hình cơ s d liu m ñưc biu di&n là mô hình d"a trên lý
thuyt v ñi s gia t(.
2. Mc tiêu ca ñ tài
M%c ñích nghiên cu ca ñ tài là ng d%ng lý thuyt v mô hình
cơ s d liu m, s( d%ng ngôn ng XML ñ biu di&n nhiu dng
d liu m khác nhau, cho phép m hóa cơ s d liu sn có nh'm
thu thp, lưu tr và th"c hin các truy vn trên cơ s d liu m ng
d%ng trong vic khai phá d liu nh'm ñưa ra các d" báo trong tương
lai.
3. Đi tưng nghiên cu
Đi tưng mà ñ tài nghiên cu bao gm vic tìm hiu mt s
vn ñ ny sinh trong quá trình qun lý thông tin nhân s", nghiên cu
v ñi s gia t( và mô hình cơ s d liu m d"a trên lý thuyt v ñi
s gia t(.
3
4. Phương pháp nghiên cu
Đ tài th"c hin d"a trên nhiu phương pháp nghiên cu khác
nhau: kho sát tình hình th"c t v các vn ñ v s( d%ng nh ng
thông tin không ñy ñ, không ch)c ch)n trong th"c t, vn ñ v lưu
tr và x( lý nh ng thông tin ñó, tìm hiu v cách x( lý thông tin
nhân s", nghiên cu lý thuyt v cơ s d liu m d"a trên lý thuyt
v ñi s gia t( và ngôn ng XML.
5. Ý nghĩa khoa hc và th!c ti"n ca ñ tài
V m#t ý nghĩa khoa hc và th"c ti&n ca ñ tài là xây d"ng
nh ng chc năng cho phép thu thp, lưu tr nh ng thông tin không
ch)c ch)n, không ñy ñ; cho phép lưu tr , x( lý và th"c hin truy
vn trên nh ng thông tin ñó; góp phn quan trng trong lĩnh v"c khai
thác thông tin ñ#c bit là nh ng thông tin m. Kt qu này còn tip
t%c phát trin cho các tính toán và khai thác tri thc t* cơ s d liu
m.
6. B cc ca lu#n văn
B c%c ca lun văn gm: Phn m ñu. Chương 1, trình bày
nh ng khái nim cơ bn. Chương 2, nghiên cu ng d%ng logic m
theo lý thuyt v ñi s gia t(. Chương 3, xây d"ng ng d%ng ñưa ra
các modul ca bài toán. Kt lun và kin ngh+.
4
Chương 1. T$NG QUAN
1.1. ĐI S% GIA T&
1.1.1. M't s khái ni(m
1.1.2. Các tính ch)t ca ñ' ño tính m* trong ĐSGT
M(nh ñ 1.2. [5]
(1) fm(hx) = , vi
(2) fm(c
-
) + fm(c
-
)= 1
(3) , trong ñó
(4) , vi
(5) và , vi và
Đ+nh lý 1.2. [5][9] Cho X = (X, G, H, ) là mt ĐSGT tuyn
tính. Ta có các phát biu sau:
(1) Vi , H(x) là tp s)p th t" tuyn tính.
(2) Nu G là tp s)p th t" tuyn tính thì H(G) cũng s)p
th t" tuyn tính.
1.2. MÔ HÌNH BIU DIN CSDL M THEO CÁCH TI,P
CN ĐSGT
Cho mt ĐSGT tuyn tính ñy ñ = (X, G, C, H,
Φ
,
Σ
,≤),
trong ñó là min các giá tr+ ngôn ng ca thuc tính
ngôn ng ñưc sinh ra t* tp các phn t( sinh G= {0, c
-
, W, c
+
, 1}
b'ng vic tác ñng các gia t( trong tp và là hai phép tính vi
ng nghĩa là cn trên ñúng và cn dưi ñúng ca tp H(x), tc là
and , quan h là
quan h s)p th t" tuyn tính trên X cm sinh t* ng nghĩa ca ngôn
ng [5].
5
1.2.1. Ng- nghĩa d- li(u d!a trên vi(c ñ+nh lưng Đ.i s gia t/
1.2.1.1. Đt vn ñ
1.2.1.2. Ng nghĩa d liu da trên vic ñnh lưng ĐSGT
Đ+nh nghĩa 1.5. [5] Cho , xét
là mt phân hoch ca [0, 1]. Gi là hàm ñ+nh
lưng ng nghĩa trên X.
(1) u b'ng v theo mc k, ñưc ký hiu u=
k
v, khi và ch! khi I(u)
và I(v) cùng cha trong mt khong m mc k. Có nghĩa là vi
và .
(2) u khác v theo mc k, ñưc ký hiu , khi và ch! khi
I(u) và I(v) không cùng cha trong mt khong m mc k.
(3) u nh- hơn v theo mc k, ñưc ký hiu u<
k
v, khi và ch! khi
I(u) và I(v) không cùng cha trong mt khong m mc k và (u) <
(v).
1.2.2. Phương pháp x/ lý giá tr+ kho0ng
Mt cách t$ng quát, nu là giá tr+ a ta chuyn thành [a, a], nu
giá tr+ là khong a ta chuyn thành [a- ,a+ ], vi ñưc xem là bán
kính vi tâm a. Nu giá tr+ t* a ñn b, thì ñưc chuyn thành [a, b].
Do ñó, quan h Thunhapcanhan có th chuyn thành quan h sau [5]:
1.2.2.1. Chuyn các giá tr khong v ñon con [0, 1] tương ng
Gi =[min, max] là min tr+ kinh ñin ca thuc tính
m trong mt quan h, trong ñó min, max tương ng là giá tr+ nh-
nht và giá tr+ ln nht ca . Trưc ht, ta s( d%ng hàm f ñ
chuyn ñ$i giá tr+ thuc thành giá tr+ thuc [0, 1]. Tip
theo, khong [a, b] ñưc bin ñ$i thành ñon con [0, 1] tương ng
khi s( d%ng hàm f, hay .
6
1.2.2.2. Đi sánh các giá tr khong
Cho ĐSGT X=(X, G, H, ) và mt giá tr+ khong [a, b]. Đ so
sánh mt giá tr+ vi [a, b], trưc ht chuyn [a, b] v ñon con
ca [0,1]. Vì tính m ca x là mt ñon con ca [0,1], do ñó ñ so
sánh và ñon con [0,1], chúng ta ch! cn d"a vào phn giao
ca hai ñon con ca [0,1] tương ng [5].
Vi , ký hiu và ,
tương ng vi vic chuyn ñ$i giá tr+
khong [a, b] v ñon con ca [0,1].
(1) Vi m.i nu tn ti sao cho
thì .
(2) Vi m.i sao cho thì:
Khi ñó vi x và x
1
, gi s( x<x
1
nu
thì
Ngưc li nu thì .
(3) Vi m.i nu tn ti sao cho
thì:
Nu tn ti sao cho và
thì .
1.2.3. Ng- nghĩa d- li(u d!a trên lân c#n tôpô ca ĐSGT
1.2.3.1. Đ tương t mc k
Chúng ta luôn luôn gi thit r'ng m.i tp H
-
và H
+
cha ít nht 2
gia t(. Xét X
k
là tp tt c các phn t( ñ dài k. D"a trên các khong
m mc k và các khong m mc k+1 chúng ta mô t không hình
thc vic xây d"ng mt phân hoch ca min [0,1] như sau:
Vi k = 1, các khong m mc 1 gm I(c
-
) và I(c
+
). Các khong
m mc 2 trên khong I(c
-
) là
7
. Khi ñó, ta xây d"ng phân hoch v ñ tương t" mc 1 gm các lp
tương ñương sau: ;
;
; và mt cách tương t",
và .
Ta thy, tr* hai ñim ñu mút và , các giá
tr+ ñi din , và ñu là ñim trong tương ng
ca các lp tương t" mc 1 , và .
Tương t", vi k=2, ta có th xây d"ng phân hoch các lp tương
t" mc 2. Ch/ng hn, trên mt khong m mc 2, ch/ng hn,
vi hai khong m k là
và chúng ta s0 có các lp tương ñương dng
sau: ,
và
, vi i sao cho và
i0.
B'ng cách tương t" như vy ta có th xây d"ng các phân hoch
các lp tương t" mc k bt kỳ.
1.2.3.2. Lân cn mc k ca khái nim m
Đ+nh nghĩa 1.8. [5] Cho U là tp vũ tr% các thuc tính, r là quan
h xác ñ+nh trên U, gi s( t
1
và t
2
là hai b d liu thuc quan h r.
Ta ký hiu và gi chúng b'ng nhau mc k, nu mt
trong các ñiu kin sau xy ra:
(1) Nu thì ;
(2) Nu mt trong hai giá tr+ là khái nim m,
ch/ng hn ñó là , thì ta phi có
;
8
(3) Nu c hai giá tr+ là khái nim m, thì
.
Đ+nh nghĩa 1.9. [5] Cho U là tp vũ tr% các thuc tính, r quan
h xác ñ+nh trên U, gi s( t
1
và t
2
là hai b d liu thuc quan h r.
Khi ñó
(1) Ta vit , nu ho#c
;
(2) Ta vit , nu ;
(3) Ta vit , nu ;
Sau ñây là ñ+nh lý kh/ng ñ+nh h các khong là mt phân
hoch ca Dom(A
i
) và giá tr+ ñ+nh lưng ca luôn là ñim
trong ca lân cn mc k ca x.
1.2.4. Ph thu'c d- li(u trong cơ s1 d- li(u m*
1.2.4.1. Ph thuc hàm m
1.2.4.2. Ph thuc hàm m vi lưng t ngôn ng
a) Ph thuc hàm m vi lưng t ngôn ng
b) Ph thuc ñơn ñiu
c) Ph thuc ñơn ñiu trong CSDL kinh ñin
1.2.4.3. Ph thuc ñơn ñiu trong CSDL m
a) Ph thuc ñơn ñiu tăng mc k
b) Ph thuc ñơn ñiu gim mc k
1.3. NGÔN NG ĐÁNH D2U M R3NG XML
1.3.1. Document Prolog (ph4n m1 ñ4u tài li(u)
1.3.2. Ph4n n'i dung ca tài li(u XML
1.3.2.1. Th
Th2 là các t* gi a các ký t" “<” và “>”. Đ#c t XML quy ñ+nh
rt rõ v cách ñ#t tên th2: có th b)t ñu b'ng ký t", gch chân (_),
9
ho#c du hai chm (:), các ký t" k tip có th là ký t", ký s, gch
ni, du chm, du hai chm nhưng không ñưc là khong tr)ng.
1.3.2.2. Th m (th bt ñu) và th ñóng (th kt thúc)
Th2 m b)t ñu b'ng ký t" “<” và kt thúc b'ng ký t" “>”; th2
ñóng b)t ñu b'ng ký t" “</” và kt thúc b'ng ký t" “>”. Các th2
luôn ñi c#p vi nhau, sao cho mi th2 m ñu có mt th2 ñóng tương
ng.
1.3.2.3. Phn t
Phn t( là toàn b thông tin t* ñu ca mt th2 m ñn cui ca
mt th2 ñóng
1.3.2.4. Phn t r ng
Phn t( r.ng là phn t( ch! có duy nht mt th2. Đây là trưng
hp các phn t( không kèm theo d liu và có dng <tên th/>, ví d%
như <img/>, <li/>, <br/>.
1.3.2.5. Phn t gc
Phn t( gc là phn t( b)t ñu mt tài liu XML.
1.3.2.6. Thuc tính (Attribute)
1.3.3. Đnh nghĩa kiu tư liu (DTD)
1.3.3.1. Đnh nghĩa các phn t
1.3.3.2. Khai báo phn t vi #PCDATA
1.3.3.3. Khai báo phn t cha nhiu phn t con
1.3.3.4. Đnh nghĩa phn t r ng
1.4. T$NG K,T CHƯƠNG
Các ni dung trong chương này tp trung gii thiu v ñi s gia
t(, v mô hình cơ s d liu m d"a trên lý thuyt v ñi s gia t(.