中文模板

Size: px

Start display at page:

Download "中文模板"

黛沛美余
5 years ago
Views:

1 ISSN , CODEN RUXUEW Journal of Software, Vol8, No6, June 2007, pp DOI: 0360/jos8429 Tel/Fax: by Journal of Software All rights reserved F-Index: Twig,2+,,, (, 00872) 2 (, ) F-Index: A Flattened Structural Index for Speeding up Twig Query Processing ZHOU Jun-Feng,2+, MENG Xiao-Feng, JIANG Yu, XIE Min (Information School, Renmin University of China, Beijing 00872, China) 2 (Department of Computer Science and Technology, Yanshan University, Qinhuangdao , China) + Corresponding author: Phn: , zhoujf@ysueducn, Zhou JF, Meng XF, Jiang Y, Xie M F-Index: A flattened structural index for speeding up twig query processing Journal of Software, 2007,8(6): Abstract: How to process twig query quickly and correctly has attracted much attention in research society recently Filtering query irrelevant elements before query execution is an important step for reducing elements scanned at query processing As a flattened structural index, F-Index is proposed to filter out all query irrelevant index nodes, thus query irrelevant elements can be filtered out rapidly and mostly, especially when it is processing deeply nested XML documents with a complex structure After filtering, a new efficient query algorithm based on the remaining elements is proposed to accelerate query processing Experimental results on various datasets indicate that twig query s performance can be improved significantly by using F-Index Key words: : XML; query optimization; twig query; filtering; structural index twig XML,, F-Index,,, XML,, F-Index : XML; ;twig ; ; : TP3 : A XML, XML Supported by the National Natural Science Foundation of China under Grant Nos , ( ); the National Basic Research Program of China under Grant No2003CB37000 ( (973)); the Key Project of Ministry of Education of China under Grant No03044 ( ); the Program for New Century Excellent Talents in University ( ) Received ; Accepted

2 430 Journal of Software Vol8, No6, June 2007 XML,,Twig ( ) Twig Twig, (PC) (AD),XPath //book [//appendix]//figure book figure, book appendix, XML,, XML XML, XMark, -index 54 ; TreeBank,-index ,, Table Comparison of different datasets features Dataset Size (M) Tags Doc nodes -index nodes Doc nodes/-index nodes XMark TreeBank AD PC,,, : () F-Index,,XML,F-Index (2), (3), 2 3 F-Index F-Index 4 F-Index 5 6 * 7 8 [ 5], ; [6 3], ; [4,5],,TwigStack [4], AD, PC, AD Twig, [5] XR-Tree, XML, [6], DataGuide [7],-index [8] F&B [9] [6,20 22] [6,20],, [2,22] TreeBank,,, [22],, / PC, // AD, Tag, A,B,, A,B, a,b

3 :F-Index: Twig 43 2 :, 2 a A b a 2 a 3 c 4 B A 2 C 2 b 2 c c 2 c 3 d 3 B 2 C D 2 Fig d d 2 e (a) XML-Document (a) XML D E (b) -Index (b) -Index XML document and the corresponding -index structure XML -index : //C[//D]/E, TwigStack c c 4,d d 3,e, (b), -index C,D E, 2 c,c 2,c 3,d,d 2,e, c 4,d 3,, :c,c 3,, 2,, :,,, 3 F-Index 3 F-Index start,end,level -index -index Tag, start 2, F-Index A n Tag B, B i, n 2 B i n A -index, A S={n,n 2,,n k },,n i ( i k) A,, S Tag, S=S S 2 S m (m k) S i S j = (( i m) ( j m) (i j)),,m Tag, S i ( i m), S i, n, A Tag B, 2 nb,, Si, S B, 3 3(a), 3(b) 3(a),AncestorNode A, A Tag C ;ChildNode C 2, A Tag C C 2,, ;MinDescNode A Tag C start, C,nDescCount A Tag C (b), 2 Tag C, C,C 2 A A MinDescNode 2 C, 2 3(b) A Tag C (b), Tag A Tag C, AncestorNode, 3(e), Tag A Tag C

