Minimize a datalog program
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.