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)
Incoming Non-self Citations Over Time
Authors
- 1. Werner Nutt
- 2. Yehoshua Sagiv
- 3. Sara Shurin
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 728 | Optimizing Queries Using Materialized Views: A Practical, Scalable Solution | 2001 | SIGMOD | 0.00017459654 |
| 971 | Rewriting Aggregate Queries Using Views | 1999 | PODS | 0.00014915911 |
| 1,059 | Answering Complex SQL Queries Using Automatic Summary Tables | 2000 | SIGMOD | 0.00014370009 |
| 1,520 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.00011524911 |
| 2,475 | Querying Aggregate Data | 1999 | PODS | 8.6942707e-05 |
| 5,196 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6311982e-05 |
| 5,743 | Explaining Wrong Queries Using Small Examples | 2019 | SIGMOD | 5.3432106e-05 |
| 7,658 | Scalable Delivery of Stream Query Result | 2009 | VLDB | 4.6817213e-05 |
| 11,094 | Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle | 2024 | VLDB | 4.1905499e-05 |
| 12,305 | Equivalence of SQL Queries In Presence of Embedded Dependencies | 2009 | PODS | 4.1905499e-05 |
| 12,441 | Index-Based Multidimensional Array Queries: Safety and Equivalence | 2007 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 58 | Efficient Optimization of a Class of Relational Expressions | 1978 | SIGMOD | 0.00064817807 |
| 335 | Optimization of Real Conjunctive Queries | 1993 | PODS | 0.00027012705 |
| 582 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019753367 |
| 583 | Answering Queries with Aggregation Using Views | 1996 | VLDB | 0.00019705383 |
| 2,836 | Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions | 1993 | PODS | 8.0466188e-05 |
| 2,887 | Semantic Query Optimization in Datalog Programs (Extended Abstract) | 1995 | PODS | 7.9640219e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,097 | Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries | 2018 | VLDB | 9.5439744e-05 |
| 1,520 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.00011524911 |
| 10,931 | Computing Range Consistent Answers to Aggregation Queries via Rewriting | 2024 | PODS | 4.1905499e-05 |
| 5,509 | Translating and Optimizing SQL Queries Having Aggregates | 1987 | VLDB | 5.4706803e-05 |
| 2,475 | Querying Aggregate Data | 1999 | PODS | 8.6942707e-05 |
| 971 | Rewriting Aggregate Queries Using Views | 1999 | PODS | 0.00014915911 |
| 8,699 | Equivalence of Nested Queries with Mixed Semantics | 2009 | PODS | 4.4604187e-05 |
| 12,305 | Equivalence of SQL Queries In Presence of Embedded Dependencies | 2009 | PODS | 4.1905499e-05 |
| 5,196 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6311982e-05 |
| 13,828 | Equivalences Among Aggregate Queries with Negation | 2001 | PODS | - |