Answering ordered tree pattern queries over fuzzy XML data

摘要

The widespread employment of XML requires the development of efficient methods to support advanced tree pattern queries. In addition, in real-world applications that involve analysis and management of databases, uncertainty is often an inherent property of data. Although a large number of researches have been dedicated to modeling uncertain XML and answering queries over uncertain XML data, how to conduct order-based tree pattern queries on fuzzy XML data remains an open problem. In this work, we aim to fill this gap and tackle the problem of order-based queries on fuzzy XML data. Based on the node encoding, we propose efficient tree pattern matching algorithms serving for ordered queries over fuzzy XML data. In particular, our algorithms adopt a two-phase processing technique: the first phase generates the root-to-leaf path solutions, and the second phase merges these path solutions for producing the desired matches to the ordered tree pattern. Typically, our approach only needs to access data related to the query nodes in the tree pattern once to obtain all the matching answers. Finally, a comprehensive experimental evaluation is carried out to investigate the performance of the proposed approaches.