Deciding Equivalences among Aggregate Queries

Summary: Characterizes equivalence of conjunctive aggregate queries with comparisons for min, max, count, count-distinct, and sum via dominance mappings (min/max), CQ-set equivalence (count-distinct), and isomorphism for bag-set/count, covering many sum cases. All characterizations are PSPACE-decidable; linear (no repeated predicates) queries admit PTIME algorithms; sum with both comparisons and constants requires a more elaborate criterion. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: he1492737b8e1ee6b
Venue: PODS
Year: 1998
Pagerank: 8.7196256e-05
Overall Rank: 2,269 | 84.75%
DOI: 10.1145/275487.275512

Incoming Non-self Citations Over Time

Authors

1. Werner Nutt (German National Research Center for Information Technology; Hebrew University)
2. Yehoshua Sagiv (Hebrew University)
3. Sara Shurin (Hebrew University)

BibTeX Citation

@inproceedings{nutt_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Deciding Equivalences among Aggregate Queries}},
        url = {https://dl.acm.org/doi/10.1145/275487.275512},
        doi = {10.1145/275487.275512},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Nutt, Werner and Sagiv, Yehoshua and Shurin, Sara},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
553	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.0001652591
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013280642
1,054	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00012269068
1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011242154
2,289	Querying Aggregate Data	1999	PODS	8.6891266e-05
4,847	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	6.3823876e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
8,823	Scalable Delivery of Stream Query Result	2009	VLDB	5.268676e-05
11,617	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	4.9793485e-05
12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9793485e-05
12,916	Index-Based Multidimensional Array Queries: Safety and Equivalence	2007	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033914384
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016272161
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.1006747e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
2	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	11,494	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS
4	6,055	Translating and Optimizing SQL Queries Having Aggregates	1987	VLDB
5	2,289	Querying Aggregate Data	1999	PODS
6	880	Rewriting Aggregate Queries Using Views	1999	PODS
7	9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
8	12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
9	5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS
10	14,326	Equivalences Among Aggregate Queries with Negation	2001	PODS