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

Laws of set algebra, Laws of Set Algebra From the given Venn diagram w...

Laws of Set Algebra From the given Venn diagram where T is the universal set and A its subset that we can deduce a number of laws as: i. A υ Ø = A ii. A υ T = T

The null hypothesis, The null hypothesis It is the hypothesis being tes...

The null hypothesis It is the hypothesis being tested, the belief of a specific characteristic for illustration, US Bureau of Standards may walk to a sugar making company along

Matrix, how to solve for x

how to solve for x

More volume problems, More Volume Problems : Under this section we are de...

More Volume Problems : Under this section we are decide to take a look at several more volume problems. Though, the problems we see now will not be solids of revolution while we

Show that cos12+cos60+cos84=cos24+cos48 , L.H.S. =cos 12+cos 60+cos 84 =c...

L.H.S. =cos 12+cos 60+cos 84 =cos 12+(cos 84+cos 60) =cos 12+2.cos 72 . cos 12 =(1+2sin 18)cos 12 =(1+2.(√5 -1)/4)cos 12 =(1+.(√5 -1)/2)cos 12 =(√5 +1)/2.cos 12   R.H.S =c

Unconditional and conditional probability, Two events A and B are ind...

Two events A and B are independent events if the occurrence of event A is in no way related to the occurrence or non-occurrence of event B. Likewise for independent

Rounding, what is the nearest ten thousand of 92,892?

what is the nearest ten thousand of 92,892?

4.4238/[1.047+{1.111*[9.261/7.777]}*1.01, Ask question #Min 4.4238/[1.047+{...

Ask question #Min 4.4238/[1.047+{1.111*[9.261/7.777]}*1.01

Geometry, Awhat is polygonesk question #Minimum 100 words accepted#

Awhat is polygonesk question #Minimum 100 words accepted#

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