Polynomial time algorithm - first order query, Mathematics

Assignment Help:

For queries Q1 and Q2, we say Q1 is contained in Q2, denoted Q1 ⊆ Q2, iff Q1 (D) ⊆ Q2(D) for every database D.

  • The container problem for a fixed Query Q0 is the following decision problem: Given a query Q, decide whether Q0 ⊆ Q.
  • The containee problem for a fixed query Q0 is the following decision problem: Given a query Q, decide whether Q ⊆ Q0.

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

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

(d) For every first-order Query Q0, there is an algorithm to decide the containee problem for Q0 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 Discussions:- Polynomial time algorithm - first order query

Cooking measurement question, Ask question what is half of 1 1/3 liquid mea...

Ask question what is half of 1 1/3 liquid measurements?

F distribution or variance ratio distribution, Frequency Distribution or Va...

Frequency Distribution or Variance Ratio Distribution This was developed by R. A Fisher in 1924 and is normally defined in terms of the ratio of the variances of two usually d

SURFACE AREA AND VOLUMES, Metallic spheres of radii 6 centimetre, 8 centime...

Metallic spheres of radii 6 centimetre, 8 centimetre and 10 centimetres respectively are melted to form a single solid sphere. Find the radius of the resulting sphere.

Cycloid - parametric equations and polar coordinates, Cycloid The param...

Cycloid The parametric curve that is without the limits is known as a cycloid.  In its general form the cycloid is, X = r (θ - sin θ) Y = r (1- cos θ)  The cycloid pre

Variation and proportion, i am not getting what miss has taught us please w...

i am not getting what miss has taught us please will you will help me in my studies

System of linear equations, create a system of linear equations that has (2...

create a system of linear equations that has (2,3)as a solution.

Angles, in the quadrilateral abcd,ab is 4.3,bd is 5.1,ad is 4.8.angle bdc i...

in the quadrilateral abcd,ab is 4.3,bd is 5.1,ad is 4.8.angle bdc is 20 degrees and angle c is 80 degrees.all dimentions in metres.calculate the unknown sides and angles of the plo

General approach of exponential functions, General approach of Exponential ...

General approach of Exponential Functions : Before getting to this function let's take a much more general approach to things. Let's begin with b = 0 , b ≠ 1. Then an exponential f

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd