4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 13 '12 at 12:05
  • $\begingroup$ 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). $\endgroup$ – Trylks Jan 14 '12 at 20:20
  • $\begingroup$ 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. $\endgroup$ – Trylks Jan 18 '12 at 14:20
  • 3
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 18 '12 at 21:14
  • 1
    $\begingroup$ 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.) $\endgroup$ – András Salamon Jan 19 '12 at 20:19
6
$\begingroup$

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

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 (preprint)

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.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 14 '12 at 13:24
  • $\begingroup$ 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. $\endgroup$ – Trylks Jan 14 '12 at 20:09
  • $\begingroup$ @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. $\endgroup$ – András Salamon Jan 15 '12 at 9:10
  • $\begingroup$ 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. $\endgroup$ – Trylks Jan 18 '12 at 14:18
0
$\begingroup$

Search for transitive reduction of a directed graph.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Trylks Jan 10 '12 at 13:09
  • $\begingroup$ 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? $\endgroup$ – Dmytro Korduban Jan 10 '12 at 15:38
  • 1
    $\begingroup$ If we have a datalog program with the four clauses we can discard the fourth, because it can be derived from the other three. $\endgroup$ – Trylks Jan 11 '12 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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