B GIO DC V O TO TRNG I HC s PHM H NI ====== INH TH THY MT Sể TNH CHT CA LC ễ CN BNG TRONG Mễ HèNH D LIU DNG KHI LUN VN THC S MY TNH H NI, 2015 LI CM N e hon thnh lun ny tụi ó nhn c s giỳp tn tỡnh ca thy hng dn khoa hc, ca cỏc thy cụ trng i hc S phm H Ni Tụi xin chõn thnh cm n cỏc thy cụ trng i hc S phm H Ni ó to iu kin hc tp, nghiờn cu v giỳp tụi rt nhiu quỏ trỡnh lm lun c bit tụi xin cm n thy PGS.TS Trnh ỡnh Thng ó tn tỡnh hng dn, ch bo tụi sut quỏ trỡnh hc tp, nghiờn cu ti v giỳp tụi hon thnh bn lun ny Vnh Phỳc, ngy 01 thỏng 06 nm 2015 Hc viờn inh Th Thy LI CAM OAN Tụi xin cam oan õy l kt qu nghiờn cu ca tụi di s hng dn khoa hc ca PGS TS Trnh ỡnh Thng Cỏc s liu, kt qu nờu lun l trung thc v cha tng c cụng b bt k cụng trỡnh no khỏc Hoc viờn inh Th Thy MC LC LI CM N LI CAM OAN DANH MC CC BNG .5 DANH MC CC HèNH V M U CHNG 1: Mễ HèNH D LIU QUAN H V L c CN BNG 11 1.1 Mụ hỡnh d liu quan h 11 1.1.1 Tng quan v mụ hỡnh d liu quan h 11 1.1.2 Thuc tớnh v thuc tớnh 12 1.1.3 Quan h, lc quan h 12 1.1.4 Khúa ca quan h 13 1.2 Cỏc phộp tớnh ca i s quan h .14 1.3 Ph thuc hm 18 1.4 Bao úng 19 1.5 Khoỏ 21 1.6 Lc cõn bng mụ hỡnh quan h 23 Kt lun 27 CHNG 2: Mễ HèNH D LIU DNG KHI 28 2.1 Mụ hỡnh d liu dng 28 2.1.1 Khi, lc 28 2.1.2 Lỏt ct .30 2.2 i s ttờn 32 2.3 Ph thuc hm trờn 40 2.4 Bao úng mụ hỡnh d liu dng 42 2.5 Khoỏ ca lc i vi ph thuc hm F trờn R .43 Kt lun 45 CHNG 3: LC CN BNG TRONG Mễ HèNH D LIU DNG KHI 47 3.1 Lc cõn bng mụ hỡnh d liu dng 47 3.1.1 Cỏc tớnh cht .48 3.1.2 Thut toỏn dch chuyn lc v dng cõn bng 51 3.2 Mt s tớnh cht m rng ca lc cõn bng mụ hỡnh d liu dng 56 Kt lun 59 KT LUN 60 TI LIU THAM KHO 61 DANH MC CC BNG Bng 1.1 Biu din quan h r 13 Bng 1.2 Biu din vớ d Nhõn Viờn 13 Bng 1.3 Biu din quan h Sinh Viờn 14 Bng 1.4 Biu din quan h r, s, r u s 15 Bng 1.5 Bng biu din quan h r, s, r n s 15 Bng 1.6 Biu din cỏc quan h r , s , r \ s , s \ r 16 Bng 1.7 Biu din quan h r , SB>D{r) 17 Bng 2.1 Biu din lỏt ct r(/?Hck7) 30 Bng 2.2 Biu din h gm quan h T, r2 31 DANH MC CC HèNH V Hỡnh 2.1 Biu din im hc viờn DiemHV (/?) 29 Hỡnh 2.2 Biu din cỏc r(R), s(R) .32 Hỡnh 2.3 Biu din r, s kh hp .33 Hỡnh 2.4 Biu din cỏc r , , r u 34 Hỡnh 2.5 Biu din cỏc r , s , r n s 35 Hỡnh 2.6 Biu din cỏc khi: r , s ,s \ r 35 Hỡnh 2.7 Biu din cỏc r ,r =ri/>(/) 37 Hỡnh 2.8 Biu din CT 4~y4(r) 39 DANH MC CH VIT TT V K HIU Kớhiờu Y ngha PTH Ph thuc hm LQH Lc ụ quan h LCB Lc ụ cõn bng LS Vờ trỏi RS Vờ phi n Phộp giao u Phộp hp \ Phộp tr c Tp Nm ong Thuc Khụng thuc ụ An pha fi Bờ ta Tụn ti Fh Ph thuc hm F M U Lý chn ti xõy dng c mt h thng c s d liu tt, ngi ta thng s dng cỏc mụ hỡnh d liu thớch hp ó cú mt s mụ hỡnh c s dng ttong cỏc h thng c s d liu nh: Mụ hỡnh thc th - liờn kt, mụ hỡnh mng, mụ hỡnh phõn cp, mụ hỡnh hng i tng, mụ hỡnh d liu datalog v mụ hỡnh quan h Trong s cỏc mụ hỡnh ny thỡ cú ba mụ hỡnh d liu thng c s dng l mụ hỡnh phõn cp, mụ hỡnh mng v mụ hỡnh quan h i vi ba mụ hỡnh ny thỡ mụ hỡnh quan h c quan tõm hn c Mụ hỡnh ny c E.Codd xut nm 1970 Tuy nhiờn cỏc quan h cú cu trỳc phng (tuyn tớnh) nờn mụ hỡnh ny cha ỏp ng i vi cỏc ng dng phc tp, cỏc c s d liu cú cu trỳc phi tuyn tớnh, Trong nhng nm gn õy, vic nghiờn cu nhm m rng mụ hỡnh d liu quan h ó c nhiu nh khoa hc quan tõm Theo hng nghiờn cu ny mt mụ hỡnh d liu mi ó c xut ú l mụ hỡnh d liu dng Mụ hỡnh d liu ny c xem l mt m rng ca mụ hỡnh d liu quan h gúp phn hon thin v lý thuyt thit k ca mụ hỡnh d liu dng em ó chn ti Mt s tớnh cht ca lc cõn bng mụ hỡnh d liu dng Trong ti ny mt s tớnh cht m rng ca lc cõn bng ó c phỏt biu v chng minh Mc ớch nghiờn cu - Tỡm hiu v mụ hỡnh d liu dng - Tỡm hiu v lc cõn bng, cỏc tớnh cht ca lc cõn bng v phộp dch chuyn lc v dng lc cõn bng - Phỏt biu v chng minh mt s tớnh cht m rng ca lc cõn bng Nhim v nghiờn cu - Tỡm hiu v mụ hỡnh d liu quan h v lc cõn bng mụ hỡnh d liu quan h v lc cõn bng, cỏc tớnh cht ca nú, phộp dch chuyn lc v dng cõn bng - Tỡm hiu v mụ hỡnh d liu dng - Phỏt biu v chng minh mt s tớnh cht m rng ca lc cõn bng i tng v phm v nghiờn cu - i tng nghiờn cu cỏc tớnh cht ca lc cõn bng mụ hỡnh d liu dng - Phm vi nghiờn cu mụ hỡnh d liu dng Phng phỏp nghiờn cu Trong quỏ trỡnh trin khai ti, chỳng tụi s dng ch yu cỏc phng phỏp: Thu thp ti liu, phõn tớch, suy lun, tng hp, ỏnh giỏ ti liu v lc khi, mụ hỡnh d liu dng khi, lc khi, lc cõn bng T ú xut mt s tớnh cht ca lc cõn bng mụ hỡnh d liu quan h Nhng úng gúp múi ca ti - Tỡm hiu mụ hỡnh d liu dng - Tỡm hiu lc cõn bng trờn v cỏc tớnh cht ca nú - Phỏt biu v chng minh mt s tớnh cht m rng lc cõn bng trờn v trờn lỏt ct Cu trỳc ca lun Lun gm: Li m u, ba chng ni dung, phn kt lun v ti liu tham kho Chng 1: Trỡnh by cỏc khỏi nim c bn nht v mụ hỡnh quan h: Trỡnh by cỏc phộp toỏn i s trờn mụ hỡnh quan h, cỏc v ph thuc hm, 48 3.1.1 Cỏc tớnh cht Nh ta ó bit, F cú dng thu gn t nhiờn cú ngha l F tha cỏc iu kin sau: a) F khụng cha cỏc ph thuc hm tm thng, ngha l cỏc ph thuc hm cú dng: X ->yeF v lD y b) Hai v trỏi v phi ca mi ph thuc hm F khụng giao nhau: V fe F :IS )n R S )= c) Cỏc v ỏi ca mi ph thuc hm ong F khỏc ụi mt, ngha l: V f,g gF :LS(f)=LS(g)f=g Ta cú cỏc nhn xột sau: Nhõn xột: Cho lc a=(R,F),R=(id ; A A2, ,An) l lc cõn bng Khi ú, nu id={x} thỡ lc cõn bng a suy bin thnh lc quan h cõn bng mụ hỡnh d liu quan h Mnh 3.1: Cho lc a = (R, F), R = (d\ A , An) l lc cõn bng Khi Ve d , lc ca lỏt ct ti im x : a x = (Rx, F fa) cng l lc cõn bng Mờnh 3.2: Cho lc a = (R, Fn), R=(d\ An) Khi ú nu 49 VX e id , lc ca lỏt ct ti im X : ax (Rx, Fx) l lc cõn bng thỡ a=(R, F)cng l lc cõn bng Chng minh: Tht vy, vỡ Vjc e id, ax (Rx,Fhx) lc cõn bng nờn theo nh ngha ta cú: Fhx dng thu S9n t nhiờn v L S ^ ) = RS{Fhx) = T ú suy ra: (1) Mt khỏc Fhx dng thu gn t nhiờn nờn: Fh=J cng dng thu gn t nhiờn.(2) Theo cỏc kt qu (1) v (2) ta cú: a=(R, Fh) l lc cõn bng T cỏc mnh 3.1 v 3.2 ta rỳt iu kin cn v sau v lc cõn bng: Mnh 3.3: Cho lc kha = (R, Fh),R = (id\A, A2, ,An) Kh ú: a=(R, F) l lc cõn bng kh v ch kh Vjt G id , lc ca lỏt ct ti im X : =ax{Rx,Fx) l lc cõn bng Mờnh 3.4: Cho lc khia=(R,Fh),R=(id;Aớ,A2, ,An) Khi ú: a Neu - l thỡ V jc Gèd, (X x^R ^F fo^v a=(R,Fl) l cỏc lc khụng cõn bng b Nu a=(R,Fh) l lc cõn bng thỡ giao ca cỏc khúa lc 50 ax =(R,FfèJC),Vx Gèd l t/ix=0 c Nu a=(R,F) l lc cõn bng thỡ giao ca cỏc khúa nú l U j= Chng minh: a Vi n = thỡ Vjc e id, ax = (Rx, Fhx) cú Rx = (x, Aj) = , ngha l lc ax =(Rx, Ffa.) ch cú mt thuc tnh ch s Nh vy, i vi Fhx ch cú kh nng to cỏc ph thuc hm sau: A ằA (tm thng) A >0 (tmthng) ằ (tmthng) >A Do ú ta ch cú th chn Ffa = hoc Ffa = (0 ằ) Trng hp th nht: Rx =x (1\ f vc= ta ú:LS(F)=RS(F)=0 ^ R x Trng hp i hai: Rx = xl, = { ằ A} ta cú: LS(F) = = RS(F) Vy c hai trng hỗrp thỡ lc lỏt ct ti im X e id : ax - (Rx, ^ ) u khụng phi l lc cõn bng b Nu a = (R,Fh) l lc cõn bng thỡ theo kt qu ca mnh 3.3 cỏc lc lỏt ct ax = (Rx, Ffa), (Vjc e id) l lc cõn bng T ú ta cú: V f z F hx: R S ( f) r ^ L S ( f) = Suy ra: V / e F f e : R S ) \ L S ) = /5(/) Do ú: 51 u M= u S ( F hx) - R x Theo cụng thc tớnh giao cỏc khúa ta cú: Ujx =Rx \M =Rx \R x =0,Vx& id c Nu a = (R, F)l lc cõn bng thỡ theo tớnh cht ca nú ta cú: V / e F : / ( / ) n JLS(/) = Suy ra: V /e F A: R S ) \ L S ( f ) = RS(f) Do ú: u T cụng thc tớnh giao cỏc khúa ta cú: Uj = R \M = R \R = Cho lc a = (R,Fh), R = (id',A,A2 , ,An), Fh l y cỏc ph thuc hm Khi ú ta cú thut toỏn dch chuyn lc a v dng cõn bng sau õy: 3.1.2 Thuõt toỏn dich chuyn lc v dang cõn bng m V m o o Algorithm Balance Format Balance (a) Input: a = (R, Fh), Fh l y cỏc ph thuc hm Output: Lc cõn bng ò = (V,Gh) Method t Gh : - Natural_Reduce (Fh) ; Chn X bt k e i d , tớnh giao ca cỏc khúa ax = {R^Gfa): 52 tfh = u >); Xỏc nh ; 3.1 P:=S(Gk)\LS(Gk); 3.2 M = (P U ợx G hx-, 3.3 To lc ò x = (V^.Gfe),V, = while M ^ 4.1 Dch chuyn /^(VjpG/^theo ò x = ò x \M \ //:=\ , ^ = ^ \ 4.2 Loi Gfa cỏc ph iuc dng: X ằ0 4.3 Nhúm cỏc ph thuc hm cú cựng v ỏi ong Ghx X ->yl5 X thnh X ->yl5 Y2, ,Yk ; M: = , \ L ( Gto); endwhile; 5.t/?:=U s h) . //v := u u Return (/?) ; End Balance õy Natural_Reduce Fh l thut toỏn rỳt gn t nhiờn i vi ph thuc hm Fh 53 Mnh 3.5: Lc ò = (V,Gh)thu c sau thc hin thut toỏn Balance l lc cõn bng Chng minh: chng minh ò = (y,Gh) l lc cõn bng ta chng minh vi mi JCGid thỡ ò x = (Vx,Ghx) l lc cõn bng, t ú theo kt qu ca mnh 2.3 ta suy ò = (Y,Gh) l lc cõn bng Ta thy sau bc ca thut toỏn c thc hin thỡ Gh ó dng thu gn t nhiờn T ú suy vi mi x&id thỡ Ghx cng dng thu gn t nhiờn Mt khỏc, ta cú: p : = RS(Ghx)\LS(Ghxy, M = (PUxèq dng thu gn t nhiờn nờn: V / e G f a : R S ) n L S ) = => R S ) \ L S ) = RS(f) Doú:ớ/b=vx\u (/)=vx\S(Gfa) Ta cú: LS(Gfa) = hx J hx L5(Gfe) \ M , tng t RS{Ghx) = RS(Ghx) \ M Ta chng minh ng thc: LSiGfa) \ M = RSiGfa)\ M =VX\ M theo s sau: LSiGfc)\ M ỗzVx \M ỗzRSiGfc)\ M LSiGfo)\M Tht vy, ti bc lp u tiờn ta cú: a) LS(Gfa) \ M ỗzVx \ M ,hin nhiờn b) Vx \M ỗ/?5,(Gfec)\M : Neu A&VX\ M M =(PU u )g Do ú: A Ê u = vx \ RSiGfo) =>Ae RSte) v ú A e RSiGfa) \ M 54 ) ặS(Gfe)\M ỗLS(Gfe) \ M : Neu AeặS(Gfe)\Mthi AeRSiGfc) vA ẫM= ( P U b ) ^ Do ú: A Ê P = RS(Ghx)\LS(Ghx) ^ A e L S ( G hx) v vỡ vy: A e L5(Gto) \ M T ln lp th hai tr i, ti bc 4.2 ca thut toỏn, sau loi b cỏc ph thuc hm dng: X > G ^thỡ cỏc Vx v RSiGfa) khụng thay i C th l ng thc Vx RS(Gfa) c bo ton, nhiờn LSiGfa) cú th b gim i Nh vy, sau bc 4.2 thỡ tớnh cht v cõn bng cú th b vi phm Vũng lp while cú nhim v cõn bng ba Vx, ặSXGfo) v LSiGfa) Do vy, ta phi tớnh tip lng chờnh lch: M : =VX \LS(G) ti bc 4.4 Theo b v cỏc thuc tớnh phi nguyờn thy ta cú Mc Q =>tp cỏc khúa Key(òx) khụng thay i quỏ trỡnh dch chuyn Neu M ta tip tc dch chuyn lc òx theo lng chờnh lch M Vỡ lc lỳc u l hu hn v cỏc phộp dch chuyn u thu nh kớch thc ca cỏc Vx,LS(Ghx), RSiGfa) nờn n lỳc no ú thỡ M vũng lp kt thỳc Ta chng minh vũng lp kt thỳc ta s thu c lc tha tớnh cõn bng Tht vy, t M = = > r =LS(Ghx), mt khỏc kt hp vi bt bin ca vũng lp: vx = RSiG^X ta cú: LS(Gfe) = RSib) = Vx Mờnh 3.6: Mi lc a = (R,F) vi Fl y cỏc ph thuc hm, u chuyn c v dng cõn bng ò = (,Gh) tha tớnh cht : 55 Key(a) = UfđKey(ò) ú J l giao cỏc khúa ca a Thut toỏn dch chuyn cú phc a thc theo chiu di d liu vo 0(n2m), ú n l s lng thuc tớnh, m l s lng ph thuc hm Chng minh: Thut toỏn Balance chuyn lc a = (R, Fh) v lc cõn bng ò = (V, G) Ngoi ra, da vo kt qu ca mnh v vic dch chuyn lc theo cỏc thuc tớnh khụng khúa v giao ca cỏc kha ta cú: Key {) = Uj@ Key(ò) Mi bc ca thut toỏn Balance u cú phc khụng qaO(m,n), M l thuc tớnh cú ti a n phn t; ú M tin ti thỡ vũng lp while cn thc hin ti a n ln Tng hp li, phc ca thut toỏn l 0(n2m ) Vớ d 3.2: Cho lc a = {R,F), R = (id-,A,A2,A ,A4,A5,A6),id ={1 2} F={1(1) 2(1) 11(4) 2(4) i(2)21(3)2(3)2(5)2(5) ^ (6) _^l(3)2(3) ^5)2(5) _^(2)2(2) ^5)2(5) _ ^ (3 )2(3)j Sau chuyn ph thuc hm F v dng thu gn t nhiờn, ta tớnh1 = , thc hin vic chuyn lc a = (R,F) v lc cõn bng ò - ( V ,G ) ta c: V = (id,A2,A5),G = {1(2)2(2) ->1(5)2(5), 1(5)2(5) ->1(2)2(2)} Vy ò = (y,G) l lc cõn bng 56 Mt khỏc ta d thy: Keyò = }, tũ ú s dng kt qu ó bit mnh trờn ta cú: Key {) = Uj â Keyiò) = (1(1Ơ 2Ơ 6)2(6)) â1(2)2(2) ,1(5)2(5)} ^{) ={ ^ 6\ Ê 12&2^} Mờnh 3.7: Cho lc a = (R,Fh) R = {d',A^,A1, ,An) Neu M = \ J v Vjc e d,Mx e ML(Fh)Mx thỡ ta cú: a M GKey(a) v ch M = ^J b.M e Key {) kh v ch kh M + =|^J 3.2 Mt s tớnh cht m rng ca lc cõn bng mụ hỡnh d liu dng Mnh 3.8: Mi lc a = (R,Fh) vi F l y cỏc ph thuc hm, u chuyn c v dng cõn bng ò = (V,Gh) tha tớnh cht SKa = U j đ SKò Trong ú u l giao cỏc khúa ca a,SKa l cỏc siờu khúa ca a , SKò l cỏc siờu khúa ca ò Chng minh: (=>) Gi s ta úM a e SKa , ú M a l mt siờu khúa ca lc a=>3Ka GKey (a) cho^ Mt khỏc, theo mnh 3.7 ta cú: 57 Key(a) = Uj Keyiò) ^ K a = U jđ K ò vi Kò e Keyiò) T ú suy : U jđ K ò =>( \Uj)=>Kò, theo tớnh cht ca phộp dch chuyn ta cú (M a \ u ) l thuc tớnh ch s ca lc /?, ú nú l siờu khúa ca ò tMò = iMa \ Uj)=>Mò e SXò Vy ta cú: M a = Uj @ M ò ^ > M a g U @ SKò ^> SK a Uj đ S K ò (1) ( Kò GKeyiò) 'Kò Mò Mt khỏc, theo mnh 3.7 ta cú: Key(a) = Uf đ Key(ò) Ka = u I đ Kò l mt khúa ca lc a ngha l Ka e Key{) Vy ta cú: (JJ â M ò) , (Uj đ Kò) = Ka =>(Uj đ M ò) l mt siờu khúa ca lc a , ngha l: (Uj M p ) e S K ( a ) = ằ SKa ^ U j SKò (2) T (1) v (2) ta suy ra: SKa = U jđ SKò Mờnh 3.9: Mi lc a = (R,Fh) vi Fh l y cỏc ph thuc hm, u chuyn c v dng cõn bng ò = (V,Gh) tha tớnh cht: Vx e id : SKax = x SKòx ú: l giao cỏc khúa ca c lỏt ct ax, SKax l cỏc siờu khúa ca lc lỏt ct ax, SKòx l cỏc siờu khúa ca lc lỏt catòx Chng minh: Vỡ Fh l y cỏc ph thuc hm, nờn chng minh mnh ny ta ch cn chng minh nú ỳng vi mt X e id l 58 (=>) Gi s ta cú M ax e SKax, ú l mt siờu khúa ca lc lỏt ct ax ^>3 Kax GKey(ax) cho Kax ầZM ax Mt khỏc, ieo mnh 3.6 ta cú: vi Ka e Key(a), Kò e Key(ò), Kax l hn ch ca Ka trờn lc lỏt ct a x Theo tớnh cht khúa ca lc i vúi ph thuc hm F ta suy ra: Kax = Ujx â Kpx, õy òx l hn ch ca ò trờn lc lỏt ct ò x Nh vy ta cú: M a x ^ K a x =Ubcđ K ò x ^>{Ma x\U bc) ^ K òx, theo tớnh cht ca phộp dch chuyn ta cú (Max Xx) l thuc tớnh ch s ca lc lỏt ct òx, ú nú l siờu khúa ca ò x t M òx = (Max \ UIx) => Mò x ^ SKòx-V%y ta cú: M ax =Ujx @ M ò x = > : &Ujx â S K p x ^ S K a x ỗzUjx â S K p x (3) ( òx e Key(òx) : Kòx ầ Mòx Mt khỏc, theo mnh 3.6 ta cú: Key {) = đ Key iò) =>Ka =Uj đ Kò l mt khúa ca lc , ngha l Ka e Key {), K ò GKey iò), õy Kòx l hn ch ca khúa K ò trờn lc lỏt ct òx Theo tớnh cht khúa ca lc i vi ph thuc hm F ta suy ra: Kax = UIx â Kòx Vy ta cú: (^Lc đ M òx) (Ix Kòx) = Kax =>{UIx M òx) l mt siờu khúa ca lc lỏt ct ax , ngha l: ( M ò x ) e S K ( a x) => SKax UIx SKòx (4) T (3) v (4) ta suy ra: SKax =UIxđ SKòx Theo gi thit Fh l y cỏc ph thuc hm nờn ta cú: 59 V* e id : SKax = UIx â SKpx Kt luõn Trong chng lun ó trỡnh by lc cõn bng mụ hỡnh d liu dng khi, phộp dch chuyn lc v dng cõn bng ng thũi phn cui ca chng trỡnh by mt s tớnh cht m rng ca lc cõn bng Trờn c s ca cỏc kt qu ny ta cú th nghiờn cu tip mi quan h gia lc cõn bng lc v ờn lc quan h, gúp phn lm hon chnh thờm lý thuyt v mụ hỡnh d liu dng 60 KT LUN Lun ó hon thnh c mt s kt qu c th nh sau: - Tỡm hiu v mụ hỡnh d liu dng khi, lc cõn bng - Tỡm hiu thut toỏn dch chuyn mt lc v dng cõn bng, tớnh ỳng v phc ca thut toỏn ny - Phỏt biu v chng minh dng biu din ca cỏc siờu khúa trờn lc v dng biu din ca cỏc siờu khúa trờn lc lỏt ct Nhng kt qu trờn thu c ng vi mt dng c bit ca ph thuc hm trờn ú l Fh Khi Fh ny c m rng mt ph thuc hm bt k thỡ nhng kt qu thu c v lc cõn bng cũn ỳng hay khụng li l hng nghiờn cu tip theo ca lun 61 TI LIU THAM KHO [1] Nguyn Xuõn Huy (1996), Giỏo trỡnh Cụng ngh phn mm, Nh xut bn i hc Tng hp Tp HCM [2] Nguyn Xuõn Huy, Trnh ỡnh Thng (1997), Mụ hỡnh c s d liu dng , K yu cỏc bỏo cỏo khoa hc ca Hi tho mt s chn lc ca Cụng ngh Thụng tin, i li, 8/1997, tr 14-19 [3] Nguyn Xuõn Huy, Trnh ỡnh Thng (1998), Mụ hỡnh c s d liu dng khi, tin hc v iu khin hc [4] Nguyn Xuõn Huy, Trnh ỡnh Thng (1999), Mt vi thut toỏn ci t cỏc phộp toỏn ca i s quan h mụ hỡnh d liu dng , Tp Tin hc v iu khin hc, 15(3), tr 8-17 [5] Nguyn Xuõn Huy (2006), Cỏc ph thuc ogic c s d liu Nh xut bn Thng kờ, H Ni [6] Nguyn Xuõn Huy (2013), Giỏo trỡnh kim nh phn mm, Ti liu hun B Thụng tin v Truyn thụng [7] Lờ Vn Phựng, Quỏch Xuõn Trng (2010), Khai phỏ d liu Data Mining, nh xut bn thụng tin v truyn thụng [8] Lờ Vn Phựng (2010), C s d liu quan h v Cụng ngh phõn tớch Thit k, Nh xut bn Thụng tin v Truyn thụng, H Ni [9] Nguyn Tu (2008), Giỏo trỡnh c s d liu Nh xut bn i hc quc gia H Ni [10] Trinh ỡnh Thng (2011), Mụ hỡnh d liu dng khi, Nh xut bn Lao ng [11] Trinh ỡnh Thng , Trn Minh Tuyn (2012), Lc cõn bng, v trỏi cc tiu v khúa vi phộp dch chuyn lc Hi tho quc gia 62 ln th XV Mt s chn lc ca cụng ngh thụng tin v truyn thụng - H Ni [12] V c Thi (1997), C s d liu - Kin thc v thc hnh Nh xut bn thng kờ, H Ni [13] Trnh ỡnh Vinh (2011), Mt s ph thuc d liu c s d liu Lun ỏn Tin s Toỏn hc [14] Lờ Tin Vng (1997), Nhp mụn c s d liu quan h Nh xut bn khoa hc v k thut, H Ni Ting anh [15] Aravind Krishna Kalavagattu, Mining Approximate Functional Dependencies as Condensed Representations of Association Rules, Arizona State University, 2008 [16] Dalkilic, M.M., Robertson, E.L.: Information Dependencies, Proceedings of ACM PODS (2000), pp 245-253 [17] D Pyle (2003J, Business Modeling and Data Mining, Morgan Kaufmann Publishers, San Francisco, CA [18] Hector Garcia-Molina, Jeffrey D Ullman, and Jennifer Widom, Database Systems: The Complete Book, Prentice Hall Publisher, 2000 [19] Hong Yao, Howard J Hamilton, Cory J Butz, FD_Mine: Discovering Functional Dependencies in a Database Using Equivalences, Second IEEE International Conference on Data Mining, 2002 [20] Huhtala, Y., Karkkainen, J., Porkka p., and Toivonen, H., TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies, The Com-puter Journal, 42(2), pp 100-111, 1999 [21] Jiawei Han and Micheline Kamber Data Mining Concepts and Techniques 2007 Chapter & Chapter (Intelligent Database Systems [...]... * v \u e R ,v ^ S ,u M -V.M} Nu M = u n V = 0 , R * s s cho ta tớch Descartes, trong ú mi b 18 ca quan h R s c ghộp vi mi b ca quan h s - Kt ni bng (Equi - Join): L phộp kt ni trong ú tt c cỏc phộp so sỏnh trong iu kin F u l bng - Kt ni t nhiờn (Natural - Join): L phộp kt ni bng ttờn cỏc thuc tớnh trựng tờn ca hai quan h trong ú mt thuc tớnh trựng tờn s b loi khi quan h kt qu, Kớ hiu : r * s * Phộp... 1.3 Ph thuc hm Khi xột n mi quan h gia cỏc d liu trong CSDL quan h thỡ mt trong nhng yu t quan trng nht c xột n l s ph thuc gia cỏc thuc tớnh ny vi thuc tớnh khỏc T ú cú th xõy dng nhng rng buc cng nh loi b i nhng d tha d liu trong mt CSDL Ph thuc hm l nhng mi quan h gia cỏc thuc tớnh ong CSDL quan h Khỏi nim v ph thuc hm cú mt vai trũ rt quan trng trong vic thit k mụ hỡnh d liu Mt trng thỏi ph thuc... khụng khúa 23 1.6 Lc cõn bng trong mụ hỡnh quan h nh ngha 1.9 LQH a = (U,F)ó gi l cõn bng nu tp PTH F trong a tha cỏc tớnh cht BI -B A sau õy: Bl Hp cỏc v trỏi, cỏc v phi ca cỏc PTH trong F ỳng bng tp thuc tớnh u : LS(F) = RS(F) = U B2 F khụng cha cỏc PTH tm thng, tc l cỏc PTH cú v trỏi cha v phi: V X ,Y U : X ^ Y = > ( X ^ > Y Ê F ) B3 Hai v trỏi hoc v phi ca mi PTH trong F ri nhau (khụng giao nhau):... V LC CN BNG ằ - Mụ hỡnh d liu quan h l mt trong nhng mụ hỡnh c quan tõm nhiu nht hin nay Nhiu tỏc gi ó quan tõm nghiờn cu v ó thu c cỏc kt qu tt Mt ttong cỏc kt qu ny l lc cõn bng v cỏc tớnh cht ca nú - Mụ hỡnh d liu quan h v lc cõn bng s c trỡnh by trong phn di õy - hiu rừ hn v mụ hỡnh d liu quan h v lc cõn bng cỏc vn ny c trỡnh by chng 1 ó c núi ti trong ti liu [5], [9], [13] 1.1 Mụ hỡnh d... tp cỏc giỏ tr Ta cú th xem mt quan h nh mt bng, trong ú mi hng l mt b v mi ct l mt thuc tớnh Ta cú th biu din mt s thc th - liờn h trong mụ hỡnh quan h Khi ú cỏc d liu ca s thc th - liờn h c biu din bi hai loi quan h: - Mt tp thc th E cú th c biu din bi mt quan h m lc quan h ca nú cha tt c cỏc thuc tớnh ca tp thc th ú Mi b ca quan h biu din mt thc th trong th hin ca E Mi liờn h gia tp E,E2, ,Ek uc... lc quan h cha cỏc thuc tớnh trong cỏc khúa ca E ,E 2, ,Ek Bng 12 cỏch t li tờn cho cỏc thuc tớnh nu cn, ta m bo rng khụng cú hai tp thc th trong danh sỏch cú cỏc thuc tớnh cựng tờn, ngay c khi hai tp thc th ny ch l mt 1.1.2 Thuc tớnh v min thuc tớnh nh ngha 1.1 - Thuc tớnh l c trng ca cỏc quan h - Min thuc tớnh l tp giỏ tr m t ú ta cú th rỳt ra cỏc giỏ tr c th xut hin trong cỏc ct biu din thuc tớnh,... LQH a = (U,F) u c a v dng cõn bng b = (V,G) tha tớnh cht: Key() â Key(b) Trong ú Uj l giao cỏc khúa ca a Thut toỏn dch chuyn cú phc tp a thc theo chiu di d liu vo 0 (n , trong ú n l s lng thuc tớnh trong u , m l s lng PTH trong F Vớ d 1.11 1 Lc quan h a = (JJ, F ) vúi = ABCD v F = {A ằDC, B >AC, ~^>A,D>B} l cõn bng 2 Nu thờm cho mt thuc tớnh chng hn E v gi nguyờn tp PTH thỡ thu c LQH khụng... Key{B) = {Ê,C}.T õy suy ra Key {) = Uđ, Key(b) = â {B,E} = {AHB,AHE} nh ngha: 1.10 Cho (M ,