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

Interpretations of the derivative , Interpretations of the Derivative : ...

Interpretations of the Derivative : Before moving on to the section where we study how to calculate derivatives by ignoring the limits we were evaluating in the earlier secti

Find the generating function, Find the generating function for the number o...

Find the generating function for the number of r-combinations of {3.a, 5.b, 2.c}          Ans:  Terms sequence is given as r-combinations of {3.a, 5.b, 2.c}. This can be writte

Angles, why is a complimentary angle 90 degres

why is a complimentary angle 90 degres

Describe three ways to write negative fractions, Describe Three Ways to Wri...

Describe Three Ways to Write Negative Fractions? There are three different ways that a negative fraction can be written. They are all represent the same value. 1. The negative

Example of repeated eigenvalues, Illustration : Solve the following IVP. ...

Illustration : Solve the following IVP. Solution: First get the eigenvalues for the system. = l 2 - 10 l+ 25 = (l- 5) 2 l 1,2 = 5 Therefore, we got a

Design an automaton that accepts only even numbers, Design an automaton tha...

Design an automaton that accepts just only even numbers of 0s and even number of 1's. Ans: The needed automata that accepts even number of 0's and even number of 1's is specifi

Lesson 6 Homework Practice, For every girl taking classes at the martial ar...

For every girl taking classes at the martial arts school there are 3 boys who are taking classes at the school. If there are 236 students taking classes write and solve a proportio

Complex fractions, A small airplane used 5and2over3 gallons of fuel to fly ...

A small airplane used 5and2over3 gallons of fuel to fly a 2 hour trip.how many gallons were used each hour

Calculus, f(x)= 2e^5x+6 find the domain of f and find x-intercept.

f(x)= 2e^5x+6 find the domain of f and find x-intercept.

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