Datalog as a Lingua Franca for Provenance Querying and Reasoning

Provenance, i.e., the lineage and processing history of data, has become increasingly important within scientific workflow systems. Provenance information can be used, e.g., to explain, debug, and reproduce the results of computational experiments as well as to determine the validity and quality of data products. Standard models for representing provenance information (such as OPM) largely focus on providing a minimal, common set of observables and constraints (in terms of causal and temporal relationships). For scientific workflow applications, however, the workflow itself and the corresponding (implicit) contraints on provenance relationships are often essential for interpreting and querying provenance information. In this paper, we propose Datalog as a “lingua franca” for representing, querying, and specifying integrity constraints over provenance information, and introduce a unifying provenance model for specifying workflows, traces, and temporal constraints. We also demonstrate advantages of using Datalog together with the unified model through a number of examples.