The Research Of Extended Twig Pattern Matching Technology Based On FTContainsExpr

XML employs a tree-structured model for representing data,and queries over XML documents are typically represented as twig patterns.At the same time, keyword search over XML documents has been well studied because of its intuitive and friendly query interface.In order to integrate the fruits of XML query processing techniques in the data management field with those in the information retrieval field, W3C develop s the XQuery Full-Text as a full-text extension to XQuery.It can be used to seamlessly query over both the structure and the text content of XML documents. We propose the extended twig pattern and its matching problem based on the conjunctive-keyword semantic FTContainsExpr expression in XQFT.The extended twig pattern matching problem introduces new challenges because of the proposal of keyword-containment edge.First,we design a solution,which is composed of DILPathStack and DeweyPathStack algorithms,to the problem based on dewey encoding.DILPathStack first computes the SLCAs of the keyword nodes,and then utilize them to guide DeweyPathStack to match the structural paths.The computation of SLCAs prevents the useless node s in the data streams from stack operations in DeweyPathStack and accelerates the entire matching process.Afterwards,we analyze the deficiencies of DILPathStack and DeweyPathStack, and then propose the ILETwigStack algorithm which is based on region encoding and fits all general extended twig patterns directly.ILETwigStack reconstruct the extended twig pattern.It shrinks each group of keyword nodes into one query node and replaces the original streams of the group with their SLCA stream.The reconstructed twig pattern can then be matched by TwigStack.This solution not only reduces the structural complexity of the extended twig pattern but also cuts down the amount of initial data streams a lot.Experimental results show that ILETwigStack offers considerable performance benefits compared with DILPathStack and TwigStack when processing extended twig pattern queries.