Eh, to be honest I don't really know a substantial amount about Datalog. My
specialty is Inductive Logic Programming and I'm interested in Datalog because
it's decidability makes it a convenient represantation language for
machine-learned logic programs. A very simple version of Datalog is sufficient
for my purposes so I haven't really dabbled much in variations or more modern
versions.

So I might well be wrong about decidability depending on the absence of
negation. Now that I think of it again, the problem with negation, in particular
the negation-as-failure (NAF) in Prolog, is that it breaks the monotonicity of
inference. Monotonicity in this context means that the model of a logic program
(the set of facts that are immediate consequences of the facts and rules in the
program, and that are derived in a bottom-up fashion with a TP operator, in
let's say "traditional" Datalog) can only increase with the introduction of new
facts. With NAF, this is not the case -introduction of a new fact may make a
previously derived true fact now false. So maybe the problem with negation, at
least NAF, is that it breaks the soundness of the inference procedure because
facts already derived as true become false when new facts are derived.

I give a (very crude, sorry) example of how Datalog's bottom-up evaluation works
in an earlier comment:

https://news.ycombinator.com/item?id=26522737

In short, bottom-up evaluation proceeds in discrete steps where at each step a
new set of facts is derived from the facts and rules known so-far. Newly derived
facts are added to the program so the set of facts in the program increases
until no new facts can be derived. Without NAF, when a new set of facts is
derived and added to the program, the truth value of already derived facts
cannot change. But _with_ NAF, bottom-up evaluation may introduce a new fact in
step k that makes a fact derived in step k - j false. So now we have an unsound
derivation procedure.

I wonder if this unsoundness actually translates to undecidability. Suppose the
above happens - we introduce a new fact A and some existing fact B becomes
false. What can we do to avoid this? Well, we can't know the truth value of B
after the derivation of A before actually deriving A (because we don't know the
truth of A before we can derive it), so we can't avoid deriving A. What we can
do is go back and re-evaluate the truth of each derived fact, find that B is now
false, and remove it from the program. But what if removing B allows a new fact,
C, to be derived which was previously false because of B, and C is such that A
is now false? Well, A cannot be derived given C, and without A we must derive B.
Which means we have to get rid of C again and allow A back in. So now we're
stuck in a loop.

I don't know if this is actually something that can happen or not, I was just
thinking through the problem right now given your question, so I may be talking
nonsense. In any case, if there is such a problem with NAF, then maybe modern
datalogs have a different negation scheme, allowing classical negation (as does
Answer Set Programming). But I really don't know about that, hence my question
to the OP about the kind of negation they mean.

Which was a genuine question btw! I really don't know how modern Datalogs work.

Anyway I'll go check a few sources and see if my sketch proof of undecidability
above makes any sense and I'll come back to let you know what I find :)