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

how do you solve quadratic equations by factoring?

Find models of energy production and energy usage from 2 different countries, each on a different continent, which predict future energy production and demands. How was data collec

How to raise Powers of Monomials ? To raise a monomial to a certain power: Step 1: Place the entire monomial inside parentheses, and place the desired power outside the paren

THE MULTIPLICATION ALGORITHM :  Some Class 3 children in a nearby school had been taught the standard multiplication. Algorithm, and had even done reasonably well in the tests bas

Algebraic Word Problems: Equations: 1. The total electrical output of one nuclear facility is 200 megawatts more than that of another nuclear facility. Let L be the

In a 2500 word report do the market analysis of China. Under this you have to explain: - What are the advantages and disadvantages for foreign company to set up its business cent

Problem 1 Work through TALPAC 10 Basics (refer to attached handout). Answer the set of questions at the end of tutorial module. Problem 2 Referring to both the haul cyc

Inverse Cosine : Now see at inverse cosine.  Following is the definition for the inverse cosine.                         y = cos -1 x       ⇔ cos y = x                   for

Describe Common Phrases to Represent Math Operations? The table below shows the common phrases used in word problems to represent addition, subtraction, multiplication, and div