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

Factors in denominator and partial fraction decomposition, Factors in Denom...

Factors in Denominator and Partial Fraction Decomposition Factor in denominator Term in partial  fraction decomposition   ax + b

Quantitative techniques, mentioning the type of business you could start an...

mentioning the type of business you could start and the location of your business, use the steps of quantitative methods for decision making narrating them one by one in the applic

Find out the surface area of the solid, Find out the surface area of the so...

Find out the surface area of the solid acquired by rotating y = √ (9-x 2 ), - 2 x 2 about the x-axis. Solution The formula that we'll be using here is, S = ∫ 2Πyds

form a pythagorean triple, A Pythagorean triple is a set of positive integ...

A Pythagorean triple is a set of positive integers (a,b,c) like  a2 + b2 = c2.  Write a function "ispythag" that will receive 3 positive integers (a, b, c in that order) and will r

Activity example of one to one correspondence learning, Devise one activity...

Devise one activity each to help the child understand 'as many as' and 'one-to-one correspondence'. Try them out on a child/children in your neighbourhood, and record your observat

#probability, A B C play a game. If chance of their winning it in an attemp...

A B C play a game. If chance of their winning it in an attempt arr2/3, 1/2, 1/4 respective. A has a first chance followed by Band Called respective chances of winning the game.

Trigonometry, if tan theta =1,find the value of sin4 theta + cos4 theta

if tan theta =1,find the value of sin4 theta + cos4 theta

Find the perimeter of triangle, The length of the sides of a triangle are 2...

The length of the sides of a triangle are 2x + y/2 , 5 x/3 + y + 1/2  and 2/3 x  + 2y + 5/2. If the triangle is equilateral. Find its perimeter. A ns: 2x + y/2 = 4x + y

Truth criteria-nature of mathematics, Truth Criteria :  Consider the follo...

Truth Criteria :  Consider the following statements: i) Peahens (i.e., female peacocks) lay eggs around September. ii) Water boils at 100°C. iii) 5 divides 15 without lea

Linear equation, The sum of the digit number is 7. If the digits are revers...

The sum of the digit number is 7. If the digits are reversed , the number formed is less than the original number. find the number

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