--%>
Assignment Help - homework help

Containee problem

For queries Q1 and Q2, we say Q1 is containedin Q2, denoted Q1 C Q2, iff Q1(D) C Q2(D) for every database D.

The container problern for a fixed Query Qo is the following decision problem:
Given a query Q, decide whether Qo C Q.

The containee probletn for a fixed guery Qo is the following decision problem:
Given a query Q, decide whether Q C Qo.

Formally prove or disprove the following statements:

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

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

(c) For every conjunctive euery Qo, there is a polynomial-time algorithm to decide the containee problem for Q0 and for grven conjunctive queries  Q.

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

   Related Questions in Mathematics

  • Q : Econ For every value of real GDP,

    For every value of real GDP, actual investment equals

    		•
  • Q : Ordinary Differential Equation or ODE

    What is an Ordinary Differential Equation (ODE)?

    		•
  • Q : Problem on mixed-strategy equilibrium

    Assume three Offices (A, B, & C) in downtown,  simultaneously decide whether to situate in a new Building. The payoff matrix is illustrated below. What is (are) the pure stratgy Nash equilibrium (or equilibria) and mixed-strtegy equilibrium of the game?

    		•
  • Q : Elementary Logic Set & Model of a

    Prove that Elementary Logic Set is a Model of a Boolean Algebra The three Boolean operations of Logic are the three logical operations of  OR ( V ), AN

    		•
  • Q : Elasticity of Demand For the demand

    For the demand function D(p)=410-0.2p(^2), find the maximum revenue.

    		•
  • Q : Explain the work and model proposed by

    Explain the work and model proposed by Richardson.

    		•
  • Q : Explain Factorisation by trial division

    Factorisation by trial division: The essential idea of factorisation by trial division is straightforward. Let n be a positive integer. We know that n is either prime or has a prime divisor less than or equal to √n. Therefore, if we divide n in

    		•
  • Q : Who developed a rigorous theory for

    Who developed a rigorous theory for Brownian motion?

    		•
  • Q : Simulation with Arena An office of

    An office of state license bureau has two types of arrivals. Individuals interested in purchasing new plates are characterized to have inter-arrival times distributed as EXPO(6.8) and service times as TRIA(808, 13.7, 15.2); all times are in minutes. Individuals who want to renew or apply for a new d

    		•
  • Q : First-order formulas over the

    Consider the unary relational symbols P and L, and the binary relational symbol On, where P(a) and I(a) encode that a is apoint and a (sraight) line in the 2-dimensional space, respectively, while On(a,b) encodes  that a is a point, b is a line, and o lies on b.

    		•