XML文件樹(shù)狀路徑查詢之最佳化研究

1、2022/2/22DBLAB NTOU1/372022/2/22DBLAB NTOU2/37大綱n研究動(dòng)機(jī)n系統(tǒng)架構(gòu)及相關(guān)定義n查詢句最佳化處理n實(shí)驗(yàn)結(jié)果n結(jié)論與未來(lái)方向2022/2/22DBLAB NTOU3/37研究動(dòng)機(jī)n結(jié)構(gòu)化合併 (Structural Join) 的順序nRelational Database, value-based equi-join, two tables and and columnsnXML, structural join, containment relationshipn改善結(jié)構(gòu)化合併的順序n利用最佳化演算法找到不同的結(jié)構(gòu)化合併順序2022/2/22D

2、BLAB NTOU4/37系統(tǒng)架構(gòu)User I nt er f ace ( XQuer y and Resul t )Par si ng XQuer y andBui l di ng XQuer y Tr eeRet r i evi ng Par t i al Dat aRet r i evi ng Fi nal Dat aCombi ni ng Fr agment Pat hBui l di ng Fr agment Pat hXQuer y Tr eeEP- Tr eeEC- Tabl eVal ue I ndexM at ched EC Tupl esResul tBui l di ng

3、 Fr agment Pat hTr eeFPTI nput XQuer yOpt i mi zat i on Pr ocess前置處理前置處理最佳化查詢處理最佳化查詢處理將XQuery轉(zhuǎn)換成XQuery Tree分割成Suffix Path並從相關(guān)資料結(jié)構(gòu)取得Partial Data將XQuery Tree轉(zhuǎn)換成片段路徑樹(shù)利用最佳化演算法找出六種走訪順序黏合符合片段路徑的答案將符合片段路徑的答案組成最後的結(jié)果自XML文件中取出資料2022/2/22DBLAB NTOU5/37Parsing XQuery and Building XQuery TreeFor $p in document (

4、“.tw/catalog.xml”)/catalogs/catalog/itemWhere $p/author/name/first_name= Germain and$p/publisher/ name_of_city= CozumelReturn$p/author/date_of_birth ,$p/publisher/name_of_state cat al ogs0cat al og1i t em2aut hor3publ i sher7nam e4dat e_of_bi rt h6nam e_of_st at e9fi rst _nam

5、 e5 =Cozumel=Germainnam e_of_ci t y8RootD NG NG NG NCNLNLNLNLN2022/2/22DBLAB NTOU6/37Retrieving Partial Datacat al ogs0cat al og1i t em2aut hor3publ i sher7name4dat e_of _bi r t h6name_of _st at e9f i r st _name5 =Cozumel=Germainname_of _ci t y8RootDNGNGNGNCNLNLNLNLN/catalogs/catalog/item/author/nam

6、e/first_name= Germain/date_of_birth/publisher/name_of_city= Cozumel/name_of_staten根據(jù)GN、DN、LN來(lái)切割出Suffix Path2022/2/22DBLAB NTOU7/37Retrieving Partial Data (cont.)2、267、12、31、44、4810、13、328、9、14、342025、27、50、51、59、6317、18、3433、35、36、37、38cat al ogs0cat al og1i t em2aut hor3publ i sher7name4dat e_of _b

7、i r t h6name_of _st at e9f i r st _name5name_of _ci t y8RootDNGNGNGNCNLNLNLNLN/catalogs/catalog/item/author/name/first_name= Germain/date_of_birth/publisher/name_of_city= Cozumel/name_of_staten利用相關(guān)資料結(jié)構(gòu)取得Partial DataPartial Data2022/2/22DBLAB NTOU8/37片段路徑樹(shù) (Fragment Path Tree)2、267、12、31、44、4810、13、3

8、28、9、14、342025、27、50、51、59、6317、18、3433、35、36、37、38cat al ogs0cat al og1i t em2aut hor3publ i sher7name4dat e_of _bi r t h6name_of _st at e9f i r st _name5name_of _ci t y8RootDNGNGNGNCNLNLNLNLNXQuery Tree10、13、328、9、11、3425、27、50、51、59、6317、18、3433、35、36、37、38aut hor3publ i s her7dat e_of _bi r t h6

