For queries Q_{1} and Q_{2}, we say Q_{1} is contained in Q_{2}, denoted Q_{1} ⊆ Q_{2}, iff Q_{1} (D) ⊆ Q_{2}(D) for every database D.
- The container problem for a fixed Query Q_{0} is the following decision problem: Given a query Q, decide whether Q_{0} ⊆ Q.
- The containee problem for a fixed query Q_{0} is the following decision problem: Given a query Q, decide whether Q ⊆ Q_{0}.
Formally prove or disprove the following statements:
(a) For every conjunctive query Q_{0}, there is a polynomial-time algorithm to decide the container problem for Q_{0} and for given conjunctive queries Q.
(b) For every conjunctive query Q_{0}, there is a polynomial-time algorithm to decide the container problem for Q_{0} and for given conjunctive queries Q that can be obtained from Q_{0} by adding some atoms.
(c) For every conjunctive query Q_{0}, there is a polynomial-time algorithm to decide the containee problem for Q_{0} and for given conjunctive queries Q.
(d) For every first-order Query Q_{0}, there is an algorithm to decide the containee problem for Q_{0} and for given first-order queries Q. To prove a statement, sketch an algorithm, along with an argument why it is polynomial, if possible. To disprove it, provide an M-hardness or undecidability proof.