\documentclass[11pt,a4paper]{ivoa}
\input tthdefs

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}    % for nicer _
\usepackage{booktabs, tabulary}    % for nicer tables
\usepackage{verbatimbox}  % for smaller font size etc.

% make the text in pdf properly searchable
\usepackage{lmodern}

% use listings for including text files and code snippets
\usepackage{listings}

\title{ProvenanceDM Implementation Note}

\ivoagroup{DM}

\author{Kristin Riebe}
\author{Mathieu Servillat}
\author{François Bonnarel}
%\author{Anastasia Galkin}
\author{Mireille Louys}
\author{Michèle Sanguillon}
%\author{Ole Streicher}
\author{IVOA Data Model Working Group}

\editor{Kristin Riebe}
\editor{Mathieu Servillat}

\previousversion[]{no previous versions yet}

% own definitions
\definecolor{todocolor}{rgb}{1,1,0.8}
\definecolor{darkred}{rgb}{0.6,0,0}
\definecolor{rose}{rgb}{1.0,0.88,0.88}
\definecolor{darkgrey}{rgb}{0.35,0.35,0.35}

\newcommand{\TODO}[1]{%
    \noindent%
    \colorbox{todocolor}{%
            \parbox{0.85\linewidth}{\sffamily \textbf{TODO:}\\
            #1}
    }%
    \vspace{2pt}

}

\newcommand{\note}[1]{%
    \noindent%
    \textcolor{darkgrey}{{\sffamily Note:} \emph{#1}}%
}


\newcommand{\paragraphlb}[1]{\paragraph{#1}\mbox{}\\} % paragraph with line break

\setlength{\fboxsep}{5pt}
%\setlength{\fboxrule}{1.5pt}
\newcommand{\warning}[1]{%
    \vspace{\baselineskip}
    \noindent
    \parbox{\linewidth}{%
        \colorbox{darkred}{%
            \parbox{0.7\linewidth}{\large \sffamily \textcolor{white}{Warning}}%
        }\\[-1pt]
        \noindent%
        \fcolorbox{darkred}{rose}{%
            \parbox{0.7\linewidth-2\fboxrule}{#1}%
        }%
    }%
    \vspace{\baselineskip}
}%

% for nicer tables:
\renewcommand{\arraystretch}{1.3}
\newcommand{\head}[1]{\textbf{#1}}


% define new command for classes, in case we decide later on for a different style
\newcommand{\class}[1]{\emph{#1}}
\newcommand{\attribute}[1]{\texttt{#1}}
\newcommand{\attr}[1]{\texttt{#1}} % equivalent to \attribute


\begin{document}
\newcolumntype{Y}{>{\raggedright\arraybackslash}X}

\begin{abstract}
\TODO{This document is still very preliminary and may change any time.}

This document collects use cases, guidelines and implementation notes for the IVOA Provenance Data Model as described in \citet{std:ProvenanceDM}. It contains details on the used classes and attributes for each use case, design decision, problems and open issues. It is separated from the standard document for IVOA Provenance, since it contains non-normative information.
% and now it can be updated without affecting the standard.

\end{abstract}


\section{How to use the data model}

The IVOA Provenance Data Model has been developed along with its implementations from different projects. 
We gather here some tips to implement and use the model for a specific project.

% 2017-09-20 mireille's suggestion : classify the various paragraphs under main ideas in subsubsections 
%\subsubsection{Before using the model}
\paragraph{Before using the model}
We noticed that the simple knowledge of what is provenance information is important for the conception of all projects. Before using or not ProvenanceDM and associated services, it is good practice to locate and collect information on the activities, entities and agents that will be manipulated, and be sure that this information is not lost along the way. For example, a script may use intermediate files (such as calibration files for observations) that may not be tracked by the system.

%% 2017-09-20 mireille's suggestion :\subsubsection{Define unique identifiers}
\paragraph{Define unique identifiers}
It would be convenient if each data object or even each file 
gets a unique id that can be referenced. The W3C provenance model requires ids
for entities, activities and agents, and they have to be qualified strings, 
i.e. containing a namespace. For example, an activity in the RAVE-pipeline could 
have the id `\texttt{rave:radialvelocity\_pipeline\_20160901}'. 
Using a namespace for each 
project for these ids will help to make them unique. 
IVOIDs, DOI's or ORCIDs are potentially good candidates for unique identifiers.

%% 2017-09-20 mireille's suggestion : \subsubsection{Benefits of using description classes}
%% 2017-09-20 mireille's suggestion : %\paragraph{Use of the description classes} 
\paragraph{Use of the description classes} 
One may only use the core data model without the description classes if they are not needed for the project. In that case, it is recommended to merge the attributes of the description classes into the main classes (\class{Entity}/\class{Activity}/\class{Agent}, and if needed \class{Parameter}). In the same way, when serializing the provenance information, the description classes can be merged to the main classes, which is needed to produce W3C compliant provenance files.

\paragraph{Add project specific attributes to your entities, activities and agents}
We proposed generic attributes for the different classes, but there are probably project specific attributes that need to be added. 
It is also required at this level to disentangle \class{Entity} properties and \class{EntityDescription} properties: everything that you may know about an entity before its creation, belongs to the \class{EntityDescription} (e.g. file \attribute{format}, \attribute{content\_type}, \attribute{dataproduct\_type}, \attribute{category}, \dots).

\paragraph{Group common features for entities and/or activities}
If inside the project, the different entities that will be manipulated are already defined precisely, as well as the activities producing them, then the description classes are probably of interest and will help reducing
%2017-09-20 mireille's suggestion : help reducing
 the redundancy in the provenance information stored. 

\paragraph{Create ActivityDescription files}
A model using description classes to define templates for activities and
entities has an advantage for normalization: the common processes could be
described once and for all at some place and then be reused when recording
provenance information for certain entities and activities.
If description classes are relevant for a project, it may be sufficient to store the descriptions directly as \class{ActivityDescription} files.
% (see Section \ref{sec:description-serialization}). 
Those can be created and centralized before implementing a provenance database or service.

\paragraph{Link to an Authentication System}
We proposed to add optional attributes to the \class{Agent} class (email, phone, address). Some projects may include an authentication system with a user directory. In that case a link should be kept between the \class{Agent} identifiers and the ones used in the authentication system when it is relevant, and information should be synchronized. However, there may be some agents that are not defined in the authentication system, so the information may not be easy to merge.


\paragraph{Adding additional metadata to an existing Entity}
It could happen that after creating entities and storing their provenance, additional metadata is needed for those entities. For example, an ObsCoreDM description may have to be added to some entities when they are made available to the public. In that case, the entity will receive an external identifier (e.g. a \attribute{publisher\_did}), which should thus be associated to the entity provenance identifier (Entity.id) in a relation table.
% 2017-09-20 mireille's suggestion : add this sentence
This allows to match existing Ids between different data models metadata descriptions as highlighted in the mapping table in the standard document.
% \ref{tab:datasetmapping} in Section~\ref{sec:dmlinks}.



\section{\texttt{voprov} Python package}\label{sec:implementation_voprov}
The \texttt{voprov}\footnote{\url{https://github.com/sanguillon/voprov}} package is an open source Python library derived from the \texttt{prov} Python
library (MIT license) developed by Trung Dong Huynh (University of
Southampton). 

% 2017-09-20 mireille's suggestion :rewording and homgeneize the formats names
The \texttt{prov} package implements the W3C Provenance Data Model.  It offers to
describe the provenance and provides different output formats of the serialized data: PROV-N, PROV-JSON, PROV-XML and to build diagrams in the following graphic formats: PDF, PNG, SVG.

The \texttt{voprov} library allows users to describe the provenance of their data
according to the IVOA Provenance Data Model. It allows the description of flows
of activities (pipelines) with eventually the composition of the different
steps. It provides the VOTable serialization in PROV-VOTable format.

This library is currently used in the context of the POLLUX database which hosts
synthetic stellar spectra. The provenance files are created from the non
normalized information found in the Pollux header files. The serialization is
proposed in three levels of detail and in different formats: on one hand in PROV-N,
PROV-JSON, PROV-XML and PROV-VOTable formats and on the other hand in PDF, PNG and SVG graphic
formats. The VO user or the VO tool is informed of the existence of the
provenance in a DataLink entry of the Simple Spectral Access protocol (SSAP) response which gives information on
how to retrieve a given provenance file.

% 2017-09-20 mireille's suggestion :this could be shifted and detailed in the Implementation note as I mention above
%\subsubsection{Graphic formats}
%\label{sec:graphic_formats}
%The \texttt{voprov} Python module can also provide provenance information in graphic formats: PNG, SVG and PDF.
%In the above example, you have to add the following instructions in your Python program:
%
%\begin{verbatim}
    %dot = prov_to_dot(provdoc, use_labels=True)
    %dot.write_png('ex1.png')
    %dot.write_svg('ex1.svg')
    %dot.write_pdf('ex1.pdf')
%\end{verbatim}
%
%\begin{figure}
%\centering
%\includegraphics[width=0.9\textwidth]{access_ex1.png}
%\caption{Example: png format@}
%\label{fig:example}
%\end{figure}

The following is an example of a python program which describes the provenance and generates the different formats of serialization.
\begin{verbnobox}[\scriptsize]
import sys
from prov.model import ProvDocument
from prov.dot import prov_to_dot
import pdb

try:
    provdoc = ProvDocument()
    provdoc.add_namespace('prov', 'http://www.w3.org/ns/prov#')
    provdoc.add_namespace('voprov', 'http://www.ivoa.net/documents/dm/provdm/voprov/')
    provdoc.add_namespace('ivo', 'http://www.ivoa.net/documents/rer/ivo/')
    provdoc.add_namespace('hips', 'http://cds.u-strasbg.fr/data/')

    provdoc.entity('ivo://CDS/P/DSS2color#RGB_NGC6946',\
        {'voprov:name':'RGB DSS2 image for NGC 6946', \
         'voprov:annotation':'PNG RGB image for galaxy NGC 6946'})

    provdoc.entity('ivo://CDS/P/DSS2/POSSII#POSSII.J-DSS2.143',\
        {'voprov:name':'POSSII Blue Survey DSS2 NGC6946', \
         'voprov:annotation':'Blue POSSII Schmidt survey around NGC 6946'})

    provdoc.entity('ivo://CDS/P/DSS2/POSSII#POSSII.F-DSS2.143',\
        {'voprov:name':'POSSII Red Survey DSS2 NGC6946', \
         'voprov:annotation':'Red POSSII Schmidt survey around NGC 6946'})

    provdoc.entity('ivo://CDS/P/DSS2/POSSII#POSSII.N-DSS2.143',\
        {'voprov:name':'POSSII Infra Red Survey DSS2 NGC6946', \
         'voprov:annotation':'Infrared POSSII Schmidt survey around NGC 6946'})

    provdoc.activity('hips:AlaRGB1', '2017-04-18T17:28:00', '2017-04-19T17:29:00', \
          {'voprov:name':'Aladin RGB 1',\
           'voprov:annotation': 'Aladin RGB image generation for NGC 6946',\
           'voprov:desc_name': 'Aladin RGB image generation algorithm', \
           'voprov:desc_type': 'RGBencoding', \
           'voprov:desc_doculink':'http://aladin.u-strasbg.fr/aladin.gml'})

    provdoc.used('hips:AlaRGB1', 'ivo://CDS/P/DSS2/POSSII#POSSII.J-DSS2.143')
    provdoc.used('hips:AlaRGB1', 'ivo://CDS/P/DSS2/POSSII#POSSII.F-DSS2.143')
    provdoc.used('hips:AlaRGB1', 'ivo://CDS/P/DSS2/POSSII#POSSII.N-DSS2.143')

    provdoc.wasGeneratedBy('ivo://CDS/P/DSS2color#RGB_NGC6946', 'hips:AlaRGB1', '')

    f_out = open('ex1.json','w')
    f_out.write(provdoc.serialize(indent=2))
    f_out.close()
    f_out = open('ex1.provn','w')
    f_out.write(provdoc.get_provn())
    f_out.close()
    provdoc.serialize(format='xml', destination='ex1.xml')
    f_out = open('ex1.votable','w')
    f_out.write(provdoc.serialize(format='votable',indent=2))
    f_out.close()

except Exception, e:
        print("Error while writing the file : %s !" %str(e))
        sys.exit(1)

\end{verbnobox}





\section{Provenance for CTA}
The Cherenkov Telescope Array (CTA) is the next generation ground-based very high energy gamma-ray instrument. It will provide a deep insight into the non-thermal high-energy universe. Contrary to previous Cherenkov experiments, it will serve as an open observatory providing data to a wide astrophysics community, with the requirement to propose self-described data products to users that may be unaware of the Cherenkov astronomy specificities. The proposed structure of the metadata is presented in Figure~\ref{fig:cta_dm}.

\begin{figure}
\centering
\includegraphics[width=\textwidth]{CTA_DM_high_level.png}
\caption[CTA high level data model structure]{CTA high level data model structure with Pipeline stages and connection to IVOA ProvenanceDM.}
\label{fig:cta_dm}
\end{figure}

Cherenkov telescopes indirectly detect gamma-rays by observing the flashes of Cherenkov light emitted by particle cascades initiated when the gamma-rays interact with nuclei in the atmosphere. The main difficulty  is that charged cosmic rays also produce such cascades in the atmosphere, which represent an enormous background compared to genuine gamma-ray-induced cascades. Monte Carlo simulations of the shower development and Cherenkov light emission and detection, corresponding to many different observing conditions, are used to model the response of the detectors.  With an array of such detectors the shower is observed  from several points and, working backwards, one can figure out the origin, energy and time of the incident particle. The main stages of the CTA Pipeline are presented inside Figure~\ref{fig:cta_dm}. Because of this complexity in the detection process, provenance information of data products is necessary to the user to perform a correct scientific analysis.

Provenance concepts are relevant for different aspects of CTA:
\begin{itemize}
\item Data diffusion: the diffused data products have to contain all the relevant context information with the assumptions made as well as a description of the methods and algorithms used during the data processing.
\item Pipeline: the CTA Observatory must ensure that data processing is traceable and reproducible.
\item Instrument Configuration: the characteristics of the instrument at a given time have to be available and traceable (hardware changes, measurements of e.g. a reflectivity curve of a mirror, ...)
\end{itemize}

We tested the tracking of Provenance information during the data analysis using the Python \texttt{prov} package inside OPUS\footnote{\url{https://github.com/ParisAstronomicalDataCentre/OPUS}} (Observatoire de Paris UWS System), a job control system developed at PADC (Paris Astronomical Data Centre). This system has been used to run CTA analysis tools and provides a description of the Provenance in the PROV-XML or PROV-JSON serializations, as well as a graph visualization (see Figure~\ref{fig:cta_prov}).

\begin{figure}
\centering
\includegraphics[width=0.8\textwidth]{CTA_prov.png}
\caption[Provenance description of a CTA analysis step]{Provenance description of a CTA analysis step.}
\label{fig:cta_prov}
\end{figure}

The CTA Pipeline contains a specific Provenance class dedicated to the collection of provenance information after each processing step. This information is returned as an output file for now.




\section{Provenance for the POLLUX database}

POLLUX is a stellar spectra database proposing access to high resolution synthetic spectra computed using the best available models of atmosphere (CMFGEN, ATLAS and MARCS), performant spectral synthesis codes (CMF\_FLUX, SYNSPEC and TURBOSPECTRUM) and atomic line lists from VALD database and specific molecular line lists for cool stars. 

Currently the provenance information is given to the astronomer in the header of the spectra files (depending on the format: FITS, ASCII, XML, VOTable, ...) but in a non-normalized description format. 

The implementation of the provenance concepts in a standardized format allows users on one hand to benefit from tools to create, visualize and transform to another format the description of the provenance of these spectra and on a second hand to select data depending on provenance criteria. An example visualization of (W3C compatible) provenance metadata for a POLLUX spectrum is given in Figure~\ref{fig:pollux}.

\begin{figure}
\centering
\includegraphics[width=0.9\textwidth]{usecase_Pollux_example1.png}
\caption[Example for provenance metadata for a POLLUX spectrum]{Example for provenance metadata for a POLLUX spectrum, produced from a W3C compatible format (e.g. using \texttt{prov:startTime} instead of \texttt{voprov:startTime}).}
\label{fig:pollux}
\end{figure}



\section{Provenance of HiPS datasets}
HiPS \citep{std:HiPs} is an IVOA recommendation for a new hierarchical
organization of pixel data, allowing smooth browsing of all-sky data collections
in astronomy. It is based on the HEALPix tesselation of the sky into equal-area
cells for a given HEALPix order, where each cell is given an image tile.
Adaptative resolution is achieved by a hierarchy of tiles at increasing
order. Sorting and organization is based on a tree of nested directories, each
of which is associated with a tile. In the processing chain, HiPS can be seen
as a kind of ``legacy level'' for observational data.


A HiPS dataset can be generated either by Aladin in ``hipsgen'' mode or by other
software.
%\cite{if others}.  
The processing distinguishes 3 main different methods for estimating cell values
with parameters: FIRST (nearest neighbour), MEAN, and MEDIAN of the neighbouring
pixels. Up to 50 parameters can help to tune the processing, among them the
highest resolution's HEALPix order, the sky background value to be substracted,
the border width or the mask to apply to original images in order to avoid
including bad areas, etc.


An example of provenance metadata for a HiPS collection generated from a
collection of SERC Schmidt plates scanned by CAI-Observatoire de Paris with the
MAMA facility and serialized in PROV-N format is given at \\
\url{http://wiki.ivoa.net/twiki/bin/view/IVOA/ProvSerialisationExample/HiPS-prov-provn.txt}, the corresponding VOTable-format is available at \\
\url{http://wiki.ivoa.net/twiki/bin/view/IVOA/ProvSerialisationExample/HiPS-prov-vot.xml}.

Here is an excerpt of the corresponding PROV-N serialization:

\begin{verbnobox}[\scriptsize]
prefix ivo <http://www.ivoa.net/documents/rer/ivo/>
prefix ex <http://www.example.com/provenance/>
prefix voprov <http://www.ivoa.net/documents/dm/provdm/voprov/>
prefix ds <http://www.ivoa.net/documents/dm/datasetdm/>
prefix hips <http://www.ivoa.net/documents/apps/hips/>

Entity
( ivo://CDS/P/MAMA/ESO-R, 
[ voprov:name = "ESO-R MAMA HIPS at CDS",
voprov:type= "voprov:entity",
voprov:annotation = "HiPS version of ESO Schmidt survey digitized by Mama and processed by CDS",
voprov:doculink = "http://cds.u-strasbg.fr/hips/documentation.html#structure",
ds:calibLlevel = 3,
ds:dataproduct_type = "voprov:hips_pixels",
ds:access_reference = "http://CDS/P/MAMA/ESO-R", // as defined in ObsCore and Dataset DM
hips:HiPS_properties = "http://cds.u-strasbg.fr/hips/p/mama/eso-r/properties.txt"] )

// Relationship
WasAttributedTo(ivo://CDS/P/MAMA/ESO-R, ivo://cds, voprov:role= "voprov:creator")

Agent
(ivo://cds,
[ voprov:name= "CDS",
voprov:email = "question@astro.unistra.fr",
voprov:type = "Organisation" ]) 

WasGeneratedBy  (ivo://CDS/P/MAMA/ESO-R, EHG1, -) 

Activity
(EHG1,
[ voprov:name = "ESO HiPS generation 1",
voprov:startTime = "2016-07-18", 
voprov:endTime = "2016-07-20",
voprov:annotation = "Final generation activity of HiPS for ESO Mama survey",
voprov:activityDescription = "HipsgenM"] )
 
ActivityDescription 
(HipsgenM,
[ voprov:name = "HiPSgen_Mean",
voprov:type = "data encoding",
voprov:subtype= "HiPSgen",
voprov:doculink = "http://cds.u-strasbg.fr/HiPSGEN-Documentation"])

WasAssociatedWith( EHG1, Buga, voprov:role="voprov:operator")
WasAssociatedWith(EHG1, ivo://CDS, voprov:role="voprov:creator")
WasAttributedTo(( ivo://CDS/P/MAMA/ESO-R, buga, voprov:role= "voprov:operator")
\end{verbnobox}



\section{Provenance for the RAVE project}
% General intro to project
The RAVE (RAdial Velocity Experiment) \footnote{\url{http://www.rave-survey.org/}} is a survey that observed the spectra of half a million stars from the southern hemisphere.
In a pipeline of several steps the data were calibrated, reduced and stellar properties
were determined, which were then released in the form of star catalogues. 

Providing provenance information, e.g. from which spectrum and fibre a 
dataset was coming from and which steps were involved in processing the data, can help scientists
to understand the data, the restrictions and judge the data quality.
It would also be useful to be able to compare if, how and why the derived data for some stars have changed between different releases.

%We put together some major steps of the RAVE pipeline in W3C-compatible PROV-N notation
%and uploaded the file to the Provenance Store\footnote{\url{https://provenance.ecs.soton.ac.uk/store/}}. This allows to view graphs of the workflow by visualizing only the main entities or activities and restricting the displayed relations. It shows that the provenance concepts explained in this draft can be applied directly to data obtained from astronomical observations.

%We also tested a Django implementation of the Provenance DM classes along with provenance metadata from the RAVE project stored in an SQLite database. 
%This allows to quickly setup a provenance web application for serving provenance data in order to allow users to track and understand the production of the final data products.


% with interfaces to view all instances of a class or details for a single object (REST API), extract provenance information for single entities and visualizing the provenance information using Javascript.

%track and understand the production of the final data products, we created a web application for
%serving provenance metadata.

\subsection{Django web application}
\paragraph{General information}
% General info on web application, database, used classes
We set up a web application by implementing the Provenance DM classes along with provenance metadata from the RAVE project
using the Django Python Web Framework\footnote{\url{https://www.djangoproject.com/}} and storing the metadata information in an SQLite database.
%This allows to quickly setup a provenance web application for serving provenance data in order to allow users to track and understand the production of the final data products.
In such a Django application, each class of the
Provenance Data Model can be implemented as a class (a Django ``model'') in the webapp. Django
automatically creates a database table for each class, with one column for each defined class
attribute. Figure~\ref{fig:rave-classes} shows the ProvenanceDM classes which were  implemented for this use case and exist as tables in the (SQLite) database of the webapp.

\begin{figure}[h]
\centering
\includegraphics[width=1.0\textwidth]{provenance-rave-django-models.pdf}
\caption{This figure shows the classes that were actually implemented in the
RAVE web application along with their attributes (light grey = optional) and
relations to each other. This figure was extracted directly from the web application using \texttt{manage.py graph\_models}. The full resolution image can be found in the volute
repository, \url{http://volute.g-vo.org/svn/trunk/projects/dm/provenance/implementation-note/provenance-rave-django-models.pdf}.}
\label{fig:rave-classes}
\end{figure}

We split the web application into two parts: a reusable package called
\texttt{django-prov\_vo}\footnote{\url{https://github.com/kristinriebe/djangp-prov_vo/}} and the main web application. The \texttt{django-prov\_vo}
package contains an implementation of the provenance classes, interfaces to access the
data and the functionality to serializa the complex provenance information into
different formats.

% -- Features
\paragraph{Features}
Using this Django web application, it is possible to rather quickly setup a provenance web service with the following features:

\begin{itemize}
\item List all instances of a class (e.g. all activities or all entities)
\item Show details for a single object (e.g. all the properties for a selected activity)
\item ProvDAL access to retrieve provenance information for a given entity, activity or agent identifier
\item Serialisation of provenance information into different formats (PROV-N, PROV-JSON), also in W3C-compatible form
\item Visualization of provenance information with Javascript
\end{itemize}

% -- REST API
\paragraph{REST API}
The first two points, listing instances and showing details for each ProvenanceDM class
are implemented as a REST API, using the
Django RESTFramework\footnote{\url{http://www.django-rest-framework.org/}} module.
Here are some example URLs for this:

\begin{itemize}
\item \texttt{\{base-url\}/api/activities/}: list of all activity instances
\item \texttt{\{base-url\}/api/activities/?format=json}: same, in simple json format
\item \texttt{\{base-url\}/api/activities/rave:act\_classificationPipeline/}: details for the activity with ID \texttt{rave:act\_classificationPipeline}
\item \texttt{\{base-url\}/api/used/}: list of all used relations
\end{itemize}


% IDs, namespaces
%\subsection{IDs}
\paragraph{Identifiers}
For each activity, agent or entity, an identifier (ID) is defined using the ``rave'' namespace defined for this project.
This is useful for ensuring unique IDs. A namespace is also required for constructing qualified identifiers for W3C compatible serialisations.


\subsection{Implementation details}
The following sections are more technical and describe with more details some of the issues that arose during the implementation and their solutions.

\subsubsection{Tracking provenance}
Provenance for an entity, activity or agent can be tracked backwards
or even forward via the different relations using
database queries. Here we used a straight-forward approach, without further optimisation, by implementing three recursive functions: one for finding an \emph{activity} and following its relations, one for tracking an \emph{entity} and one for tracking an \emph{agent}.
They search for the desired activity/entity/agent in any of the corresponding relations (e.g. for activity, check used, wasGeneratedBy, wasInformedBy, hadStep), extract the activity, entity or agent the desired activity/entity/agent is linked with and call the corresponding function for tracking it further (recursively).

%Note that we decided to follow entities and activities only backwards in time, not forward. Also, for \emph{hadMember} and \emph{hadStep}-relations we only follow the links ``upwards'', to the parent (\emph{Collection} or \emph{Activity}), i.e. we ignore the children. Otherwise the retrieved provenance information would quickly become too much. Tracing child and forward links as well would result in extracting basically all provenance records, even if just the provenance for one specific entity was requested.

\subsubsection{ProvDAL}
The IVOA ProvenanceDM specification \citep{std:ProvenanceDM} describes a method to retrieve
provenance information for a specified entity, activity or agent via a ProvDAL service interface.
We have implemented it
for this web application, using \texttt{provdal/} as endpoint with following
request parameters:
\begin{itemize}
\item \texttt{ID}: a valid qualified identifier for an entity or activity (can occur multiple times)
\item \texttt{DEPTH}: a positive integer (including 0) for following the provenance graph this number of relations or \texttt{ALL} for everything
\item \texttt{RESPONSEFORMAT}: format of the serialized response, currently only \texttt{PROV-JSON} and \texttt{PROV-N} are implemented
\item \texttt{DIRECTION}: direction of the provenance tracking, either \texttt{BACK} or \texttt{FORTH}. This only affects the way how \class{used}, \class{wasGeneratedBy}, \class{wasDerivedFrom} and \class{wasInformedBy} are followed.
\item \texttt{MEMBERS}, \texttt{STEPS}, \texttt{AGENT}: additional flags that can be \texttt{true} or \texttt{false}.
\item \texttt{MODEL}: extra parameter for choosing a serialization compliant to \texttt{IVOA} ProvenanceDM or \texttt{W3C} ProvDM
\end{itemize}
This allows to retrieve provenance descriptions in the desired format and compliant to W3C or including the IVOA ProvenanceDM extensions.

We additionally implemented following non-standard extension:
\begin{itemize}
\item \texttt{RESPONSEFORMAT=GRAPH} retrieves a html page with an interactive visualisation of the provenance description
\end{itemize}

A typical request looks like this:

\begin{verbatim}
{base-url}/provdal/?ID=rave:20121220_0752m38_089&DEPTH=1&
    RESPONSEFORMAT=PROV-N&MODEL=IVOA
\end{verbatim}

This generates a serialised description of the entity with ID \texttt{rave:20121220\_0752m38\_089} and its direct relations, in PROV-N format:

\begin{verbnobox}[\scriptsize]
document
prefix prov <http://www.w3.org/ns/prov#>
prefix voprov <http://www.ivoa.net/documents/ProvenanceDM/ns/voprov/>
prefix custom <http://www.ivoa.net/documents/ProvenanceDM/ns/custom/>
prefix xsd <http://www.w3.org/2000/10/XMLSchema#>
prefix rave <http://www.rave-survey.org/prov/>
prefix org <http://www.ivoa.net/documents/ProvenanceDM/ns/org/>
prefix vo <http://www.ivoa.net/documents/ProvenanceDM/ns/vo>

activity(rave:act_dataextraction, 2003-04-11T14:42:16Z, 2012-05-27T17:05:00Z, 
    [voprov:name="Data Extraction", voprov:type="obs:Extraction", 
    voprov:annotation="RAVE observations, data release 4", 
    voprov:doculink="RAVE DR4: Kordopatis et al. 2013, AJ, 146, Issue 5, 
    article id. 134, pp.421-451"])
entity(rave:20121220_0752m38_089, [voprov:name="20121220_0752m38_089", 
    voprov:annotation="Properties of observed star derived for this 
    observation in RAVE DR4", voprov:rights="voprov:public", 
    custom:dataType="databaseRow", 
    custom:storageLocation="https://www.rave-surve.org/query/"])
entity(rave:DR4_RAVEDR4, [voprov:name="RAVEDR4 main", 
    voprov:annotation="The main RAVE DR4 table", voprov:rights="voprov:public", 
    custom:dataType="databaseTable", 
    custom:storageLocation="https://www.rave-survey.org/project/documentation/dr4/rave_dr4/"])
wasGeneratedBy(rave:20121220_0752m38_089, rave:act_dataextraction, -)
hadMember(rave:DR4_RAVEDR4, rave:20121220_0752m38_089)
endDocumentdocument
\end{verbnobox}

We implemented a web form\footnote{\url{https://escience.aip.de/provenance-rave/prov_vo/provdal}} as frontend for the ProvDAL interface, in which all the parameters can be set. The form does not support asking for multiple IDs at once for now.


\paragraph{Content negotiation with HTTP Accept}
We also check, if the HTTP accept header is compatible with the requested response format.
If it is not, a 406 Not Accepted error is returned. The following table shows the accept types that we
considered compatible with the implemented serialization format. If either an unsupported REPSONSEFORMAT value or accept header is requested, the HTTP error 415 Not Supported is returned.\\


\begin{tabulary}{1.0\textwidth}{@{}p{0.4\textwidth}p{0.4\textwidth}@{}}
\toprule
\head{RESPONSEFORMAT} & \head{HTTP accept}\\
\midrule
PROV-N & text/plain \newline text/* \newline */*\\
PROV-JSON & application/json \newline application/* \newline */*\\
\bottomrule
\end{tabulary}


\subsubsection{Collection}
For RAVE, each pipeline step operates on a number of files which can be summarized as a collection. E.g. the processing step ``IRAF Reduction'' produces a set of files with reduced spectra, which are summarized as ``IRAF Reduced dataset'', a collection. The individual files are members of this collection (via \emph{hadMember} relationship).

A \emph{Collection} is derived from the Entity-class and thus inherits the same attributes and relations. Since we did not need any additional attributes for collections, we did not make use of the extra \emph{Collection} class, and only marked entities that are collections by setting their type-attribute to ``collection'' (like it is done in W3C serialisations).
Thus, when looping over a list of entities, it is also faster to check if they are a collection (only need to check an attribute and not check if an entity occurs in the list of collections
as well).

\subsubsection{Serializations}
We implemented serializers for each class, which directly map the used classes and attributes into the required format, adding the voprov-namespace to each attribute.
This is useful for processing the provenance information with ProvenanceDM-aware VO-tools.
However, according to the IVOA Provenance DM requirements, it must also be possible to serialize the provenance information into at least one of the W3C formats. Thus we also implemented W3C variants of the serializers. These map the additonal classes and attributes from ProvenanceDM to a valid W3C representation.

Here's a list of the main changes/mappings for converting from the IVOA model to W3C serialisation:

\begin{itemize}
\item namespace \texttt{voprov} $\rightarrow$ \texttt{prov} for those attributes that are the same in W3C (e.g. ID, role, startTime, endTime)
\item attribute \texttt{voprov:name} $\rightarrow$ \texttt{prov:label}
\item attribute \texttt{voprov:annotation} $\rightarrow$ \texttt{prov:description}
\item attribute \texttt{prov:role} is not allowed in W3C's \emph{wasAttributedTo}, thus use \texttt{voprov:role}
\item \emph{hadMember} has no ID and no optional attributes in W3C
\item \emph{Collection} $\rightarrow$ \emph{Entity} with \texttt{prov:type = prov:collection}
%\item \emph{ActivityFlow} $\rightarrow$ \emph{Activity} with \texttt{voprov:votype = voprov:activityFlow}
% doculink?
\end{itemize}

\paragraph{W3C serialization of \emph{ActivityFlow}}
The classes \emph{ActivityFlow} and \emph{HadStep} do not exist in W3C. When a W3C compliant
serialization of a provenance description including an activityFlow is needed, these classes
have to be expressed with existing W3C classes:
\begin{itemize}
\item Represent each activityFlow as an activity; additional attribute \verb|voprov:votype = 'voprov:activityFlow'|
\item Represent each hadStep relation as a wasInfluencedBy relation; additional attribute \verb|voprov:votype = 'voprov:hadStep'|
\end{itemize}

For example, an activityFlow and related activities in IVOA ProvenanceDM, PROV-N notation may look like this:

\begin{verbnobox}[\scriptsize]
activityFlow(rave:act_pipeline, -, -, [voprov:name="RAVE Pipeline"])
activity(rave:act_sparvPipeline, -, -, [voprov:name="SPARV-Pipeline"])
activity(rave:act_irafReduction, -, -, [voprov:name="IRAF Reduction"])
hadStep(rave:act_pipeline, rave:act_irafReduction)
hadStep(rave:act_pipeline, rave:act_sparvPipeline)
wasInformedBy(rave:act_sparvPipeline, rave:act_irafReduction)
\end{verbnobox}
and the corresponding W3C serialisation would look like this:
\begin{verbnobox}[\scriptsize]
activity(rave:act_pipeline, -, -, [voprov:votype="voprov:activityFlow", voprov:name="RAVE Pipeline"])
activity(rave:act_sparvPipeline, -, -, [voprov:name="SPARV-Pipeline"])
activity(rave:act_irafReduction, -, -, [voprov:name="IRAF Reduction"])
wasInfluencedBy(rave:act_pipeline, rave:act_irafReduction, [voprov:votype="voprov:hadStep"])
wasInfluencedBy(rave:act_pipeline, rave:act_sparvPipeline, [voprov:votype="voprov:hadStep"])
wasInformedBy(rave:act_sparvPipeline, rave:act_irafReduction)
\end{verbnobox}

This way, an activityFlow can be expressed with W3C compliant terms, and it is possible to
convert from this representation to an IVOA-compliant version including activityFlow and hadStep
explicitly. Note also, that there exists also at least one other attempt to model workflows, e.g. D-PROV\footnote{\url{https://www.usenix.org/system/files/conference/tapp13/tapp13-final3.pdf}}, which is using extensions to W3C Prov.

% \TODO{Auto-generate wasGeneratedBy and used-relations for flows or not?}

\subsubsection{VOSI resources}
The necessary interfaces \texttt{availability} and \texttt{capabilities}
are implemented in an additional reusable package, \texttt{django-vosi}.


\subsubsection{Sources, demo}
Please note that this RAVE Provenance web application is still a prototype and may change any time.
\begin{itemize}
\item Sources of the web application:\\
    \url{https://github.com/kristinriebe/provenance-rave}\\
    \url{https://github.com/kristinriebe/django-prov_vo}\\
    \url{https://github.com/kristinriebe/django-vosi}
\item Live demo version:\\
    \url{https://escience.aip.de/provenance-rave}\\
    The base-url for the given examples is\\
    \url{https://escience.aip.de/provenance-rave/prov_vo/}
\item Javascript example for provenance visualisations:\\
    \url{https://escience.aip.de/prov/graphs/example.html}
\end{itemize}



\clearpage
\section{Provenance from SimDM classes for CosmoSim}
etc. etc.


\bibliography{ivoatex/ivoabib,prov-refs}

\end{document}
