Database Paper Browser

Back to papers

Optimization of Real Conjunctive Queries

Summary: Analyzes optimization of conjunctive queries under bag (multiset) semantics rather than the usual set semantics. Shows that classical set-based rewrite rules and complexity results do not generalize, exposing distinct correctness conditions and optimization obstacles. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
988
Venue
PODS
Year
1993
Pagerank
0.00027036073
Overall Rank
335 | 97.68%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
561 An Annotation Management System for Relational Databases 2004 VLDB 0.00020115419
584 Answering Queries with Aggregation Using Views 1996 VLDB 0.0001971526
607 Extending Query Rewriting Techniques for Fine-Grained Access Control 2004 SIGMOD 0.00019266724
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014925576
1,511 Using Schematically Heterogeneous Structures 1998 SIGMOD 0.00011602872
1,522 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.0001153051
1,952 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.9677831e-05
2,099 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5479391e-05
2,103 Deciding Equivalences among Aggregate Queries 1998 PODS 9.5385023e-05
2,311 On Improving User Response Times in Tableau 2015 SIGMOD 9.0539767e-05
2,475 Querying Aggregate Data 1999 PODS 8.7017602e-05
3,062 Efficient Multi-way Theta-Join Processing Using MapReduce 2012 VLDB 7.6343994e-05
3,307 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.2431594e-05
3,775 Bag Query Containment and Information Theory 2020 PODS 6.775636e-05
3,901 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 6.6499845e-05
4,388 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 6.2303078e-05
5,195 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6366303e-05
5,487 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 5.4791501e-05
5,709 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 5.3602702e-05
6,274 Classification of Annotation Semirings over Query Containment 2012 PODS 5.1321227e-05
6,275 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.1319495e-05
6,294 Containment of Nested XML Queries 2004 VLDB 5.1255418e-05
6,300 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.1223169e-05
6,606 Explainable Security for Relational Databases 2014 SIGMOD 4.996456e-05
6,837 The Generalized Pre-Grouping Transformation: Aggregate-Query Optimization in the Presence of Dependencies 2003 VLDB 4.9111342e-05
6,881 Query Evaluation using Overlapping Views: Completeness and Efficiency 2006 SIGMOD 4.8964953e-05
6,995 Structure and Complexity of Bag Consistency 2021 PODS 4.8683245e-05
7,022 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 4.8576599e-05
7,782 New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions 1994 PODS 4.6523963e-05
8,493 Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? 2004 VLDB 4.4991066e-05
8,645 Predicate Pushdown for Data Science Pipelines 2023 SIGMOD 4.4772518e-05
8,704 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4647149e-05
9,791 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 4.2818172e-05
10,002 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.1945683e-05
10,926 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 4.1945683e-05
11,638 Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory 2019 PODS 4.1945683e-05
11,657 An Efficient Index for RDF Query Containment 2019 SIGMOD 4.1945683e-05
11,893 Raising Authorization Awareness in a DBMS 2015 CIDR 4.1945683e-05
12,297 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.1945683e-05
12,828 Tutorial: Languages for Collection Types 1994 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0040449103
58 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00064826446
445 The Magic of Duplicates and Aggregates 1990 VLDB 0.0002294367
837 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016097758
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,297 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.1945683e-05
6,881 Query Evaluation using Overlapping Views: Completeness and Efficiency 2006 SIGMOD 4.8964953e-05
2,398 Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) 1992 PODS 8.8973978e-05
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
10,002 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.1945683e-05
1,199 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD 0.00013354204
5,195 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6366303e-05
9,791 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 4.2818172e-05
2,727 Semantic Query Optimization in the Presence of Types 2010 PODS 8.2216778e-05
1,522 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.0001153051