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.6880978e-05
Overall Rank: 2,284 | 84.70%
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
556	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016470022
882	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013239752
1,059	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00012224962
1,279	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011207548
2,301	Querying Aggregate Data	1999	PODS	8.6620636e-05
4,871	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	6.3583165e-05
5,214	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2136202e-05
8,850	Scalable Delivery of Stream Query Result	2009	VLDB	5.2489348e-05
11,670	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	4.9605343e-05
12,831	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9605343e-05
12,964	Index-Based Multidimensional Array Queries: Safety and Equivalence	2007	PODS	4.9605343e-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
104	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033799916
312	Optimization of Real Conjunctive Queries	1993	PODS	0.00021306615
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016228477
645	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015188342
2,727	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0704592e-05
2,937	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8226419e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,678	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
2	1,279	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	11,552	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS
4	6,070	Translating and Optimizing SQL Queries Having Aggregates	1987	VLDB
5	2,301	Querying Aggregate Data	1999	PODS
6	882	Rewriting Aggregate Queries Using Views	1999	PODS
7	9,166	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
8	12,831	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
9	5,214	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS
10	14,371	Equivalences Among Aggregate Queries with Negation	2001	PODS