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

Hierarchical multiple regression, A group of children who lived near a lead...

A group of children who lived near a lead smelter in El Paso, Texas, were identified and their blood levels of lead were measured. An exposed group of 46 children were identified w

Assignment, how do mathematical ideas grow?

how do mathematical ideas grow?

What is the area covered through the motion of the fan, The arm of a ceilin...

The arm of a ceiling fan measures a length of 25 in. What is the area covered through the motion of the fan blades while turned on? (π = 3.14) The ceiling fan follows a circula

Find third order partial derivatives, Question: Find all third order pa...

Question: Find all third order partial derivatives for the function   F(x,y)= log xy+ e (x+y) -x/y.

Chanllenge, apzza driver delivered 27 pizzas in one night he delivered more...

apzza driver delivered 27 pizzas in one night he delivered more then one pizza to only one house . every other hhouse he only delivered pizza to 18 houses . how many pizzas did he

Quan. literacyprofiency, 3.20 euros per kilogram, 1 kilogram =2.2 pounds an...

3.20 euros per kilogram, 1 kilogram =2.2 pounds and current exchange rate is $1=0.9 euros. what is the price per pound?

Differential equation, Cos(x+y)+sin(x+y)=dy/dx(solve this differential equa...

Cos(x+y)+sin(x+y)=dy/dx(solve this differential equation)

Explain equation, Equation s(in Tth second)=u+at-a/2 seems to be dimensiona...

Equation s(in Tth second)=u+at-a/2 seems to be dimensionally incorrect.why?

the comic book, a) The first comic book is of shakitman was sold in 1938. ...

a) The first comic book is of shakitman was sold in 1938. In 2010, the estimated price for this comic book in good condition was about $500,000. This represented a return of 25 per

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