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

Convergence, Assume that (xn) is a sequence of real numbers and that a, b €...

Assume that (xn) is a sequence of real numbers and that a, b € R with a is not eaqual to 0. (a) If (x n ) converges to x, show that (|ax n + b|) converges to |ax + b|. (b) Give

Solving equations, darien agrees to sponsor her sister $8 plus $1 for every...

darien agrees to sponsor her sister $8 plus $1 for every mile she walks.Write an expression to show her total money

Example for comparison test for improper integrals, Example for Comparison ...

Example for Comparison Test for Improper Integrals Example:  Find out if the following integral is convergent or divergent. ∫ ∞ 2 (cos 2 x) / x 2 (dx) Solution

Arithmetic progression, the radii of circular base of right circular cylind...

the radii of circular base of right circular cylinder and cone are in the ratio of 3:4 and their height are in the ratio of the 2:3 what is the ratio of their volume?

Integration, what is integration and how is it important

what is integration and how is it important

Mount everest is 29, Mount Everest is 29,028 ft high. Mount Kilimanjaro is ...

Mount Everest is 29,028 ft high. Mount Kilimanjaro is 19,340 ft high. How much taller is Mount Everest? Subtract Mt. Kilimanjaro's height from Mt. Everest's height; 29,028 - 19

Simulation and Modeling, I have some sample simulation and modeling practic...

I have some sample simulation and modeling practice questions using isee Stella software.

Evaluate performance of mental arithmetic maths, E 1) Try the two activitie...

E 1) Try the two activities detailed above with a few children around you Evaluate whether they really helped to improve the children's performance of mental arithmetic. Anot

Percents, write as a percent 6/10

write as a percent 6/10

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