Polynomial time algorithm - first order query, Mathematics

Assignment Help:

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.


Related Discussions:- Polynomial time algorithm - first order query

Pythagorean theorem, when one side of a triangle is 15cm and the bottom of ...

when one side of a triangle is 15cm and the bottom of the triangle is 12cm what would x be rounded to the nearest tenth?

What is permutations explain with examples, What is Permutations explain wi...

What is Permutations explain with examples? Each arrangement of a set of elements is called a permutation. In other words, every possible way (order) of writing a group of lett

Application of statistics-economic order quantities (eoq), economic order q...

economic order quantities (EOQ) Statistics may be utilized in ordering or making economic order quantities as EOQ. It is significant for a business manager to understand that

Fractions, how to divide fractions?

how to divide fractions?

Shares and dividend, a man in rested rupee 800 is buying rupee 5 shares and...

a man in rested rupee 800 is buying rupee 5 shares and then are selling at premium of rupee 1.15. He sells all the shares.find profit

Using euclid''s algorithm find the value of x & y, If d is the HCF of 30, 7...

If d is the HCF of 30, 72, find the value of x & y satisfying d = 30x + 72y. (Ans:5, -2 (Not unique) Ans:    Using Euclid's algorithm, the HCF (30, 72) 72 = 30 × 2 + 12

Find the ratio of line segment, Find the ratio in which the line segment jo...

Find the ratio in which the line segment joining A(6,5) and B(4,-3) is divided by the line y=2           (Ans:3:5) Ans :   Let the ratio be k:1 x = 4 k + 6/ k +1 y

Sketch a graph of the microphone signal, Figure shows noise results for a p...

Figure shows noise results for a prototype van measured on a rolling road. The vehicle had a four-cylinder-in-line engine. The engine speed was varied in 3rd gear from just above

Homogeneous system , Provided a homogeneous system of equations (2), we wil...

Provided a homogeneous system of equations (2), we will have one of the two probabilities for the number of solutions. 1.   Accurately one solution, the trivial solution 2.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd