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.00027012705
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.00020099434
583 Answering Queries with Aggregation Using Views 1996 VLDB 0.00019705383
607 Extending Query Rewriting Techniques for Fine-Grained Access Control 2004 SIGMOD 0.00019248482
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014915911
1,508 Using Schematically Heterogeneous Structures 1998 SIGMOD 0.00011593524
1,520 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011524911
1,959 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.958725e-05
2,097 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5439744e-05
2,105 Deciding Equivalences among Aggregate Queries 1998 PODS 9.5309231e-05
2,318 On Improving User Response Times in Tableau 2015 SIGMOD 9.04679e-05
2,475 Querying Aggregate Data 1999 PODS 8.6942707e-05
3,068 Efficient Multi-way Theta-Join Processing Using MapReduce 2012 VLDB 7.6241861e-05
3,311 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.2361776e-05
3,782 Bag Query Containment and Information Theory 2020 PODS 6.7691169e-05
3,903 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 6.6439695e-05
4,385 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 6.2247394e-05
5,196 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6311982e-05
5,497 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 5.4741034e-05
5,719 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 5.3551435e-05
6,272 Classification of Annotation Semirings over Query Containment 2012 PODS 5.1271971e-05
6,273 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.1270241e-05
6,293 Containment of Nested XML Queries 2004 VLDB 5.1206121e-05
6,300 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.1174095e-05
6,606 Explainable Security for Relational Databases 2014 SIGMOD 4.9917624e-05
6,836 The Generalized Pre-Grouping Transformation: Aggregate-Query Optimization in the Presence of Dependencies 2003 VLDB 4.9065277e-05
6,884 Query Evaluation using Overlapping Views: Completeness and Efficiency 2006 SIGMOD 4.8917858e-05
6,993 Structure and Complexity of Bag Consistency 2021 PODS 4.8636515e-05
7,024 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 4.8530001e-05
7,782 New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions 1994 PODS 4.6479178e-05
8,492 Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? 2004 VLDB 4.4947925e-05
8,625 Predicate Pushdown for Data Science Pipelines 2023 SIGMOD 4.4784651e-05
8,699 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4604187e-05
9,794 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 4.2777144e-05
10,001 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.1905499e-05
10,930 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 4.1905499e-05
11,642 Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory 2019 PODS 4.1905499e-05
11,662 An Efficient Index for RDF Query Containment 2019 SIGMOD 4.1905499e-05
11,901 Raising Authorization Awareness in a DBMS 2015 CIDR 4.1905499e-05
12,305 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.1905499e-05
12,837 Tutorial: Languages for Collection Types 1994 PODS 4.1905499e-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.0040465394
58 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00064817807
448 The Magic of Duplicates and Aggregates 1990 VLDB 0.00022922417
835 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016081611
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,305 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.1905499e-05
6,884 Query Evaluation using Overlapping Views: Completeness and Efficiency 2006 SIGMOD 4.8917858e-05
2,396 Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) 1992 PODS 8.8892825e-05
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
10,001 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.1905499e-05
1,201 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD 0.00013341955
5,196 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6311982e-05
9,794 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 4.2777144e-05
2,732 Semantic Query Optimization in the Presence of Types 2010 PODS 8.2137395e-05
1,520 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011524911