  We study first-order model checking, by which we refer to the problem of
deciding whether or not a given first-order sentence is satisfied by a given
finite structure. In particular, we aim to understand on which sets of
sentences this problem is tractable, in the sense of parameterized complexity
theory. To this end, we define the notion of a graph-like sentence set, which
definition is inspired by previous work on first-order model checking wherein
the permitted connectives and quantifiers were restricted. Our main theorem is
the complete tractability classification of such graph-like sentence sets,
which is (to our knowledge) the first complexity classification theorem
concerning a class of sentences that has no restriction on the connectives and
quantifiers. To present and prove our classification, we introduce and develop
a novel complexity-theoretic framework which is built on parameterized
complexity and includes new notions of reduction.
