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

Most crucial aspect of learning multiplication, Which of the following is t...

Which of the following is the most crucial aspect of learning multiplication? i) Multiplication facts ii) Recall of tables and their recitation iii) Understanding "how man

Find the sum of series r/(r+1)(r+2)(r+3)from 1 upto infinity, Apply the con...

Apply the concept of partial fraction and add the corresponding terms. The terms will get cut automatically leaving the first and last term

Subtangents & subnormals, show that the subtangent at any point on parabola...

show that the subtangent at any point on parabola y2 =4ax is twice the abscissa at that point.

The low temperature in Achorage, The low temperature in Anchorage, Alaska t...

The low temperature in Anchorage, Alaska today was negative four degrees. The low temperature in Los Angeles, California was sixty-three degreees. What is the difference in the two

Complex Numbers, How do you compute the phase/angle of a complex number? i....

How do you compute the phase/angle of a complex number? i.e 1+2i

GRAPH, HOW CAN WE TAKE SUPPOSE THE VALUES OF X AND Y

HOW CAN WE TAKE SUPPOSE THE VALUES OF X AND Y

Random variable, RANDOM VARIABLE A variable which assumes differ...

RANDOM VARIABLE A variable which assumes different numerical values as a result of random experiments or random occurrences is known as a random variable. The rainfal

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