Database Paper Browser

Back to papers

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
1099
Venue
PODS
Year
1997
Pagerank
9.9677831e-05
Overall Rank
1,952 | 86.43%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
48 Data Integration: A Theoretical Perspective 2002 PODS 0.00069720859
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028596715
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
2,399 Query Rewriting for Semistructured Data 1999 SIGMOD 8.8973689e-05
2,727 Semantic Query Optimization in the Presence of Types 2010 PODS 8.2216778e-05
3,084 On the minimization of Xpath queries 2003 VLDB 7.6011919e-05
6,299 Incremental View Maintenance For Collection Programming 2016 PODS 5.1225782e-05
6,300 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.1223169e-05
6,312 Type Inference for Datalog and its Application to Query Optimisation 2008 PODS 5.1158809e-05
7,248 Positive Higher-Order Queries 2010 PODS 4.7902631e-05
8,704 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4647149e-05
9,741 Containment of Conjunctive Object Meta-Queries 2006 VLDB 4.2936538e-05
12,606 The NEXT Framework for Logical XQuery Optimization 2004 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
51 Including Group-By in Query Optimization 1994 VLDB 0.00067123727
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054402763
100 Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers 1987 VLDB 0.00049624696
114 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00046339735
200 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00035012858
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
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
938 Queries Independent of Updates 1993 VLDB 0.00015197786
1,302 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012705525
1,578 Constraint Checking with Partial Information 1994 PODS 0.00011284233
1,783 Normal Forms and Conservative Properties for Query Languages over Collection Types 1993 PODS 0.00010568101
2,398 Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) 1992 PODS 8.8973978e-05
4,699 Semantic Representations and Query Languages for Or-sets 1993 PODS 5.9885891e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,598 Polynomial-time program transformations in deductive databases 1990 PODS 4.7004867e-05
10,002 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.1945683e-05
9,791 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 4.2818172e-05
7,248 Positive Higher-Order Queries 2010 PODS 4.7902631e-05
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
7,758 Containment and Equivalence of Well-Designed SPARQL 2014 PODS 4.6598957e-05
144 Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) 1982 PODS 0.00041462501
1,522 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.0001153051
4,048 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 6.4968603e-05
8,704 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4647149e-05