XML文件树状路径查询之最佳化研究课件

1、XML文件樹狀路徑查詢之最佳化研究Query Optimization For XML Twig Pattern Processing指導教授：張雅惠 博士研究生:蘇智宏10/10/20221/37DBLAB NTOUXML文件樹狀路徑查詢之最佳化研究Query Optimi大綱研究動機系統架構及相關定義查詢句最佳化處理實驗結果結論與未來方向10/10/20222DBLAB NTOU大綱研究動機10/9/20222DBLAB NTOU研究動機結構化合併 (Structural Join) 的順序Relational Database, value-based equi-join, two ta

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

3、20224DBLAB NTOU系統架構前置處理最佳化查詢處理將XQuery轉換成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根據GN、DN、LN來切割出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利用相關資料結構取得Partial DataPartial Data10/10/20227DBLAB NTOURetrieving Partial Data (cont.片段路徑樹 (Fragment Path Tree)XQuery Tree片段路徑樹透過查詢樹中的GN、DN、LN建構出片段路徑樹片段路徑樹中的節點代表一Suffix Path10/10/20228DBLAB NTOU片段路徑樹 (Fragment

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

7、9/問題定義最佳化查詢處理給予一個片段路徑樹 FPT (FN, FE) ，且每一節點NiFN都已取得符合其對應Suffix Path的資料，我們的最佳化查詢處理，會根據經驗法則提出六種適當的結構化合併的順序，使其在建立片段路徑及組合成最後答案時，能有較好的效率。片段路徑樹10/10/202211DBLAB NTOU問題定義最佳化查詢處理片段路徑樹10/9/202211DBL查詢句最佳化處理最佳化處理模組根據經驗法則，找出六種結構化合併順序建立片段路徑模組將片段路徑中的答案黏合成符合片段路徑的答案組合片段路徑模組透過GFP_Table內的答案組出最後的結果擷取結果模組自XML文件中取出資料產生所

8、有可能的路徑實際產生所有可能的結構化合併順序10/10/202212DBLAB NTOU查詢句最佳化處理最佳化處理模組10/9/202212DBLA最佳化處理模組走訪片段路徑樹起點：根節點或葉節點中間點：依partial data數量大小表示法： (X, Y)X根節點：R葉節點： S or BY中間點： S or B六種結構化合併順序SS, SB, BS, BB, RS, RB10/10/202213DBLAB NTOU最佳化處理模組走訪片段路徑樹10/9/202213DBLAB最佳化處理模組 (cont.)最佳化處理模組在片段路徑樹上走訪的過程 (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.)最佳化處理模組在片段路徑樹上走建立片段路徑模組針對片段路徑序列分別作處理對片段序列中的每一片段路徑上的節點，其上所帶有的Partial Data資料進黏合，以建立符合片段路徑結構的資料 利用節點的起始編碼 (Start) 、結尾編碼 (End) 、深度編碼 (Level) ，判斷兩個Suffix Path是否具有適當的結構關係 GFP_Table82010/10/202215DBLAB NTOU建立片段路徑模組針對片段路徑序列分別作處理GFP_Tabl

11、e建立片段路徑模組 (cont.)經過建立片段路徑模組處理完的片段路經樹及GFP_Table10/10/202216DBLAB NTOU建立片段路徑模組 (cont.)經過建立片段路徑模組處理完的組合片段路徑模組依GFP_Table大小，由小至大組合調整片段路徑序列結構上的關係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調整好結構關係的片段路徑序列10/10/202217DBLAB NTOU組合片段路徑模組依GFP_Table大小，由小至大組合Don組合片段路徑模組 (cont.)NULL33252710/10/202218DBLAB NTOU組合片段路徑模組 (cont.)NULL33252710/9產生所有可能的結構化合併順序狀態樹 (StateTree)狀態樹節點中放的是片段路徑樹每個子

13、節點代表片段路徑樹結構化合併的過程片段路徑樹狀態路徑樹節點10/10/202219DBLAB NTOU產生所有可能的結構化合併順序狀態樹 (StateTree)片產生所有可能的結構化合併順序 (cont.)10/10/202220DBLAB NTOU產生所有可能的結構化合併順序 (cont.)10/9/202實驗實驗環境CPU：Pentium 4 2.40GHz記憶體：512MB 作業系統：Windows 2000 Advanced Server 實作工具：Microsoft Visual C+ 6.010/10/202221DBLAB NTOU實驗實驗環境10/9/202221DBLAB N

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

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

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

17、log)(in TPC-lineitem)10/10/202225DBLAB NTOU組合順序的分析 (cont.)組合片段路徑花費的總次數(in建立片段路徑模組分析針對不同的data sets及查詢句類型來進行分析觀察建立片段路徑處理時間與處理總資料筆數(in XBench-catalog.a)10/10/202226DBLAB NTOU建立片段路徑模組分析針對不同的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最佳化查詢系統比較最佳演算法的六種走訪順序SS, SB, BS, BB, RS, RB論文李03系統Pre產生所有可能走訪順序系統Best, Worst組合時採用由小至大的方式10/10/202233DBLAB NTOU最佳化查詢系統比較最佳演算法的六種走訪順序10/9/2022最佳化查詢系統比較 (cont.)時間(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最佳化查詢系統比較 (cont.)時間(ms)BestSSS最佳