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 |
|---|---|---|---|---|
| 731 | Optimizing Queries Using Materialized Views: A Practical, Scalable Solution | 2001 | SIGMOD | 0.00017468889 |
| 971 | Rewriting Aggregate Queries Using Views | 1999 | PODS | 0.00014925576 |
| 1,059 | Answering Complex SQL Queries Using Automatic Summary Tables | 2000 | SIGMOD | 0.00014382575 |
| 1,522 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.0001153051 |
| 2,475 | Querying Aggregate Data | 1999 | PODS | 8.7017602e-05 |
| 5,195 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6366303e-05 |
| 5,733 | Explaining Wrong Queries Using Small Examples | 2019 | SIGMOD | 5.3483446e-05 |
| 7,660 | Scalable Delivery of Stream Query Result | 2009 | VLDB | 4.6862657e-05 |
| 11,091 | Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle | 2024 | VLDB | 4.1945683e-05 |
| 12,297 | Equivalence of SQL Queries In Presence of Embedded Dependencies | 2009 | PODS | 4.1945683e-05 |
| 12,432 | Index-Based Multidimensional Array Queries: Safety and Equivalence | 2007 | PODS | 4.1945683e-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.00064826446 |
| 335 | Optimization of Real Conjunctive Queries | 1993 | PODS | 0.00027036073 |
| 581 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019767772 |
| 584 | Answering Queries with Aggregation Using Views | 1996 | VLDB | 0.0001971526 |
| 2,830 | Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions | 1993 | PODS | 8.054172e-05 |
| 2,877 | Semantic Query Optimization in Datalog Programs (Extended Abstract) | 1995 | PODS | 7.9715251e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,099 | Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries | 2018 | VLDB | 9.5479391e-05 |
| 1,522 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.0001153051 |
| 10,928 | Computing Range Consistent Answers to Aggregation Queries via Rewriting | 2024 | PODS | 4.1945683e-05 |
| 5,498 | Translating and Optimizing SQL Queries Having Aggregates | 1987 | VLDB | 5.4750555e-05 |
| 2,475 | Querying Aggregate Data | 1999 | PODS | 8.7017602e-05 |
| 971 | Rewriting Aggregate Queries Using Views | 1999 | PODS | 0.00014925576 |
| 8,704 | Equivalence of Nested Queries with Mixed Semantics | 2009 | PODS | 4.4647149e-05 |
| 12,297 | Equivalence of SQL Queries In Presence of Embedded Dependencies | 2009 | PODS | 4.1945683e-05 |
| 5,195 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6366303e-05 |
| 13,814 | Equivalences Among Aggregate Queries with Negation | 2001 | PODS | - |