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. Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming, . (doi:10.1145/3236950.3236954) (KAR id:68499)

PDF Author's Accepted Manuscript
Language: English
Download (1MB) Preview
[thumbnail of article.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


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: Article
DOI/Identification number: 10.1145/3236950.3236954
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: Organisations -1 not found.
Depositing User: Dominic Orchard
Date Deposited: 06 Aug 2018 09:22 UTC
Last Modified: 09 Dec 2022 19:15 UTC
Resource URI: (The current URI for this page, for reference purposes)
Orchard, Dominic A.:
  • Depositors only (login required):


Downloads per month over past year