Polynomial time algorithm - first order query, Mathematics

For queries Q1 and Q2, we say Q1 is contained in Q2, denoted Q1 ⊆ Q2, iff Q1 (D) ⊆ Q2(D) for every database D.

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

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 Q0 by adding some atoms.

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

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

Posted Date: 3/1/2013 12:16:09 AM | Location : United States







Related Discussions:- Polynomial time algorithm - first order query, Assignment Help, Ask Question on Polynomial time algorithm - first order query, Get Answer, Expert's Help, Polynomial time algorithm - first order query Discussions

Write discussion on Polynomial time algorithm - first order query
Your posts are moderated
Related Questions
This time we are going to take a look at an application of second order differential equations. It's now time take a look at mechanical vibrations. In exactly we are going to look

use the distributive law to write each multiplication in a different way. the find the answer. 12x14 16x13 14x18 9x108 12x136 20x147

I have about 6 Statistics questions, can anyone help me?

limit x-a/|x-a| equals x-a [a]a [b]0 [c]-a [d]none 0f these

Submit your working in (neat) handwritten form (do not type up your solutions). For the plots that you generate in Maple or Matlab, you can print them out and attach them at the en


The following table contains some information about the model used. Assume the probabilities given by the model are those of being a good writer. Variable

Tchebyshev Distance (Maximum Travel Distance per Trip Using Rectilinear Distance): It can be calculated by using following formula: d(X, Pi) = max{|x - ai|, |y - bi|} (Source

why we use decision making using minimization of regret method in uncertainty?

1. The lifetime T (in days) of an electrical component has reliability function given by: R(t) = e -0.01t for time t > 0. An electrical system consists of four such components. Th