On the optimal approximation of queries using tractable propositional languages
On the optimal approximation of queries using tractable propositional languages
复制标题
DOI：
10.1145/1938551.1938575
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
Robert Fink;Dan Olteanu
中科院分区：
文献类型：
--
作者：
Robert Fink;Dan Olteanu
本文研究了概率数据库上无自连接的近似合取查询的上下界问题，该问题可以更有效地计算。我们通过一个间接的方法来研究这个问题：给定一个命题公式，用一种更严格的语言找到公式，它们分别是的最大下界和最小上界。我们研究的语言的只读一次公式，其中每个变量最多出现一次，和只读一次公式的析取范式的界限。我们展示了单值公式最佳界限的语法和模型理论特征的等价性，并提出了可以用多项式延迟对其进行枚举的算法。这样的边界可以通过使用传递闭包和特殊选择构造扩展的一阶查询来表示的查询来计算。除了概率数据库，这些结果也可以在关系数据库中的近似查询评估的问题，因为查询表示的界限可以计算在多项式组合复杂度。
This paper investigates the problem of approximating conjunctive queries without self-joins on probabilistic databases by lower and upper bounds that can be computed more efficiently. We study this problem via an indirection: Given a propositional formula , find formulas in a more restricted language that are greatest lower bound and least upper bound, respectively, of . We study bounds in the languages of read-once formulas, where every variable occurs at most once, and of read-once formulas in disjunctive normal form. We show equivalences of syntactic and model-theoretic characterisations of optimal bounds for unate formulas, and present algorithms that can enumerate them with polynomial delay. Such bounds can be computed by queries expressed using first-order queries extended with transitive closure and a special choice construct. Besides probabilistic databases, these results can also benefit the problem of approximate query evaluation in relational databases, since the bounds expressed by queries can be computed in polynomial combined complexity.