As huge volumes of data are organized or exported in tree-structured form, it is quite necessary to extract useful information from these data collections using effective and efficient query processing methods. A natu...As huge volumes of data are organized or exported in tree-structured form, it is quite necessary to extract useful information from these data collections using effective and efficient query processing methods. A natural way of retrieving desired information from XML documents is using twig pattern （TP）, which is, actually, the core component of existing XML query languages. Twig pattern possesses the inherent feature that query nodes on the same path have concrete precedence relationships. It is this feature that makes it infeasible in many actual scenarios. This has driven the requirement of relaxing the complete specification of a twig pattern to express more flexible semantic constraints in a single query expression. In this paper, we focus on query evaluation of partially specified twig pattern （PSTP） queries, through which we can reap the most flexibility of specifying partial semantic constraints in a query expression. We propose an extension to XPath through introducing two Samepath axes to support partial semantic constraints in a concise but effective way. Then we propose a stack based algorithm, pTwigStack, to process a PSTP holistically without deriving the concrete twig patterns and then processing them one by one. Further, we propose two DTD schema based optimization methods to improve the performance of pTwigStack algorithm. Our experimental results on various datasets indicate that our method performs significantly better than existing ones when processing PSTPs.展开更多
Tree Match算法是一种有效的Twig查询匹配算法,但其存在反复分析Twig模式的缺点。针对该问题,引入编译中的部分求值技术,提出一种Twig查询优化方案。通过部分求值提前完成对Twig模式的分析,生成查询专用的指令序列代替原查询程序,并给...Tree Match算法是一种有效的Twig查询匹配算法,但其存在反复分析Twig模式的缺点。针对该问题,引入编译中的部分求值技术,提出一种Twig查询优化方案。通过部分求值提前完成对Twig模式的分析,生成查询专用的指令序列代替原查询程序,并给出查询机执行引擎,从而消除重复计算,优化XML树模式查询过程。实验结果表明,在不同Twig模式下,该优化方案能够有效提高XML查询的执行效率。展开更多
Finding all occurrences of a twig query in an XML database is a core operation for efficient evaluation of XML queries. It is important to effiectively handle twig queries with wildcards. In this paper, a novel path-p...Finding all occurrences of a twig query in an XML database is a core operation for efficient evaluation of XML queries. It is important to effiectively handle twig queries with wildcards. In this paper, a novel path-partitioned encoding scheme is proposed for XML documents to capture paths of all elements, and a twig query is modeled as an XPattern extended from tree pattern. After definition, simplification, normalization, verification and initialization of the XPattern, both work sets and a join plan are generated. According to these measures, an effiective algorithm to answer for a twig query, called DMTwig, is designed without unnecessary elements and invalid structural joins. The algorithm can adaptively deal with twig queries with branch ([ ]), child edge (/), descendant edge (//), and wildcard (*) synthetically. We show that path-partitioned encoding scheme and XPattern guarantee the I/O and CPU optimality for twig queries. Experiments on representative data set indicate that the proposed solution performs significantly.展开更多
针对目前已有XML通配符查询处理需将文档中所有元素标签读入内存中,匹配效率低的问题,提出一种新的基于LSPI(leaf sibling of path information)索引的不确定XML包含通配符和复杂谓词的查询处理算法Prob-BooleanStarTwig。算法基于有效...针对目前已有XML通配符查询处理需将文档中所有元素标签读入内存中,匹配效率低的问题,提出一种新的基于LSPI(leaf sibling of path information)索引的不确定XML包含通配符和复杂谓词的查询处理算法Prob-BooleanStarTwig。算法基于有效过滤策略自底向上进行模式匹配,将通配符转换成A-D关系和层次信息约束,解决传统通配符匹配问题,避免多次扫描查询模式,提高查询速度。理论分析和实验结果表明,算法的查询效率明显优于已有的算法。展开更多
基金Supported partially by the National Natural Science Foundation of China (Grant No. 60833005)the National High-Tech Research & Development Program of China (Grant Nos. 2007AA01Z155, 2009AA011904)the National Basic Research Program of China (Grant No.2003CB317000)
文摘As huge volumes of data are organized or exported in tree-structured form, it is quite necessary to extract useful information from these data collections using effective and efficient query processing methods. A natural way of retrieving desired information from XML documents is using twig pattern （TP）, which is, actually, the core component of existing XML query languages. Twig pattern possesses the inherent feature that query nodes on the same path have concrete precedence relationships. It is this feature that makes it infeasible in many actual scenarios. This has driven the requirement of relaxing the complete specification of a twig pattern to express more flexible semantic constraints in a single query expression. In this paper, we focus on query evaluation of partially specified twig pattern （PSTP） queries, through which we can reap the most flexibility of specifying partial semantic constraints in a query expression. We propose an extension to XPath through introducing two Samepath axes to support partial semantic constraints in a concise but effective way. Then we propose a stack based algorithm, pTwigStack, to process a PSTP holistically without deriving the concrete twig patterns and then processing them one by one. Further, we propose two DTD schema based optimization methods to improve the performance of pTwigStack algorithm. Our experimental results on various datasets indicate that our method performs significantly better than existing ones when processing PSTPs.
基金supported by the National High-Tech Research and Development Plan of China (Grant No.2005AA4Z3030)
文摘Finding all occurrences of a twig query in an XML database is a core operation for efficient evaluation of XML queries. It is important to effiectively handle twig queries with wildcards. In this paper, a novel path-partitioned encoding scheme is proposed for XML documents to capture paths of all elements, and a twig query is modeled as an XPattern extended from tree pattern. After definition, simplification, normalization, verification and initialization of the XPattern, both work sets and a join plan are generated. According to these measures, an effiective algorithm to answer for a twig query, called DMTwig, is designed without unnecessary elements and invalid structural joins. The algorithm can adaptively deal with twig queries with branch ([ ]), child edge (/), descendant edge (//), and wildcard (*) synthetically. We show that path-partitioned encoding scheme and XPattern guarantee the I/O and CPU optimality for twig queries. Experiments on representative data set indicate that the proposed solution performs significantly.
文摘针对目前已有XML通配符查询处理需将文档中所有元素标签读入内存中,匹配效率低的问题,提出一种新的基于LSPI(leaf sibling of path information)索引的不确定XML包含通配符和复杂谓词的查询处理算法Prob-BooleanStarTwig。算法基于有效过滤策略自底向上进行模式匹配,将通配符转换成A-D关系和层次信息约束,解决传统通配符匹配问题,避免多次扫描查询模式,提高查询速度。理论分析和实验结果表明,算法的查询效率明显优于已有的算法。
