What are the best references for self study in DATALOG? I am particularly interested in expressive power, complexity results, evaluation methods, extensions of DATALOG with negation etc. Are there any books or papers that cover all these?

  • 1
    $\begingroup$ An important relatively recent complexity paper related to DATALOG that comes to my mind is (though perhaps you are looking for surveys only): A. Atserias. On Sufficient Conditions for Unsatisfiability of Random Formulas, Journal of the ACM, 51(2), pages 281-311, 2004. $\endgroup$ Mar 21, 2011 at 5:45

2 Answers 2


Most of what you are looking for is well-covered in the survey

  • Stefano Ceri, Georg Gottlob, and Letizia Tanca, What you always wanted to know about Datalog (and never dared to ask), IEEE Transactions on Knowledge and Data Engineering 1 146–166, 1989. (link, reprint)

and its references. The field then went fairly quiet for a long time.

Recently various extensions to Datalog have been gaining a lot of attention, and the Datalog 2.0 conference in 2010 was well-attended. I'm personally quite partial to the Datalog± family of extensions, since they allow several kinds of description logics to be captured in a well-behaved and well-understood fragment of classical logic:

  • Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz, Datalog±: a unified approach to ontologies and integrity constraints, ICDT 2009, 14–30. (link)

The standard reference (more complete and up to date than the Ceri et al survey) is Foundations of Databases by Abiteboul, Hull, and Vianu. (Happily, Addison-Wesley has given the authors permission to post the PDFs online.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.