A formal account of the open provenance model

To the provenance community,

Natalia, Jan and myself are pleased to announce the availability of the
following paper, which can be downloaded from 
http://eprints.ecs.soton.ac.uk/21819/


A formal account of the open provenance model.
Natalia Kwasnikowska, Luc Moreau, and Jan Van den Bussche.

The Open Provenance Model (OPM) is a community data model for provenance 
that is designed to facilitate the meaningful interchange of provenance 
information between systems. Underpinning OPM, is a notion of directed 
graph, used to represent data products and processes in- volved in past 
computations, and dependencies between them; it is complemented by 
inference rules allowing new dependencies to be derived. The Open 
Provenance Model was designed from requirements captured in two 
`Provenance Challenges', and tested during the third: these challenges 
were international, multi-disciplinary activities aiming to exchange 
provenance information between multiple systems and query it. The design 
of OPM was mostly driven by practical and pragmatic considerations. The 
purpose of this paper is to formalize the theory underpinning this data 
model. Specifically, this paper proposes a temporal semantics for OPM 
graphs, defined in terms of a set of ordering constraints between 
time-points associated with OPM constructs. OPM inferences are 
characterized with respect to this temporal semantics, and a novel set 
of patterns is introduced to establish soundness and completeness 
properties. Building on this novel foundation, the paper proposes new 
definitions for graph algebraic operations, graph refinement and the 
notion of account, by which multiple descriptions of a same execution 
are allowed to co-exist in a same graph. Overall, this paper provides a 
strong theoretical underpinning to a data model being adopted by a 
community of users that help its disambiguation and promote 
inter-operability.

Best regards,
Natalia, Jan and Luc

-- 
Professor Luc Moreau
Electronics and Computer Science   tel:   +44 23 8059 4487
University of Southampton          fax:   +44 23 8059 2865
Southampton SO17 1BJ               email: l.moreau@ecs.soton.ac.uk
United Kingdom                     http://www.ecs.soton.ac.uk/~lavm