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

MATLAB, Program of "surface of revolution" in MATLAB

Program of "surface of revolution" in MATLAB

Integration, Integrate ((cosx)*(sinx))/(sin(2x)) with respect to x

Integrate ((cosx)*(sinx))/(sin(2x)) with respect to x

Percents, If 2/3 of a number is 24 then 1/4 of a number is...

If 2/3 of a number is 24 then 1/4 of a number is...

Which of the following sets are equal, Which of the following sets are equa...

Which of the following sets are equal? S 1 = {1, 2, 2, 3}, S 2 = {x | x 2 - 2x + 1 = 0}, S 3 = {1, 2, 3}, S 4 = {x | x 3 - 6x

Identify the surface for the equation , Identify the surface for each of th...

Identify the surface for each of the subsequent equations. (a) r = 5 (b) r 2 + z 2 = 100 (c) z = r Solution (a)  In two dimensions we are familiar with that this

Each child is unique in learning development, Each Child Is Unique :  Alth...

Each Child Is Unique :  Although every child goes through similar stages of development, the process may vary from one set of children to another, and also from one child to anoth

Profit maximization, a medical clinic performs three types of medical tests...

a medical clinic performs three types of medical tests that use the same machines. Tests A, B,and C take 15 minutes, 30 minutes and 1 hours respectively, with respective profits of

Arden''s Theorem, Find the Regular Grammar for the following Regular Expres...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

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