4 432 Journal of Software Vol8, No6, June 2007 AncestorNode ChildNode MinDescNode ndesccount A C 2 C 2 (a) The link element (b) A link element instance (a) (b) A B C D E A B C D E A 2 B 2 C 2 D 2 ReachableTag AC (c) The link head (c) A C 2 C 2 AC (d) A link head instance (d) A 2 C C (e) A link instance (e) Fig2 Query aided structure 2 Fig3 The link structure 3 3(c), 3(d),ReachableTag -index Tag, 3(d),,AC Tag A -index Tag C, Tag A A i, A i Tag C,, Tag A A m, A m Tag C 3(a) 3(c) 3(e) (b) Tag A Tag C, Tag, 4 F-Index 2 F-Index 3 //A/B, Tag A -index, Tag B 4 //A//B, Tag A -index,, Tag B 5 Twig//A[//B]//C, AB AC, AncestorNode, Tag A,, Tag B C, Tag B C A //A[/B]//C //A[//B]/C Twig Tag A,F-Index, 5 3 4, A, //A//B //A//C 6 Twig, //A[//B]/C[//D]/E, Tag A, Tag C, Tag B,D E, B C, D E A 6 5, 2: 5 3 F-Index Q, C D, C D AD,,, C D,C 2 D 2 Q 2, CD, CE, AncestorNode, ; AncestorNode, 4 Q 2 C D E

5 :F-Index: Twig 433 AA AB AC AD AE CD CE A A 2 A 2 A B B 2 A C 2 C 2 A - D 2 A - E C D D C E E A 2 B 2 B 2 A 2 C C A 2 - D A 2 - E C 2 D 2 D 2 D B C D Q C Q 2 A C D Q 3 E E Fig4 Structure of F-Index 4 F-Index Fig5 Query examples 5 Q 3, 4 F-Index : () F-Index, (2) 3 :,F-Index,, F-Index,F-Index 32 F-Index Tag,,,F-Index Tag,, n Tag,,F-Index O(n index n Tag ),,n index,n Tag Tag,,, Tag 4 F-Index A, Tag A, A A 3: 5(c) Q 3, A C, A,A A B,C,D,E,,A C PC,A B,D,E AD,A B C 4 FilterData(indexInfo) : curbranchnode=filterinfogetfirst(); 2: while (curbranchnode) 3: ToTagList=curBranchNodeGetToTagList();

6 434 Journal of Software Vol8, No6, June : while (not bfilterend) 5: if (FindMatchedSeq()) 6: RecordMatchedSeq(curBranchNode); 7: AdvanceAllPointer(ToTagList); 8: else 9: break; 0: curbranchnode=filterinfogetnext(); : RecordFilterResult(FilteredResult); 2: return FilteredResult; Procedure FindMatchedSeq() : while (all pointers in ToTagList are not equal) 2: ur=findminpointer(totaglist) 3: AdvancePointer(ur); 4: if (ur=null) 5: return false; 6: return true; Procedure RecordMatchSeq(curNode) : childnode=curnodefirstchild(); 2: while (childnode) 3: Q i =curnodegetchildnodevalue(); 4: P i =childnodegetnodevalue(); 5: while(q i =P i ) 6: NodeList=Node(P i )GetRecordedList(); 7: MergeNodeList(curNode,NodeList); 8: P i =childnodegetnextnodevalue(); 9: childnode=curnodenextchild() filterinfo,filterinfogetfirst(), Q 3 C 2~9 curbranchnode, 3 curbranchnodegettotaglist(), ToTagList FilterEnd(),,FindMatchedSeq(),RecordMatchedSeq(curBranchNode), 0 filterinfogetnext(),,,, 2 FindMatchedSeq(), ToTagList AncestorNode, 2, false ToTagList, true, RecordMatchSeq(curNode), curnodefirstchild() curnode, 3 curnodegetchildnodevalue() Q i, P i, 4 childnodegetnodevalue() P i, Q i =P i, 6 Node(P i )GetRecordedList() 7 MergeNodeList(curNode,NodeList) 8 curnodenextchild(), PC AD :

