Equivalences among aggregate queries with negation
Equivalences among aggregate queries with negation
复制标题
带有否定的聚合查询之间的等价性
DOI：
10.1145/375551.375595
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Y. Sagiv
中科院分区：
文献类型：
--
作者：
Sara Cohen;W. Nutt;Y. Sagiv
查询等价性研究的析取聚合查询否定子目标，常量和比较。给出了聚集函数count、max、sum、prod、top2和parity的等价性的充分刻画。一个相关的问题是，对于一个给定的自然数N，确定两个给定的查询是否是等价的所有数据库与最多N个常数。我们称这个问题为有界等价。给出了有界等价可判定性的一个完整刻画。特别是，它表明，这个问题是可判定的所有上述聚合函数以及cntd（计数不同），标准差（标准差），中位数和平均值。对于准线性查询（即，其中不重复肯定出现的谓词的查询）示出了对于聚集函数COUNT、MAX、SUM、PROD、TOP2、奇偶校验和AVG，可以在多项式时间内判定等价性。类似的结果也适用于cntd，只要有一些附加条件。结果表达在抽象的聚合函数的特性，并使用新的证明技术。最后，给出的结果也意味着等价，袋集语义下，是可判定的非聚集查询与否定。
Query equivalence is investigated for disjunctive aggregate queries with negated subgoals, constants and comparisons. A full characterization of equivalence is given for the aggregation functions count, max, sum, prod, top2 and parity. A related problem is that of determining, for a given natural number N, whether two given queries are equivalent over all databases with at most N constants. We call this problem bounded equivalence. A complete characterization of decidability of bounded equivalence is given. In particular, it is shown that this problem is decidable for all the above aggregation functions as well as for cntd (count distinct), stdev (standard deviation), median and avg. For quasilinear queries (i.e., queries in which predicates that occur positively are not repeated) it is shown that equivalence can be decided in polynomial time for the aggregation functions count, max, sum, prod, top2, parity, and avg. A similar result holds for cntd provided that a few additional conditions hold. The results are couched in terms of abstract characteristics of aggregation functions, and new proof techniques are used. Finally, the results presented also imply that equivalence, under bag-set semantics, is decidable for nonaggregate queries with negation.