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

Simple equations, three times the first of the three consecutive odd intege...

three times the first of the three consecutive odd integers is 3 more than twice the third integer. find the third integer.

GCF, Find the GCF of 70 and 112

Find the GCF of 70 and 112

Volumes of solids of revolution -method of cylinders, Volumes of Solids of ...

Volumes of Solids of Revolution / Method of Cylinders In the previous section we started looking at determine volumes of solids of revolution.  In this section we took cross se

Compositions of relations, Let Consider R A Χ B, S B Χ C be two relation...

Let Consider R A Χ B, S B Χ C be two relations. Then compositions of the relations S and R given by SoR A Χ C and is explained by (a, c) €(S o R) iff € b € B like (a, b) € R,

Shares and dividends, I need to make an assignment on this topic what shoul...

I need to make an assignment on this topic what should i write in it

Find the slope of this line, The following graph shows the growth of the me...

The following graph shows the growth of the median home value in a particular region of the United States starting in 1996.  The graphs starts in 1996 and shows the trend through t

Determine the measure of the smallest angle, The calculation of two complem...

The calculation of two complementary angles are in the ratio of 7:8. Determine the measure of the smallest angle. a. 84° b. 42° c. 48° d. 96° b. Two angles are compl

Developing an understanidng of multiplication, DEVELOPING AN UNDERSTANIDNG ...

DEVELOPING AN UNDERSTANIDNG OF MULTIPLICATION :  The most important aspect of knowing multiplication is to understand what it means and where it is applied. It needs to be first i

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