Efficient Processing of XML Twig Patterns with Parent ChildXML模式与母儿的有效处理.pptVIP

CIKM Efficient Processing of XML Twig Patterns with Parent Child Edges: A Look-ahead Approach Jiaheng Lu, Ting Chen, Tok Wang Ling National University of Singapore Nov. 11. 2004 Outline ? XML Twig Pattern Matching Problem definition State of the Art: TwigStack Sub-optimality of TwigStack Our algorithm: TwigStackList Performance Conclusion XML Twig Pattern Matching An XML document is commonly modeled as a rooted, ordered and labeled tree. Regional Coding Node Label1: (startPos: endPos, LevelNum) E.g. What is a Twig Pattern? A twig pattern is a small tree whose nodes are tags, attributes or text values and edges are either Parent-Child (P-C) edges or Ancestor-Descendant (A-D) edges. E.g. Selects Figure elements which are descendants of Paragraph elements which in turn are children of Section elements having child element Title Twig pattern : XML Twig Pattern Matching Problem Statement Given a query twig pattern Q, and an XML database D, we need to compute ALL the answers to Q in D. E.g. Consider Q1 and Doc 1: Previous work: TwigStack TwigStack2: a holistic approach Two-phase algorithm: Phase 1 TwigJoin: intermediate root-leaf paths are outputted Phase 2 Merge: merge the intermediate path list to get the result Previous work: TwigStack A node q in a twig pattern Q is associated with a stack Sq Insertion and deletion in a stack Sq Insertion: An element eq from stream Tq is pushed into its stack Sq if and only if eq has a descendant eqi in each Tqi , where qi is a child of q Each node eqi recursively has the first property Deletion: An element eq is popped out from its stack if all matches involving it have been output. Sub-optimality of TwigStack Sub-optimality of TwigStack: an example Main problem and our experiment TwigStack might output some intermediate results that are useless to query answers . To have a better understanding , we perform TwigStack on real dataset. Data set : TreeBank[from U. of Washington XML datasets]