Compiling data-parallel Datalog

Thomas Gilray, Sidharth Kumar, Kristopher Micinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Datalog allows intuitive declarative specification of logical inference tasks while enjoying efficient implementation via state-of-the-art engines such as LogicBlox and Soufflé. These engines enable high-performance implementation of complex logical tasks including graph mining, program analysis, and business analytics. However, all efficient modern Datalog solvers make use of shared memory, and present inherent challenges scalability. In this paper, we leverage recent insights in parallel relational algebra and present a methodology for constructing data-parallel deductive databases. Our approach leverages recent developments in parallelizing relational algebra to create an efficient data-parallel semantics for Datalog. Based on our methodology, we have implemented the first MPI-based data-parallel Datalog solver. Our experiments demonstrate comparable performance and improved single-node scalability versus Soufflé, a state-of-art solver.

Original languageEnglish (US)
Title of host publicationCC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction
EditorsAaron Smith, Aaron Smith, Delphine Demange, Rajiv Gupta
PublisherAssociation for Computing Machinery, Inc
Pages23-35
Number of pages13
ISBN (Electronic)9781450383257
DOIs
StatePublished - Mar 2 2021
Event30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021 - Virtual, Online, Korea, Republic of
Duration: Mar 2 2021Mar 3 2021

Publication series

NameCC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction

Conference

Conference30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021
CountryKorea, Republic of
CityVirtual, Online
Period3/2/213/3/21

Keywords

  • Datalog
  • Logic
  • Parallelism
  • Relational Algebra

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Signal Processing

Fingerprint Dive into the research topics of 'Compiling data-parallel Datalog'. Together they form a unique fingerprint.

Cite this