7 :F-Index: Twig 435 4: 5(c) Q 3 F-Index Q 3, A C, C, A () C: CD CE, AD PC, 4, C D E (2) A: AB,AD,AE 3, AC,4, AncestorNode, ; A B C 2,A Tag C C 2, C C 2,,4 ; 2 A 2 B 2 C,A 2 Tag C C,, A 2 B 2 C D E 42,,F-Index O(n),,n 5, (start,end,level), start q C q 6,C q q, C q C q C q C q, Advance(C q ) ;, C q start,c q end C q level,, q C q Sorted element set of q Sorted element set of q C q2 C q3 q 2 q 3 Sorted element set of q 2 Sorted element set of q 3 Sorted element set of q 3 Fig6 Cursors during execution 6 2 (solution) q, q, q : () q, C q (2) q, q C start < C start C end C end,q q q q q > q 2 S={q,q 2,,q n } Q,Q q, q,, C q Cq C 2 q n Q :, 2 AD,, PC, PC AD 5 2 FindSolution(), true, 2 RecordMatchedResult() FindSolution() q, q,

8 436 Journal of Software Vol8, No6, June 2007 (q C i q ) C q, FindSolution q i q i q, C q AD, true, false RecordMatchedResult() (start,end) 2 CHTwigQuery(root) : while (FindSolution(root)) 2: RecordMatchedResult(); Procedure FindSolution(q) : for q i in children(q) do 2: while ( Cq i is not a descendant of Cq) 3: while ( C start<cqstart) 4: Advance(C ); q i 5: if (end(q i )) 6: return false; 7: while ( C start> Cqend) 8: Advance(C q ); 9: if (end(q)) 0: return false; : if (!FindSolution(q i )) 2: return false; 3: return true q i q i 3 F-Index,, 3,, 4 3 FilterQuery(root) : FilteredResult=FilterData(indexInfo); 2: for each Seq in FilteredResult; 3: AppendSeqToQuery(Seq); 4: CHTwigQuery(root); Procedure RecordMatchedResult (q) : for each q i in children(q) do 2: while (!end(q i ) & C end<cqend) 3: if (RecordMatchedResult(q i )) 4: AddResultToParent(q i,q); 5: Advance(q i ) q i 5: //A//C/D, -index A C D,A C 2 D 2 A 2 C D, 7 A C D, 2,3 C A,C C,C D a,c 2 d,, 2, a c 2 d a c 2 d 2 a A C 2 D 2,3 C A,C C,C D, a,c 4 d 3,, a c 4 d 3 A 2 C D,3 C A,C C,C D a 2,c 2 d, 2 2, a 2 c 2 d a 2 c 2 d 2

9 :F-Index: Twig 437 A a a a 2 a 3 C c c 2 c 3 c 4 c c 2 c 3 d 2 D d d 3 d d 2 Fig7 The elements after filtering 7 52 TwigStack 2, :(), O(mn 2 ),,m,n ;(2), [2],, O(k index /n),,k index,n CHTwigQuery, O(n/m),,n CHTwigQuery,m (start,end) 6 * F-Index, (start,end,level,parentstart),,parentstart start, parentstart 7( ) Q *, Q * Q : () Q=A/*/B Q =A//B, C A level+2=c B level (2) Q=A//*//B Q=A/*//B Q=A//*/B Q =A//B, C A level+2 C B level (3) Q=A/*[/B]/C Q =A[//B]//C, C A level+2=c B level C A level+2=c C level C B parentstart=c C parentstart (4) Q=A//*[/B]/C Q =A[//B]//C, C A level+2 C B level C A level+2 C C level C B parentstart=c C parentstart (5) Q A,B n *, C A level+n+ C B level (6) Q twig * n, (3) (4) 6 * 6, [23] *,, * twig 6: //A[*[/B]/C]/D //A[//B][//C]/D, 7 (C A level+2=c B level) C A level+2=c C level) (C B parentstart=c C parentstart) 7 P4 28GHz,G RAM,80G PC, Windows XP VC++60 TwigStack [4] itwigstack [2] SegSJ [22] XMark [24] TreeBank [24] F-Index -index 72 XMark QX~QX8, Treebank QT~QT4, 2

