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

Numerical.analysis. , Please, I want to know and study "stability 0n predic...

Please, I want to know and study "stability 0n predictor -corrector method .My gmail is [email protected] heap and kind to me .Thanks for this.

Statistics Assignment, I need help in assignment of stats? Please give me a...

I need help in assignment of stats? Please give me assist in my stats exam.

Rectilinear figures, what are rctilinear figures ? types of rectilinear fig...

what are rctilinear figures ? types of rectilinear figures and their propertiees.

Bricklayer estimates 6.5 how many bricks will he required, A bricklayer est...

A bricklayer estimates that he requires 6.5 bricks per square foot. He needs to lay a patio that will be 110 square feet. How many bricks will he required? Multiply 6.5 by 110;

Complex number, a ,b,c are complex numbers such that a/1-b=b/1-c=c-1-a=k.fi...

a ,b,c are complex numbers such that a/1-b=b/1-c=c-1-a=k.find the value of k

Determine how much more time it will take to reach the base, A man on a top...

A man on a top of a tower observes a truck at an angle of depression α where tanα = 1/√5 and sees that it is moving  towards the base of the tower. Ten minutes later, the angle of

Angles, why is a complimentary angle 90 degres

why is a complimentary angle 90 degres

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