<p>There does not seem to be a general algorithm.</p>

<p>Checking whether two Datalog programs are equivalent (in the sense of producing the same output database for every possible input database) is undecidable.  The containment problem, of checking whether one Datalog program always produces all the tuples of the other (plus possibly some others), is also undecidable.  So there is no general algorithm for verifying the output of your proposed minimization algorithm.  One can generate all syntactically valid Datalog programs up to the size of the input Datalog program, but there is no general way to check whether these are equivalent to or even implied by the original Datalog program.</p>

<ul>
<li>Oded Shmueli, <em>Equivalence of Datalog queries is undecidable</em>, The Journal of Logic Programming <strong>15</strong>(3) 231–241, 1987.  doi: <a href="http://dx.doi.org/10.1016/0743-1066%2893%2990040-N">10.1016/0743-1066(93)90040-N</a></li>
</ul>

<p>What you perhaps mean is minimization over all Datalog programs made up only of the terms that occur in the original program, such as the $A(x) \leftarrow D(x).$ example you provided above.  This is a restricted form of Datalog containment, since one only wants to check containment between syntactically closely related Datalog programs.  It is not obvious to me whether this restriction makes the problem decidable or not, although there may be some related work, perhaps in the rewriting systems or finite automata communities.</p>

<p>Restricting the problem somewhat, one can try to find an equivalent minimal non-recursive Datalog program.  Unfortunately checking for equivalence between a recursive and a non-recursive Datalog program requires time that is triply exponential in the size of the programs, and checking whether the recursive program is contained in the non-recursive one requires doubly exponential time.  Moreover, these algorithms require constructing exponential-sized tree automata, so are probably not feasible for actual implementation.</p>

<ul>
<li>Surajit Chaudhuri and Moshe Vardi, <em>On the Equivalence of Recursive and Nonrecursive Datalog Programs</em>, JCSS <strong>54</strong>(1), 61–78, 1997. doi: <a href="http://dx.doi.org/10.1006/jcss.1997.1452">10.1006/jcss.1997.1452</a> (<a href="http://www.cs.rice.edu/~vardi/papers/pods92rj.pdf">preprint</a>)</li>
</ul>

<p>Finally, consider <em>really</em> simple Datalog programs, where there are only two unary predicates $T(x)$ and $F(x)$, such that $T(x) \equiv \lnot F(x)$.  In other words, each variable must take either the value "true" or "false".  Each such Datalog program then corresponds to a Horn formula, a universally quantified conjunction of Horn clauses.  The minimization problem for these highly restricted Datalog programs is still NP-hard, and also likely to be hard to approximate.</p>

<ul>
<li>Amitava Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi, and György Turán, <em>On Approximate Horn Formula Minimization</em>, ICALP 2010, doi:<a href="http://dx.doi.org/10.1007/978-3-642-14165-2_38">10.1007/978-3-642-14165-2_38</a> (<a href="http://www.cs.uic.edu/~dasgupta/resume/publ/papers/icalp2010.pdf">preprint</a>)</li>
</ul>

<p>The authors mention some prior work on efficient algorithms for restricted cases, such as quasi-acyclic Horn formulas and for approximation in terms of the number of different variables in the formula.</p>

<p>You might also be interested in the literature on finding shortest implicants.</p>

CC BY-SA 3.0
2012-01-14T13:24:08.743Z
I do not think that any of the hardness results you mentioned applies to this question exactly for the reason you mentioned: “What you perhaps mean is minimization over all Datalog programs made up only of the terms that occur in the original program.”  Also my interpretation of the question is to find a minimal subset of the clauses which is equivalent to the original program, not necessarily the one with the minimum number of clauses.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-14T20:09:18.153Z
Thank you for your reply. I think that for non-recursive datalog checking whether two programs are equivalent should be feasible, since all the inferences that can be done are finite and we can compare them after that. I may have other relevant properties in my datalog and I may not be aware of them because overlooked their relevance, so I'll re-analyze that after reading the papers.

Tsuyoshi Ito you are right. The subset of the clauses would be referred not only to the original clauses but to the set of clauses that can be deduced from the original program.
Trylks
CC BY-SA 3.0
2012-01-15T09:10:45.180Z
@TsuyoshiIto: you are right, but perhaps posting the signposts on the edges of the cliff has helped Trylks to find which road was actually desired.
András Salamon
CC BY-SA 3.0
2012-01-18T14:18:28.490Z
After reading the papers I think this doesn't apply. Datalog program containment is undecidable, so I cannot verify the correctness for an arbitrary output, but my output is not arbitrary, if I can proof every step is correct then the result must be correct as well. Some transformations are valid and that (at least) seems fairly provable.
Trylks
CC BY-SA 3.0
2012-01-13T19:45:16.613Z
2012-01-13T19:45:16.613Z
András Salamon
<p>Search for <a href="http://en.wikipedia.org/wiki/Transitive_reduction" rel="nofollow">transitive reduction</a> of a directed graph.</p>

CC BY-SA 3.0
2012-01-10T13:09:03.173Z
I've updated the original example to contain a conjunction. I thought about the dominator tree, but could not find a good way to apply it either. Sorry if I was unclear about this.
Trylks
CC BY-SA 3.0
2012-01-10T15:38:32.460Z
Sorry, I had not understood your question...

I don't understand how the example works. It seems like we can't discard any clauses. Where am I wrong?
Dmytro Korduban
CC BY-SA 3.0
2012-01-11T12:05:17.123Z
If we have a datalog program with the four clauses we can discard the fourth, because it can be derived from the other three.
Trylks
CC BY-SA 3.0
2012-01-10T12:45:15.317Z
2012-01-10T12:45:15.317Z
Dmytro Korduban
<p>We can consider a datalog program as a set of clauses. Some of them allow to derive others. For instance from:</p>

<pre><code>A(x) :- B(x), C(x).
B(x) :- D(x).
C(x) :- D(x).
</code></pre>

<p>We can derive:</p>

<pre><code>A(x) :- D(x).
</code></pre>

<p>Given a datalog program, a <em>minimal equivalent datalog program</em> is a subset of the given program with the smallest number of clauses that allows to derive the full datalog program. Minimal equivalent datalog program is not unique at least in the presence of cycles. Finding any of them is enough; I don't need to find them all.</p>

<p>The clauses contain no disjunctions, only an implication and an atom in the head. Alternate definition: clauses are composed by disjunctions (no conjunctions) and there is only one non-negated predicate. All predicates are unary or binary, and contain variables or constants. There may be recursion, and it may be limited to unary predicates.</p>

<p>I'm searching for an algorithm that allows to find this minimal datalog program for a given program, but I could not find it. It may just be a matter of not using the correct terms, or maybe my confusion is deeper. In any case this seems a fundamental problem when working with datalog and my guess is that it was solved decades ago.</p>

<p>Do you know any algorithm for this? Should I use a different terminology?</p>

<p>Thank you.</p>

<p>PD: a more enticing example that allows greater optimization:</p>

<pre><code>A(x):- I(x).        B(x):- P(x,y).      P(x,y):- T(x,y).
A(x):- C(x).        G(x):- L(x).        P(x,z):- T(y,x).
A(x):- R(x,y).      H(x):- P(x,y).      P(x,z):- U(y,x).
A(x):- R(y,x).      H(x):- T(x,y).      P(y,x):- T(x,y).
D(x):- A(x).        I(x):- J(x).        P(z,x):- R(y,x).
D(x):- T(y,x).      I(x):- T(x,y).      R(x,y):- T(x,y).
E(x):- I(x).        C(x):- K(x).        R(y,x):- T(x,y).
E(x):- R(x,y).      C(x):- R(x,y).      S(x,z):- T(x,y).
F(x):- A(x).        C(x):- T(y,x).      S(x,z):- R(x,y).
F(x):- H(x).        C(x):- U(x,y).      S(y,x):- T(x,y).
F(x):- R(y,x).      J(x):- K(x).        S(y,x):- U(x,y).
B(x):- D(x).        J(x):- R(x,y).      T(y,x):- U(x,y).
B(x):- C(x).        K(x):- U(x,y).      U(x,z):- R(x,y).
B(x):- J(x).        L(x):- R(y,x).      U(x,z):- P(x,y).
B(x):- L(x).                
</code></pre>

<p>I was calculating the result manually, but I think I can do it with an algorithm, it's going to take a while.</p>

<p>PD: I found this: A. Pettorossi and M. Proietti, “Transformation of logic programs: Foundations and techniques,” The Journal of Logic Programming, vol. 19–20, Supplement 1, pp. 261–320, May 1994.</p>

