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

Find the distance between these two cities, Memphis, Tennessee, and New Orl...

Memphis, Tennessee, and New Orleans, Louisiana, lie approximately on the same meridian. Memphis has latitude 35°N and New Orleans has latitude 30°N. Find the distance between these

Statistics, How many 4 digit numbers can be formed using the numbers: 1 – 7...

How many 4 digit numbers can be formed using the numbers: 1 – 7. Repeated numbers CAN NOT be used

Laplace transform, what is the Laplace transform of e^9(-t)^a)

what is the Laplace transform of e^9(-t)^a)

Draw the graph for finite state machine, Consider the finite state machine ...

Consider the finite state machine whose state transition table is : Draw the graph for it.  Ans: The graph for the automata according to the transition table is drawn b

Need answer urgently, using a pair of compasses a ruler and a pencil. const...

using a pair of compasses a ruler and a pencil. construct a triangle CDE in which DE=10cm, DC+8cm and CDE= 45 degrees. construct CF perpendicular to DE such that F lies on DE using

Briefly explain markov chains, Question 1 An experiment succeeds twice as ...

Question 1 An experiment succeeds twice as often as it fails. Find the chance that in the next six trials there will be at least four successes Question 2 An insurance compan

Word problem, tom has 150 feet of fencing to enclose a rectangular garden. ...

tom has 150 feet of fencing to enclose a rectangular garden. if the length is to be 5 feet less than three the width, find the area of the garden

Exponential and logarithmic fuctions, How long does it take for an amount o...

How long does it take for an amount of money P to double itself if it is invested at 8% interest compounded 4 times a year?

Derivatives of trig functions, Derivatives of Trig Functions In this s...

Derivatives of Trig Functions In this section we will see derivatives of functions other than polynomials or roots of polynomials. We'll begin this process off through taking

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