  Provenance refers to the documentation of an object's lifecycle. This
documentation (often represented as a graph) should include all the information
necessary to reproduce a certain piece of data or the process that led to it.
In a dynamic world, as data changes, it is important to be able to get a piece
of data as it was, and its provenance graph, at a certain point in time.
Supporting time-aware provenance querying is challenging and requires: (i)
explicitly representing the time information in the provenance graphs, and (ii)
providing abstractions and efficient mechanisms for time-aware querying of
provenance graphs over an ever growing volume of data. The existing provenance
models treat time as a second class citizen (i.e. as an optional annotation).
This makes time-aware querying of provenance data inefficient and sometimes
inaccessible. We introduce an extended provenance graph model to explicitly
represent time as an additional dimension of provenance data. We also provide a
query language, novel abstractions and efficient mechanisms to query and
analyze timed provenance graphs. The main contributions of the paper include:
(i) proposing a Temporal Provenance Model (TPM) as a timed provenance model;
and (ii) introducing two concepts of timed folder, as a container of related
set of objects and their provenance relationship over time, and timed paths, to
represent the evolution of objects tracing information over time, for analyzing
and querying TPM graphs. We have implemented the approach on top of FPSPARQL, a
query engine for large graphs, and have evaluated for querying TPM models. The
evaluation shows the viability and efficiency of our approach.
