--%>
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 : 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 : State Prime number theorem Prime number

    Prime number theorem: A big deal is known about the distribution of prime numbers and of the prime factors of a typical number. Most of the mathematics, although, is deep: while the results are often not too hard to state, the proofs are often diffic

    		•
  • Q : Calculus I need it within 4 hours. Due

    I need it within 4 hours. Due time March 15, 2014. 3PM Pacific Time. (Los Angeles, CA)

    		•
  • 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 : Area Functions & Theorem Area Functions

    Area Functions 1. (a) Draw the line y = 2t + 1 and use geometry to find the area under this line, above the t - axis, and between the vertical lines t = 1 and t = 3. (b) If x > 1, let A(x) be the area of the region that lies under the line y = 2t + 1 between t

    		•
  • Q : Problem on budgeted cash collections

    XYZ Company collects 20% of a month's sales in the month of sale, 70% in the month following sale, and 5% in the second month following sale. The remainder is not collectible. Budgeted sales for the subsequent four months are:     

    		•
  • Q : Pig Game Using the PairOfDice class

    Using the PairOfDice class design and implement a class to play a game called Pig. In this game the user competes against the computer. On each turn the player rolls a pair of dice and adds up his or her points. Whoever reaches 100 points first, wins. If a player rolls a 1, he or she loses all point

    		•
  • Q : Explain the work and model proposed by

    Explain the work and model proposed by Richardson.

    		•
  • Q : Statistics math Detailed explanation of

    Detailed explanation of requirements for Part C-1 The assignment states the following requirement for Part 1, which is due at the end of Week 4: “Choose a topic from your field of study. Keep in mind you will need to collect at least [sic] 3- points of data for this project. Construct the sheet y

    		•
  • Q : Explain Black–Scholes model Explain

    Explain Black–Scholes model.

    		•