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
Human resource management Statistics may be utilized in efficient employ of human resources for example we may provide questionnaires to workers to find out where the manageme

do you have 3 digit and 4 digit number problem

find the number of ways 17 employees can b chosen from 327

Calculate Moving Average The table given below represents company sales; calculate 3 and 6 monthly moving averages, for data Months Sales


A building is in the form of a cylinder surrounded by a hemispherical vaulted dome and contains   41(19/21-) cu m of air. If the internal diameter of the building is equal to its t

How long does it take for an amount of money P to double itself if it is invested at 8% interest compounded 4 times a year?

Q1: Find three positive numbers whose sum is 54 and whose product is as large as possible.


Standardizing a Random Variable       If X is a random variable with E(X) = m and V(X) = s 2 , then Y = (X – m)/ s is a random variable with mean 0 and standard deviatio