TY - GEN

T1 - Conjunctive query containment revisited

T2 - 6th International Conference on Database Theory, ICDT 1997

AU - Chekuri, Chandra

AU - Rajaraman, Anand

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

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 we can obtain good bounds on the query width of Q using the treewidth of the incidence graph of Q. 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 we can obtain good bounds on the query width of Q using the treewidth of the incidence graph of Q. 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=84948974054&partnerID=8YFLogxK

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

M3 - Conference contribution

AN - SCOPUS:84948974054

SN - 9783540622222

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 56

EP - 70

BT - Database Theory - ICDT 1997 - 6th International Conference, Proceedings

A2 - Afrati, Foto

A2 - Kolaitis, Phokion

PB - Springer

Y2 - 8 January 1997 through 10 January 1997

ER -