Compiling data-parallel Datalog

Thomas Gilray; Sidharth Kumar; Kristopher Micinski

doi:10.1145/3446804.3446855

Compiling data-parallel Datalog

Thomas Gilray, Sidharth Kumar, Kristopher Micinski

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference contribution

4 Scopus citations

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 language	English (US)
Title of host publication	CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction
Editors	Aaron Smith, Aaron Smith, Delphine Demange, Rajiv Gupta
Publisher	Association for Computing Machinery, Inc
Pages	23-35
Number of pages	13
ISBN (Electronic)	9781450383257
DOIs	https://doi.org/10.1145/3446804.3446855
State	Published - Mar 2 2021
Event	30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021 - Virtual, Online, Korea, Republic of Duration: Mar 2 2021 → Mar 3 2021

Publication series

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

Conference

Conference	30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021
Country/Territory	Korea, Republic of
City	Virtual, Online
Period	3/2/21 → 3/3/21

Keywords

Datalog
Logic
Parallelism
Relational Algebra

ASJC Scopus subject areas

Software
Hardware and Architecture
Signal Processing

Access to Document

10.1145/3446804.3446855

Cite this

Gilray, T., Kumar, S., & Micinski, K. (2021). Compiling data-parallel Datalog. In A. Smith, A. Smith, D. Demange, & R. Gupta (Eds.), CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction (pp. 23-35). (CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction). Association for Computing Machinery, Inc. https://doi.org/10.1145/3446804.3446855

Compiling data-parallel Datalog. / Gilray, Thomas; Kumar, Sidharth; Micinski, Kristopher.
CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction. ed. / Aaron Smith; Aaron Smith; Delphine Demange; Rajiv Gupta. Association for Computing Machinery, Inc, 2021. p. 23-35 (CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Gilray, T, Kumar, S & Micinski, K 2021, Compiling data-parallel Datalog. in A Smith, A Smith, D Demange & R Gupta (eds), CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction. CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction, Association for Computing Machinery, Inc, pp. 23-35, 30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021, Virtual, Online, Korea, Republic of, 3/2/21. https://doi.org/10.1145/3446804.3446855

Gilray T, Kumar S, Micinski K. Compiling data-parallel Datalog. In Smith A, Smith A, Demange D, Gupta R, editors, CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction. Association for Computing Machinery, Inc. 2021. p. 23-35. (CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction). doi: 10.1145/3446804.3446855

Gilray, Thomas ; Kumar, Sidharth ; Micinski, Kristopher. / Compiling data-parallel Datalog. CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction. editor / Aaron Smith ; Aaron Smith ; Delphine Demange ; Rajiv Gupta. Association for Computing Machinery, Inc, 2021. pp. 23-35 (CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction).

@inproceedings{d11e2440ea4347bc862b1ec98afc7832,

title = "Compiling data-parallel Datalog",

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{\'e}. 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{\'e}, a state-of-art solver.",

keywords = "Datalog, Logic, Parallelism, Relational Algebra",

author = "Thomas Gilray and Sidharth Kumar and Kristopher Micinski",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021 ; Conference date: 02-03-2021 Through 03-03-2021",

year = "2021",

month = mar,

day = "2",

doi = "10.1145/3446804.3446855",

language = "English (US)",

series = "CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction",

publisher = "Association for Computing Machinery, Inc",

pages = "23--35",

editor = "Aaron Smith and Aaron Smith and Delphine Demange and Rajiv Gupta",

booktitle = "CC 2021 - Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction",

}

TY - GEN

T1 - Compiling data-parallel Datalog

AU - Gilray, Thomas

AU - Kumar, Sidharth

AU - Micinski, Kristopher

PY - 2021/3/2

Y1 - 2021/3/2

N2 - 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.

AB - 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.

KW - Datalog

KW - Logic

KW - Parallelism

KW - Relational Algebra

UR - http://www.scopus.com/inward/record.url?scp=85102291537&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85102291537&partnerID=8YFLogxK

U2 - 10.1145/3446804.3446855

DO - 10.1145/3446804.3446855

M3 - Conference contribution

AN - SCOPUS:85102291537

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

SP - 23

EP - 35

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

A2 - Smith, Aaron

A2 - Demange, Delphine

A2 - Gupta, Rajiv

PB - Association for Computing Machinery, Inc

T2 - 30th ACM SIGPLAN International Conference on Compiler Construction, CC 2021

Y2 - 2 March 2021 through 3 March 2021

ER -

Compiling data-parallel Datalog

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this