FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Declarative Algorithms in Datalog with Aggregates: user-friendly formal semantics conducive to performance and scalability

Authors: Carlo Zaniolo, Ariyam Das, Mohan Yang, Alex Shkapsky, Matteo Interlandi and Tyson Condie

Paper Information

Title:Declarative Algorithms in Datalog with Aggregates: user-friendly formal semantics conducive to performance and scalability
Authors:Carlo Zaniolo, Ariyam Das, Mohan Yang, Alex Shkapsky, Matteo Interlandi and Tyson Condie
Proceedings:ICLP Proceedings of ICLP 2018
Editors: Paul Tarau and Alessandro Dal Palu'
Keywords:Datalog, Declarative Algorithms, Aggregates, NonMonotonic Semantics
Abstract:

ABSTRACT. Pre-mappable (PreM ) extrema constraints in recursive Datalog programs enable concise declarative formulations for classical algorithms (Zaniolo et al. 2017). The programs expressing these algorithms have formal non- monotonic semantics with efficient and scalable support on multiple platforms (Shkapsky et al. 2016) (Yang et al. 2017). However proving PreM for different programs can be challenging for programmers; thus, in this paper, we introduce simple templates that allow users to verify with ease that their programs have the PreM property along with the rigorous semantics and the efficient and scalable implementation associated with it. We thus obtain simple declarative formulation for classical algorithms in two equivalent versions: one with perfect model semantics and the other with stable model semantics.

Pages:19
Talk:Jul 17 17:45 (Session 123: Technical Communications II)
Paper: