Deciding Containment for Queries with Complex Objects (Extended Abstract)

Summary: Decidable containment and weak-equivalence for a conjunctive query language over complex objects via translation to novel 'simulation' and 'strong simulation' conditions on CQs (conditions involve arbitrary quantifier alternations). Shows simulation/strong-simulation checking is NP-complete, yields NP-completeness of CQ equivalence with grouping/aggregates, and identifies that weak-equivalence collapses to full equivalence when answers cannot contain empty sets. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h775bb99da1ffbca5
Venue: PODS
Year: 1997
Pagerank: 9.5718481e-05
Overall Rank: 1,818 | 87.78%
DOI: 10.1145/263661.263665

Incoming Non-self Citations Over Time

Authors

1. Alon Y. Levy (AT&T)
2. Dan Suciu (AT&T)

BibTeX Citation

@inproceedings{levy_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{Deciding Containment for Queries with Complex Objects (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/263661.263665},
        doi = {10.1145/263661.263665},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Levy, Alon Y. and Suciu, Dan},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
1,660	On the Decidability of Query Containment under Constraints	1998	PODS	9.9592164e-05
2,127	Query Rewriting for Semistructured Data	1999	SIGMOD	9.0005009e-05
2,881	On the minimization of XPath queries	2003	VLDB	7.9134117e-05
4,459	Semantic Query Optimization in the Presence of Types	2010	PODS	6.590177e-05
6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.9001613e-05
6,219	Incremental View Maintenance For Collection Programming	2016	PODS	5.8471493e-05
6,437	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.7853525e-05
7,805	Positive Higher-Order Queries	2010	PODS	5.4501544e-05
9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2224867e-05
10,055	Containment of Conjunctive Object Meta-Queries	2006	VLDB	5.087795e-05
13,089	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
73	Including Group-By in Query Optimization	1994	VLDB	0.00037522101
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034124569
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
875	Queries Independent of Updates	1993	VLDB	0.00013316445
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,119	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011950395
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010379636
2,169	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	8.9247938e-05
2,349	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5999717e-05
4,619	Semantic Representations and Query Languages for Or-sets	1993	PODS	6.4993923e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
2	10,392	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS
3	10,130	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS
4	7,805	Positive Higher-Order Queries	2010	PODS
5	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
6	5,948	Containment and Equivalence of Well-Designed SPARQL	2014	PODS
7	136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS
8	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
9	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
10	9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS