translation from Datalog to SQL

Question

I am still thinking on how to translate the recursivity of a Datalog program into SQL, such as

P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).

where A/1 is an EDB predicate. This, there is a co-dependency between P and Q. For longer queries, how to solve this problem?

Moreover, is there any system completely implement the translation? If there is, may I know what system or which paper may I refer?

Answer 1

If you adopt an approach of "tabling" previous conclusions and forward-chain reasoning on these to infer new conclusions, no recursive "depth" is required.

Bear in mind that Datalog requires some restrictions on rules and variable that assure finite termination and hence finitely many conclusions. Variables must have a finite range of possible values, for example.

Let's assume your example refers to constants rather than to variables:

P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).

One wrinkle is that you want A/1 to be implemented as an extended stored procedure or external code. For that I would propose tabling all the results of calling A on all possible arguments (finitely many). These are after all among the conclusions (provable statements) of your system.

Once that is done the forward-chaining inference proceeds iteratively rather than recursively. At each step consider each rule, applying it with premises (right-hand sides) that are previously obtained (tabled) conclusions if it produces a new conclusion. If no rule produces a new conclusion in the current step, halt. The proof procedure is complete.

In your example the proofs stop after all the A facts are adduced, because there are no conclusions sufficient to apply either rule to get new conclusions.