CC BY-SA 3.0
2012-01-13T12:05:34.317Z
I am not familiar with Datalog.  Assuming that a Datalog program consists of Horn clauses, isn’t it just the matter of testing whether each clause is derived from the other clauses one by one?  If it is, then remove it and continue with the other clauses.  This should give you one minimal set of clauses which is equivalent to the original program.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-14T20:20:53.547Z
In that case a removed clause could be useful to remove another clause, and the latter would not be removed if the former was removed first. It would be feasible ordering the clauses in a lattice if there were no cycles, but I'm afraid I have cycles. And I guess I'd have to cite the SoA anyway (and that's why I was asking for the terminology).
Trylks
CC BY-SA 3.0
2012-01-18T14:20:36.987Z
The cycles can be arbitrarily broken if I'm not mistaken, I'll proceed with the implementation, but this is not my only task, so it's going to take a while. Thank you.
Trylks
CC BY-SA 3.0
2012-01-18T21:14:43.143Z
What do you mean by “minimal”?  Namely, do you mean minimal in terms of inclusion relation, or the smallest number of clauses?  I thought that you meant the former (because that is the usual meaning of “minimal set”), but from your comments it sounds like you meant the latter.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-19T14:34:59.550Z
I mean the latter. Sorry if the terminology isn't correct. The clauses contain no disjunctions, only an implication and an atom in the head. Alternate definition: clauses are composed by disjunctions (no conjunctions) and there is only one non-negated predicate.
Trylks
CC BY-SA 3.0
2012-01-19T20:19:18.083Z
It is now clear that the question as it is currently written is distinctly underspecified.  Could you identify other restrictions, for instance are all your predicates unary?  (Also, instead of making this a long discussion thread, please instead edit the question to clarify.)
András Salamon
CC BY-SA 3.0
2012-01-20T11:39:48.807Z
Edited. I think that's everything. Sorry for not identifying these restrictions before.
Trylks
CC BY-SA 3.0
2012-01-21T01:02:33.153Z
I edited the question to clarify the meaning of “minimal” in the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-22T18:10:16.020Z
Your question is still unclear.  1. You imply that your Datalog programs are recursive.  Is this correct?  2. If so, are the recursive predicates unary (i.e. is the recursion monadic)?  Monadic recursion leads to decidable containment, but even a single non-monadic recursive predicate is enough for undecidability.  3. Do you have a more complex example that would be interesting to you?
András Salamon
CC BY-SA 3.0
2012-01-24T16:35:07.467Z
The datalog programs are recursive. The recursive predicates can be binary or unary. I can restrict recursion to unary predicates and then try to check if the solution is applicable to datalog w/ recursive binary predicates, which where causing a lot of trouble anyway. I'm editing the original post to add this and an example, I can link it if that's more readable. I'm currently working on nice looking examples, I hope this is enough (specially without an algorithm). Sorry for the hard question, I really thought this was solved decades ago, now I see it's by far not as simple as I thought.
Trylks
<ds.algorithms><lo.logic><db.databases><logic-programming>
Minimize a datalog program
Trylks
# Minimize a datalog program

(Asked by: username_0 on 2012-01-10)

We can consider a datalog program as a set of clauses. Some of them allow to derive others. For instance from:
A(x) :- B(x), C(x).
B(x) :- D(x).
C(x) :- D(x).

We can derive:
A(x) :- D(x).

Given a datalog program, a minimal equivalent datalog program is a subset of the given program with the smallest number of clauses that allows to derive the full datalog program. Minimal equivalent datalog program is not unique at least in the presence of cycles. Finding any of them is enough; I don't need to find them all.
The clauses contain no disjunctions, only an implication and an atom in the head. Alternate definition: clauses are composed by disjunctions (no conjunctions) and there is only one non-negated predicate. All predicates are unary or binary, and contain variables or constants. There may be recursion, and it may be limited to unary predicates.
I'm searching for an algorithm that allows to find this minimal datalog program for a given program, but I could not find it. It may just be a matter of not using the correct terms, or maybe my confusion is deeper. In any case this seems a fundamental problem when working with datalog and my guess is that it was solved decades ago.
Do you know any algorithm for this? Should I use a different terminology?
Thank you.
PD: a more enticing example that allows greater optimization:
A(x):- I(x).        B(x):- P(x,y).      P(x,y):- T(x,y).
A(x):- C(x).        G(x):- L(x).        P(x,z):- T(y,x).
A(x):- R(x,y).      H(x):- P(x,y).      P(x,z):- U(y,x).
A(x):- R(y,x).      H(x):- T(x,y).      P(y,x):- T(x,y).
D(x):- A(x).        I(x):- J(x).        P(z,x):- R(y,x).
D(x):- T(y,x).      I(x):- T(x,y).      R(x,y):- T(x,y).
E(x):- I(x).        C(x):- K(x).        R(y,x):- T(x,y).
E(x):- R(x,y).      C(x):- R(x,y).      S(x,z):- T(x,y).
F(x):- A(x).        C(x):- T(y,x).      S(x,z):- R(x,y).
F(x):- H(x).        C(x):- U(x,y).      S(y,x):- T(x,y).
F(x):- R(y,x).      J(x):- K(x).        S(y,x):- U(x,y).
B(x):- D(x).        J(x):- R(x,y).      T(y,x):- U(x,y).
B(x):- C(x).        K(x):- U(x,y).      U(x,z):- R(x,y).
B(x):- J(x).        L(x):- R(y,x).      U(x,z):- P(x,y).
B(x):- L(x).                

I was calculating the result manually, but I think I can do it with an algorithm, it's going to take a while.
PD: I found this: A. Pettorossi and M. Proietti, “Transformation of logic programs: Foundations and techniques,” The Journal of Logic Programming, vol. 19–20, Supplement 1, pp. 261–320, May 1994.

**Tags:** ds.algorithms, lo.logic, db.databases, logic-programming
> **Comments:**
> **username_1**: I am not familiar with Datalog.  Assuming that a Datalog program consists of Horn clauses, isn’t it just the matter of testing whether each clause is derived from the other clauses one by one?  If it is, then remove it and continue with the other clauses.  This should give you one minimal set of clauses which is equivalent to the original program.  
> **username_0**: In that case a removed clause could be useful to remove another clause, and the latter would not be removed if the former was removed first. It would be feasible ordering the clauses in a lattice if there were no cycles, but I'm afraid I have cycles. And I guess I'd have to cite the SoA anyway (and that's why I was asking for the terminology).  
> **username_0**: The cycles can be arbitrarily broken if I'm not mistaken, I'll proceed with the implementation, but this is not my only task, so it's going to take a while. Thank you.  
> **username_1**: What do you mean by “minimal”?  Namely, do you mean minimal in terms of inclusion relation, or the smallest number of clauses?  I thought that you meant the former (because that is the usual meaning of “minimal set”), but from your comments it sounds like you meant the latter.  
> **username_0**: I mean the latter. Sorry if the terminology isn't correct. The clauses contain no disjunctions, only an implication and an atom in the head. Alternate definition: clauses are composed by disjunctions (no conjunctions) and there is only one non-negated predicate.  
> **username_2**: It is now clear that the question as it is currently written is distinctly underspecified.  Could you identify other restrictions, for instance are all your predicates unary?  (Also, instead of making this a long discussion thread, please instead edit the question to clarify.)  
> **username_0**: Edited. I think that's everything. Sorry for not identifying these restrictions before.  
> **username_1**: I edited the question to clarify the meaning of “minimal” in the question.  
> **username_2**: Your question is still unclear.  1. You imply that your Datalog programs are recursive.  Is this correct?  2. If so, are the recursive predicates unary (i.e. is the recursion monadic)?  Monadic recursion leads to decidable containment, but even a single non-monadic recursive predicate is enough for undecidability.  3. Do you have a more complex example that would be interesting to you?  
> **username_0**: The datalog programs are recursive. The recursive predicates can be binary or unary. I can restrict recursion to unary predicates and then try to check if the solution is applicable to datalog w/ recursive binary predicates, which where causing a lot of trouble anyway. I'm editing the original post to add this and an example, I can link it if that's more readable. I'm currently working on nice looking examples, I hope this is enough (specially without an algorithm). Sorry for the hard question, I really thought this was solved decades ago, now I see it's by far not as simple as I thought.  

---

## 2 answers

### Answer by username_2 on 2012-01-13. Score: 6

There does not seem to be a general algorithm.

Checking whether two Datalog programs are equivalent (in the sense of producing the same output database for every possible input database) is undecidable. The containment problem, of checking whether one Datalog program always produces all the tuples of the other (plus possibly some others), is also undecidable. So there is no general algorithm for verifying the output of your proposed minimization algorithm. One can generate all syntactically valid Datalog programs up to the size of the input Datalog program, but there is no general way to check whether these are equivalent to or even implied by the original Datalog program.

* Oded Shmueli, *Equivalence of Datalog queries is undecidable*, The Journal of Logic Programming **15**(3) 231–241, 1987. doi: [10.1016/0743-1066(93)90040-N](http://dx.doi.org/10.1016/0743-1066%2893%2990040-N)

What you perhaps mean is minimization over all Datalog programs made up only of the terms that occur in the original program, such as the $A(x) \leftarrow D(x).$ example you provided above. This is a restricted form of Datalog containment, since one only wants to check containment between syntactically closely related Datalog programs. It is not obvious to me whether this restriction makes the problem decidable or not, although there may be some related work, perhaps in the rewriting systems or finite automata communities.

Restricting the problem somewhat, one can try to find an equivalent minimal non-recursive Datalog program. Unfortunately checking for equivalence between a recursive and a non-recursive Datalog program requires time that is triply exponential in the size of the programs, and checking whether the recursive program is contained in the non-recursive one requires doubly exponential time. Moreover, these algorithms require constructing exponential-sized tree automata, so are probably not feasible for actual implementation.

* Surajit Chaudhuri and Moshe Vardi, *On the Equivalence of Recursive and Nonrecursive Datalog Programs*, JCSS **54**(1), 61–78, 1997. doi: [10.1006/jcss.1997.1452](http://dx.doi.org/10.1006/jcss.1997.1452) ([preprint](http://www.cs.rice.edu/~vardi/papers/pods92rj.pdf))

Finally, consider *really* simple Datalog programs, where there are only two unary predicates $T(x)$ and $F(x)$, such that $T(x) \equiv \lnot F(x)$. In other words, each variable must take either the value "true" or "false". Each such Datalog program then corresponds to a Horn formula, a universally quantified conjunction of Horn clauses. The minimization problem for these highly restricted Datalog programs is still NP-hard, and also likely to be hard to approximate.

* Amitava Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi, and György Turán, *On Approximate Horn Formula Minimization*, ICALP 2010, doi:[10.1007/978-3-642-14165-2\_38](http://dx.doi.org/10.1007/978-3-642-14165-2_38) ([preprint](http://www.cs.uic.edu/~dasgupta/resume/publ/papers/icalp2010.pdf))

The authors mention some prior work on efficient algorithms for restricted cases, such as quasi-acyclic Horn formulas and for approximation in terms of the number of different variables in the formula.

You might also be interested in the literature on finding shortest implicants.

> **Comments:**
> **username_1**: I do not think that any of the hardness results you mentioned applies to this question exactly for the reason you mentioned: “What you perhaps mean is minimization over all Datalog programs made up only of the terms that occur in the original program.”  Also my interpretation of the question is to find a minimal subset of the clauses which is equivalent to the original program, not necessarily the one with the minimum number of clauses.  
> **username_0**: Thank you for your reply. I think that for non-recursive datalog checking whether two programs are equivalent should be feasible, since all the inferences that can be done are finite and we can compare them after that. I may have other relevant properties in my datalog and I may not be aware of them because overlooked their relevance, so I'll re-analyze that after reading the papers.  Tsuyoshi Ito you are right. The subset of the clauses would be referred not only to the original clauses but to the set of clauses that can be deduced from the original program.  
> **username_2**: @TsuyoshiIto: you are right, but perhaps posting the signposts on the edges of the cliff has helped Trylks to find which road was actually desired.  
> **username_0**: After reading the papers I think this doesn't apply. Datalog program containment is undecidable, so I cannot verify the correctness for an arbitrary output, but my output is not arbitrary, if I can proof every step is correct then the result must be correct as well. Some transformations are valid and that (at least) seems fairly provable.  

---

### Answer by username_3 on 2012-01-10. Score: 0

Search for [transitive reduction](http://en.wikipedia.org/wiki/Transitive_reduction) of a directed graph.

> **Comments:**
> **username_0**: I've updated the original example to contain a conjunction. I thought about the dominator tree, but could not find a good way to apply it either. Sorry if I was unclear about this.  
> **username_3**: Sorry, I had not understood your question...  I don't understand how the example works. It seems like we can't discard any clauses. Where am I wrong?  
> **username_0**: If we have a datalog program with the four clauses we can discard the fourth, because it can be derived from the other three.  

---

