Efficient processing of top-k twig queries over probabilistic XML data
Efficient processing of top-k twig queries over probabilistic XML data
复制标题
DOI：
10.1007/s11280-011-0144-2
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
B. Ning;Chengfei Liu;J. Yu
中科院分区：
文献类型：
--
作者：
B. Ning;Chengfei Liu;J. Yu
与关系模型相比，XML数据模型的灵活性允许更自然地表示不确定数据。小枝模式与XML数据的匹配是从XML文档中查询信息的一个基本问题。对于概率XML文档，由于数据的不确定性，每个小枝答案都有一个概率值。概率值小的小枝答案对用户毫无用处，用户通常只想得到概率值最大的k个答案。为此，现有的用于普通XML文档的算法不能直接适用，因为需要处理概率分布节点和有效地计算概率XML中答案的top-k概率。本文研究了在概率XML文档中直接寻找具有top-k概率值的小枝答案问题。本文提出了一种新的概率XML编码方案PEDewey。在此编码方案的基础上，我们设计了两种算法来寻找小枝查询的top-k概率答案。一个称为ProTJFast，用于根据按文档顺序排列的元素流处理概率XML数据；另一个称为PTopKTwig，基于按路径概率值排序的元素流。通过实验研究了这些算法的性能。
The flexibility of XML data model allows a more natural representation of uncertain data compared with the relational model. Matching twig pattern against XML data is a fundamental problem in querying information from XML documents. For a probabilistic XML document, each twig answer has a probabilistic value because of the uncertainty of data. The twig answers that have small probabilistic value are useless to the users, and usually users only want to get the answers with the k largest probabilistic values. To this end, existing algorithms for ordinary XML documents cannot be directly applicable due to the need for handling probability distributional nodes and efficient calculation of top-k probabilities of answers in probabilistic XML. In this paper, we address the problem of finding twig answers with top-k probabilistic values against probabilistic XML documents directly. We propose a new encoding scheme called PEDewey for probabilistic XML in this paper. Based on this encoding scheme, we then design two algorithms for finding answers of top-k probabilities for twig queries. One is called ProTJFast, to process probabilistic XML data based on element streams in document order, and the other is called PTopKTwig, based on the element streams ordered by the path probability values. Experiments have been conducted to study the performance of these algorithms.