9、name_of _s t at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r s t _name5LN片段路徑樹(shù)n透過(guò)查詢樹(shù)中的GN、DN、LN建構(gòu)出片段路徑樹(shù)n片段路徑樹(shù)中的節(jié)點(diǎn)代表一Suffix Path2022/2/22DBLAB NTOU9/37片段路徑樹(shù) (cont.)n片段路徑n片段路徑的第一個(gè)節(jié)點(diǎn)為葉節(jié)點(diǎn)或分支節(jié)點(diǎn)，最後一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)或分支節(jié)點(diǎn)3、10、134、9、11、3425、27、50、51、59、6317、18、2233、35、36、37、38aut hor3publ

10、i sher7dat e_of _bi r t h6name_of _st at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r st _name5LNfirst_name-authorpublisher-item2022/2/22DBLAB NTOU10/37片段路徑樹(shù) (cont.)n片段路徑序列n給予一個(gè)片段路徑樹(shù) FPT (FN, FE) ，若F1FN為其中的片段路徑，且FE中所有的edge正好被表示一次，則 (F1FN) 為一組片段路徑序列。 3、10、134、9、11、3425、27

11、、50、51、59、6317、18、2233、35、36、37、38aut hor3publ i sher7dat e_of _bi r t h6name_of _st at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r st _name5LNi t em -cat al ogaut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t e

12、mfi rst _nam e-aut hor片段路徑序列2022/2/22DBLAB NTOU11/37問(wèn)題定義n最佳化查詢處理n給予一個(gè)片段路徑樹(shù) FPT (FN, FE) ，且每一節(jié)點(diǎn)NiFN都已取得符合其對(duì)應(yīng)Suffix Path的資料，我們的最佳化查詢處理，會(huì)根據(jù)經(jīng)驗(yàn)法則提出六種適當(dāng)?shù)慕Y(jié)構(gòu)化合併的順序，使其在建立片段路徑及組合成最後答案時(shí)，能有較好的效率。10、13、328、9、11、3425、27、50、51、59、6317、18、3433、35、36、37、38aut hor3publ i sher7dat e_of_bi rt h6nam e_of_st at e9nam e_o

13、f_ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20fi rst _nam e5LN片段路徑樹(shù)2022/2/22DBLAB NTOU12/37查詢句最佳化處理n最佳化處理模組n根據(jù)經(jīng)驗(yàn)法則，找出六種結(jié)構(gòu)化合併順序n建立片段路徑模組n將片段路徑中的答案黏合成符合片段路徑的答案n組合片段路徑模組n透過(guò)GFP_Table內(nèi)的答案組出最後的結(jié)果n擷取結(jié)果模組n自XML文件中取出資料n產(chǎn)生所有可能的路徑n實(shí)際產(chǎn)生所有可能的結(jié)構(gòu)化合併順序2022/2/22DBLAB NTOU13/37最佳化處理模組n走訪片段路徑樹(shù)n起點(diǎn)：根節(jié)點(diǎn)或葉節(jié)點(diǎn)n中

14、間點(diǎn)：依partial data數(shù)量大小n表示法： (X, Y)nXn根節(jié)點(diǎn)：Rn葉節(jié)點(diǎn)： S or BnYn中間點(diǎn)： S or Bn六種結(jié)構(gòu)化合併順序nSS, SB, BS, BB, RS, RB3、10、134、9、11、3425、27、50、51、59、6317、18、2233、35、36、37、38aut hor3publ i sher7dat e_of _bi r t h6name_of _st at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r st _name5LN2022/2/

15、22DBLAB NTOU14/37最佳化處理模組 (cont.)n最佳化處理模組在片段路徑樹(shù)上走訪的過(guò)程 (RB)10、13、328、9、14、3425、27、50、51、59、6317、18、3433、35、36、37、38aut hor3publ i sher7dat e_of_bi rt h6nam e_of_st at e9nam e_of_ci t y8G NG NLNLNLN2、267、12、31、44、48cat al og1i t em2D NG N20fi rst _nam e5LN*catalogitemitem-catalog*item, publisher*author

16、-itemitemauthorauthordate_of_birth*date_of_birth-authorheadpublisheritem*publisherpublisher-itemname_of_state*name_of_state-publisherauthor-first_nameheadheadpublisher-name_of_cityauthor-first_namepublishername_of_city*name_of_city-publisherfirst_name-authorauthorfirst_nameheadUnVistedListFPListFPSe

