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: 1147
Venue: PODS
Year: 1998
Pagerank: 8.8882317e-05
Overall Rank: 2,238 | 84.65%
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
559	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016528822
869	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013503594
1,034	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00012516197
1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.000113935
2,305	Querying Aggregate Data	1999	PODS	8.7766218e-05
4,759	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	6.5207388e-05
5,062	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.3799383e-05
8,663	Scalable Delivery of Stream Query Result	2009	VLDB	5.3887668e-05
11,297	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	5.093636e-05
12,492	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	5.093636e-05
12,626	Index-Based Multidimensional Array Queries: Safety and Equivalence	2007	PODS	5.093636e-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
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
554	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016580778
633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015560958
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05
2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	8.0012184e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,829	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
2	1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	11,146	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS
4	5,950	Translating and Optimizing SQL Queries Having Aggregates	1987	VLDB
5	2,305	Querying Aggregate Data	1999	PODS
6	869	Rewriting Aggregate Queries Using Views	1999	PODS
7	8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
8	12,492	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
9	5,062	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS
10	14,015	Equivalences Among Aggregate Queries with Negation	2001	PODS