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

1、XML文件樹(shù)狀路徑查詢之最佳化研究Query Optimization For XML Twig Pattern Processing指導(dǎo)教授：張雅惠 博士研究生:蘇智宏10/10/20221/37DBLAB NTOUXML文件樹(shù)狀路徑查詢之最佳化研究Query Optimi大綱研究動(dòng)機(jī)系統(tǒng)架構(gòu)及相關(guān)定義查詢句最佳化處理實(shí)驗(yàn)結(jié)果結(jié)論與未來(lái)方向10/10/20222DBLAB NTOU大綱研究動(dòng)機(jī)10/9/20222DBLAB NTOU研究動(dòng)機(jī)結(jié)構(gòu)化合併 (Structural Join) 的順序Relational Database, value-based equi-join, two ta

2、bles and and columnsXML, structural join, containment relationship改善結(jié)構(gòu)化合併的順序利用最佳化演算法找到不同的結(jié)構(gòu)化合併順序10/10/20223DBLAB NTOU研究動(dòng)機(jī)結(jié)構(gòu)化合併 (Structural Join) 的順系統(tǒng)架構(gòu)前置處理最佳化查詢處理將XQuery轉(zhuǎn)換成XQuery Tree分割成Suffix Path並從相關(guān)資料結(jié)構(gòu)取得Partial Data將XQuery Tree轉(zhuǎn)換成片段路徑樹(shù)利用最佳化演算法找出六種走訪順序黏合符合片段路徑的答案將符合片段路徑的答案組成最後的結(jié)果自XML文件中取出資料10/10/

3、20224DBLAB NTOU系統(tǒng)架構(gòu)前置處理最佳化查詢處理將XQuery轉(zhuǎn)換成XQuerParsing XQuery and Building XQuery TreeFor $p in document (“.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 10/10/20225DBLAB NT

4、OUParsing XQuery and Building XQRetrieving Partial Data/catalogs/catalog/item/author/name/first_name= Germain/date_of_birth/publisher/name_of_city= Cozumel/name_of_state根據(jù)GN、DN、LN來(lái)切割出Suffix Path10/10/20226DBLAB NTOURetrieving Partial Data/cataloRetrieving Partial Data (cont.)/catalogs/catalog/item/a

5、uthor/name/first_name= Germain/date_of_birth/publisher/name_of_city= Cozumel/name_of_state利用相關(guān)資料結(jié)構(gòu)取得Partial DataPartial Data10/10/20227DBLAB NTOURetrieving Partial Data (cont.片段路徑樹(shù) (Fragment Path Tree)XQuery Tree片段路徑樹(shù)透過(guò)查詢樹(shù)中的GN、DN、LN建構(gòu)出片段路徑樹(shù)片段路徑樹(shù)中的節(jié)點(diǎn)代表一Suffix Path10/10/20228DBLAB NTOU片段路徑樹(shù) (Fragment

6、Path Tree)XQue片段路徑樹(shù) (cont.)片段路徑片段路徑的第一個(gè)節(jié)點(diǎn)為葉節(jié)點(diǎn)或分支節(jié)點(diǎn)，最後一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)或分支節(jié)點(diǎn)first_name-authorpublisher-item10/10/20229DBLAB NTOU片段路徑樹(shù) (cont.)片段路徑first_name-au片段路徑樹(shù) (cont.)片段路徑序列給予一個(gè)片段路徑樹(shù) FPT (FN, FE) ，若F1FN為其中的片段路徑，且FE中所有的edge正好被表示一次，則 (F1FN) 為一組片段路徑序列。 片段路徑序列10/10/202210DBLAB NTOU片段路徑樹(shù) (cont.)片段路徑序列片段路徑序列10/

7、9/問(wè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í)，能有較好的效率。片段路徑樹(shù)10/10/202211DBLAB NTOU問(wèn)題定義最佳化查詢處理片段路徑樹(shù)10/9/202211DBL查詢句最佳化處理最佳化處理模組根據(jù)經(jīng)驗(yàn)法則，找出六種結(jié)構(gòu)化合併順序建立片段路徑模組將片段路徑中的答案黏合成符合片段路徑的答案組合片段路徑模組透過(guò)GFP_Table內(nèi)的答案組出最後的結(jié)果擷取結(jié)果模組自XML文件中取出資料產(chǎn)生所

8、有可能的路徑實(shí)際產(chǎn)生所有可能的結(jié)構(gòu)化合併順序10/10/202212DBLAB NTOU查詢句最佳化處理最佳化處理模組10/9/202212DBLA最佳化處理模組走訪片段路徑樹(shù)起點(diǎn)：根節(jié)點(diǎn)或葉節(jié)點(diǎn)中間點(diǎn)：依partial data數(shù)量大小表示法： (X, Y)X根節(jié)點(diǎn)：R葉節(jié)點(diǎn)： S or BY中間點(diǎn)： S or B六種結(jié)構(gòu)化合併順序SS, SB, BS, BB, RS, RB10/10/202213DBLAB NTOU最佳化處理模組走訪片段路徑樹(shù)10/9/202213DBLAB最佳化處理模組 (cont.)最佳化處理模組在片段路徑樹(shù)上走訪的過(guò)程 (RB)*catalogitemitem-ca

9、talog*item, publisher*author-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_na

10、meheadUnVistedListFPListFPSequence*10/10/202214DBLAB NTOU最佳化處理模組 (cont.)最佳化處理模組在片段路徑樹(shù)上走建立片段路徑模組針對(duì)片段路徑序列分別作處理對(duì)片段序列中的每一片段路徑上的節(jié)點(diǎn)，其上所帶有的Partial Data資料進(jìn)黏合，以建立符合片段路徑結(jié)構(gòu)的資料 利用節(jié)點(diǎn)的起始編碼 (Start) 、結(jié)尾編碼 (End) 、深度編碼 (Level) ，判斷兩個(gè)Suffix Path是否具有適當(dāng)?shù)慕Y(jié)構(gòu)關(guān)係 GFP_Table82010/10/202215DBLAB NTOU建立片段路徑模組針對(duì)片段路徑序列分別作處理GFP_Tabl

11、e建立片段路徑模組 (cont.)經(jīng)過(guò)建立片段路徑模組處理完的片段路經(jīng)樹(shù)及GFP_Table10/10/202216DBLAB NTOU建立片段路徑模組 (cont.)經(jīng)過(guò)建立片段路徑模組處理完的組合片段路徑模組依GFP_Table大小，由小至大組合調(diào)整片段路徑序列結(jié)構(gòu)上的關(guān)係DoneFPSequenceStructureListUnStructureListfirst_name-authorfirst_nameauthorname_of_city-publisherpublisher-itemauthor-itemitempublisher-itempublishername_of_city

12、-publishername_of_cityitem-catalogname_of_state-publishercatalogname_of_statedate_of_birth-authordate_of_birth調(diào)整好結(jié)構(gòu)關(guān)係的片段路徑序列10/10/202217DBLAB NTOU組合片段路徑模組依GFP_Table大小，由小至大組合Don組合片段路徑模組 (cont.)NULL33252710/10/202218DBLAB NTOU組合片段路徑模組 (cont.)NULL33252710/9產(chǎn)生所有可能的結(jié)構(gòu)化合併順序狀態(tài)樹(shù) (StateTree)狀態(tài)樹(shù)節(jié)點(diǎn)中放的是片段路徑樹(shù)每個(gè)子

13、節(jié)點(diǎn)代表片段路徑樹(shù)結(jié)構(gòu)化合併的過(guò)程片段路徑樹(shù)狀態(tài)路徑樹(shù)節(jié)點(diǎn)10/10/202219DBLAB NTOU產(chǎn)生所有可能的結(jié)構(gòu)化合併順序狀態(tài)樹(shù) (StateTree)片產(chǎn)生所有可能的結(jié)構(gòu)化合併順序 (cont.)10/10/202220DBLAB NTOU產(chǎn)生所有可能的結(jié)構(gòu)化合併順序 (cont.)10/9/202實(shí)驗(yàn)實(shí)驗(yàn)環(huán)境CPU：Pentium 4 2.40GHz記憶體：512MB 作業(yè)系統(tǒng)：Windows 2000 Advanced Server 實(shí)作工具：Microsoft Visual C+ 6.010/10/202221DBLAB NTOU實(shí)驗(yàn)實(shí)驗(yàn)環(huán)境10/9/202221DBLAB N

