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: h2910756246fca9dd
Venue: PODS
Year: 1993
Pagerank: 0.00021374145
Overall Rank: 310 | 97.92%
DOI: 10.1145/153850.153856

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Hewlett Packard Enterprise)
2. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{chaudhuri_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Optimization of Real Conjunctive Queries}},
        url = {https://dl.acm.org/doi/10.1145/153850.153856},
        doi = {10.1145/153850.153856},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chaudhuri, Surajit and Vardi, Moshe Y.},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 41 of 41 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
525	An Annotation Management System for Relational Databases	2004	VLDB	0.00016890994
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016272161
568	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00016262553
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013280642
1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011242154
1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.9031411e-05
1,728	Using Schematically Heterogeneous Structures	1998	SIGMOD	9.7779564e-05
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,269	Deciding Equivalences among Aggregate Queries	1998	PODS	8.7196256e-05
2,289	Querying Aggregate Data	1999	PODS	8.6891266e-05
2,700	On Improving User Response Times in Tableau	2015	SIGMOD	8.1188166e-05
2,931	Efficient Multi-way Theta-Join Processing Using MapReduce	2012	VLDB	7.8405483e-05
2,961	Proving Query Equivalence Using Linear Integer Arithmetic	2023	SIGMOD	7.8068219e-05
3,297	Automated Verification of Query Equivalence Using Satisfiability Modulo Theories	2019	VLDB	7.4452842e-05
3,526	Bag Query Containment and Information Theory	2020	PODS	7.2321894e-05
3,570	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.1977783e-05
4,974	SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra	2020	VLDB	6.3318399e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
5,841	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.9735439e-05
6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.9001613e-05
6,299	Classification of Annotation Semirings over Query Containment	2012	PODS	5.8190435e-05
6,319	Containment of Nested XML Queries	2004	VLDB	5.8153622e-05
6,477	Explainable Security for Relational Databases	2014	SIGMOD	5.7726401e-05
6,666	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.7157324e-05
7,138	The Generalized Pre-Grouping Transformation: Aggregate Query Optimization in the Presence of Dependencies	2003	VLDB	5.6008068e-05
7,266	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	5.5699944e-05
7,330	Structure and Complexity of Bag Consistency	2021	PODS	5.5503389e-05
7,419	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.5326094e-05
8,005	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.4085878e-05
8,153	Predicate Pushdown for Data Science Pipelines	2023	SIGMOD	5.3891786e-05
8,877	Efficient XML-to-SQL Query Translation: Where to Add the Intelligence?	2004	VLDB	5.257159e-05
9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2224867e-05
9,363	Complex Event Recognition meets Hierarchical Conjunctive Queries	2024	PODS	5.1868213e-05
10,130	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	5.0751052e-05
10,392	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.9793485e-05
12,133	Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory	2019	PODS	4.9793485e-05
12,152	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.9793485e-05
12,201	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9793485e-05
12,386	Raising Authorization Awareness in a DBMS	2015	CIDR	4.9793485e-05
12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9793485e-05
13,312	Tutorial: Languages for Collection Types	1994	PODS	4.9793485e-05

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.0023947656
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033914384
531	The Magic of Duplicates and Aggregates	1990	VLDB	0.00016847212
1,113	An Extended Relational Algebra with Control Over Duplicate Elimination	1982	PODS	0.00011971883

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
2	2,349	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS
3	7,266	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	10,392	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS
6	1,098	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD
7	5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS
8	10,130	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS
9	4,459	Semantic Query Optimization in the Presence of Types	2010	PODS
10	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS