Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what abstract machine does it model?
What problems are solvable in Datalog?
computation models;chomsky hierarchy
According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine or an EXPTIME RAM machine.