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

Limits, Limits The concept of a limit is fundamental in calculus....

Limits The concept of a limit is fundamental in calculus. Often, we are interested to know the behavior of f(x) as the independent variable x approaches some

Differential Equations, 1.Verify Liouville''s formula for y "-y" - y'' + y ...

1.Verify Liouville''s formula for y "-y" - y'' + y = 0 in (0, 1) ? 2.Find the normalized differential equation which has {x, xex} as its fundamental set. 3.6Find the general soluti

Euler equations, Euler Equations - Series Solutions to Differential Equ...

Euler Equations - Series Solutions to Differential Equations In this section we require to look for solutions to, ax 2 y′′ + bxy′ + cy = 0 around x0  = 0. These ki

Types of series - telescoping series, Telescoping Series  It's now tim...

Telescoping Series  It's now time to look at the telescoping series.  In this section we are going to look at a series that is termed a telescoping series.  The name in this c

Please help me solve these Problems step by step, What angle (to the neares...

What angle (to the nearest degree) corresponds to the cos 0.6 or what is cos-1(0.6)? (Note: Use Appendix I) What angle (to the nearest degree) corresponds to the sin 0.6 or what

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