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

Use the power function to find derivative, Given, y = f(x) = 2 x 3 - 3x 2 ...

Given, y = f(x) = 2 x 3 - 3x 2 + 4x +5 a)  Use the Power function to find derivative of the function. b)  Find the value of the derivative at x = 4.

Prove that the poset has a unique least element, Prove that the Poset has a...

Prove that the Poset has a unique least element Prove that if (A, ) has a least element, then (A,≤)  has a unique least element. Ans: Let (A, ≤) be a poset. Suppose the po

Complex analysis test, Can anyone help with my exam. I have 8 questions to ...

Can anyone help with my exam. I have 8 questions to do which is due on 02-14-13

In an election contested between a and b determine vote, In an election con...

In an election contested between A and B, A obtained votes equal to twice the no. of persons on the electoral roll who did not cast their votes & this later number was equal to twi

find the vector projection - vectors, Given the vectors u = 3 i - 2 j ...

Given the vectors u = 3 i - 2 j + k ,   v = i + 2 j - 4 k ,    w = -2 i + 4 j - 5 k use vector methods to answer the following: (a) Prove u , v and w can form

Perimeter of trinagle, what is the perimeter of a triangele with the sides ...

what is the perimeter of a triangele with the sides of 32 in /22 in/20 in/

Give the introduction to scientific notation, Give the Introduction to Scie...

Give the Introduction to Scientific Notation? In mathematics, it can be very difficult and time-consuming to do calculations involving very large and very small numbers. This i

Definition of the definite integral , Using the definition of the definite ...

Using the definition of the definite integral calculate the following.                                                             ∫ 0 2  x 2   + 1dx Solution Firstly,

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