Datalog

Datalog is the functor-free subset of pure Prolog. Yes, of Prolog. Datalog resides in the intersection of several interesting topics such as logic, database theory, complexity theory and universal algebra. Datalog is a very convenient database and query language, and can express practically relevant queries that relational algebra cannot express. Datalog is also a programming language: Its program complexity is EXPTIME-complete, which means that Datalog can express a vast number of algorithms with at most polynomial overhead. Various extensions make it even more expressive and useful.

Recommended reading about the expressive power and complexity of Datalog:

Markus Krötzsch, Database Theory, Lecture 10: Expressive Power and Complexity of Datalog, https://iccl.inf.tu-dresden.de/w/imag...

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and Expressive Power of Logic Programming, https://web.archive.org/web/201708081...