Comprehensive survey of recursive query processing and optimization techniques using Datalog
Authors: Todd J. Green, Shan Shan Huang, Boon Thau Loo, Wenchao Zhou. 2013.
In Foundations and Trends in Databases Vol. 5 No. 2.
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.
Read the PDF: Comprehensive survey of recursive query processing and optimization techniques using Datalog (opens in a new tab)
Related Posts
Functional Aggregate Query (FAQ): Questions Asked Frequently
We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical models and logic. This is our main conceptual contribution.
Design and Implementation of the LogicBlox System
The LogicBlox system aims to reduce the complexity of software development for modern applications which enhance and automate decision-making and enable their users to evolve their capabilities via a “self-service” model.