Conjunctive query containment revisited

We consider the problems of conjunctive query containment and minimization, which are known to be NP-complete, and show that these problems can be sol ved in polynomial time for the class of acyclic queries, We then generalize the notion of acyclicity and define a parameter called query width that ca ptures the ''degree of cyclicity" of a query: in particular, a query is acy clic if and only if its query width is 1. We give algorithms for containmen t and minimization that run in time polynomial in n(k), where n is the inpu t size and k is the query width. These algorithms naturally generalize thos e for acyclic queries, and are of practical significance because many queri es 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 inciden ce 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 sh ow that a polynomial-time approximation algorithm is unlikely for this prob lem. Finally, we apply our containment algorithm to the practically importa nt problem of finding equivalent rewritings of a query using a set of mater ialized views. (C) 2000 Elsevier Science B.V. All rights reserved.