Skip to main content

Automatic reordering for dataflow safety of Datalog

Contrastin, Mistral, Orchard, Dominic A., Rice, Andrew C. (2018) Automatic reordering for dataflow safety of Datalog. In: Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. . ACM ISBN 978-1-4503-6441-6. (doi:10.1145/3236950.3236954)

PDF - Author's Accepted Manuscript
Download (371kB)
[img]
Official URL
http://dx.doi.org/10.1145/3236950.3236954

Abstract

Clauses and subgoals in a Datalog program can be given in any order without affecting program meaning. However, practical applications of the language require the use of built-in or external predicates with particular dataflow requirements. These can be expressed as input or output “modes” on arguments. We describe a static analysis of moding for Datalog which calculates how to transform an ill-moded program into a well-moded program by reordering clause subgoals to satisfy dataflow requirements. We de- scribe an incremental algorithm which efficiently finds a reordering if it exists. This frees the programmer to focus on the declarative specification of a program rather than implementation details of external predicates. We prove that our computed reorderings yield well-moded programs (soundness) and if a program can be made well-moded, then we compute a reordering to do so (completeness).

Item Type: Conference or workshop item (Proceeding)
DOI/Identification number: 10.1145/3236950.3236954
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Faculties > Sciences > School of Computing
Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Dominic Orchard
Date Deposited: 06 Aug 2018 09:22 UTC
Last Modified: 29 May 2019 20:58 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/68499 (The current URI for this page, for reference purposes)
Orchard, Dominic A.: https://orcid.org/0000-0002-7058-7842
  • Depositors only (login required):

Downloads

Downloads per month over past year