What is First-Order Rewritable (and FO-Query)? I just wonder what FO Rewritable is, put an example to make it clearer for me. Also, I heard that a language that is FO Rewritable is very good, in what sense?

It is said as follow:


  A class C of TGDs is ﬁrst-order rewritable (or FO-rewritable) iff for every set of TGDs $\Sigma$ in C, and for every BCQ Q, there exists a ﬁrst-order query $Q_\Sigma$ such that for every database
  instance D, it holds $D\cup\Sigma\models Q$ iff $D\models Q_\Sigma$.


Since answering ﬁrst-order queries is in the class $\textrm{AC}_0$ in the data complexity, it immediately follows that for FO-rewritable TGDs, BCQ answering is in $\textrm{AC}_0$ in the data complexity.

Then my question can be extended into, what is a first-order query?

Link to the paper: http://portal.acm.org/citation.cfm?doid=1514894.1514897
Part of the answer is in your question: if your language is FO-rewritable, query answering is in $\textrm{AC}_0$ in data complexity, which is almost as good as it gets. However, keep in mind that you have to pay the cost of computing $Q_\Sigma$, which might be expensive, though you have to do it only once.

Other good thing is that, for a FO-rewritable language, you reduce the problem of answering a query over a database with dependencies to answering a query over a database without dependencies. But again, the size of the new query ($Q_\Sigma$) might be exponential (or worse, but I'm not so sure) in the size of $Q$ and $\Sigma$ (because you have to encode the TGDs in $Q_\Sigma$ somehow). Anyways, roughly speaking it means you are reducing a problem to a simpler problem. I guess that's why it's very good.