Modelling Provenance using Structured Occurrence Networks

Abstract. Occurrence Nets (ON) are directed acyclic graphs that repre-sent causality and concurrency information concerning a single execution of a system. Structured Occurrence Nets (SONs) extend ONs by adding new relationships, which provide a means of recording the activities of multiple interacting, and evolving, systems. Although the initial moti-vations for their development focused on the analysis of system failures, their structure makes them a natural candidate as a model for express-ing the execution traces of interacting systems. These traces can then be exhibited as the provenance of the data produced by the systems under observation. In this paper we present a number of patterns that make use of SONs to provide principled modelling of provenance. We discuss some of the benefits of this modelling approach, and briefly compare it with others that have been proposed recently. SON-based modelling of prove-nance combines simplicity with expressiveness, leading to provenance graphs that capture multiple levels of abstraction in the description of a process execution, are easy to understand and can be analysed using partial order techniques underpinning their behavioural semantics.