  We study the problem of conjunctive query evaluation relative to a class of
queries; this problem is formulated here as the relational homomorphism problem
relative to a class of structures A, wherein each instance must be a pair of
structures such that the first structure is an element of A. We present a
comprehensive complexity classification of these problems, which strongly links
graph-theoretic properties of A to the complexity of the corresponding
homomorphism problem. In particular, we define a binary relation on graph
classes, which is a preorder, and completely describe the resulting hierarchy
given by this relation. This relation is defined in terms of a notion which we
call graph deconstruction and which is a variant of the well-known notion of
tree decomposition. We then use this hierarchy of graph classes to infer a
complexity hierarchy of homomorphism problems which is comprehensive up to a
computationally very weak notion of reduction, namely, a parameterized version
of quantifier-free first-order reduction. In doing so, we obtain a
significantly refined complexity classification of homomorphism problems, as
well as a unifying, modular, and conceptually clean treatment of existing
complexity classifications. We then present and develop the theory of
Ehrenfeucht-Fraisse-style pebble games which solve the homomorphism problems
where the cores of the structures in A have bounded tree depth. Finally, we use
our framework to classify the complexity of model checking existential
sentences having bounded quantifier rank.
