--%>
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 : Explain Factorisation by trial division

    Factorisation by trial division: The essential idea of factorisation by trial division is straightforward. Let n be a positive integer. We know that n is either prime or has a prime divisor less than or equal to √n. Therefore, if we divide n in

    		•
  • Q : Properties for polynomial Specify the

    Specify the important properties for the polynomial.

    		•
  • 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 : Numerical solution of PDE this

    this assignment contains two parts theoretical and coding the code has to be a new. old code and modified code will appear in the university website .

    		•
  • Q : Problem on augmented matrix Consider

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

    		•
  • Q : Profit-loss based problems A leather

    A leather wholesaler supplies leather to shoe companies. The manufacturing quantity requirements of leather differ depending upon the amount of leather ordered by the shoe companies to him. Due to the volatility in orders, he is unable to precisely predict what will b

    		•
  • Q : Relationships Between Data Introduction

    Relationships Between Data - Introduction to Linear Regression Simple Regression Notes If you need guidance in terms of using Excel to run regressions, check pages 1 - 10 of the Excel - Linear Regression Tutorial posted to th

    		•
  • Q : Probability and Stochastic assignment

    Introduction to Probability and Stochastic Assignment 1: 1. Consider an experiment in which one of three boxes containing microchips is chosen at random and a microchip is randomly selected from the box.

    		•
  • Q : Maths A cricketer cn throw a ball to a

    A cricketer cn throw a ball to a max horizontl distnce of 100m. If he throws d same ball vertically upwards then the max height upto which he can throw is????

    		•
  • Q : Explain Black–Scholes model Explain

    Explain Black–Scholes model.

    		•