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
compare 643,251;633,512; and 633,893. The answer is 633,512

Consider the equation x 2 y′′+ xy′- y = 4x ln x (a) Verify that x is a solution to the homogeneous equation. (b) Use the method of reduction of order to derive the second


Product and Quotient Rule : Firstly let's see why we have to be careful with products & quotients.  Assume that we have the two functions f ( x ) = x 3   and g ( x ) = x 6 .

How do I solve step by step 7

Michael made 19 out of 30 free-throws this basketball season. Larry's freethrow average was 0.745 and Charles' was 0.81. John made 47 out of 86 free-throws. Who is the best free-th

What is the square root of 36? To search the square root (√) you ask yourself, "What number multiplied through itself gives me 36?" 6 .6 = 36; thus, 6 is the square root of 36.

Sharon purchased six adult movie tickets. She spent $43.50 on the tickets. How much was each ticket? To ?nd out the price of each individual ticket, you should divide the total

give me some examples on continuity

The equation -2x^2-kx-2=0 has two different real soultions. find the set of possible values for k.