Luận văn Phụ thuộc dữ liệu và việc biểu đạt các phụ thuộc dữ liệu bằng ngôn ngữ logic tân từ

CHUdNG 2: cAC PHl,J THUOC DO LI~U KHAC CHUdNG 2 cAc PHIJ THUQC DU LI~U KHAc Khai ni<%mph\!thuQchamtrongtrilongh9Pt6ngquatkhongdud~vethe't caclo(;liph\!thuQct6nt(;litrongquailh<%.Trongthe'gidi th1jcconco nhi~ulo(;li ph~thuQcdu li<%unua.Trangchildngnay,chungta kh::wsatthemcac ph\! thuQcduli<%ukhac.MQtsf)trongnhungph\!thuQcnayd~nde'ncacd(;lngchu§:n caohdn,nhil ph~thuQcda tri va dinh nghIad(;lngchu§:n4, ph\!thuQcke'tva d(;lngchu§:n5. Cuf)icling,chungta xet cacph\!thuQcbaa hamva ph\!thuQc sinh. 2.1.PH{)THUQC DA TRJ (Multivalueddependency) Trong childng1,chungtada tha'yr~nggiuadfi'li<%uco mQtmf)iquailh<% vdinhauvado Ia ph\!thuQcham.Nhilngdokhongphiii la duynha't.Ch~nh(;ln, tenchakhongphiiilaxacdinhduynha'tenmQtduaconmala mQtho?cmQt sf)con.M6i quail h<%do trongcd sa dfi'li<%ugQiIa phl;!thuQcda trio Giii sachungtaco mQtlil9Cd6 quailh<%R, va x, Y la cact~pconcuaR. V6 tr1jcquail,chungtanoir~ng"X xacdinhdatriY", ho?c"comQtphl;!thuQc datricuaY vaoX", ky hi<%uIa X -7-7 Y, ne'uvdinhfi'nggia tri cuaX, t6nt(;li ffiQt~pr6ngho~cnhi6ugiatri tUdnglingtrenY makhonglien quailgi Wicac giatricuacacthuQctinhconl(;licuaR - X - Y. V~m?~hinhthuc,chungtacoth~dinhnghIa: 40 CHUdNG 2:cAc PHI)THUQCDOLI~UKHAc Dinh nghia2.1: Cho PRS =(U, D, dam)la mt)tlu'Qcd6nguyenthuy.X, Y cU. 4Mt)tph\!thut)cda tri (MVD) X -?-? Y trenPRS la mt)trangbut)csao chorangbut)cnaydlt<jCthGabdimt)tquailh~r ne"uva chine"u: Vdi 2 bt)bfftky t,u E r ne"ut[X]=u[X] thi t6nt~ibt)v E r v[XY] =t[XY] vav[X(U - Y)] =u[X(U - Y)] Mt)tMVD X -?-? Y trenPRS gQila mt)tMVD tim thu'ongne"u: . Y c X, ho~c . XuY=U Mt)tph\!thut)cda td t~mthu'ongsedungtrenmQiquailh~cuaPRS; no du<jcgQila t~mthu'ongbdi vi no khongxac dinhbfftky rangbut)cnaotren FRS. Dinhly 2.1: Cho RS =(U, D, dam,N, SC) la mt)tlu'<jcd6 quail h~.X, Y cU. Hai m~nhd6 santu'dngdu'dng: (1) SC F X -?-? Y (2) \j r: rIa quailh~cuaRS r =r(XY] * r[X(U - Y)] Tli dinhly 2.1va djnhly 1.5d chu'dng1,chungtacoke"tquasanday: Ke"tqua: X -?-? Y F X -?-? U - Y (ph~nbli) X -? Y F X -?-? Y (ph\!thut)cdatridu'Qcsuyd~nbdiph\!thut)cham). 41 CHUdNG 2:cAc PHl,JTHUQCDOLI~UKHAc Ktt qua tren cho tha"ym6i lien quail giil'aphl;!thu(k ham (FD) va phl;! thuQcda tfi (MVD). MQt h<$tien d~ cho bai tmin suy d~ntrong lOp cac phl;! thuQ"chamvaphl;!thuQcda tridu'QcBeeri,Faginva Howarddu'aranam1973. Dinhly 2.2: ChoJll Ia h<$cactiend~sail: (FDl) Lu?t phanx~: (FD2) Lu?t tangtntdng: (FD3) Lu?t biicc~u: (MVDl) Lu?t bu: (MVD2) Lu?t cQng: (MVD3) Lu?t b~cc~u: 'i/y c X, X -+Y ne"uZ c U va X -+Y thlXZ -+YZ {X -+Y, Y -+Z} ~ X -+Z X -+-+ Y ~ X -+-+ U - X - Y X -+-+ Y ~ WX -+-+VY ntuv c W {X-+-+ Y, Y -+-+Z} ~ X -+-+ Z - Y (FM1) (mvdsuyd~nbdi fd): X -+Y ~ X -+-+Y (FM2) (biicc~uh6nhQp): {X -+-+ Y, Y -+Z} ~ X -+Z - Y J/lla xacdang,d~ydiiva kh6ngthua. Cac lu~tsailco th~suyd~ndu'Qchrh<$tiend~J1i va vlJllla xacdangnen nhil'nglu~tnayclingxacdang. X -+-+Y ~ X -+-+U - Y {X-+-+ Y, X -+-+Z} ~ X -+-+ YZ {X -+-+ Y, X -+-+Z} ~ X -+-+ Y n Z (MVD1' - bu): (MVD4 -:-hQP): (MVD5 - giao): (MVD6 - tru): {X-+-+ Y, X -+-+Z} ~ X -+-+Y - Z 42 CHUaNG 2: cAc PHV THUQC DO LI~U KHAc Co thStha'yr~ngv€f phiHcuaphvthuQcda tri trongsuydi~n1adongdO'i ydiphepbu va giao(bdiV?ydongvdi h<;Jpva trli).Tli do co du'<;JcY tu'dngma tat?'Pcacfd va mvdcothSsuyd§ndu'<;JctUt?Pfd vamvddarho. Blnh ly 2.3: U 1at?PcacthuQctinhcua1u'<;Jcd6RS.Co thSphanho~chU - x thanh caet?PthuQctinhY 1,Y2,...,YksaGrho: N€fu Z c U - X thlX ~~ Z dlf<;JcthoatrenmN th€ hi~nr khi vachi khi Z 1ah<;Jpcua mQtsO'Yj (i E {I, 2, ...,k}). GQihQcact?P Y1, Y2, ...,Yknoi tren(dO'ivdi mQtt?P cacfd va mvd)1a cdsdphVthuQcdO'ivdiX, ky hi~u1aDEP(X). Bai toansuy d§n tronglOpcac rangbuQcki€u phV thuQchamva phv thuQcdatriquyv€ bai toanHmbaadongvacdsdphVthuQcrho mQtt?PthuQc tinh. Thu~ttmln2.1:TinhcdsdphVthuQc[6] Nh?p:T?p phVthuQcdatriM trent?PthuQctinhU va mQtt?PX c U Xua't:Cd sdphVthuQccuaX dO'ivdiM Phlfdngphap: ChungtakhdidguvdimQtt?Pcact?Ph<;JpS macuO'irung setrdthanhcd sdphVthuQc.Luc bandgu,S chuachimQtt?P la U - X; nghia1aS ={U- X}. ChungtaHml?p di l?p l~icacphvthuQcV ~~ W trongM va mQtt?PY trongS saGrho Y co giaovdiW nhu'ngkhanggiaovdi V rho d€fnkhi khang 43 CHUdNG 2:cAc PHl,JTHUOCDOLlI;UKHAc conthayd6inaGd6ivdiS. Sail d6thayY b~ngY n W vaY - W trongS.T~p cact~ph<jpS cu6iclingla cdsdph1;lthuQcchoX. ; Thu~ttoan n6i tren lam vi~ctrong thai gian da thuc lien bai toan suy d~n d6i vdi ph1;lthuQcham va ph1;lthuQcda tri quye"tdinh du<jctrong thai gian da iliac. Dinh nghia2.2: MQtlu<jcd6 quailh~d d<;lngchu~nthutu'(4NF) ne"um6iph1;lthuQcdatri x ~~ Y trongM+(M la t~pcacph1;lthuQchamvaph1;lthuQcdatri),trongd6 Y khongphftila t~pconcuaX, vaXY khongchuata'tcacacthuQctinhcua hi<jcd6,thlX la sieukh6acualu<jcd6quailh~. Ta nh~nxet la ne"uR c6 d<;lng4NF thl n6phaic6 d<;lngBCNF, nghlala, 4NF la di~uki~nm<;lnhhdnBCNF. Th~tv~y,gia sa r~ngR khongc6 d<;lng BCNF bdi VI c6 mQtph1;lthuQchamX ~ A, trongd6 X khongphai la sieu kh6a,vaA khongthuQcX. Ne"uXA =R thlch~cch~nX phaichuamQtkh6a. Do v~yXA khongth~chuamQithuQctlnhcuaR. Theo tiend~X ~ A suyra x ~~ A. Vi XA "*R va A khongthuQcX, X ~~ A la mQtvi ph<;lm4NF. M1;lcdichcuad<;lngchu~nb6nla tachnh6cacquailh~nh~mbie"ncacph1;l thuQcda tri tpanhnhungph1;lthuQcda tri t~mthuangtrongquailh~mdi d~ khongc~nki~mITanua. Vi d~2.1:Xet lu<jcd6quailh~NHANVIEN(TNV, TDA, TPT), vdi TNV latennhanvien,TDA latendvan,TPT la tenph1;lta. M ={TNV~~ TDA} 44 CHUdNG 2: cAc PHV THUQC DO LI~U KHAc .,a)NHANVIEN: b)NHANVIEN_DUAN NHANVIEN_PHUT A Hinh2.1 Quanh~NHANVIEN d hinh 2.1(a)thl khongd 4NF VI trongcac phlf thuQcdatrikhongt~mthu'ongTNV ~~ TDA vaTNV ~~ TPT, TNV khong lasieukhoacuaNHANVIEN. Cac phlfthuQcda trikhongt~mthu'onglaml~p l~icacgia tri dlf thuatrongcac bQ.Tuy nhien,1u'<Jcd6 NHANVIEN thl d BCNFbdiVIkhongcophlfthuQchamco trongNHANVIEN. Ta phan ra NHANVIEN thanh NHANVIEN _DUAN Va NHANVIEN_PHUTA (hinh2.1(b)).Cil haidSud 4NF, bdi VI TNV ~~ TDA laMVD dm thlfongtrongNHANVIEN_DUAN va TNV ~~ TPT Ia MVD t~mthu'ongtrongNHANVIEN_PHUT A. 45. TNV TDA TPT An X Thinh An Y Vu9ng An X Vu9ng An Y Thinh TNV TDA An X An Y TNV TPT An Thinh An Vu9ng CHUdNG 2: cAc PHl,J THUOC DO Llt;U KHAc B~ lam r6 y nghlac~nphltigill quailh~d 4NF, chungta xemhinh2.2 sau: '(a)NHANVIEN (b)NHANVIEN_DU AN NHANVIEN_PHUT A Hinh2.2 Co 16 b'QtrongNHANVIEN d hinh 2.2(a).N6u chungta phanra NHANVIENthanhNHANVIEN_DUAN vaNHANVIEN_PHUTA, nhlt(]hinh 2.2(b),chungtachic~nnitca la 11bQtrongcahaiquailh~,va cacbQnayd~u nhohdncacbQtrongNHANVIEN. Hdn filla,di thu'ongkhi C?Pnh?tclingse 46 TNV TDA TPT An X Thinh An Y VuQng An X VuQng An Y Thinh Blnh W Doan Blnh X Doan Blnh Y D0 lll Blnh Z Doan Blnh W Thinh Blnh X Thinh Blnh Y Thinh Blnh Z Thinh Blnh W Ktt Blnh X Ktt Blnh Y Ktt Blnh Z Ktt TNV TDA An X An Y Blnh W Blnh X Blnh Y Blnh Z TNV TPT An Thinh An VuQng Blnh Doan Blnh Thinh Blnh Ktt CHUdNG 2: cAC PHl) THUQC DO LI~U KHAC du<;Jctnlnhkhoi.Vi dl,l,n€u Binh b~tdftulamvi<$cd mQtd1!ankhac,chungta phiii them3 bQtrongNHANVIEN - m6i phl,lta mQtbQ.Ne"uchungtaqUell themba'tky mQttrongnhungbQnay,quailh<$trdnenkhongnha'tqUail.Tuy nhien,chi cftnmQtbQduynha'themVaGquailh<$4NF NHANVIEN_DUAN. Va'nd~tu'dngtVxiiy fa d6ivdi cacdi thu'ongkhi xoava sttane"umQtquailh<$. khongd 4NF. Vi dlf2.2: R =(ABCDE) M ={A --+BC, C --+--+DE} Khong d d:;mgchu~n4 VI C --+--+DE la phl,lthuQcda tri khong tftm thuong. Ne"uphan ra lu<;Jcde)trenthanhhai lu'<;Jcde): thIlu'<jcde)trend dC;lngchu~n4. Ba'tky khi naGchungtaphanfa mQtlu'<jcde)quailh<$R thanhRl =(X u Y) vaR2=(R - Y) d1!atrenmQtMVD X --+--+Y trongR, phepphanraco thuQctinhn6ikhongma't.Nhu'v~ydi~uki<$ncftnva du chophepphanra mQt lu<;Jcde)thanhhai'lu'Qcde)la co thuQctinhn6ikhongma'tLJ1 '. ThuQctlnh LJl': Lu'<;Jcde)quailh<$Rl va R2hinhthanhtUs1!phanra n6ikhongma'tcuaR ne"uva chi n€u Rl n R2 --+--+(R1-R2)(ho~cdo s1!d6ixung,n€u va chi ne"u(R1n R2) --+--+(R2- R1)). 47 CHUaNG 2: cAc PHVTHUQCDOLI~UKHAc E)i~unaytu'dngtVthuQctinhLJ1, ngo~itrti'LJ1' g6mcacacFD vaMVD. Chungtaco th~phattri~nthu~tloan 1.9d chtfdng1 thanhthu~tloan2.2,tC;lo mQtphandi n6i khongmfftthanhlu<;1cd6 quanh~d 4NF. Thu~tloan nay khongc~nthi6tsinhramQtphanfil baaloancacph\!thuQcham. Thu~ttoaD2.2:Phanran6ikhongmffthanhquanh~4NF[2] E)~tD :={R}; While co mQtlu<;1cd6quanh~Q trongD khongd 4NF thl Begin ChnmQt1tf<;1cd6quanh~Q trongD chtfad4NF; TIm mQtMVD khongt~mthtfongX ~~ Y trongQ vi phC;lm4NF; Thay the'Q trongD b~nghai1u<;1cd6(Q - Y) va (X u Y) End; MQtva'nd~phuctC;lPhdn1aco th~comQts6ph\!thUQCda trichungtahy v9ngse dungkhi chi6umQtquailh~h<;1pyr cuaR trenmQtt~pconX c R, nhu'ngkhonghy vngr~ngnhungph\!thuQcnaydungtrongchinhr. MQtph\! thuQcnhuthe'gi1anhung(embedded)trongR. Do do, chungta phailUll y khithuth~pta'tca cacrangbuQcdu<;1cxem1adungtrongnhungquailh~r cua R,khongdu<;1cbi) quacacph\!thuQcda tri nhung.Tuy nhiencacph\!thuQc hamnhungkhongbaagioxayfa;chungtad~dangchungminhdtf<;1cr~ngn6u Y --7Z dungtrongquailh~r cuaR dtf<;1cchie'ulen X thl Y ~ Z clingdung trongr. 48 CHUdNG 2: cAc PHl,JTHUOCDOLI~UKHAc Vi d~2.3:Oia sit trongchu'dngtrinhhQcco nhungmanphaihQctru'oc truockhi hQcmQtmannaodo. OQie la tenmanhQc,S la tensinhvien,P la ten~onhQcphaihQctruoctruockhihQce, vaY la nammaS hQcP. Ph\! thuQchamho~cph\!thuQcdatrikhongt~mthu'ongduynhfftla SP ~ Y. v~y chungtacoth~phandi eSpy thanheps vaSpy, cacIu'Qcd6nayhi€n nhien laa4NF. Ph\!thuQcdatri e ~~ S khongdung.eh~nh~nco th~cocacbQsail trongquailh~r cuaeSpy r (C KTLT s P NMTH Y) 1998Hai KTLT nhungkhongtim thffybQ Tam CSLT 1999 KTLT Hai CSLT 1999 Co th~Hai dahQcxongmaneSLT VI do la manh9ctru'ochoman KTLT, nhu'ngkhongphaivaonam1999. Tuy nhien,nSuchungtachie'umQtquailh~hQpl~cuar cuaeSpy tren esp,e ~~ S vatheoquiuiebu,e ~~ P clingdung.E>i~unaynoileuding IDQtsinhvien'khidangky hQcmQtmanhQc(KTLT) du'Qcyellc~uph,HIffy xongcacmonphaihQctntoc(NMTH va CSLT) cuamanhQcdovaomQtthai gian ao,do.VI the',C ~~ SvaC~~ P lanhungph\!thuQcdatrinhungcua esp.Ke'tquala,CSPthvcsvkhonga4NF,vanophaidu'Qcphanrathanhes vaCP. 49 CHUdNG 2: cAe PHV THUOC DO LI~U KHAe Ne'unhus1,1't6nt(;licuamQtph\!thuQcda tri trongmQtlu<;1cd6 quailh~ tu'dngling voi kha nangtach- ke'tn6ikhongma'tthongtin lu<;1cd6 naythanh haifuanhph~n,thlmQtdiu hoi t1!nhiennaysinhla: co th~bi~udi~nmQtlo(;li rangbuQcnaGbdi di~uki~ntach- ke'tn6i khongma'tthongtin cua nhi~u thanhph~n.R6 ranglo(;lirangbuQcdonh~nph\!thuQcdatIi nhula mQttru'ong h<;Jprieng. 2.2.PH{) THUOC KET (Join Dependencies) Djnh nghla2.3: ChoFRS =(U, D, dam)la mQtlu<;1cd6nguyenthuy Cho Xl, X2, ...,Xk C U voi U\=l Xi =U. MQtph\!thuQcke'ttrenFRS ky hi~uIa Xl *... * Xk la mQtrangbuQCsaG choffiQtquailh~r trenFRS thoarangbuQcnayne'uva chine'u r =r[Xd * ... * r[Xk] H~qua:ChoFRS=(U, D, dam)la ffiQtlu<;1cd6nguyenthuy . Ne'uX, Y c U, thl(X ~~ Y Q XY * X(U - Y)) . Ne'uX, Y c U voiXl U X2 =U thl Xl * X2Q Xl (I.X2 ~~ Xl QXI (lX2~~X2 Djnh nghla 2.4: [5] MQtph\!thuQcke't*[RI, R2,...,Rp] trenR Ia t~mthuongne'uno du<;1cthoa vdiffiQiquail h~feR). 50 CHUdNG 2: cAc PHl,J THUOC DO LI~U KHAc Dinh nghia2.5: MQt luQcet6quailh~d d9-ngchuffnthlinam(SNF) hayd9-ngchuffnchie'u ke't(PJNF) ling yoi t~pSC cacph\!thuQcham,ph\!thuQcetatri, ya ph\!thuQc ke'tn6uyoi mQiph\!thuQcke'tkh6ngtffmthuongJD(R1,R2,...,Rn)trongSC+, m6iRi la mQtsieukhoacuaR. Vi dl;t2.4: X6t luQcet6quail h~CUNGCAP(TNCC, TPCC, TDA), yoi TNCC la tennhaclingca"p,TPCC la tenphffnclingca"p,TDA la tendlj an. CUNGCAP(TNCC An An Binh Thinh Vuong TPCC A B A B C TDA) X Y Y Z X ------------------------------------------------------------ Binh An A A X Y (a)Quanh~CUNGCAP kh6ngcoph\!thuQcetatri liend 4NF. Tuynhien,no sekh6ngd SNF ne'ucoJD(Rl,R2,R3). R2 R3 I TNCC I TDA I I TPCC An X A R1 I TNee I TPce TDA An A X (b)Phanraquailh~CUNGCAP yoi ph\!thuQcktt thanhbaquailh~SNF. Hlnh2.3 51 An B An Y B Y Binh A Binh Y A Y Thinh B Thinh Z B Z Vuong e Vuong X C X CHUdNG 2:cAc PHl,JTHUQCDOLI~UKHAc Xet quail h~CUNGCAP ahlnh2.3(a)(chIxetnhungbQa trendu'ang g<;lchkhongli~nnet).Trongtru'angh<;1pnaymQtbQth€ hi~nmQtnhacungca'p clingca'pmQtphgnriengWimQtdvanriengbi~t,nhu'v~ykhongcocacph\! thuQcda tri tgmthu'ang.Quanh~CUNGCAP daa4NF vasekhongbi phan fa.Chuy Ianhungquailh~chuaph\!thuQcdatrikhongtgmthu'angcokhuynh huangtrathanh"ta'tcakhoa"cacquailh~;conghIala,khoacuachungla ta't canhfi'ngthuQctinhcuachungvaiMall. GiGgiasll'rangbuQcsaildayluauluaudung:ba'tky khi naGme>tnha clingca'psclingca'pphgnp,vamQtdv anj sll'd\!ngphgnp, va nhaclingca'ps clingca'pit nha'tmQtphgnchodv anj, thl nhaclingca'ps clingsedangcling ca'pphgnp chodv anj. RangbuQcnayco th~du'<;1cphatbi€u l<;litrongnhung cachkhac va xac dinhmQtph\!thuQck€t JD(Rl,R2,R3) giuaba phepchi6u Rl(TNCC, TPCC), R2(TNCC, TDA), va R3(TPCC, TDA) cua quail h~ CUNGCAP. N6u rangbuQcnay dung,nhungbe>adlfai du'angg<;lchkhong li~n netahlnh 2.3(a)ph<lit6n t<;litrongba'tky th~hi~nh<;1pphapcua quail h~ CUNGCAP va cling chuanhungbQatrendu'angg<;lchkhongli~nnet.ffinh 2.3(b)th~hi~nquailh~CUNGCAP vai ph\!thuQck€t du'<;1cphanra thanhba quailh~Rl, R7, vaR3 mam6ichungd~ua 5NF. 52 CHUdNG 2: cAc PHl,JTHUQCDOLI~UKHAc Chungtaeoth€ tomt~teaebuGeehugnhoanhusail: Table voi nhungnh6ml~p ---------------- Loq.i nh6mI~p Dq.ngchuan1 ---------------- Loq.iphl,!thu9C tUngphan Dq.ngchuan2 ---------------- Loq.iphl,!thu9c baGcau Dq.ngchuan3 ---------------- Dq.ngchuanBC ---------------- Loq.inhung phI,!thu9Cdatrj Dq.ngchuan4 ---------------- Dq.ngchuan5 Tomt~teaebuGetrongehugnboa. 53 CHUdNG 2: cAc PHl,JTHUQCDOLlt;UKHAc Co th~coi mvdIa mQttru'ongh<jpmdrQngcuafd va la mQttntongh<jp d~cbi~tcuajd. Tuy nhienchungtav~nchuatlmthffymQth~tieDd~xacdang d~yducholOpjd nhttd6ivoilopmvdvard.TuynhienmQthu~ttoaDquySt I dinhcho bai toaDsuydi~ntronglOprangbuQcg6mcaefd vajd, g9i la san l du6i(chase)du<jcduara bdi Maier, Mendelzonvi Sagiv Dam19.75.Thu~t. tmlnlien quaildSnmQts6khaini~msailday: Dinhnghia2.6:ChoR ={Rl,R2,...,Rp}la t~pcaclu<jcd6quailh~,voi R =RIR2...Rp. SC Ia mQtt~pcacrangbuQctrenlu<jcd6quailh~R. . Anh x~chiSukSt(project-Joinmappings)dinhnghiatrenlu<jcd6R, ky hi~umR,la illQthamtrennhungquailh~trenR saocho: mR(r)=1tRl(r)* 1tR2(r)*...*1tRp(r) Quanh~feR)la mQtdi~mc6dinhcuaanhx~mRnSumR(r)=r.T~p. tfftcacacdi~mc6dinhcuamRdu<jcky hi~ula FIX(R). SATR(SC)la t~pcuatfftca cacquailh~r trenR thGatfftcacacrang. buQctrenSC. SC F sc,nSuSATR(SC)c SATR(sc). Ta quailtamdSnP Ia t~pnhungquailh~r trenR saochomR(r)=r,hIcla pc FIX(R). NSu P =SAT(SC), di~uki~nkhongmfftthongtin chocd sd du , li~utrenlu<jcd6cdsdduli~uR coth~phatbi~unhusau: SAT(SC) c FIX(R) ho~c SC F *[R] 54 CHUdNG 2: CAC PHl,J THUQC DO LlE;UKHAC Blnh nghia 2.7:ChoR ={A!,A2,...,Am}Hit~pcacthuQctinh.T~pV, la hQicuahai t~pkhonggiaonhauVdva Vn,ma . Vd ={al, a2, ..., am}la t~pcac bie'ndu<jcphanbi~t(distinguished variables) . Vn={hi,b2,...}la ~pcacbie'nkhongdu<jcphanbi~t(undistinguished variables). MQttableauT(R) la mQtquailh~trenR, trongdo m6i thuQctinhAi E R, dom(Ai)={ailU Vn . Tableaula mQtbangco mcQttu'dnglingvdim thuQctinhcuaR, va n dongtu'dnglingvdinquanh~concuaphanraD cuaR. M6i 0 cuadongi vaCQtj cuatabbleauchliamQttronghaigiatrisail: . ajne'uRi cochliathuQctinhtu'dnglingtrongcQtj. . bkne'ukhong,chis6k b~td~ub~ng1vatangd~nm6ikhic~ndung de'ngia trib. Vi df:l2.5:Cho R = {AlA2,A2A3,A3~}. TableauTR du<jcthShi~nnhu 55 sail: TR ( AI Az A3 A4 ) al az bl b2 b3 az a3 b4 bs b6 a3 a4 CHUdNG 2: cAc PHV THUQC DO LI~UKHAc Dinh nghia2.8:Cho P la m9tt~pcacquailh~trenhf<;1cd6R. Ne'uT1va I TzlahaitableauxtrenR, thiTl chuaTztrenP, vie'thi Tl ~pTz,ne'uTl (r)~ Tz(i) d6i vdi mQiquailh~r trongP. Tl vaTzla tu'dngdudngtrenP, vie'tla Tl =pTz, ne"uTl ~pTz va Tz ~pTl . Chung taquail tamde'nP =SA T(SC) va vie'ttAt==SAT(SC)la ==sc . B6 d~2.1:ChoTl vaTzIanhungtableautrenlu<;1cd6R vachoP la m9t t~pcacquailh~trenR.ChoT'l vaT'zlanhungtableausaccho 1. T 1==pT' 1va T2=pT' zva 2. T'l vaT'2coinhuIa nhungquailh~d trongP Thi Tl CpT2ne'uvachine'uT'l C T' z Bflng b6 d6 2.1, chungta co thS kiSm tra Tl CSCT2 ne'uchungta co nhunglu~tdStUm9ttableaumyyT, Omm9ttableauT' sac cho T ==SCT'. Nhunglu~tbie'nd6ichonhungtableauIabflngcachapd1Jngcacfd vajd co ffi~trongSC thongquacaclu~tF va] saudaychode'nkhi khongcothem ffi9ttr~ngthainaonuachobang. Lu~tF: X ~ Y la fd thuQcSC.Ne'uuvav IahaibQtrongT sacchou[X]=v[X] thid6ngnha:t1J(A)va v(A) chom6ithuQctinhA thuQCY bflngcachd~tl~iten ffi9tronghaibie'ndonhu'sau: Gia siru(A)=d1va v(A) =d2.Ne'ud1ho~cd2la bie'ndu<;1cphanbi~t, ch~ngh~nd1la bie'ndu'<;1cphanbi~tthimQixua:thi~ncuad2du<;1cthaythe'bdi d1. 56 CHUdNG 2: cAcPHl) THUQC oQ LI~UKHAc Ntu ca dl lfind2d~ula bitn khangdu'<jcphanbi~tthl mQixua"thi~ncua bitn kernchI s61Onhdndlt<jCthaythe'bdibie'nkia (bie'nco chI s6nhohdn). DinhIy 2.4:ChoT' laktt quacuaapd\mglu~tF d6ivdiphl,lthuQcham X ~ A tditableauT. T vaT' thltu'dngdu'dngtrenSAT(X ~ A). L u~HJ: Cho S ={SI,S2,...,Sp}Ia mQtt~pcaclu'<jcd6quailh~va cho*[5] Ia mQt jd trenU. Cho T la rnQttableauva cho WI,W2,...,Wpla cachangcuaT rnaco th~ktt n6i tren5 vdi ktt quaw. A.pdl,lnglu~tJ cho *[5] Wi T chochungta hlnhthanhtableauT =T u {w}. Dinh Iy 2.5: Cho 5 ={51,52,...,5p}.Cho T' la ktt qua cua ap dl,mglu~tJ d6ivdi *[5] tditableauT. T vaT' thltu'dngdu'dngtren5AT(*[5]). Thu~tloanchase,la di tImmQttabkauT* tUmQttableauT vamQt~p phl,lthuQc5Cchotru'dc,saGchoT =scT* vaT* IarnQtquailh~trong5AT(C). Thu~tloanchasethldu<jcmatelddngian.ChoT va5C, apd\mglu~tF va lu~t J ke'th<jpvdi cacFDs va JDs trong5C, chodtn khi naGchungconthayd6i. B~ngdinhI)"2.1va 2.2,ntu sl,f tinhloanktt thuc,no luan luand~tdlt<jCmQt tableauT* =scT. T* du<jcgQila mQtsandu6icuaT bdi 5C. Chasesc(T)Ia thS hi~nta'tcanhlingsandu6inhuv~y.Do do,T* E chasesc(T). Vi d~2.6:Cho tableauT =TRvdi R ={AB,BD, ACD}la tableaud hinh du'diayvacho5C={*[ABC,BCD], B ~ C, AD ~ C}. 57 CHUdNG 2: cAc PHl,J THUQC DO LlJ;U KHAc 58 T(A B C D) 81 8z b1 bz b3 8z b4 84 81 bs 83 84 A.p dl;lng lut F d6i ydi B C du'Qctableau T 1 T1(A B C D) 81 8Z b1 bz b3 8z b1 84 81 bs 83 84 A.pdl;lnglut J d6i ydi *[ABC,BCD] du'QctableauT2 Tz(A B C D) 81 8z bl bz b3 8Z b1 84 al bs a3 a4 al az b1 84 b3 8z b1 bz A.p dl,mglut F d6i ydi AD C du'Qctableau T3 T3(A B C D) 81 8z 83 bz b3 8z a3 84 81 bs 83 84 81 8z 83 84 CHUdNG 2: cAc PHl,J THUQC DO LI~U KHAc Ap dl;mglu~tJ mQtl~nnuad6ivoi [ABC,BCD] du'QctableauT* Khongconlu~tbie'nd6inaotu'dnglingvoicacphlJ thuQctrongSC co th~ apdl;mgdti thayd6iT*. Ngoaifa, T*, nhu'mQtquailh~,thia SAT(SC). Dinh If 2.6:ChoTl vaT:zIa nhungtableau,va choSC la mQtt~pcac rangbuQc.Tl CscT:zne'uvachine'uchasescCTl)C chasescCT2). Chungtamongmu6nmQtphu'dngti~nd~ki~mtrakhi naot~tca Mung quailh~trongSAT(SC) co th~th~hi~nmQtcachtrungthlfcbai nhungphep chie'ucuachungtrennhunghtQcd6quailh~trongIu'Qcd6cd saduli~uR nao do.Di~uki~nnay,du'Qcphatbi~utu'dngdu'dngnhu'la SC F *[R] ho~cfiR, la d~ctinh nh~nd~nganhx~tren SAT(SC). Trong y nghla slf tu'dngdu'dng tableau,TR=scTr maT1la tableauchichliaWd,dongcuat~tcanhungbie'n phanbi~t.Trlad~ctinhnh~nd:~lllganhx~trent~tcacacquanh~. Y d6 cua thu~toanChasela bie'nd6ibangkhai t(;lOcuaphlJ thuQck~t n5ij U la jd c~ndu'Qcquye'tdinhtrongbai toansuydi€n bai mQtt~pSC) b~ng eachapdlJngcacfd vajd com~trongSC thongquacaclu~tF vaJ chode'n khikhongcothemmQtr~ngthainaonuachobang. Vi df!,2.7:Ap dlJngsandu6i 59 T*(A B C D) at a2 a3 b2 b3 a2 a3 a4 at bs a3 a4 at a2 a3 a4 b3 a2 a3 b2 CHUdNG 2: CAC PHV THUQC DO LI~U KHAC Cho RS =(U, D, dam,M, SC) la mQtlucjcd5quailh~ . U ={A,B, C, D} . SC ={A~ D, *[AB, BCD]} J la phl;!thuQcke'tn6i *[AB, BC, AD]. Dungthu~ttoansandu6id~chiraSC F J. Bangkhdit(;locuaJ Ia r(J): Ap dl;!nglu~tF d6ivdiA ~ D ducjctableauTl 60 T(A B C D) al a2 bi b2 b3 a2 a3 b4 al bs b6 a4 TI(A B C D) al a2 bi a4 b3 a2 a3 b4 al bs b6 a4 Ap dl;!nglut J d6i vdi *[AB, BCD] ducjctableauT2 T2(A B C D) al a2 bi a4 b3 a2 a3 b4 al bs b6 a4 al a2 a3 b4 b3 a2 bl a4 Ap dl;!nglut F mQtl§n nii'ad6ivdiA D ducjctableauT* CHUdNG 2: cAe PHl,J THUGC DO Llt;U KHAe T* co mQthangchIg6mcacbie'ndu'<jcphanbi~tlienk6tlu~nSC F J. BlOb If 2.7: Bai toansuydi~ntronglOpcacrangbuQcg6mfd vajd quy€t dinhdu'<jc trongthaigianNP - hard. GiGchungtaco mQtphl,lthuQchamkhongt~mthu'angX ~ A, vamu6n ki~rntracoSC F X ~ A khong.ChungtaKaydlfngmQttableauTx nhu'san: Tx cohaihang,Wdva WK.HangWdthlcotoannhungky hi~uphanbi~t;hang wxthlco nhungbie'nphanbi~td nhungcQtX va nhungbi6nkhongphanbi~t aCQtkhac. Blob If 2.8: SC F X ~ A n6uvachIn6uchasescCTx)cochIcacbi6nphanbi~ttren cQtA. Vi dl:l2.8:Cho U = {A,B, C, D},SC ={A~ D} 61 T*(A B C D) a[ a2 bi a4 b3 a2 a3 a4 a[ bs b6 a4 a[ a2 a3 a4 b3 a2 b[ a4 Ta kim tra xern co SC F BC D khong? TBc(A B C D) a[ a2 a3 a4 b[ a2 a3 b2 CHUdNG 2: cAc PHl,J THUQC DO Llt;U KHAc Chung ta thffychasesc(TBc)=TBc. C6 mQtb2trongcQtD, do d6 khongc6 SC F BC --+D. Ne'u SC' = {A --+ D, *[ABC, CD]}, thi chasesC'(TBc)la tableauT* sau: Chung ta da dinh nghlaX+nhu la baa d6ngcua mQtt~pthuQctinh X ling yoi t~pcac phl,lthuQcham F. Chung ta co th~md fQngdinh nghla d~baa ham nhungJD vaFD. Dinh nghTa2.9:ChoSC la mQtt~pcuacacFD va JD va choX la mQtt~p cuacacthuQctinh.Bao d6ngcuaX ling voi SC, ky hi~uX+,la t~pIOnnhfft cuanhungthuQctinh Y saocho SC F X --+Y. Chuy la ne'uSC chila cacFD, dinhnghlamoi se thu l';lithanhdinh nghlacu. H " ?t; qua: . D6i voi mQtSC chotruoc,X+la t~pcuatfftca cac thuQctinhA sao cho nhungcQtA cua chasesc(Tx) c6 chI nhungbie'nphan bi~t. . Ne'uJ la mQtt~pcac JD, thi J F X --+Y suyraX ::>Y. D6 la,mQtt?P , cac JD suyra chI cacFD t~mthuong. Dinh ly 2.9:Cho SC la mQtt~pcaerangbuQc,va cho Y la mQtt~pcac thuQctinhkhong thuQcX+bdi SC. SC F X --+--+Y n€u va chI ne'uchasesc(Tx) chuamQtdong Uyvoi nhungbie'nphanbi~tdungtrongtfftca nhungcQtYX+. 62 T*(A B C D) al az a3 a4 bl az a3 a4 T* chI c6 a4d cQtD, nhu vy SC' F BC --+D. CHUdNG 2: cAe PHV THUQC DO LI~U KHAc Vi<$cxet tinhdungcuam<$nhd~SC 1= scvdi sc la mQtph\!thuQcham, khai ni<$mchuy~ndich luQcd6 quan h<$da thamgia hifu hi~u VaGbi~u di~n baadongcuat~pthuQctinhvathu~tloantlmbaadong. DinhIf 2.10:[1] ChoU t~pcacthuQctinh,F t~pcacphvthuQcham,datrivaktt n6t vei hait~pthuQctinhkhonggiaonhaumyyx, y c U chungtaco: (XY)+ F =X(Y)+ F\X Dinh If 2.11: Cho t~pSC cacrangbuQcbaag6mphVthuQcham,da tri va ktt n6i.Cho ffiQtphvthuQchamf: X ~ Y. Khido: SC 1= X ~ Y khivachikhiY c (X)\c Vi dl:l2.9: Cho luQcd6RS vdiU =ABCDEG SC={AC ~ B, B ~ ACD, ABC ~ D, ADE ~ BCG, CG ~ AE, BD ~ ACD, [ABCDE, CDG], [ABDE, CDG, AC], [ABCDE, EG]} X=AC Tinh (X)+sc? Giiii: UI =U \ X =BDEG SCI =SC \ X ={4>~ B, B ~ D, DE ~ BG, G ~ E, BD ~ D (1o~ti), [BDE, DG], [BDE, DG, 4>](1o~i),[BDE, EG]} 63 CHUdNG 2: cAc PHl,J THUc)C DO LlI;U KHAc ={cp ~ B, B ~ D, DE ~ BG, G ~ E, [BDE,DG], [BDE, EG]} VI cp ~ B lien B E X\Cl SC2=SC1\B ={cp~ D, DE ~ G, G ~ E, [DE,DG], [DE, EG]} Co D E X+SC2 SC3 =SC2\ D ={E~ G, G ~ E, [E, G]} cp+SC3=EG X+SC =ABCDEG Dli saothlbai tminsuyd~nd6ivoi lopjd trongt6ngquatv~nkhongdu'<;5c giiHquye'thi~uquanhu'd6ivoi lOpmvd.Ne'uh~nche'l~i,chi xet cacjd co ffiQts6 c6 dinh(t6ida)cacthanhph~nke'tn6i, thu~toansandu6ilam vi~c voithaigiandathuctrencaclOpjd nhu'v~y.[7] 2.3.PHT) THUQC BAO HAM (InclusionDependency) Ph1;IthuQcbaahamdu'<;5cdinhnghladSchu§:nhoanhungrangbuQcquail h~tu'dngtacoVi d1;I,rangbuQckhoango~i(ho~ctoanVynthamchie'u)khong th~du'<;5cchi ra nhu'mQtFD hayMVD bai VIno lienke'tnhungthuQctinhgiua nhungquailh~;nhu'ngnoco thSdu'<;5cchira nhu'mQtph1;IthuQcbaaham.MQt eachhinhthuc,mQtph1;IthuQcbaahamR.X c S.Y giuahai t~pthuQctinh- X cualu'<;5cd6 quail h~R, va Y cualu'<;5cd6 quail h~S - chirarangbuQcla,ab~t kythaidiSmnaokhir lamQthShi~ncuaR vaslamQthShi~ncuaS,chung taphaico: 1tx(r)c 1ty(s) 64 CHUdNG 2: cAc PHU THUQC DO LI~U KHAc MQtcachhi~nnhien,t~pcacthuQctinhtrennoph1;lthuQcbaahamdu<;1c chira - X cuaR vaY cuaS - phaico s6gi6ngnhaucacthuQctinh.ThemVaG do,mi~ntricuanhungthuQctinhtudnglingphaitudngthich. Vi dl;l2.10 Cho mQtIU<;1cd6 quailh~ CONG_TY =(U, D, dam,M, SC) vdi . U ={MSNV, TenNV, MSLB, TenLB, CV, LUONG} . D vadamco th~dU<;1cxacdinhtheomQtcachnaGdo,nhungd dayco giathuy€t dom(MSNV)=dom(MSLB) vadom(TenNV)=dom(TenLB) Giathi€tnaycohamylamQtm?tHinhd~onaGdoclingla mQtnhanvien cuacongty vam?tkhacm6inhanviend~ucokhanangtrdthanhlanhd~o. Ngu nghIacuaIU<;1cd6 quailh~nayla m6ibQse biSudi~nthongtin v6 ffiQtnhanviencuacongty b~ngcachduara mas6, tencongvi~c,ludngcua d6iW<;1ngayvacamas61~ntencuanguoilanhd~otn;fctie'panhta. . SC g6mcacph1;lthuQcham: MSNV ~ TenNV MSLB ~ TenLB {MSNV,CV} ~ LUONG va cadi6uki~nla m6ilanhd~ola mQtnhanvienco congvi~c"lanh d "I ~o. 65 CHUdNG 2: cAc PHI) THUOC DO LlE;UKHAc RangbuQccu6itrangSC co thSdu'cjchlnhthuchoanhu'sail:ne"ur la mQt quailh~cualu'cjcd6CONG-TY thl: r[MSLB] c r[MSNV] MQt rangbuQcnhu'v~yducjcgQila mQtph\!thuQcbaaham.Ph\! thuQc baahamco thSbaag6mhdnmQtthuQctinh,ch~nhi;ln: r[MSLB, TenLB] c r[MSNV, TenNV] Vi dl!-2.11:Trangvi d\!1.7,chungtacococacid: THUCHIEN_DA.MSNV c NHANVIEN .MSNV THUCHIEN_DA.MSDA c DUAN.MSDA Chungtaclingco thSsa d\!ngnhungph\!thuQcbaahamdS thShi~n nhii'ngquailh~class/subclass. Vi dl!-2.12:Tfftca nhungthl/cthSngu'oithShi~ntrangcd sddu li~ucua ffiQtru'ongdi;lihQcnhu'nhanvien,nguyensinhvien,sinhvien... la thanhvien cuakiSu thl/cthSngu'oi,chungda du'cjchuyenbi~thoathanhcac subclass. Chungta co cac ph\!thuQcbaahamgiua sO'chungminhnhanclancua lop ngu'oiva sO'chungminhnhanclancuacacsubclasscuano. Dinh ngh'ia2.10: Cha PRS,=(U,D,dam)lamQtlucjcd6nguyenthuy. AI, ...,AkvaBI, ...,BklahaidaycacthuQctinhphanbi~tcuat~pU voi clingdQdai.MQtph\!thuQcbaaham[AI, ...,Ak ] C [BI, ...,Bk] trenPRS la ffiQtrangbuQcsaacharangbuQcnaydu'cjcthoabdi mQtquailh~r ne"uva chi n€u 66 CHUdNG 2:cAc PHl,JTHUQCDOLlI;UKHAc Vt E r:3t' E r Vi =1,...,k : t(AD=t'(Bi) C6 th~tha'yding ki~mITas1/t6n t~icua cac phl;lthuQcki~u fd, mvd hay jd chungta kh6ngbaa giOso sanhnhunggia tri tu'dngling vdi nhungthuQc tinhkhacnhau,trongkhi (j ki~uid (phl;lthuQcbaaham)thll~i khac.Do v~y matinhquye"tdinhdu'<;$cclingnhu'dQphlic t~pcuabai loan suyd~ncualOp cacid ra'tphl;lthuQcvao bimcha'tcua nhungmiSngia tri tu'dngling vdi cac thuQctinh.Chung ta sa dl;lnggia thuye"tr~ngcling mQtmiSngia tri vo h~n c1u'<;$cgallchom6ithuQctinh. Dinh ly 2.12: Cho() lah~cacliendSsail: . (idl) id dm thu'ong: CPF [AI, ...,Ak] C [AI, ...,Ak] . (id2)Chie'u/ hoanvi: [AI, ...,Ak] C [BI, ...,Bk] F [Ail. ..., Aie] C [Bil, ...,Bie] d6ivdim6iday{iI,...,ie}cacs6nguyenphanbi~tla'ytU t~p{l, ...,k} . (id3)B~cc~u{[AI, ...,Ak] C [BI, ...,Bk], [BI, ...,Bk] C [CI, ...,Ck]} F [AI, ..., Ad C [CI, ...,Ck ] () la mQth~cacliendSxacdangvad~ydud6ivdibailoansuyd~ncho phl;lthuQcbaa ham. Dinh ly 2.13: Bai loansuyd~nchoph\!thuQcbaahamIa quye"tdinhdu'<;$c. C6 th~tha'yr5 rangngunghlat1fnhiencuaca hai lo~irangbuQc:phl;l thUQchamvaphl;lthuQCbaaham.Tuy nhienkhi xemxetbai loansuyd~ncho 67 CHUdNG 2: cAC PHI) THUOC DO LI~U KHAC caph\!thuQchamvabaahamke'tqual(;likhacdi, di€u naydii duQcchi ra bdi ChandraA.K., M.Y. Vardi (SIAM Journalof computing14:3,pp. 671- 677, August1985). Blnh 1:5'2.14: Bai roansuyd§:nchoph\!thuQchamva ph\!thuQcbaahamla khong quye'tdinhduQc. Trong truonghQpd~cbi~tchungtaco ke'tquasau:bai roansuyd§:ncho ph\!thuQchamva ph\!thuQcbaahammQtngoi (unaryid) v§:nla quye'tdinh duQc.Tuy nhienkhi xuffthi~nid hai ngoi (binaryid) l~ptilc tinhquye'tdinh duQcbi mfftdi. 2.4.CAC PHl) THUQC SINH (GeneratingDependencies) Nhi€u lac gia dii tlmcachxacdinhcac lOpph\!thuQcrQngIOnhdnbaa g5mcacph\!thuQck€ trennhunhungtru'onghQpd~cbi~t.D(;lngcacph\!thuQc t6ngquatsaudayduQcgQila ph\!thuQcsinh.[6] Blnh nghia2.11:Ph\!thuQcsinhtrenmQtluQcd6 quailh~Al...Anla mQt bi€u thuccod(;lng (tl,..,.,t0/ t trongdotj la cacn-bQky hi~u,t la mQtn-bQkhac(khidochungtaco mQt ph\!thuQcsinhbQ)ho~cla mQtbieuthucx =y,trongdoxvaylacackyhi~u xuffthi~ntrongcactj (khidochungtaco mQtph\!thuQcsinhd~ngthuc).chung tagQicac tj la gia thuye't(hypotheses)va t la ke'tlu~n(conclution).V€ tntc 68 CHUdNG 2: cAc PHV THUOC DO LlE;UKHAc quail, ynghla cua phl;l thuQcla, d6i vdi m6i quail h~trongd6Omthiycacgia thie't,ke'tlu~nse dung.8<iph.ithi~ndu'Qccac bQgia thie't,chung tac6 th<id~t l(;litencho mQtsO'ho~ctit ca cac ky hi~udu'Qcdungtrongnhunggia thie't, lamchochungkhdpvdi nhungky hi~udu'Qcdungtrongquailh~nay.f)~tl(;li tenchocacky hi~udu'Qcapdl;lngchoke'tlu~nclingnhu'cacgiathie't,va dI nhienn6phaidu'Qcapdl;lngchotit camQixuit hi~ncuaIDQtkyhi~u.Chung tasedu'ara IDQtdinhnghlahinh thuchdnsailkhi da:thaolu~nva phantich IDQtsO'vi dl;l. Ta xemphl;lthuQchamva phl;lthuQcdatri nhu'IDQtkhlmgdinhv~nhung quailh~,d6 la "ne'ubie'tdu'QcmQtki<ium~unaod6 thl chungtasebie'tduQc di~unay".Trongtru'onghQpphl;lthuQcham,"di~unay" lien h~de'nd~ngthuc cuamQtsO'ky hi~u,con d6i vdi nhungphl;lthuQcda tr!, "di~unay" chinhIa IDQtbQkhacva clingphaithuQcquailh~. Binh ly 2.15: . Phl;lthuQchamla mQttru'onghQpriengcua phl;lthuQcsinhd~ngthuc. . Phl;l thuQcda tri, ke'tn6i va baa ham la nhung tru'onghQprieng cua phl;l thuQc sinh bQ. 69 CHUdNG 2: cAc PHl,J THUQC DO LlE;UKHAc Binh nghTa2.12: MQtph\!thuQcsinh(bQhayd~ngthlic)du<;jcgQila dinhki~une'ukh6ng coky hi~unaGdu<;jcg~nvdihdnmQtthuQctinh. Truongh<;jpngu<;jcl,;lichungtacoph\!thuQckh6ngdinhki~u. Trongph\!thuQcsinhbQco th~xua'thi~nlu<;jngtU3 chocacky hi~unaG do,clingcoth~kh6ng,tu'dnglingvdinh~nxetnayla khaini~md~yduvaph\! thuQcnhung. Binh nghTa2.13: MQt ky hi~utrongke'tlu~nkh6ngxua'thi~nd mQtndi khacdu<;jcgQila dQcnha't(unique). MQt ph\!thuQcsinhdu<;jcgQila nhung(embedded)ne'uno co mQtho~c nhi~uky hi~udQcnha'tvadu<;jcgQila d~ydu(full)ne'unokh6ngcoky hi~u dQcnha't.MQtph\!thuQcdatridu<;jcnhungVaGtrongmQt~pcacthuQctinhS thinophaico nhungky hi~udQcnha'trongta'tcacacthanhph~nkh6ngthuQc s. Vi dl:t2.13: . Ph\! thuQcham la ph\!thuQcdinh ki~uva ph\!thuQcda tri la ph\!thuQc dinhki~uvad~yduo . Ph\!thuQcke'tn6iQd)la dinhki~u . Ph\!thuQcbaaham(id)vilalakh6ngdinhki~uvilalanhung. Vidl:t2.14: 70 CHUdNG 2: cAC PHl,J THUQC DO LI~U KHAC Ph\!thue>chamA ~ B kh~ngdinhr~ngn€u chungtatha"ytrongquailh~r n~odocohaibe>ab1cld1vaab2c2d2thlb1=b2trongnhungbe>nay. Ph\!thue>cda tfi A ~~ B kh~ngdinhr~ngn€u co hai be>trenthlphaico be>ab1c2d2trong quail h~ r, la me>tkh~ngdinh y€u hdn kh~ngdinh b1=b2. Bi€u di~ndclo<;linayduQctrInhbaynhuhInh2.4. 71 R (A B C D) Gia thie't a bl CI dl a bz Cz dz Ke'tlu?n bl =bz (a) Ph\! thue>chamA B R (A B C D ) Gia thie't a bl CI dl a bz Cz dz Ke'tlu?n a bl Cz dz (b) Ph\! thue>cda tri A B R (A B C D E ) a d a b " Giathie't b e C d e a e Ke'tlu?n a b C d e (c) Ph\! thue>ckt AD*AB*BE*CDE*AE CHUdNG 2: cAc PHLJ THUOC DO LI~U KHAc R (A B c D) Giathie't Ke'tlu?n (d) Phl,lthuQcda tri nhungA --+--+B I C. d31aky hic$udQcnh~t. s (E F G) CI dl g (e)Phl,lthuQcbaahamhamR.X c S.Y. Vdi X =CD,Y =EF Hinh 2.4 Cac phl,lthuQcdli<;5ctrInhbay dlidi dl;lngbang. MQt 1ydo d6 dlia ra ky hic$uphl,lthuQcsinh1ano d~nde"nmQtphlidng phapddngiancho vic$csuyd~ncacphl,lthuQc.Phepki6m tra nayd~uthich h9Pchocacph\!thuQcd~ydli thuQct~tcacaclo~i,m~cdunocochiphithai gianlahamIJ?u,VIV?ykhongdli<;1clia chuQngbfingthU?tloantinhbaadong d~suyd~ncacphl,lthuQchamtUnhungphl,lthuQchamkhac,ho~cbfingthu?t loantinhcdsaphl,lthuQCkhi chIxetph\!thuQchamvaph\!thuQcdatrioKhi co caephl,lthuQcnhung,phlidngphapnayco th6suyd~nthanhcong,nhlingke"t quakhongxac dinhdli<;1c.Th?t fa, hic$nnaychliaco thU?tloannaoki6m tra 72 a bl CI dl a b2 C2 d2 a bl C2 d3 R (A B C D) Gia thie't al bl CI dl - Ke'tlu?n CHUdNG 2: cAc PHl,JTHUQCDOLI~UKHAc du'cjcmQtphl,lthuQcnhungco thSsuydiSnlogictUnhungphl,lthuQckhachay khong,ngaycakhi nhungphl,lthuQcnaydu'cjcgioih~ntrongmQtlop ddngian nhu'cacphl,lthuQcdatrinhung. Dinh nghia2.14:Anh x~ky hi~u(thesimplemapping)la mQthamh tU mQtt~pcacky hi~uS de'nmQtt~pky hi~uT; nghlala voi m6iky hi~ua thuQc S,h(a) la mQtky hi~uthuQcT. Chungtav~nchopheph(a)va h(b)clingbiSu thimQtph~ntU'cuaT, ngaycane'ua* b. Ne'uJ.l=aIa2...anlamQtbQco cac ky hi~uthuQcS, chungta co thSap dl,lnganhx~ky hit%uh choJ.ldS thudu'cjcbQh(J.l)=h(al)h(a2)...h(an).Ne'u {J.lI, ...,~lm}la t~pcacbQcocacky hit%uthuQcS, va {VI,...,vd la t~pcacbQco cac kyhit%uthuQcT, chungtanoico mQtanhx~ky hit%utUt~pcacbQthilnha'tdtn t~pthilhaintucomQthamh saochovoimQi =I, 2, ...,k, h(J.li)la Vjvoi mQt giatfi j naodo. V~nco thShaiho~cnhi~uJ.lidu'cjcanhx~thanhclingmQtVj, vamQtVjv~nco thSkhongla anhcuaba'tky bQJ.linao. Vi df:l2.15:Cho A ={abc,ade,fbe}vaB ={xyz,wyz}.Co nhi~uanhx~ kyhit%utli'A vaoB. Ch~ngh~n,h(a)=h(t)=x, h(b)=bed)=y,vah(c)=bee) =z. VI v~y,h anhx~ta'tcababQtrongA thanhxyz.MQt anhx~ky hit%unua cog(a)=x, g(b) =g(d) =y, g(c)=gee)=z, vag(t)=w. Anh x~ky hit%ug bie'n abcvaadethanhxyz,nhu'ngl~ibie'nfbethanhwyz. Ta dii dinhnghlaanhx~ky hit%uIa nhunghamtheoky hit%u,va khi du'cjc apdl,lngvao cac t~pcuacachang,chungta dii du'athemyeti c~uIa anhx~ dli<Jcapdl,lngchom6ihangcuat~pthilnha'thanhmQthangcuat~pthilhai. 73 CHUdNG 2: cAc PHl,J THUOC DO Llt;U KHAc Songsongd6,chungtadadinhnghTanhunganhXi;!tUhangde'nhang,va du'a themyell c~ula khongc6 ky hi~unaodu'<;canhXi;!bai hai hangkhacnhau thanhnhungky hi~ukhacnhau.VI v~y,trongVI d\!tren,chungtakhongthS anhXi;!abcthilnhxyz vaadethanhwyzdu'<;cbaiVI a sedu'<;canhXi;!thanhca xvaw. Vdi khai ni~ffiv~anhXi;!ky hi~u,chungtac6thSdinhnghTay nghTacua caeph\!thuQcsinh.Chungta n6i ffiQtquailh~r thoamQtph\!thuQcsinhbQ (tl,...,tk)/ t ne'uvdih la mQtanhXi;!ky hi~utli'tit cacacgia thie't{tl,...,tdvaor, chungta c6 thS ma rQngh cho nhungky hi~udQcnhit trongt saocho bet) thUQcr. Chungtaclingn6idng r thoaphl.,lthuQcsinhd~ngthlic(tl,...,t0/ a=b ne'uvdih la ffiQtanhXi;!ky hi~utUcacgiathie'tvaor, chungtaphaic6h(a)= h(b). Vi dl.;l2.16:Cho sc13phl.,lthuQcsinhahlnh2.5(a)varIa quailh~ahlnh 2.5(b). (a) Ph\!thuQcsc Hlnh2.5MQtphl.,lthuQcsinhva ffiQtquailh~thoaphl.,lthuQcnay. 74 ar br Cr ar bz Cz az br Cz r (A B C) 0 1 2 0 3 4 0 3 2 5 1 4 (b) Quan h r CHUdNG 2:cAc PHl,JTHUQCDOLI~UKHAc Chu yr~nga2la ky hi~udQcnhgt.Hinh2.5(a)la mQtvi d\!v~ph\!thuQc sinhbQhaigia thie't,kh6ngphaila ph\!thuQcdatrinhung,clingkh6ngphaila ph\!thuQcda tri dffyau; nhungph\!thuQcnhu'the'gQila ph\!thuQct~pcon (subsetdependency).[8] B~thgyr thoasc,chungtaxetanhX?kyhi~uh vacacbQcuar mam6i giathie'tcuasccoth~du'<jcanhX?de'n.BaiVIhaigiathuye'tgi6ngnhaua CQt A, va heal)chI nh~ndu'<jcmQtgia tri, chungtathgyr~ngho~cca haigia thie't dttQcanhX? thanhbQcu6iclingcuar (ne'uheal)=5),ho~ccahaidu'<jcanhX? thanhbabQdffutien(ne'uheal)=0). Trongtru'ongh<jpdffu,h anhX?bl va b2 thanh1,CI va C2thanh4. Do do chungtaco th~ma rQngh choky hi~udQc nha'ta2b~ngdinhnghlah(a2)=5.Trongtru'ongh<jpdo,h(a2b1c2)=514lamQt phffntUcuar, vi the'kh6ngcovi ph?mnaocuascvdianhX?coheal)=5. Tru'ongh<jpheal)=0,khidocacanhX?coth~duynhgtsebie'nhaigia thie'tthanhbabQdffutiencuar.MQtanhX?nhu'the'coh(bl)b~ngvdi1ho~c 3,vah(C2)b~ngvdi2 ho~c4.Trongm6it6h<jpcuab6nt6h<jpnayd~uco mQt bQthuQcr chua t6 h<jpcacgia tri do trongcac thanhphffnB va C. Vi the' chungtaco th~marQngh choky hi~udQcnhgta2b~ngcachd~th(a2)=5 ne'u h(bl)=1vah\C2)=4, va ngu'<jcl?i d~th(a2)=O. Be'nday,chungtadilxettgtcacacanhX?ky hi~uchom6igiathie'tcua scthanhmQtbQcuar, va dil thgyr~ngtrongm6i tru'ongh<jp,chungtaco th~ marQnganhX? naychoky hi~udQcnhgta2saocho ke'tlu~ncuasc co m~t trongr. Do dor thoasc. 75 CHUdNG 2:cAc PHl) THUQCDOLI~UKHAc Ap d(lngph(l thllQCchocaeqllanhi: Gia sli'chungtaco pht;1thu9csinhd~ngthlic sc=(SI,...,Sk)/ a=b va quanh~r = {JlI, ...,Jlm}.chung taco th~ap dt;1ngsc cho r ne"utlm duQc ffi9tanhx~ky hi~uh tU {sl,...,sdVaG{JlI, ...,Jlm}.Tac dt;1ngcuaapdt;1ngsc chor b~ngcachdungky hi~uanhx~h la lamchoh(a)b~ngh(b)khi chung xua'thi~ntrongcacJli , chungtaco th~dungm9ttronghaiky hi~ud~thaythe" kyhi~ukia. Ne'uchungtaco m9tpht;1thu9Csinhb9Ia e =(sl,...,s0/ s, chung tadungh d~apdt;1ngecho r b~ngcachn6ib9 h(s)VaGr. Tuy nhien,ne'ue Ia m9tpht;1 thu9cnhungthi e seco m9tho?cnhi€u ky hi~ud9Cnha't,vi the'h sekhong duQcdinhnghlachota'tcacacky hi~ucuas.TrongtrUonghQpdo,ne'uc la ffi9tky hi~ud9Cnha'trongs,chungtaset~oram9tky hi~umoi,Iaky hi~u khongxua'thi~na ba'tky ch6naGkhactrongr, vamar9ngh b~ngcachdinh nghlah(c)lakyhi~udo.DI nhien,chungtaset~oranhungky hi~uriengbi~t chom6ikyhi~ud9Cnha'tcuas. Tuynhien,chungtav~ncoth~thaythe"ta'tcacacky hi~ud9Cnha'tb~ng nhungkyhi~~hi~ncocuar d~h(s)trathanhm9tphffntli'cuar. Trongtruong h<;ipdo,yell cffuh(s)phaithu9Cr dfiduQcthoa,va chungtaduQcquy€n khong thayd6ir. 76 CHUdNG 2:cAc PHl,JTHUOCDOLlt;UKHAc ThllQtloanchasedi SllYdi~nphl!-thllQC: Bay giGchungtaxemm9tquatrinhgiupchungtagiai quye'tCallh6i SC F scdunghaysai,trongdoSC Iam9tt~pcacph\!thu9csinh,scIa m9tph\! thu9Csinhkhac.Thu t\lcnayIa m9tthu~toankhi SC chi co nhungph\!thu9c dgyduoTuynhien,ne'uSC com9ts6ph\!thu9cnhung,nosechobie't"chan If' nSunotraWidu'9C,nhu'ngnocoth~ch<;lymaikh6ngngung. Y tu'dngcuaquatrinhchaseIa chungtakhdidguvdi nhunggia thie'tcua I ph1,lthu9csccgnki~mITa,va xU'lychunggi6ngnhu'chungdat<;lOfa mQtquail h~.R6i apd\!ngnhungph\!thu9cSC choquailhe:;nay.Ne'uchungtathudu'9C mQtb9 Ia ke'tIu~ncua sc thl chungtadachungminhf~ngsc suyfa du'9CtU sr. E)ffutiengia sU'f~ngscla m9tph\!thu9Csinhb9 (tl,...,t0/ t.Chungtab~t d~uvdi quail he:;f = {tl,...,td,saildoapd\!ngta"tcacacph\!thuQctrongSC theom9tthut1!naGdoval~pl<;lichodSnkhi (1) Kh6ngconcachapd\!ngcacph\!thuQcnaGco th~lamthayd6idu'9C f, ho~c (2) Ta phat hi~nfa f~ngtrongf co mQtb9 gi6ng vdi t d ta"tca cac thanh phffn,ngo<;litrunhungvi tricuat coky hie:;ud9Cnha"t. Tuy nhien,khi apd\!ngph\!thuQcsinhd~ngthuc,ne'uIDQttronghai ky hi~udangdu'9Cgall b~ngnhauxua"thie:;ntrongt thl hay d6i ky hie:;uIda cho gio'ngky hie:;utfongt. 77 CHUaNG2:cAc PHl,JTHUOCDOLI~UKHAc Trong tru'ongh9P (2) d tren,chungtake"tlu~nr~ngSC F sc dung.Ne"u (1)dungnhu'ng(2)khongdungthlchungtake"tlu~nr~ngSC F scsai.Tht;fcte", quailh~r thudu'9Csela mQtphanvi dl;!. Dinh Iy 2.16:Qua trlnhchasedu'9Capdl;!ngcho t~pcacphl;!thuQcsinh d~ydli va mQtphl;!thuQcsinh(coth€ nhung)scxacdinhchinhxacSC F scla dunghaysai. Vid{l2.17:Chungminhr~ngtrent~pcacthuQctinhABCD {A ~~ B I C, B ~ D} F A ~~ C ID Chungtaco th€ vie"tbaphl;!thuQcnaytheoky hi~ubangnhu'tronghinh Hinh 2.6 Cac phl;!thuQctrongvi dl;!dangxet. 78 2.6 al bi CI dl al b2 C2 d2 al bi C2 d3 (a) A B I C a2 b3 C3 d4 a3 b3 C4 ds d4=ds (b) B D a4 b4 Cs d6 a4 bs C6 d7 a4 b6 Cs d7 (c)A C ID CHUdNG 2: cAc PHV THUOC DO LI~U KHAc Hinh 2.7Chu6icacquailh~du<;5cxtiyd1!ngtUphepsandu6i. Ta b~td~uvdi cac gia thie'tcua hinh2.6(c),dU<;5ctrinhbay tronghinh 2.7(a).Co thSapdvngphvthuQccuahinh2.6(a)b~ngcachsudvnganhX£;lky hi~uh(bl)=bs,h(Cl)=C6,h(dl)=d7,h(b2)=b4,h(C2)=cs,vah(d2)=d6.Anh x~naychuyS,nhaihanggia thiStcuahinh2.6(a)thanhhaihangcuahinh 2.7(a)daoch6chonhau.NSuchungtamdrQngh dSanhX£;ld3thanhmQtky hi~umoidsthico thSsuyra r~ngbQa4bscsdsthuQcr nhudu<;5ctrinhbaytrong hlnh2.7(b).ThS thi chungtaco thSapdvngphVthuQccuahinh2.6(b),b~ng eachsudvngffiQtanhX£;lky hi~udS anhX£;lhai gia thie'tcuahinh2.6(b)dSn 79 a4 b4 Cs d6 a4 bs C6 d7 (a)Quanh khdidu. a4 b4 cs d6 a4 bs C6 d7 a4 bs Cs dg (b)Saukhi apdl;mghinh2.6(a). a4 b4 Cs d6 a4 bs C6 d7 a4 bs Cs d7 (c)Saukhiapdvnghinh2.6(b). CHUaNG 2: cAc PHl,JTHUOC DO LI~U KHAc hangthuhai vathubacuahinh2.7(b)vachungminhdingd7=d8.PhepthSd7 vaod8du<;1cphananhtronghinh2.7(c).BQthuba trongbing2.7(c)gi6ngvdi kStlu?ncuahinh2.6(c),ngo(;litrucQtB, d dophffnkStlu?nco ky hi~udQc nhitlab6.chungtakStlu?nr~ngsuydi€n naycogiatrio £)~kSt thucchudngnayxin lieUra nhlingkSt qua chinhySuda co khi xemxettinhquyStdinhdu<;1ccuabai loansuyd§:nva kStquacuavi~clien d~ hoamQtcachxacdangvadffydutrongldpcacphvthuQct6ngquathdn. Dinh ly 2.17: Bai roansuyd§:nla quyStdinhdu<;1cd6ivdi cacphvthuQcsinhbQdffydu vacacphvthuQcsinhd~ngthuc. Trong cac ldp phv thuQcsinhbQnhungbai roansuy d§:nkhongquySt dinhdu<;1cm?cdli ldpconcuanoIa ldpcacid l(;lila quyStdinhdu<;1c.MQt ldp cankhacnlia,ldpphVthuQcdatrinhung(phVthuQcjd nhungchi cohai thanh phffnkStn6i) v§:nchuaco diu traWi chobai roansuyd§:n,dayconla vin d~ IDa. MQtxuhudngrit tV'nhien- xacdinhldprQngldncacphvthuQct6ngquat -nhi~ulacgi~kl1acdaco mQtsO'kStqua,xindu<;1cd§:nra sailday: . PhVthuQcd(;lisO'(AlgebraicDependency)clingvdi h~liend~cuano dlf<;1cYanakakisvaPapadimitriouphathi~nnam1980.[9] . Phv thuQct6ngquatb~ccffu (GeneralizedTransitiveDependency clingh~liend~cuaParkervaParsaye- Ghomi.[10] 80 CHUdNG 2:cAc PHI)THUOCDOLlI;UKHAc . Ph\! thuQckhuonmftu(TemplateDependency)voi hc$tien d€ cua SardivaUllman.[11] . Ph\!thuQckeo theo(ImplicationalDependency)doFaginduara nam 1982.[12] Cac lop ph\!thuQct6ngquatd€u cftnduQcth~hic$nb~ngmQtngonngii'co khanangdi~nd~tduQcbancha'ttoanh9Cchungcua ta'tca nhungki~uph\! thuQcda tlmtha'y.Logic la mQtngonngii'Gaplingt6tyell cftua'y. 81