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

Rolle''s theorem, The curve (y+1) 2 =x 2 passes by the points (1, 0) and ...

The curve (y+1) 2 =x 2 passes by the points (1, 0) and (- 1, 0). Does Rolle's Theorem clarify the conclusion that  dy dx  vanishes for some value of x in the interval -1≤x≤1?

Define regression, Define regression. The main reason of curve fitting ...

Define regression. The main reason of curve fitting is to estimate one of the variables (the dependent variable) from the other (the independent variable). The procedure of est

Division Remainders, what is the remainder when 75 is divided by 4

what is the remainder when 75 is divided by 4

Calculate the amplitude of trigonometry function, Consider the trigonometri...

Consider the trigonometric function f(t) = -3 + 4 cos(Π/ 3 (t - 3/2 )). (a) What is the amplitude of f (t)? (b) What is the period of f(t)? (c) What are the maximum and mi

..Job, Eddie mkes $15.75 per hour. Estimate how much Eddie will make per ye...

Eddie mkes $15.75 per hour. Estimate how much Eddie will make per year if he works 40 hours per week and 50 weeks per year.

Analalitic geometry, 1. Write down the canonical equations of the line pass...

1. Write down the canonical equations of the line passing through the point A(2,3, 4) and being parallel to the vector q ={5,0,-1}.

Concepts, what are core concepts of marketing?

what are core concepts of marketing?

One tailed test, One Tailed Test It is a test where the alternative hy...

One Tailed Test It is a test where the alternative hypothesis (H 1 :) is only concerned along with one of the tails of the distribution for illustration, to test a business co

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