Matching Twigs in Probabilistic XML
Matching Twigs in Probabilistic XML
复制标题
DOI：
--
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
B. Kimelfeld;Y. Sagiv
中科院分区：
文献类型：
--
作者：
B. Kimelfeld;Y. Sagiv
研究了针对概率XML的树枝查询的评估。允许投影，尤其是查询可能是布尔值。结果表明，对于概率XML的众所周知的模型，在数据复杂性下对具有投影的树枝的评估是可触犯的（而在其他概率数据模型中，投影是可靠的）。在查询和数据的复杂性下，即使没有投影（对于简单的树枝和数据），问题也变得棘手。在概率XML的早期工作中，答案始终完成。但是，通常需要产生部分答案，因为XML数据可能缺少子元素，而且，如果它们的概率太低，则可以认为完整的答案可能是无关紧要的。它显示了如何定义语义，该语义提供了相对于用户指定的概率阈值最大的部分答案。对于这种语义，它显示了如何有效评估树枝的方法，即使没有投影，也可以在查询和数据复杂性下。
Evaluation of twig queries over probabilistic XML is investigated. Projection is allowed and, in particular, a query may be Boolean. It is shown that for a well-known model of probabilistic XML, the evaluation of twigs with projection is tractable under data complexity (whereas in other probabilistic data models, projection is intractable). Under query-and-data complexity, the problem becomes intractable even without projection (and for rather simple twigs and data). In earlier work on probabilistic XML, answers are always complete. However, there is often a need to produce partial answers because XML data may have missing sub-elements and, furthermore, complete answers may be deemed irrelevant if their probabilities are too low. It is shown how to define a semantics that provides partial answers that are maximal with respect to a probability threshold, which is specified by the user. For this semantics, it is shown how to efficiently evaluate twigs, even under query-and-data complexity if there is no projection.