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 first-order rewritable (or FO-rewritable) iff for every set of TGDs $\Sigma$ in C, and for every BCQ Q, there exists a first-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 first-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

  • 2
    $\begingroup$ Do you have any links or references to these definitions? $\endgroup$ Commented Feb 11, 2011 at 14:06
  • $\begingroup$ I got it from this paper: "Datalog±: a unified approach to ontologies and integrity constraints". It is written there "Linear Datalog± is a variant of guarded Datalog±, where query answering is even FO-rewritable in the data complexity" $\endgroup$
    – zfm
    Commented Feb 11, 2011 at 15:05
  • 4
    $\begingroup$ I would also recommend giving expansions and definitions of the acronyms TGD and BCQ. Giving a link to the paper you are referring to would also help, since I can't see that anyone will be able to figure out enough to help you without reading the whole thing at this point. $\endgroup$ Commented Feb 11, 2011 at 19:53

3 Answers 3


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.


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).

As a complement to Janoma's answer above: it's 'very good'--- from the point of view of implementation --- because given a FO-rewritable language, we can use the powerful engines (for evaluating queries directly against a database without dependencies) that are available. That's basically reducing the problem to evaluation of SQL queries.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.