for queries q1 and q2 we say q1 is contained in

Question

For queries Q₁ and Q₂, we say Q₁ is contained in Q₂, denoted Q₁ ⊆ Q₂, iff Q₁ (D) ⊆ Q₂(D) for every database D.

• The container problem for a fixed Query Q₀ is the following decision problem: Given a query Q, decide whether Q₀ ⊆ Q.
• The containee problem for a fixed query Q₀ is the following decision problem: Given a query Q, decide whether Q ⊆ Q₀.

Formally prove or disprove the following statements:

(a) For every conjunctive query Q₀, there is a polynomial-time algorithm to decide the container problem for Q₀ and for given conjunctive queries Q.

(b) For every conjunctive query Q₀, there is a polynomial-time algorithm to decide the container problem for Q₀ and for given conjunctive queries Q that can be obtained from Q₀ by adding some atoms.

(c) For every conjunctive query Q₀, there is a polynomial-time algorithm to decide the containee problem for Q₀ and for given conjunctive queries Q.

(d) For every first-order Query Q₀, there is an algorithm to decide the containee problem for Q₀ 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.