Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem:
The problem $D\cup\Sigma\models Q$ is being reduced to a problem $D\models Q_\Sigma$.
Several noteworthy things are happening here. The original problem is a logical entailment question. We are asking if the Boolean query (=a special form of logical sentence) is a logical consequence of a set of facts $D$ together with a logical theory $\Sigma$ (consisting of certain rules, called tuple-generating dependencies).
If you would want to answer this question directly, you might try to compute a universal model of $D\cup\Sigma$. This can be viewed as a "completed database" which is obtained from $D$ by adding (recursively!) all the facts that need to hold true for $\Sigma$ to be satisfied. In easy cases (e.g., if the rules $\Sigma$ do not have existential quantifiers), the computation of a universal model (usually called chase in this area) may lead to an exponentially large database. In harder cases, the universal model could be much larger or simply infinite (making it impossible to compute it to answer queries). This is why the original question $D\cup\Sigma\models Q$ is hard and undecidable in general.
Now for FO-rewritable $\Sigma$, we can reduce this hard problem to a question $D\models Q_\Sigma$. You can also view this as a logical entailment problem as before, but the more natural view is to consider this as a model checking task. Indeed, $D$ is a finite structure (model) and we are merely asking if the sentence $Q_\Sigma$ is true in this structure. This problem of first-order model checking is the logical version of what practitioners know as "SQL query answering" (for basic SQL queries without complicated features). Indeed, every first-order formula $\varphi$ can be written as an SQL query $S_\varphi$ such that $D\models \varphi$ is true if and only if the query $S_\varphi$ matches the database $D$ (with facts stored in relational tables in the obvious way). This means that, in principle, the reduced problem $D\models Q_\Sigma$ can be solved by any RDBMS, without any universal model computation.
If you want to learn more about the relation of first-order logic and SQL, you should have a look at the standard textbook of Abiteboul, Hull, Vianu: Foundations of Databases, freely available online http://webdam.inria.fr/Alice/.
In terms of complexity the data complexity of answering queries over FO rewritable fragments is indeed $\text{AC}^0$, a very low, highly parallelisable complexity class that is one of the few which is known to be strictly smaller than $\text{P}$. This is what you get when disregarding the size of $\Sigma$ and $Q$ as neglectable. If you consider them, then the resulting combined complexity is usually dominated by the effort of computing the rewriting (typically exponential).
Some small remarks are possibly helpful for you to get a better idea of the overall picture:
- Many papers that discuss FO rewritability really establish "union-of-BCQs rewritability", since the rewritten formulae are not using all of first-order logic (esp. no negation and no universal quantifiers). This restriction is not part of the notion of FO rewritability, it just happens because many works rewrite fragments of positive FO where you don't need these features.
- As remarked elsewhere, it is not always practical to do this rewriting. Even well-behaved rewritable logics still may lead to unions of exponentially many exponentially large BCQs. When considering arbitrary FO-rewritable TGDs, there is no bound on the maximal size of rewritings (determining if there is an FO rewriting for a given $Q$ and $\Sigma$ is undecidable, but semi-decidable; see Baget et al. "On rules with existential variables: Walking the decidability line". Artif. Intell. 175:9-10. 2011).
- Another practical issue is that query optimisers are not always very successful on such large, artificially generated UCQs, and the NP-hardness of the UCQ query answering problem becomes noticable (i.e., ignoring query size and considering only data complexity may be misleading).
- While papers rarely discuss this, the techniques usually extend to answering non-Boolean CQs. In this case, however, one needs to add a DISTINCT when executing this on SQL systems so as to get set semantics (you do not want bag semantics with recursive tgds!). This extra duplicate elimination can be expensive.
- The notion is closely related to the concept of boundedness of a Datalog program, which asks if backward chaining (with some additional checks) eventually leads to a UCQ of bounded size. However, many works on Datalog assume that some predicates cannot appear in the database (so-called IDB predicates). This renders boundedness non-semi-decidable (Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y.: "Decidable optimization problems for database logic programs (preliminary report)". STOC 1988).