14、TOU實(shí)驗(yàn)相關(guān)介紹Data SetsData SetSize# of elementMax depthMax widthXBench-dictionary16MB281387815XBench-customer30MB489601316XBench-catalog100MB2245941710DBLP127MB3332130710TPC-lineitem30MB102297631610/10/202222DBLAB NTOU實(shí)驗(yàn)相關(guān)介紹Data SetsData SetSize# o實(shí)驗(yàn)相關(guān)介紹 (cont.)片段路徑樹(shù)類型實(shí)驗(yàn)圖表之表示方式DataSet.Pattern (XBench-ca

15、talog.a)S, B, R,(a)(b)(c)(d)10/10/202223DBLAB NTOU實(shí)驗(yàn)相關(guān)介紹 (cont.)片段路徑樹(shù)類型(a)(b)(c)組合順序的分析分析組合GFP_Table內(nèi)符合片段路徑答案由小至大的效率是最佳的413240444319269916RB466614684259271315RS471540094057271831BB403140114215270315BS545340324110268716SB617247034031267231SSRandom3Random2Random1PreOrderIncreaseTime (ms)不同組合順序的比較 (in

16、XBench-catalog)1110233024022075395RB26798388852119401RS909217720152109387BB2375277411492115399BS1245233920152078406SB812110928592125391SSRandom3Random2Random1PreOrderIncreaseTime (ms)不同組合順序的比較 (in lineitem)10/10/202224DBLAB NTOU組合順序的分析分析組合GFP_Table內(nèi)符合片段路徑答案由組合順序的分析 (cont.)組合片段路徑花費(fèi)的總次數(shù)(in XBench-cata

17、log)(in TPC-lineitem)10/10/202225DBLAB NTOU組合順序的分析 (cont.)組合片段路徑花費(fèi)的總次數(shù)(in建立片段路徑模組分析針對(duì)不同的data sets及查詢句類型來(lái)進(jìn)行分析觀察建立片段路徑處理時(shí)間與處理總資料筆數(shù)(in XBench-catalog.a)10/10/202226DBLAB NTOU建立片段路徑模組分析針對(duì)不同的data sets及查詢句類型建立片段路徑模組分析 (cont.)(in XBench-catalog.b)10/10/202227DBLAB NTOU建立片段路徑模組分析 (cont.)(in XBench-c建立片段路徑模組

18、分析 (cont.)(in XBench-catalog.c)10/10/202228DBLAB NTOU建立片段路徑模組分析 (cont.)(in XBench-c建立片段路徑模組分析 (cont.)(in XBench-catalog.d)10/10/202229DBLAB NTOU建立片段路徑模組分析 (cont.)(in XBench-c建立片段路徑模組分析 (cont.)(in TPC-lineitem.b)10/10/202230DBLAB NTOU建立片段路徑模組分析 (cont.)(in TPC-line建立片段路徑模組分析 (cont.)(in DBLP.b)10/10/20

19、2231DBLAB NTOU建立片段路徑模組分析 (cont.)(in DBLP.b)1建立片段路徑模組分析 (cont.)(in DBLP.b)10/10/202232DBLAB NTOU建立片段路徑模組分析 (cont.)(in DBLP.b)1最佳化查詢系統(tǒng)比較最佳演算法的六種走訪順序SS, SB, BS, BB, RS, RB論文李03系統(tǒng)Pre產(chǎn)生所有可能走訪順序系統(tǒng)Best, Worst組合時(shí)採(cǎi)用由小至大的方式10/10/202233DBLAB NTOU最佳化查詢系統(tǒng)比較最佳演算法的六種走訪順序10/9/2022最佳化查詢系統(tǒng)比較 (cont.)時(shí)間(ms)BestSSSBBSBB

20、RSRBWorstPreXQuery011405214061(2)14060(1)14101(3)14130(5)14105(4)14130(5)1413516653(6)XQuery0243564360(1)4360(1)4395(3)4401(4)4375(2)4404(5)44065095(6)XQuery0394679470(1)9472(2)9476(4)9480(5)9475(3)9480(5)948310467(6)XQuery041911719156(1)19156(1)19219(3)19326(5)19222(4)19327(6)1933719938(7)XQuery0585338536(1)8536(1)8543(4)8553(5)8540(3)8557(6)85609775(7)XQuery0618591859(1)1859(1)1885(4)1869(2)1870(3)1885(5)18862276(6)XQuery07220220(1)220(1)223(2)225(3)223(2)223(3)225226(4)10/10/202234DBLAB NTOU最佳化查詢系統(tǒng)比較 (cont.)時(shí)間(ms)BestSSS最佳