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
Computer monitors are calculated by their diagonals. If a monitor is advertised to be 19 in, Determine the actual viewing area, considerthe screen is square? (Round to the nearest

find the newton raphson iterative formula for a reciprocal of a number N and hence find the value of 1/23

convert 5000ml to liters

Explain this statement " As we begin the 21st century, the dilemmas of America's minority groups remain perhaps the primary unresolved domestic issue facing the nation." How might

Example for Comparison Test for Improper Integrals Example:  Find out if the following integral is convergent or divergent. ∫ ∞ 2 (cos 2 x) / x 2 (dx) Solution


Interval of Convergence After that secondly, the interval of all x's, involving the endpoints if need be, for which the power series converges is termed as the interval of conv

how do you slove 4u-5=2u-13

Every point (x,y) on the curve y=log2 3x is transferred to a new point by the following translation (x',y')=(x+m,y+n), where m and n are integers. The set of (x',y') form the curve

First, larger the number (ignoring any minus signs) the steeper the line.  Thus, we can use the slope to tell us something regarding just how steep a line is. Next, if the slope