--%>
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 : Bolzano-Weierstrass property The

    The Bolzano-Weierstrass property does not hold in C[0, ¶] for the infinite set A ={sinnx:n<N} : A is infinite; Show that has no “ limit points”.

    		•
  • Q : Problem on Maple (a) Solve the

    (a) Solve the following  by: (i) First reducing the system of first order differentiat equations to a second order differential equation. (ii) Decoupling the following linear system of equa

    		•
  • Q : Profit-loss based problems A leather

    A leather wholesaler supplies leather to shoe companies. The manufacturing quantity requirements of leather differ depending upon the amount of leather ordered by the shoe companies to him. Due to the volatility in orders, he is unable to precisely predict what will b

    		•
  • Q : Logic and math The homework is attached

    The homework is attached in the first two files, it's is related to Sider's book, which is "Logic for philosophy" I attached this book too, it's the third file.

    		•
  • Q : Numerical solution of PDE this

    this assignment contains two parts theoretical and coding the code has to be a new. old code and modified code will appear in the university website .

    		•
  • Q : Formulating linear program of a

    A software company has a new product specifically designed for the lumber industry. The VP of marketing has been given a budget of $1,35,00to market the product over the quarter. She has decided that $35,000 of the budget will be spent promoting the product at the nat

    		•
  • Q : Who independently developed

    Who independently developed a model for simply pricing risky assets?

    		•
  • Q : What is the definition of a group Group

    Group: Let G be a set. When we say that o is a binary operation on G, we mean that o is a function from GxG into G. Informally, o takes pairs of elements of G as input and produces single elements of G as output. Examples are the operations + and x of

    		•
  • Q : Problem on Linear equations Anny, Betti

    Anny, Betti and Karol went to their local produce store to bpought some fruit. Anny bought 1 pound of apples and 2 pounds of bananas and paid $2.11.  Betti bought 2 pounds of apples and 1 pound of grapes and paid $4.06.  Karol bought 1 pound of bananas and 2

    		•
  • Q : Nonlinear integer programming problem

    Explain Nonlinear integer programming problem with an example ?

    		•