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.