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

Coordinate geometry, find the points on y axis whose distances from the poi...

find the points on y axis whose distances from the points A(6,7) and B(4,-3) are in the ratio 1:2

Basic indefinite integrals- computing indefinite integrals, Basic indefinit...

Basic indefinite integrals The first integral which we'll look at is the integral of a power of x.                                ∫x n dx = (x n +1 / n + 1)+ c,          n

Parabola, please i need the answers to x^_7x+10 i want the vertex,axis of s...

please i need the answers to x^_7x+10 i want the vertex,axis of semetery,y intersect and the x intercept

Fractions, Mr. And Mrs. samuel visited Florida and purchased 120 oranges. ...

Mr. And Mrs. samuel visited Florida and purchased 120 oranges. They gave 1/4 of them to relatives, ate 1/12 of them in the hotel, and gave 1/3 of them to friends. The shipped the

+, what is 2+2=

what is 2+2=

NUMERABILITY, AFIGURE THIS OUT(3) (14) (17) (20) (25)= 8 WHAT ARE THE PROC...

AFIGURE THIS OUT(3) (14) (17) (20) (25)= 8 WHAT ARE THE PROCEDURES (-)(+)(x)(div) BETWEEN EACH NUMBER TO COME UP WITH 8 ?

Average function value, Average Function Value The average value of a ...

Average Function Value The average value of a function f(x) over the interval [a,b] is specified by, f avg = (1/b-a) a ∫ b f(x) dx Proof We know that the average

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