Survey on Query Decomposition
=====================================================================

A refined characterization of the complexity of evaluating a query is
a problem of great interest, both from the theoretical and from the
practical perspective. While evaluation and containment of conjunctive
queries are, in general, NP-complete, they can be solved in polynomial
time for queries having a join tree (also called acyclic queries).
Research in databases and graph theory helped in defining
decompositions of a query such that it can be evaluated efficiently,
provided that a certain measure, usually called *width*, is small.
This survey provides an overview of several types of decompositions
for conjunctive queries, including complexity results and a brief
discussion of the algorithms that were proposed.