--%>
Assignment Help - homework help

Containee problem

For queries Q1 and Q2, we say Q1 is containedin Q2, denoted Q1 C Q2, iff Q1(D) C Q2(D) for every database D.

The container problern for a fixed Query Qo is the following decision problem:
Given a query Q, decide whether Qo C Q.

The containee probletn for a fixed guery Qo is the following decision problem:
Given a query Q, decide whether Q C Qo.

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 Qo by adding some atoms.

(c) For every conjunctive euery Qo, there is a polynomial-time algorithm to decide the containee problem for Q0 and for grven conjunctive queries  Q.

(d) For every flrst-order Query Q0, there is an algorithm to decide the containee problem for Qo 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 Questions in Mathematics

  • Q : Bolzano-Weierstrass property The

    The Bolzano-Weierstrass property does not hold in C[0, ¶] for the infinite set A ={sinnx:n<N} : A is infinite; Show that has no “ limit points”.

    		•
  • Q : How do it? integral e^(-t)*e^(tz) t

    integral e^(-t)*e^(tz) t between 0 and infinity for Re(z)<1

    		•
  • Q : Problem on augmented matrix Consider

    Consider the following system of linear equations.  (a) Write out t

    		•
  • Q : Define terms Terms : Terms are defined

    Terms: Terms are defined inductively by the following clauses.               (i) Every individual variable and every individual constant is a term. (Such a term is called atom

    		•
  • Q : Define Big-O notation Big-O notation :

    Big-O notation: If f(n) and g(n) are functions of a natural number n, we write f(n) is O(g(n)) and we say f is big-O of g if there is a constant C (independent of n) such that f

    		•
  • Q : Problem on mixed-strategy equilibrium

    Assume three Offices (A, B, & C) in downtown,  simultaneously decide whether to situate in a new Building. The payoff matrix is illustrated below. What is (are) the pure stratgy Nash equilibrium (or equilibria) and mixed-strtegy equilibrium of the game?

    		•
  • Q : Properties of a group How can we say

    How can we say that the pair (G, o) is a group. Explain the properties which proof it.

    		•
  • Q : Set Theory & Model of a Boolean Algebra

    II. Prove that Set Theory is a Model of a Boolean Algebra The three Boolean operations of Set Theory are the three set operations of union (U), intersection (upside down U), and complement ~.  Addition is set

    		•
  • Q : Explain lognormal stochastic

    Explain lognormal stochastic differential equation for evolution of an asset.

    		•
  • Q : Problem on Datalog for defining

    The focus is on  the use of Datalog for defining properties  and queries on graphs. (a) Assume that P is some property of graphs  definable in the Datalog. Show that P is preserved beneath extensions  and homomo

    		•