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

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

Algebra 1, Im having trouble with this word problem: The three Math Idol j...

Im having trouble with this word problem: The three Math Idol judges have been eliminating contestants all day! The number of one-step equations and two-step equations who have be

Slope-intercept form, Slope-intercept form The ultimate special form of...

Slope-intercept form The ultimate special form of the equation of the line is possibly the one that most people are familiar with.  It is the slope-intercept form.  In this if

Define euler circuit and euler path, Define Euler Circuit and Euler Path.  ...

Define Euler Circuit and Euler Path.  Which of the following graphs have an Euler circuit and Euler path.

How long will the board be after he makes the cut, Tom is cutting a piece o...

Tom is cutting a piece of wood to form a shelf. He cut the wood to 3.5 feet, but it is too long to fit in the bookshelf he is forming. He decides to cut 0.25 feet off the board. Ho

Pendulum swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom

Pert, define algorithm of pert and pert with suitable examples

define algorithm of pert and pert with suitable examples

If 967.234 is divided by 10 how will the decimal point move, If 967.234 is ...

If 967.234 is divided by 10, how will the decimal point move? It will move one place to the left. While dividing by multiples of 10, the decimal point is moved to the left acco

the bug should start to move in order to increase, The temperature at the ...

The temperature at the point (x, y) on a metal plate is given by the function f(x, y) = x 3 + 4xy + y 2 where f is in degrees Fahrenheit and x and y are in inches, with the origin

Adding fractions, please give the answer 1/9+1/3 with working out

please give the answer 1/9+1/3 with working out

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