How hard is it?

Termination is not enough; we want it cheap. Two ways to measure:

Data complexity (program fixed, data grows): PTIME-complete, polynomial in the size of the database.
Combined complexity (program and data both grow): EXPTIME-complete, since a program with k variables per rule ranges over up to nᵏ tuples.

Datalog is well balanced: it adds recursion to database queries, yet stays tractable in the data. With stratified negation and an order on the data, it captures exactly the polynomial-time queries.