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?
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.)