5

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?

zfm
  • 1,906
  • 2
  • 17
  • 28
  • The example should be corrected. Note that variable y does not appear in the premises of the second rule, although it is used in the head. Datalog is [restricted so that all programs terminate](http://en.wikipedia.org/wiki/Datalog). Are you asking about ways to eliminate recursion to obtain (potentially) a single SQL query equivalent, or are you thinking about implementing recursion in a SQL context, which might be possible (with severe limitations) using stored procedures? – hardmath Jul 01 '11 at 16:37
  • @hardmath: sorry, typo... thx for the correction. Yes, I would like to implement the recursion in SQL, is it possible? – zfm Jul 03 '11 at 23:04
  • It is possible, but we are likely limited as to the depth of recursion that can be had directly. For example, MS SQL Server 2008 limits [the nesting depth of stored procedure calls to 32](http://msdn.microsoft.com/en-us/library/ms190607.aspx). It's probably enough to demonstrate a concept but not for production applications. Note that MS SQL Server does allow for calls to external coded (extended stored procedures) in which the nesting of calls is not monitored. – hardmath Jul 03 '11 at 23:18
  • You might be interested in an indirect approach to the recursion, in which "datalog" rules are applied repeatedly to infer new consequences, and these can be inserted into one or more tables, until no new deductions are possible. – hardmath Jul 04 '11 at 04:38
  • @hardmath: that's my idea! where the recursivity will be done on the program, not on the SQL... However, this is still so unmanageable for me if there is a nontrivial dependency... – zfm Jul 04 '11 at 18:26

3 Answers3

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.

hardmath
  • 8,753
  • 2
  • 37
  • 65
  • In this case, it may work, but how about in the bigger case where there is a bigger non-trivial recursive? – zfm Jul 10 '11 at 09:55
  • 1
    What I'm outlining is a process that, for conforming Datalog programs, will deduce all (finitely many) provable conclusions. If you have "terminal" predicates like `A/1` implemented as external code, these would be handled as simple facts, i.e. storing any successful results of calling them on all possible inputs (remember in Datalog the range of any variable is finite). So this "wrinkle" can be reduced to standard Datalog facts and rules. – hardmath Jul 11 '11 at 17:41
0

A possible approach is to use recursive CTEs in SQL, which provide the power of transitive closure. Relational algebra + transitive closure = Datalog.

John Cowan
  • 1,497
  • 12
  • 13
0

Logica does something like this. It translates a datalog-like language into SQL for Google BigQuery, PostgreSQL and SQLite.

hs211216
  • 1
  • 1
    Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Feb 13 '22 at 06:19