TY - JOUR

T1 - Conjunctive query containment revisited

AU - Chekuri, Chandra

AU - Rajaraman, Anand

N1 - Funding Information:
(This work was done while the authors were at Stanford University. ∗Correponding author. E-mail addresses: chekuri@research.bell-labs.com (C. Chekuri); anand@amazon.com (A. Rajaraman). 1Supported at Stanford University by an NSF Award CCR-9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. 2Supported at Stanford University by an NSF grant IRI-92-23405, ARO grant DAAH04-95-1-0192, and USAF contract F33615-93-1-1339.

PY - 2000/5/28

Y1 - 2000/5/28

N2 - We consider the problems of conjunctive query containment and minimization, which are known to be NP-complete, and show that these problems can be solved in polynomial time for the class of acyclic queries. We then generalize the notion of acyclicity and define a parameter called query width that captures the "degree of cyclicity" of a query: in particular, a query is acyclic if and only if its query width is 1. We give algorithms for containment and minimization that run in time polynomial in nk, where n is the input size and k is the query width. These algorithms naturally generalize those for acyclic queries, and are of practical significance because many queries have small query width compared to their sizes. We show that good bounds on the query width of Q can be obtained using the treewidth of the incidence graph of Q. We then consider the problem of finding an equivalent query to a given conjunctive query Q that has the least number of subgoals. We show that a polynomial-time approximation algorithm is unlikely for this problem. Finally, we apply our containment algorithm to the practically important problem of finding equivalent rewritings of a query using a set of materialized views.

AB - We consider the problems of conjunctive query containment and minimization, which are known to be NP-complete, and show that these problems can be solved in polynomial time for the class of acyclic queries. We then generalize the notion of acyclicity and define a parameter called query width that captures the "degree of cyclicity" of a query: in particular, a query is acyclic if and only if its query width is 1. We give algorithms for containment and minimization that run in time polynomial in nk, where n is the input size and k is the query width. These algorithms naturally generalize those for acyclic queries, and are of practical significance because many queries have small query width compared to their sizes. We show that good bounds on the query width of Q can be obtained using the treewidth of the incidence graph of Q. We then consider the problem of finding an equivalent query to a given conjunctive query Q that has the least number of subgoals. We show that a polynomial-time approximation algorithm is unlikely for this problem. Finally, we apply our containment algorithm to the practically important problem of finding equivalent rewritings of a query using a set of materialized views.

UR - http://www.scopus.com/inward/record.url?scp=0003505668&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003505668&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(99)00220-0

DO - 10.1016/S0304-3975(99)00220-0

M3 - Article

AN - SCOPUS:0003505668

VL - 239

SP - 211

EP - 229

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 2

ER -