10 438 Journal of Software Vol8, No6, June 2007 Table 2 Queries used in the experiment 2 Query No XPath expression Query No XPath expression QX /site/regions/africa/item/description/parlist/listitem/text/keyword QX7 //listitem[//bold]/text//emph QX2 /site/closed_auctions/closed_auction[annotation/ description[parlist/listitem/text[keyword[bold]]]]/price QX8 //listitem[//bold]/text[//emph]/keyword QX3 /site/closed_auctions//emph QT //S//ADJP[//MD] QX4 /site/people/person[//age]//education QT2 //S[/JJ]/NP QX5 //site/people/person/name QT3 //S/VP/PP[/NP/VBN]/IN QX6 //text[/bold]/emph/keyword QT4 //S/VP//PP[//NP/VBN]/IN F-Index, 5 F-Index : F-Index ; F-Index ; F-Index ; F-Index ; F-Index F-Index 3 F-Index -index,xmark,f-index -index 22 ;Treebank,F-Index -index 25,, O(n index n Tag ) Table 3 Size of F-Index and -index 3 F-Index -index Dataset (size) XMark (M) XMark (2M) XMark (35M) XMark (57) XMark (93M) XMark (6M) Treebank (84M) Elements index nodes F-Index nodes F-Index nodes/-index nodes F-Index () 8(a) 8(b), F-Index, QX, ,,, Treebank /6~/3 XMark,, QX4,SegSJ, F&B, F-Index itwigstack SegSJ Pre-Filtering QX QX2 QX3 QX4 QX5 QX6 QX7 QX8 (a) XMark F-Index QT itwigstack SegSJ QT2 QT3 (b) Treebank Pre-Filtering QT4 Fig8 Comparison of elements number 8 (2) 9(a) 9(b),F-Index, QX QX2 itwigstack, QX PC-path,,,QX2 PC-twig

11 :F-Index: Twig 439, SegSJ F&B, -index, FB, Treebank itwigstackitwigstack Treebank, Treebank -index, F-Index itwigstack SegSJ F-Index itwigstack SegSJ 0000 QX QX2 QX3 QX4 QX5 QX6 QX7 QX8 (a) XMark QT QT2 (b) Treebank Fig9 Comparison of processed index nodes number (3) QT3 9 0(a) 0(b), XMark,, F-Index, ; Treebank, Treebank, QT4, 465ms, itwigstack,xmark QX2, 4ms,Treebank QT4, ms SegSJ, F&B, -index, Treebank, F&B, QT F-Index itwigstack SegSJ F-Index itwigs SegSJ 0000 QX QX2 QX3 QX4 QX5 QX6 QX7 QX8 (a) XMark Fig Comparison of filtering time 0 QT QT2 QT3 QT4 (b) Treebank 733 F-Index (a) (b),f-index itwigstack SegSJ, TwigStack, itwigstack TwigStack, F-Index itwigstack SegSJ F-Index itwigstack SegSJ QX QX2 QX3 QX4 QX5 QX6 QX7 QX8 QT QT2 QT3 QT4 (a) XMark Fig (b) Treebank Comparison of running time after filtering 734 F-Index 2(a) 2(b), F-Index, F-Index

12 440 Journal of Software Vol8, No6, June , F-Index itwigstack SegSJ TwigStack QX QX2 QX3 QX4 QX5 QX6 QX7 QX8 Fig2 (a) XMark F-Index itwigstack SegSJ TwigStack QT QT2 QT3 QT4 (b) Treebank Comparison of the running time of different query algorithms 735 F-Index 2 3 (PC-twig,AD-twig) F-Index, F-Index, 3 F-Index itwigstack SegSJ TwigStack M 2M 35M 57M 93M 6M (a) QX6 Fig3 736 F-Index itwigstack SegSJ TwigStack M 2M 35M 57M 93M 6M (b) QX7 Comparison of the scalability of different query algorithm 3,,, TwigStack,,,F-Index, itwigstack SegSJ, F-Index, 8, XML, F-Index,,,,F-Index,, F-Index References: [] McHugh J, Widom J Query optimization for XML In: Malcolm PA, Maria EO, Patrick V, Stanley BZ, Michael LB, eds Proc of the 25th Int l Conf on Very Large Data Bases (VLDB) Edinburgh: Morgan Kaufmann Publishers,

