1 Definition and formalization
The query containment problem is a decision problem in database theory and formal logic. Given two queries Q1 and Q2 over the same database schema, the problem asks whether for every database instance D, the set of tuples returned by Q1 on D is a subset of the set returned by Q2 on D. If this holds, Q1 is said to be contained in Q2, denoted Q1 ⊆ Q2. The problem is central to query optimization, data integration, view-based query answering, and consistency checking in knowledge bases. Containment is undecidable for full first-order logic, but decidable with varying complexity for many practical query fragments such as conjunctive queries, unions of conjunctive queries, and queries with recursion or arithmetic.
1.1 Basic notation
A query is a function that maps a database instance (a finite relational structure) to a set of tuples, typically of a fixed arity. For a given query Q, the result on database D is written Q(D). Containment is defined as: Q1 ⊆ Q2 if and only if Q1(D) ⊆ Q2(D) for every database D. The containment problem is often studied within the relational model, where queries are expressed in languages such as first-order logic, relational algebra, or Datalog.
1.2 Containment vs. equivalence
Two queries Q1 and Q2 are equivalent if Q1 ⊆ Q2 and Q2 ⊆ Q1 both hold. Equivalence is a symmetric relation, whereas containment is antisymmetric. In database theory, query equivalence is often the target of optimization (e.g., replacing a query with an equivalent but more efficient one), but containment suffices for tasks such as checking whether a materialized view can answer a query. The containment relation is a preorder on queries.
1.3 Relationship to query evaluation
Query containment is conceptually different from query evaluation: evaluation computes answers for a given database, while containment checks a property across all possible databases. However, algorithmic methods for containment often leverage the same structures used in evaluation, such as homomorphisms. Understanding containment helps in determining when two queries will always yield the same answers, which is useful for caching and view maintenance.
2 Decidability and complexity
The decidability and complexity of query containment depend heavily on the expressive power of the query language. For highly expressive languages like full first-order logic, containment is undecidable. For restricted fragments, it becomes decidable, often with a precise complexity classification.
2.1 Conjunctive queries (CQ)
Conjunctive queries are the simplest and most widely studied class. A conjunctive query is a first-order formula of the form ∃y (A1 ∧ … ∧ An), where each Ai is a relational atom. Containment for conjunctive queries is decidable and has a well-known characterization.
2.1.1 Containment mapping theorem
The fundamental result for CQ containment is the containment mapping theorem: For two conjunctive queries Q1 and Q2, Q1 ⊆ Q2 if and only if there exists a mapping (homomorphism) from the variables and constants of Q2 to those of Q1 that preserves the relational atoms and maps the distinguished variables (output variables) of Q2 to those of Q1. This theorem reduces containment to checking the existence of a certain homomorphism.
2.1.2 Complexity: NP-complete
Deciding containment for conjunctive queries is NP-complete. The NP upper bound follows from guessing a containment mapping and verifying it. The lower bound is obtained by reduction from graph homomorphism, which is NP-complete. NP-completeness holds even for fixed arity queries.
2.2 Unions of conjunctive queries (UCQ)
A union of conjunctive queries is a disjunction Q = Q1 ∪ … ∪ Qk, where each Qi is a conjunctive query. The containment problem for UCQs is more complex than for single CQs.
2.2.1 Containment via checking all pairs
For UCQs, containment Q ⊆ Q' holds if and only if for every conjunctive query in Q, there exists a conjunctive query in Q' that contains it. More precisely, Q ⊆ Q' iff for each disjunct Ci of Q, there is a disjunct C'j of Q' such that Ci ⊆ C'j. This reduces UCQ containment to a universal-existential check over the disjuncts.
2.2.2 Complexity: Π₂^P-complete
The containment problem for unions of conjunctive queries is Π₂^P-complete. The upper bound follows from the characterization: for each disjunct of Q, check existence of a containing disjunct in Q'. The lower bound is proven by reduction from quantified Boolean formulas with two alternations of quantifiers.
2.3 Queries with inequalities
Adding inequalities (e.g., <, ≤, ≠) to conjunctive queries increases expressiveness but also complicates containment.
2.3.1 CQ with <, ≤, ≠
When conjunctive queries are extended with built-in predicates for inequality, the containment mapping theorem no longer holds directly. Additional conditions must be considered, such as the order type of constants and variables. The containment mapping must also preserve the ordering constraints.
2.3.2 Decidability and complexity bounds
Containment for conjunctive queries with inequalities is decidable but with higher complexity. For queries with only ≠, the problem remains NP-complete. For queries with < or ≤, the problem is Π₂^P-complete. For more complex combinations (e.g., multiple orders), the complexity can be even higher, up to exponential time.
2.4 Recursive queries (Datalog)
Datalog is a query language based on logic programming, allowing recursion through rules. Containment for Datalog queries is highly dependent on the recursion structure.
2.4.1 Containment for linear Datalog
Linear Datalog restricts recursion so that each rule has at most one recursive atom in the body. For linear Datalog, containment is decidable and has been shown to be in exponential time (or even lower for some subclasses). The decision procedure often uses automata-theoretic techniques or tree automata.
2.4.2 Undecidability for general Datalog
For general Datalog (allowing multiple recursive atoms and arbitrary recursion), containment is undecidable. This is shown by reduction from the halting problem for Turing machines or from context-sensitive grammar membership. The undecidability arises from the ability of general Datalog to simulate computations.
2.5 Queries with arithmetic and aggregation
Many practical query languages include aggregate functions (COUNT, SUM, AVG) and arithmetic operations. Containment for such queries is often undecidable in full generality.
2.5.1 Inclusion of group-by and count
When queries involve grouping and counting, containment becomes more complex. Even for restricted cases, such as queries with GROUP BY and COUNT, the problem is undecidable. Some subclasses with limited arithmetic (e.g., linear arithmetic constraints) may be decidable.
2.5.2 Undecidable cases
In general, containment for queries with aggregation and arithmetic is undecidable. This is due to the ability to encode integer arithmetic or complex constraints. Decidable fragments exist when the arithmetic is restricted to comparisons between constants and variables, or when aggregation is used only in a limited way (e.g., no nested aggregation).
3 Algorithmic approaches
Several algorithmic techniques have been developed to solve or approximate query containment. Many leverage connections to graph theory, constraint satisfaction, and logical rewriting.
3.1 Homomorphism-based methods
Homomorphisms are the central tool for conjunctive query containment. The containment mapping theorem directly yields an algorithm: search for a homomorphism from the body of Q2 to that of Q1 respecting the distinguished variables.
3.1.1 Canonical database technique
A canonical database is constructed from the body of Q1 by treating each variable as a distinct constant (skolemization). Then Q1 ⊆ Q2 if and only if Q2 evaluated on this canonical database returns a tuple that corresponds to the distinguished variables of Q1. This technique reduces containment to query evaluation on a single database instance.
3.1.2 Reducing to graph homomorphism
Since conjunctive queries can be represented as hypergraphs or labeled graphs, containment reduces to the existence of a graph homomorphism between the query graphs. This mapping has led to the use of graph algorithms and constraint satisfaction techniques for containment checking.
3.2 Query rewriting and unfolding
In the context of views and data integration, containment can be checked by rewriting the query in terms of views and then comparing the rewritings. Unfolding a query that references views into a query over base tables is a common preprocessing step. Containment of the unfolded queries then reduces to the standard problem.
3.3 Use of constraints
Database constraints, such as functional dependencies and inclusion dependencies, can affect containment. When such constraints hold on all instances, a query may be contained in another even without a containment mapping.
3.3.1 Functional dependencies
Functional dependencies can allow containment mappings that would otherwise fail. For example, if a key constraint implies that two variables must be equal, the mapping can be adjusted accordingly. Checking containment under functional dependencies generalizes the basic problem and can be solved by adding equality reasoning.
3.3.2 Inclusion dependencies
Inclusion dependencies (e.g., foreign keys) can also enable containment. Techniques often involve augmenting the query with implied joins from the constraints. The problem may become undecidable for arbitrary inclusion dependencies but is decidable for certain classes.
3.4 SAT and CSP encodings
Containment for UCQs and some extensions can be encoded as Boolean satisfiability (SAT) or constraint satisfaction problems (CSP). This allows the use of efficient off-the-shelf solvers.
3.4.1 Conjunctive queries as constraint satisfaction problems
A conjunctive query can be viewed as a CSP instance: variables are query variables, domains are the database constants, and constraints are the relational atoms. A containment mapping from Q2 to Q1 corresponds to a solution of a certain CSP derived from Q1. Thus, containment checking is essentially a CSP problem.
3.4.2 Role of Boolean satisfiability
For UCQ containment, the universal-existential quantification over disjuncts leads to a QBF (quantified Boolean formula) of a specific structure. This can be solved using SAT-based tools for quantified Boolean formulas, though the problem remains in the polynomial hierarchy.
4 Applications
Query containment has numerous practical applications in database management and knowledge representation.
4.1 Query optimization
Containment is used to detect when one query is redundant or when a cheaper query can be substituted for a more expensive one.
4.1.1 Detecting redundant subqueries
In a query with multiple subqueries, if one subquery is contained in another, its results are always a subset. The optimizer can eliminate the subquery whose results are subsumed, reducing work.
4.1.2 Minimizing query evaluation cost
By rewriting a query into an equivalent or contained query that is cheaper to evaluate (e.g., using indices or fewer joins), performance improves. Containment checks ensure correctness of the rewrite.
4.2 Data integration
In systems that combine data from multiple sources using views, containment is crucial for answering queries using views.
4.2.1 View-based query rewriting
A query Q can be answered using a set of materialized views V if there exists a rewriting of Q in terms of V that is contained in Q (for sound rewritings) or equivalent (for exact rewritings). Containment checks are used to verify the rewriting.
4.2.2 Local-as-view (LAV) vs. global-as-view (GAV)
In LAV, the global schema is described as views over the sources, and query containment helps match user queries to source capabilities. In GAV, sources are defined as views over the global schema, and containment is used to ensure that source descriptions are sufficient for answering queries.
4.3 Ontology-based data access
In ontology-based data access (OBDA), queries are posed over an ontology (e.g., in description logic) and data is stored in relational databases. Containment must be considered under the ontology's axioms.
4.3.1 Containment under description logics
Description logics (DLs) allow reasoning about concepts and roles. Query containment under DL axioms generalizes classical containment. For many DLs (e.g., DL-Lite, EL), containment remains decidable with manageable complexity.
4.3.2 Query answering with OWL 2 profiles
OWL 2 profiles such as QL and RL are designed to enable efficient query answering using database technologies. Containment under these profiles is used to optimize SPARQL query processing over RDF data.
4.4 Database schema design and maintenance
In schema design and view maintenance, containment helps determine when changes to a view affect query answers.
4.4.1 View update independence
A view is update-independent if insertions or deletions on base tables do not affect certain query results. Containment between the view definition and the query characterizes independence.
4.4.2 Consistency of materialized views
When materialized views are maintained incrementally, containment checks ensure that the updated view still supplies the same answers for a given query. This is important for data warehouses and replication systems.
5 Extensions and open problems
Despite decades of research, many aspects of query containment remain open or require further study, especially with the advent of new data models.
5.1 Containment with order and negation
Adding order predicates and negation substantially increases expressiveness and complexity.
5.1.1 First-order queries with inequalities
For full first-order queries with inequalities, containment is undecidable. However, for the fragment of conjunctive queries with inequalities but without universal quantification, it remains decidable with various complexity bounds.
5.1.2 Complexity hierarchy
The complexity of containment for queries with different mixes of inequalities, negation, and recursion forms a rich hierarchy. Some fragments are in NP, some are Π₂^P-complete, and others are EXPTIME-complete or undecidable. Open questions remain about the precise boundaries.
5.2 Containment for graph queries
Graph databases and graph pattern matching have become important, leading to new containment problems.
5.2.1 Regular path queries
Regular path queries (RPQs) ask for pairs of nodes connected by a path whose label sequence matches a regular expression. Containment for RPQs is PSPACE-complete but decidable. For conjunctions of RPQs, the complexity rises to EXPSPACE.
5.2.2 Graph pattern matching
Graph pattern matching, often based on subgraph isomorphism or homomorphism, poses containment problems similar to conjunctive queries but with additional constraints like edge labels and node properties. The problem is NP-complete for homomorphism-based matching.
5.3 Containment in probabilistic databases
Probabilistic databases assign probabilities to tuples or to worlds. Query containment must take probabilities into account: Q1 is contained in Q2 if for every probabilistic database, the probability of any tuple being in the result of Q1 is less than or equal to its probability in Q2. This problem is more complex than the deterministic case and is still being explored.
5.4 Approximation and heuristics
For undecidable or high-complexity cases, approximate containment is studied. Heuristics based on query signatures, structural summaries, or sampling can be used to quickly detect non-containment or to estimate containment. Machine learning techniques have also been applied to predict containment without full reasoning. Developing efficient approximations that work in practice remains an open research area.