17、quence*2022/2/22DBLAB NTOU15/37建立片段路徑模組n針對(duì)片段路徑序列分別作處理n對(duì)片段序列中的每一片段路徑上的節(jié)點(diǎn)，其上所帶有的Partial Data資料進(jìn)黏合，以建立符合片段路徑結(jié)構(gòu)的資料 n利用節(jié)點(diǎn)的起始編碼 (Start) 、結(jié)尾編碼 (End) 、深度編碼 (Level) ，判斷兩個(gè)Suffix Path是否具有適當(dāng)?shù)慕Y(jié)構(gòu)關(guān)係 GFP_Table8202022/2/22DBLAB NTOU16/37建立片段路徑模組 (cont.)n經(jīng)過(guò)建立片段路徑模組處理完的片段路經(jīng)樹(shù)及GFP_Table3、10、134、9、11、3425、27、50、51、59、631

18、7、18、2233、35、36、37、38author3publisher7date_of_birth6nam e_of_state9nam e_of_city8G NG NLNLNLN2、267、12、31、44、48catalog1item2D NG N20first_nam e5LNitemauthorpublisherfirst_nam edate_of_birthnam e_of_citynam e_of_state catalogitem27212263126442648itemauthor787912143134authordate_of_birth825827950951145

19、93463itempublisher71012133132publishernam e_of_state10331335133632373238publiserh nam e_of_city10171318authorfirst_nam e820G NG NG NLNLNLNLN2022/2/22DBLAB NTOU17/37組合片段路徑模組n依GFP_Table大小，由小至大組合n調(diào)整片段路徑序列結(jié)構(gòu)上的關(guān)係DoneFPSequenceStructureListUnStructureListfirst_name-authorfirst_nameauthori t em -cat al oga

20、ut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t emfi rst _nam e-aut hor1234567name_of_city-publisherpublisher-itemauthor-itemitempublisher-itempublishername_of_city-publishername_of_cityitem-catalogname_of_state-publishercatalogname_of_stat

21、edate_of_birth-authordate_of_birthi t em -cat al ogaut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t emfi rst _nam e-aut hor1234567調(diào)整好結(jié)構(gòu)關(guān)係的片段路徑序列2022/2/22DBLAB NTOU18/37組合片段路徑模組 (cont.)i t emaut horpubl i sherf i r st _namedat e_of _bi r t h

22、name_of _ci t yname_of _st at e cat al ogi t em27212263126442648i t emaut hor787912143134aut hordat e_of _bi r t h82582795095114593463i t empubl i sher71012133132publ i shername_of _st at e10331335133632373238publ i ser hname_of _ci t y10171318aut horf i r st _name820GNGNGNLNLNLNLNi t em -cat al oga

23、ut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t emfi rst _nam e-aut hor1234567NULLResul t Tabl e3325272022/2/22DBLAB NTOU19/37產(chǎn)生所有可能的結(jié)構(gòu)化合併順序n狀態(tài)樹(shù) (StateTree)n狀態(tài)樹(shù)節(jié)點(diǎn)中放的是片段路徑樹(shù)n每個(gè)子節(jié)點(diǎn)代表片段路徑樹(shù)結(jié)構(gòu)化合併的過(guò)程ABCD片段路徑樹(shù)ABCD狀態(tài)路徑樹(shù)節(jié)點(diǎn)2022/2/22DBLAB NTOU20/37產(chǎn)生所有

24、可能的結(jié)構(gòu)化合併順序 (cont.)ABCDABCD2022/2/22DBLAB NTOU21/37實(shí)驗(yàn)n實(shí)驗(yàn)環(huán)境nCPU：Pentium 4 2.40GHzn記憶體：512MB n作業(yè)系統(tǒng)：Windows 2000 Advanced Server n實(shí)作工具：Microsoft Visual C+ 6.02022/2/22DBLAB NTOU22/37實(shí)驗(yàn)相關(guān)介紹nData SetsData SetSize# of elementMax depthMax widthXBench-dictionary16MB281387815XBench-customer30MB489601316XBench

25、-catalog100MB2245941710DBLP127MB3332130710TPC-lineitem30MB10229763162022/2/22DBLAB NTOU23/37實(shí)驗(yàn)相關(guān)介紹 (cont.)n片段路徑樹(shù)類(lèi)型n實(shí)驗(yàn)圖表之表示方式nDataSet.Pattern (XBench-catalog.a)nS, B, R,(a)(b)(c)(d)2022/2/22DBLAB NTOU24/37組合順序的分析n分析組合GFP_Table內(nèi)符合片段路徑答案由小至大的效率是最佳的413240444319269916RB466614684259271315RS471540094057271

26、831BB403140114215270315BS545340324110268716SB617247034031267231SSRandom3Random2Random1PreOrderIncreaseTime (ms)不同組合順序的比較 (in XBench-catalog)1110233024022075395RB26798388852119401RS909217720152109387BB2375277411492115399BS1245233920152078406SB812110928592125391SSRandom3Random2Random1PreOrderIncreaseT

27、ime (ms)不同組合順序的比較 (in lineitem)2022/2/22DBLAB NTOU25/37組合順序的分析 (cont.)n組合片段路徑花費(fèi)的總次數(shù)0100002000030000400005000060000700008000090000100000I ncr easePr eO r derRandom 1Random 2Random 3起始點(diǎn)GFP_Table的資料筆數(shù)020000040000060000080000010000001200000I ncr easePr eO r derRandom 1Random 2Random 3執(zhí)行組合次數(shù)(in XBench-ca

28、talog)(in TPC-lineitem)2022/2/22DBLAB NTOU26/37建立片段路徑模組分析n針對(duì)不同的data sets及查詢句類(lèi)型來(lái)進(jìn)行分析n觀察建立片段路徑處理時(shí)間與處理總資料筆數(shù)97809800982098409860988099009920SSSBBSRSBBRB建立片段路徑時(shí)間(ms)360000360500361000361500362000362500363000363500364000SSSBBSRSBBRB建立片段路徑處理總資料數(shù)(in XBench-catalog.a)2022/2/22DBLAB NTOU27/37建立片段路徑模組分析 (cont.

29、)269027002710272027302740275027602770SSSBRSBSBBRB建立片段路徑時(shí)間(ms)105000105200105400105600105800106000106200106400106600106800SSSBRSBSBBRB建立片段路徑處理總資料數(shù)(in XBench-catalog.b)2022/2/22DBLAB NTOU28/37建立片段路徑模組分析 (cont.)(in XBench-catalog.c)5824582658285830583258345836583858405842SSSBRSBSBBRB建立片段路徑時(shí)間(ms)1507401

30、50760150780150800150820150840150860150880150900150920150940SSSBRSBSBBRB建立片段路徑處理總資料數(shù)2022/2/22DBLAB NTOU29/37建立片段路徑模組分析 (cont.)1235012400124501250012550126001265012700SSSBBSRSBBRB建立片段路徑時(shí)間(ms)490000491000492000493000494000495000496000SSSBBSRSBBRB建立片段路徑處理資料筆數(shù)(in XBench-catalog.d)2022/2/22DBLAB NTOU30/37

31、建立片段路徑模組分析 (cont.)2150217522002225225022752300SSSBBSBBRSRB建立片段路徑時(shí)間(ms)835008360083700838008390084000SSSBBSBBRSRB建立片段路徑處理筆數(shù)(in TPC-lineitem.b)2022/2/22DBLAB NTOU31/37建立片段路徑模組分析 (cont.)40004020404040604080410041204140416041804200SSSBBBRSBSRB建立片段路徑時(shí)間(ms)1695001695251695501695751696001696251696501696751

32、69700SSSBBBRSBSRB建立片段路徑處理資料筆數(shù)(in DBLP.b)2022/2/22DBLAB NTOU32/37建立片段路徑模組分析 (cont.)148001485014900149501500015050SSSBBSBBRSRB建立片段路徑時(shí)間(ms)555500556000556500557000557500558000558500559000559500560000560500SSSBBSBBRSRB建立片段路徑處理資料筆數(shù)(in DBLP.b)2022/2/22DBLAB NTOU33/37最佳化查詢系統(tǒng)比較n最佳演算法的六種走訪順序nSS, SB, BS, BB, RS, RBn論文李03系統(tǒng)nPren產(chǎn)生所有可能走訪順序系統(tǒng)nBest, Worstn組合時(shí)採(cǎi)用由小至大的方式2022/2/22DBLAB NTOU34/37最佳化查詢系統(tǒng)比較 (cont.)時(shí)間(ms)BestSSSBBSBBRSRBWorstPreXQuer