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

Differential equations, verify liouville''s theorem for y''''''-y''''-y''+...

verify liouville''s theorem for y''''''-y''''-y''+y=0

Application of linear function, four times an unknown number is equal to tw...

four times an unknown number is equal to twice the sum of five and that unknown number

Upper limit of normal , Frequently, tests that yield abnormal results are r...

Frequently, tests that yield abnormal results are repeated for confirmation.  What is the probability that for a usual person a test will be at least 1.5 times as high as the upper

Definition of logarithms, Q. Definition of Logarithms? Ans. A loga...

Q. Definition of Logarithms? Ans. A logarithm to the base a of a number x is the power to which a is raised to get x. In equation format: If x = a y , then log a  x

Determine the eigenvalues and eigenvectors of the matrix, Determine the eig...

Determine the eigenvalues and eigenvectors of the subsequent matrix. Solution : The first thing that we require to do is determine the eigen-values. It means we require

Phase plane, Before proceeding along with in fact solving systems of differ...

Before proceeding along with in fact solving systems of differential equations there's one topic which we require to take a look at. It is a topic that's not at all times taught in

How many feet is the new length if the new area is 141, A rectangular garde...

A rectangular garden has a width of 20 feet and a length of 24 feet. If each side of the garden is increased through the similar amount, how many feet is the new length if the new

Plot your data on a scatter plot, Devise data that link a certain relations...

Devise data that link a certain relationship OF YOUR CHOOSING between two variables. Write a rationale stating why you chose this particular data and what you are planning to STAT

Classify quadrilaterals, which quadrilaterals have only 1 pair of parallel ...

which quadrilaterals have only 1 pair of parallel sides

How do children learn maths?, HOW DO CHILDREN LEARN? : Have you ever tried...

HOW DO CHILDREN LEARN? : Have you ever tried teaching a young child what "ball" means? Did you do it by a lot of verbal description" Or did you let the child actually handle a 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