Abstract: We address the problem of query containment and query equivalence for complex objects. We show that for a certain conjunctive query language for complex objects, query containment and weak query equivalence are decidable. Our results have two consequences. First, when the answers of the two queries are guaranteed not to contain empty sets, then weak equivalence coincides with equivalence, and our result answers partially an open problem about the equivalence of $\nest, \unnest$ queries for complex objects. Second, we show that checking the equivalence of conjunctive queries with grouping and aggregates is NP-complete.

Our results rely on a translation of the containment and equivalence conditions for complex objects into novel conditions on conjunctive queries, which we call simulation and strong simulation respectively. These conditions are more complex than containment of conjunctive queries, because they involve arbitrary numbers of quantifier alternations. We show that checking simulation and strong simulation for conjunctive queries is NP-complete.