  Structural decomposition methods have been developed for identifying
tractable classes of instances of fundamental problems in databases, such as
conjunctive queries and query containment, of the constraint satisfaction
problem in artificial intelligence, or more generally of the homomorphism
problem over relational structures. Most structural decomposition methods can
be characterized through hypergraph games that are variations of the Robber and
Cops graph game that characterizes the notion of treewidth. In particular,
decomposition trees somehow correspond to monotone winning strategies, where
the escape space of the robber on the hypergraph is shrunk monotonically by the
cops. In fact, unlike the treewidth case, there are hypergraphs where monotonic
strategies do not exist, while the robber can be captured by means of more
complex non-monotonic strategies. However, these powerful strategies do not
correspond in general to valid decompositions. The paper provides a general way
to exploit the power of non-monotonic strategies, by allowing a "disciplined"
form of non-monotonicity, characteristic of cops playing in a greedy way. It is
shown that deciding the existence of a (non-monotone) greedy winning strategy
(and compute one, if any) is tractable. Moreover, despite their
non-monotonicity, such strategies always induce valid decomposition trees,
which can be computed efficiently based on them. As a consequence, greedy
strategies allow us to define new islands of tractability for the considered
problems properly including all previously known classes of tractable
instances.
