Repository logo
 

Automatic reordering for dataflow safety of Datalog

Accepted version
Peer-reviewed

Type

Conference Object

Change log

Authors

Contrastin, MIstral 
Rice, AC 
Orchard, Dominic 

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 can transform an ill-moded program into a well-moded program by reordering clause subgoals, satisfying dataflow requirements. We describe an incremental algorithm which efficiently finds a reordering if it exists. This frees the programmer to focus on the declarative specification of their program rather than on the implementation details of external predicates. We prove that our computed reorderings yield well-moded programs (soundness) and that if a program can be made well-moded, we compute a reordering to do so (completeness).

Description

Keywords

46 Information and Computing Sciences, 4612 Software Engineering

Journal Title

Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming

Conference Name

20th International Symposium on Principles and Practice of Declarative Programming

Journal ISSN

Volume Title

Publisher

Association for Computing Machinery
Sponsorship
Engineering and Physical Sciences Research Council (EP/M026124/1)
This work was supported by the EPSRC [grant number EP/M026124/1]