Foundations and Trends® in Databases > Vol 5 > Issue 2

Datalog and Recursive Query Processing

By Todd J. Green, LogicBlox Inc., USA, todd.green@logicblox.com | Shan Shan Huang, LogicBlox Inc., USA, ssh@logicblox.com | Boon Thau Loo, University of Pennsylvania, USA, boonloo@cis.upenn.edu | Wenchao Zhou, Georgetown University, USA, wzhou@cs.georgetown.edu

 
Suggested Citation
Todd J. Green, Shan Shan Huang, Boon Thau Loo and Wenchao Zhou (2013), "Datalog and Recursive Query Processing", Foundations and TrendsĀ® in Databases: Vol. 5: No. 2, pp 105-195. http://dx.doi.org/10.1561/1900000017

Publication Date: 21 Nov 2013
© 2013 T. J. Green, S. Huang, B. T. Loo, and W. Zhou
 
Subjects
Data Models and Query Languages,  Deductive Databases,  Query Processing and Optimization,  Database theory
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction 
2. Language and Semantics 
3. Recursive Query Processing 
4. Incremental Maintenance 
5. Datalog Extensions 
6. Applications 
Acknowledgements 
References 

Abstract

In recent years, we have witnessed a revival of the use of recursive queries in a variety of emerging application domains such as data integration and exchange, information extraction, networking, and program analysis. A popular language used for expressing these queries is Datalog. This paper surveys for a general audience the Datalog language, recursive query processing, and optimization techniques. This survey differs from prior surveys written in the eighties and nineties in its comprehensiveness of topics, its coverage of recent developments and applications, and its emphasis on features and techniques beyond "classical" Datalog which are vital for practical applications. Specifically, the topics covered include the core Datalog language and various extensions, semantics, query optimizations, magic-sets optimizations, incremental view maintenance, aggregates, negation, and types. We conclude the paper with a survey of recent systems and applications that use Datalog and recursive queries.

DOI:10.1561/1900000017
ISBN: 978-1-60198-752-5
106 pp. $75.00
Buy book (pb)
 
ISBN: 978-1-60198-753-2
106 pp. $115.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Language and Semantics
3. Recursive Query Processing
4. Incremental Maintenance
5. Datalog Extensions
6. Applications
Acknowledgements
References

Datalog and Recursive Query Processing

In recent years, we have witnessed a revival of the use of recursive queries in a variety of emerging application domains such as data integration and exchange, information extraction, networking, and program analysis. A popular language used for expressing these queries is Datalog.

Datalog and Recursive Query Processing surveys for a general audience the Datalog language, recursive query processing, and optimization techniques. It differs from prior surveys written in the eighties and nineties in its comprehensiveness of topics, its coverage of recent developments and applications, and its emphasis on features and techniques beyond "classical" Datalog which are vital for practical applications. Specifically, the topics covered include the core Datalog language and various extensions, semantics, query optimizations, magic-sets optimizations, incremental view maintenance, aggregates, negation, and types. It concludes with a survey of recent systems and applications that use Datalog and recursive queries.

Datalog and Recursive Query Processing provides an accessible and gentle introduction to Datalog and recursive query processing to readers with some basic background in databases (in particular, SQL and the relational model).

 
DBS-017