Minimize a datalog program

Question

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.

Answer 1

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.

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

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.

Answer 2

Search for transitive reduction of a directed graph.