Sequencing XML data and query twigs for fast pattern matching
Sequencing XML data and query twigs for fast pattern matching
复制标题
DOI：
10.1145/1132863.1132871
复制
发表时间：
2006-03
期刊：
影响因子：
--
通讯作者：
P. Rao;Bongki Moon
中科院分区：
文献类型：
--
作者：
P. Rao;Bongki Moon
我们提出了一种新的方法索引XML文档和处理树枝模式在XML数据库。数据库中的每个XML文档都可以通过prüfer的方法转换为标签序列，该方法在树和序列之间构造一对一的对应关系。在查询处理过程中，一个twig模式也被转换成它的Prüfer序列。通过对数据库中的序列集执行子序列匹配，并执行我们开发的一系列细化阶段，我们可以找到数据库中所有出现的小枝模式。我们的方法允许整体处理的树枝模式，而不打破树枝根到叶的路径，并单独处理这些路径。此外，我们在文章中表明，所有正确的答案都没有任何错误的解雇或错误的警报。实验结果表明，我们提出的技术的性能优势。
We propose a new way of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database can be transformed into a sequence of labels by prüfer's method that constructs a one-to-one correspondence between trees and sequences. During query processing, a twig pattern is also transformed into its Prüfer sequence. By performing subsequence matching on the set of sequences in the database and performing a series of refinement phases that we have developed, we can find all the occurrences of a twig pattern in the database. Our approach allows holistic processing of a twig pattern without breaking the twig into root-to-leaf paths and processing these paths individually. Furthermore, we show in the article that all correct answers are found without any false dismissals or false alarms. Experimental results demonstrate the performance benefits of our proposed techniques.