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

Basic requirement for interpolation & extrapolation to work, What is the ba...

What is the basic requirement for both interpolation and extrapolation to work?  There must exist a functional relationship between an independent variable and a dependent variable

Prove that sec2+cosec2 can never be less than 2, Prove that sec 2 θ+cosec 2...

Prove that sec 2 θ+cosec 2 θ can never be less than 2. Ans:    S.T Sec 2 θ + Cosec 2 θ can never be less than 2. If possible let it be less than 2. 1 + Tan 2 θ + 1 + Cot

Pie chart, i have this data 48 degree, 72 degree, 43.2degree, 24degree , 40...

i have this data 48 degree, 72 degree, 43.2degree, 24degree , 40.8degree on this make a pie chart

Operations research, Explain Analytical Models in Operations Research with ...

Explain Analytical Models in Operations Research with Application

Determine the angle of depression to a ship, From the top of a 200 m lighth...

From the top of a 200 m lighthouse, the angle of depression to a ship in the ocean is 23 . How far is the ship form the base of the lighthouse?

Logarithmic differentiation, Logarithmic Differentiation : There is one...

Logarithmic Differentiation : There is one final topic to discuss in this section. Taking derivatives of some complicated functions can be simplified by using logarithms.  It i

PROBLEM SOLVING, The perimeter of a rectangular swimming pool is 60m. The l...

The perimeter of a rectangular swimming pool is 60m. The length of the pool is 4 m more than the width. What is the width of the pool?

Word problem in algebra, robin runs 5 kilometers around the campus in the s...

robin runs 5 kilometers around the campus in the same length of time as he can walk 3 kilometers from his house to school. If he runs 4 kilometers per hour faster than he walks, ho

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