--%>
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 : Numerical solution of PDE i want you to

    i want you to solve this assignment. this consist of two parts theoretical and coding. the code has to be created by you. no modified or copying code. you have to mention the exact solution and the proportion error. also you have to explain the sketch that you get from the code. these information

    		•
  • Q : Problem on augmented matrix Consider

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

    		•
  • 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 : Mathematical Method for Engineers The

     The function is clearly undefined at , but despite all of this the function does have a limit as approaches 0. a) Use MATLAB and ezplot to sketch for , and use the zoom on facility to guess the . You need to include you M-file, outp

    		•
  • 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 : 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 : Global And Regional Economic Development

    The Pharmatec Group, a supplier of pharmaceutical equipment, systems and services, has its head office in London and primary production facilities in the US. The company also has a successful subsidiary in South Africa, which was established in 1990. Pharmatec South A

    		•
  • Q : Solve each equation by factoring A

    A college student invested part of a $25,000 inheritance at 7% interest and the rest at 6%.  If his annual interest is $1,670 how much did he invest at 6%?  If I told you the answer is $8,000, in your own words, using complete sentences, explain how you

    		•
  • Q : Formulating linear program of an oil

    An oil company blends two input streams of crude oil products alkylate and catalytic cracked to meet demand for weekly contracts for regular (12,000 barrels) mind grade ( 7,500) and premium ( 4,500 barrels) gasoline’s . each week they can purchase up to 15, 000

    		•
  • Q : Containee problem For queries Q 1 and Q

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

    		•