13 :F-Index: Twig 44 [2] Michael J, Franklin MJ Efficient filtering of XML documents for selective dissemination of information In: Amr EA, Michael LB, Sharma C, Umeshwar D, Nabil K, Gunter S, Kyu YW, eds Proc of the 26th Int l Conf on Very Large Data Bases (VLDB) Cairo: Morgan Kaufmann Publishers, [3] Gottlob G, Koch C, Pichler R Efficient algorithms for processing XPath queries In: Stéphane B, Akmal BC, Mong LL, Jeffrey XY, Zoé L, eds Proc of the 28th Int l Conf on Very Large Data Bases (VLDB) Hong Kong: Morgan Kaufmann Publishers, [4] Halvreson A, Burger J, Galanis L, Kini A, Krishnamurthy R, Rao AN, Tian F, Viglas SD, Wang Y, Naughton JF, DeWitt DJ Mixed mode XML query processing In: Johann CF, Peter CL, Serge A, Michael JC, Patricia GS, Andreas H, eds Proc of the 29th Int l Conf on Very Large Data Bases (VLDB) Berlin: Morgan Kaufmann Publishers, [5] Lu SC, Meng XF, Lin C, Wang Y Navigation implementation for XQuery in OrientX Journal of Computer Research and Development, 2004,4(0): (in Chinese with English abstract) [6] Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G On supporting containment queries in relational database management systems In: Aref WG, ed Proc of the ACM SIGMOD Int l Conf on Management of Data (SIGMOD) ACM, [7] Li Q, Moon B Indexing and querying XML data for regular path expressions In: Peter MGA, Paolo A, Stefano C, Stefano P, Kotagiri R, Richard TS, eds Proc of the 27th Int l Conf on Very Large Data Bases (VLDB) Rome: Morgan Kaufmann Publishers, [8] Al-Khalifa S, Jagadish HV, Koudas N, Patel JM, Srivastava D, Wu Y Structural joins: A primitive for efficient XML query pattern matching In: Agrawal R, Dittrich K, Ngu AHH, eds Proc of the 8th Int l Conf on Data Engineering (ICDE) San Jose: IEEE Computer Society, [9] Chien SY, Vagena Z, Zhang D, Tsotras VJ, Zaniolo C Efficient structural joins on indexed XML documents In: Stéphane B, Akmal BC, Mong LL, Jeffrey XY, Zoé L, eds Proc of the 28th Int l Conf on Very Large Data Bases (VLDB) Hong Kong: Morgan Kaufmann Publishers, [0] Jiang H, Lu H, Wang W, Ooi BC XR-Tree: Indexing XML data for efficient structural joins In: Umeshwar D, Krithi R, Vijayaraman TM, eds Proc of the 9th Int l Conf on Data Engineering (ICDE) Bangalore: IEEE Computer Society, [] Lam F, Shui WM, Fisher DK, Wong RK Skipping strategies for efficient structural joins In: Yoonjoon L, Jianzhong L, Kyuyoung W, Doheon L, eds Proc of the Database Systems for Advances Applications (DASFAA) Jeju Island: Springer-Verlag, [2] Wang J, Meng XF, Wang S Structural join of XML based on range partitioning Journal of Software, 2004,5(5): (in Chinese with English abstract) [3] Wang J, Meng XF, Wang Y, Wang S Target node aimed path expression processing for XML data Journal of Software, 2005,6(5): (in Chinese with English abstract) [4] Bruno N, Koudas N, Srivastava D Holistic twig joins: Optimal XML pattern matching In: Michael JF, Bongki M, Anastassia A, eds Proc of the 2002 ACM SIGMOD Int l Conf on Management of Data (SIGMOD) Madison: ACM, [5] Jiang HF, Wang W, Lu H, Yu JX Holistic twig joins on indexed XML documents In: Johann CF, Peter CL, Serge A, Michael JC, Patricia GS, Andreas H, eds Proc of the 29th Int l Conf on Very Large Data Bases (VLDB) Berlin: Morgan Kaufmann Publishers, [6] Moro MM, Vagena Z, Tsotras VJ Tree-Pattern queries on a lightweight XML processor In: Klemens B, Christian SJ, Laura MH, Martin LK, Per-Ake L, Beng CO, eds Proc of the 3st Int l Conf on Very Large Data Bases (VLDB) Trondheim: ACM, [7] Goldman R, Widom J DataGuides: Enabling query formulation and optimization in semistructured databases In: Matthias J, Michael JC, Klaus RD, Frederick HL, Pericles L, Manfred AJ, eds Proc of 23rd Int l Conf on Very Large Data Bases (VLDB) Athens: Morgan Kaufmann Publishers, [8] Milo T, Suciu D Index structures for path expressions In: Catriel B, Peter B, eds Proc of the Int l Conf on Database Theory (ICDT) Jerusalem: Springer-Verlag,

14 442 Journal of Software Vol8, No6, June 2007 [9] Kaushik R, Bohannon P, Naughton JF, Korth HF Covering indexes for branching path queries In: Michael JF, Bongki M, Anastassia A, eds Proc of the 2002 ACM SIGMOD Int l Conf on Management of Data Madison: ACM (SIGMOD), [20] Barta A, Consenc MP, Mendelzon AO Benefits of path summaries in an XML query optimizer supporting multiple access methods In: Klemens B, Christian SJ, Laura MH, Martin LK, Per-Ake L, Beng CO, eds Proc of the 3st Int l Conf on Very Large Data Bases (VLDB) Trondheim: ACM, [2] Chen T, Lu JH, Ling TW On boosting holism in XML twig pattern matching using structural indexing techniques In: Fatma Ö, ed Proc of the ACM SIGMOD Int l Conf on Management of Data (SIGMOD) Baltimore: ACM, [22] Wang W, Wang HZ, Lu HJ, Jiang HF, Lin XM, Li JZ Efficient processing of XML path queries using the disk-based F&B index In: Klemens B, Christian SJ, Laura MH, Martin LK, Per-Ake L, Beng CO, eds Proc of the 3st Int l Conf on Very Large Data Bases (VLDB) Trondheim: ACM, [23] Hou S, Jacobsen HA Predicate-Based filtering of XPath expressions In: Ling L, Andreas R, Kyuyoung W, Jianjun Z, eds Proc of the 22nd Int l Conf on Data Engineering (ICDE) Atlanta: IEEE Computer Society, [24] Miklau G XMLData repository : [5],, OrientX XQuery,2004,4(0): [2], XML,2004,5(5): [3],,, XML,2005,6(5): /6/827htm (977 ),,,,, XML (98 ),,, XML (964 ),,,,,CCF, Web,XML, (984 ),,, XML

1 2 / 3 1 A (2-1) (2-2) A4 6 A4 7 A4 8 A4 9 A ( () 4 A4, A4 7 ) 1 (2-1) (2-2) ()

1 2 / 3 1 A (2-1) (2-2) A4 6 A4 7 A4 8 A4 9 A ( () 4 A4, A4 7 ) 1 (2-1) (2-2) () (39mm E-Mail ( )( ), : : 1 1 ( ) 2 2 ( ) 29mm) WSK ( 1 2 / 3 1 A4 2 1 3 (2-1) 2-1 4 (2-2) 2-2 5 A4 6 A4 7 A4 8 A4 9 A4 10 11 ( () 4 A4, 5 6 7 8 A4 7 ) 1 (2-1) (2-2) () 1 2 (2-1) 3 (2-2) 4 5 6 7 (8 ) 9