>> The other factor we need to consider is that the polynomial data complexity
of Datalog is based on the most basic form, which doesn’t have function symbols
(ie datatypes like lists) or arithmetic. Once you start adding such features
(which almost all real-world Datalogs do), the data complexity inevitably goes
up.

The informal definition of Datalog is that it is a decidable subset of Prolog,
or a pure set of Prolog, etc, but I think it's more accurate to say that datalog
clauses are a subset of the definite clauses such that a definite clause, C, is
datalog if and only if a) C has no functions other than constants and b) every
variable in the head literal of C is shared with a literal in the body of C.

For example, below, C is datalog, D and E are not:

C = P(x,y) ← Q(x,z), R(z,y) % datalog
D = P(x,y) ← Q(x,z) % z is not shared with head(D)
E = P(x,y) ← Q(f(x),z), R(z,y) % f(x) is not a constant function.

Note that Prolog programs are sets of definite clauses, but without the
restrictions (a) and (b) of datalog.

As the article points out, lists need functions, so for example p([H|T], H) is
not datalog because [H|T] is a function, and for arithmetic n(s(0)) is not
datalog because s(0) is a function.

So what's up with functions? In logic programming a function is a function
symbol followed by n terms, where n is the arity of the function symbol, so if
f(x,y) is a function then f is a function symbol with arity 2. Unlike in
imperative programming, functions in logic programming _are not replaced by
their values_, instead the truth of a formula containing functions is calculated
by substituting the variables in the function. So f(x) can become f(a), f(b)
etc. where a and b are constants. Problem is, variables in logic programming can
be substituted for arbitrary terms and functions themselves are terms, so given
the function symbol f of arity 1 we can make an infinite number of functions:
f(x), f(f(x)), f(f(f(x))), f(f(f(f(x)))), etc. That's one important reason for
the undecidability of First Order Logic (FOL). Definite logic, the logic of
definite clauses, which is a restriction of FOL, is _semi_ decidable, meaning
that if a theorem doesn't have a proof, there is no way to know in finite time.
Datalog doesn't have functions so it removes this particular source of
undecidability. If, in addition to not having functions, the Herbrand Universe
(the set of all constants) is finite, then datalog is decidable, informally
because every proof can only replace the variables in a program with a finite
set of constants, which means there's a finite set of proofs for every program.

What about the requirement that the head literal shares variables with the body
literals? That's to ensure that the entire datalog program can be ground.
Datalog is evaluated "bottom up" meaning that literals in the body are ground
before literals in the head, so in a clause like D above, even if Q(x,z) is
grounded during evaluation, the variable y in the head of the clause cannot be
grounded because it's not shared with the body. Which means that we can't prove
that P(x,y) is a consequence of Q(x,z). In a clause like C, on the other hand,
we can ground every variable by grounding the literals in the body and so
bottom-up evaluation is possible. Bottom-up evaluation is desired because it
avoids left-recursions and it makes the ordering of clauses irrelevant for the
proof of a program, unlike in Prolog. This is an attractive property of datalog.

Now, about functions, the Inductive Logic Programming community knows a few
tricks to retain the decidability of datalog programs even with functions. The
sneakiest such trick is "flattening" where functions are "hidden" away from the
datalog clauses. For instance, instead of writing:

member(X, [X|Xs]) ← ...

With flattening we can write:

member(X, Xs) ← head(Xs,X), ...

Where "head" is defined as head([X|Xs],X). With flattening we can keep some
parts of the program datalog and the rest definite, and so have our cake and eat
it.