--%>
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 : Formal logic It's a problem set, they

    It's a problem set, they are attached. it's related to Sider's book which is "Logic to philosophy" I attached the book too. I need it on feb22 but feb23 still work

    		•
  • Q : Problem on reduced row-echelon The

    The augmented matrix from a system of linear equations has the following reduced row-echelon form. 280_row echelon method.jpg

    		•
  • Q : Use MS Excel to do the computations

    Select a dataset of your interest (preferably related to your company/job), containing one variable and atleast 100 data points. [Example: Annual profit figures of 100 companies for the last financial year]. Once you select the data, you should compute 4-5 summary sta

    		•
  • Q : Abstract Algebra let a, b, c, d be

    let a, b, c, d be integers. Prove the following statements: (a) if a|b and b|c. (b) if a|b and ac|bd. (c) if d|a and d|b then d|(xa+yb) for any x, y EZ

    		•
  • Q : State Fermat algorithm The basic Fermat

    The basic Fermat algorithm is as follows: Assume that n is an odd positive integer. Set c = [√n] (`ceiling of √n '). Then we consider in turn the numbers c2 - n; (c+1)2 - n; (c+2)2 - n..... until a perfect square is found. If th

    		•
  • Q : What is the definition of a group Group

    Group: Let G be a set. When we say that o is a binary operation on G, we mean that o is a function from GxG into G. Informally, o takes pairs of elements of G as input and produces single elements of G as output. Examples are the operations + and x of

    		•
  • Q : Linear programming model of a Cabinet

    A cabinet company produces cabinets used in mobile and motor homes. Cabinets produced for motor homes are smaller and made from less expensive materials than those for mobile homes. The home office in Dayton Ohio has just distributed to its individual manufacturing ce

    		•
  • Q : Test Please read the assignment

    Please read the assignment carefully and confirm only if you are 100% sure. Please go through below mentioned guidelines and penalties: • Your solution must be accurate and complete. • Please do not change Subject Title of the Email. • Penalty clause will be applied in case of delayed or plag

    		•
  • Q : Maths assignment complete assignment

    complete assignment with clear solution and explanation

    		•