We consider the problem of query evaluation for fragments of first-order logic. We revisit the complexity of these problems and exhibit a logical and combinatorial approach that permits to obtain tractability results for various classes : in particular for acyclic conjunctive queries and first-order queries on structures of bounded degree and on trees. This method simply tries to eliminate (under reasonable i.e. linear cost) variables of the formula while preserving the result of the query.
Then, we consider query problems as generation problems for which the complexity measure is the delay between two consecutive tuples of the result, and we show some interesting consequences for the complexity of these problems of the above described method.