• Participant names: Shawn Bowers, Tim McPhillips, and Bertram Ludaescher, in collaboration with Norbert Podhorszki and Ilkay Altintas.

   lineageEdges(Trace, [AtlasXGraphic], Edges)

   ?- traceId('1', Trace), 
      nodeForId(Trace, '341', Node),
      lineageEdges(Trace, [Node], Edges),
      drawTraceEdges(Edges, 'pq1', gif).

The following query computes and draws the corresponding data-lineage graph for the second trace, described above. Since there are three separate image collections used in the execution (i.e., the three collections are pipelined through the workflow), the result consists of three independent Atlas X Graphic objects.

   ?- traceId(TraceId, Trace), 
      traceInvocParam(Trace, 'warpParameters', '-m 12', 'AlignWarp', Invoc).

   TRACE = 1   ACTOR = AlignWarp   INVOCATION = 1
   TRACE = 1   ACTOR = AlignWarp   INVOCATION = 2
   TRACE = 1   ACTOR = AlignWarp   INVOCATION = 3
   TRACE = 1   ACTOR = AlignWarp   INVOCATION = 4
   TRACE = 2   ACTOR = AlignWarp   INVOCATION = 5
   TRACE = 2   ACTOR = AlignWarp   INVOCATION = 6
   TRACE = 2   ACTOR = AlignWarp   INVOCATION = 7
   TRACE = 2   ACTOR = AlignWarp   INVOCATION = 8

Note that only two of the image collections of the second trace use the given parameter. In addition, the parameter is used for only two of the anatomy images in one of the input image collections.

5. Find all Atlas Graphic images output from workflows where at least one of the input Anatomy Headers had an entry global maximum=4095. The contents of a header file can be extracted as text using the scanheader AIR utility. The following query (1) selects input nodes of the trace, (2) checks that the input node is of type ImageHeader, (3) checks that the header meets the given criteria, and (4) obtains the output nodes of type AtlasGraphic of the trace.

   TRACE = 1   TYPE = AtlasGraphic   TOKEN = 341   OBJECT = 68
   TRACE = 1   TYPE = AtlasGraphic   TOKEN = 349   OBJECT = 70
   TRACE = 1   TYPE = AtlasGraphic   TOKEN = 357   OBJECT = 72
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 1093   OBJECT = 225
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 1101   OBJECT = 227
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 1109   OBJECT = 229
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 1193   OBJECT = 242
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 1202   OBJECT = 244
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 1210   OBJECT = 246
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 973   OBJECT = 199
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 981   OBJECT = 201
   TRACE = 2   TYPE = AtlasGraphic   TOKEN = 989   OBJECT = 203

   ?- traceId(TraceId, Trace), 
      actorInvocation(Trace, 'SoftMean', _, _, AveragedImage), 
      nodeType(AveragedImage, 'Image'),
      lineageEdges(Trace, [AveragedImage], Edges), 
      member((_, _, 'AlignWarp', Invoc), Edges), 
      traceInvocParam(Trace, 'warpParameters', '-m 12', 'AlignWarp', Invoc).

   ?- traceId(TraceId, Trace), 
      traceInvoc(Trace, 'AlignWarp', Invoc),
      actorInvocation(Trace, 'AlignWarp', Invoc, InputNode, OutputNode), 
      nodeType(InputNode, 'Image'), 
      nodeMetadata(Trace, 'center', 'UChicago', InputNode).

   TRACE = 1   ACTOR = AlignWarp   INVOCATION = 1   TYPE = WarpParamSet   TOKEN = 245   OBJECT = 53
   TRACE = 2   ACTOR = AlignWarp   INVOCATION = 1   TYPE = WarpParamSet   TOKEN = 851   OBJECT = 176

The following query computes the sets of Atlas Graphics, where at least one Atlas Graphic has the desired metadata annotation.

   ?- traceId(TraceId, Trace), 
      traceInvoc(Trace, 'SoftMean', Invoc),
      graphicAtlasSet(Trace, Invoc, GraphicSet). 

The graphicAtlasSet is defined specifically for this query as follows:

   graphicAtlasSet(Trace, Invoc, GraphicSet) :-
      setof(G, graphicAtlas(Trace, G, Invoc), GraphicSet),
      member(Graphic, GraphicSet), 
      member(Modality, ['speech', 'visual', 'audio']), 
      nodeMetadata(Trace, 'studyModality', Modality, Graphic).

   graphicAtlas(Trace, AtlasGraphic, SoftMeanInvoc) :-
      traceOutputNode(Trace, AtlasGraphic), 
      nodeType(AtlasGraphic, 'AtlasGraphic'), 
      lineageEdges(Trace, [AtlasGraphic], Edges), 
      member((_, _, 'SoftMean', SoftMeanInvoc), Edges).

The complexity of this query is due to the generation of sets of Atlas Graphics, which is similar to peforming a group-by operation in SQL, and then further filtering groups by corresponding metadata values. Note that above we do not further return the given metadata values of the graphics (although one easily could). The result of running the above query on the two traces is:

   TRACE = 1   TOKEN SET = {341, 349, 357}
   TRACE = 2   TOKEN SET = {1093, 1101, 1109}
   TRACE = 2   TOKEN SET = {1193, 1202, 1210}

   ?- traceId('2', Trace), 
      nodeForId(Trace, '1093', Node), 
      lineageEdges(Trace, [Node], Edges), 
      member((_, DepNode, _, _), Edges), 
      nodeType(DepNode, 'Image'), 
      setof(N, traceInputNode(Trace, N), InputNodes), 
      \+ member(DepNode, InputNodes).

The result of running this query is:

   TYPE = Image   TOKEN = 1001   OBJECT = 205
   TYPE = Image   TOKEN = 1018   OBJECT = 208
   TYPE = Image   TOKEN = 1065   OBJECT = 222

   ?- traceId('2', Trace), 
      nodeForId(Trace, '1093', Node), 
      lineageEdges(Trace, [Node], Edges), 
      member((_, DepNode, _, _), Edges), 
      nodeType(DepNode, 'Image'), 
      setof(D, traceInputNode(Trace, D), InputNodes), 
      member(DepNode, InputNodes).

   TYPE = Image   TOKEN = 927   OBJECT = 190
   TYPE = Image   TOKEN = 932   OBJECT = 192
   TYPE = Image   TOKEN = 937   OBJECT = 194
   TYPE = Image   TOKEN = 942   OBJECT = 196

We note that a number of similar types of data-lineage queries are defined in (Bowers et al, 2006).

Suggested Workflow Variants

Data and Knowledge Systems

• Short team name: DAKS

• Participant names: Shawn Bowers, Tim McPhillips, Bertram Ludaescher in collaboration with Norbert Podhorszki and Ilkay Altintas.

• Project Overview: The Data and Knowledge Systems (DAKS) group at UC Davis is developing the Collection-Oriented Workflow paradigm and implementing this approach in the Kepler Workflow System. See McPhillips & Bowers (2005) and McPhillips et al (2006) listed below for more information.

• Provenance-specific Overview: Among other benefits, collection-oriented workflows enable comprehensive data and process lineage information to be recorded and passed through the workflow along with data. We demonstrate this capability in this challenge. Our approach is an adaptation of the RWS provenance model described in Bowers et al (2006) listed below. Our approach takes advantage of the collection-oriented workflow framework to:
  • Automatically infer state-reset events based on the declared scope of actors.
  • Minimize the number of provenance-relevant events that must be recorded.
  • Simplify association of workflow runs with data provenance by storing workflow inputs, outputs, and dependency information in a single, self-contained trace file.
  • Support science-oriented provenance queries, emphasizing data dependencies (lineage) as well as process details.
  • Decouple provenance representation from particular scientific workflow technologies (e.g., Kepler).

• Relevant Publications:

• • Collection-Oriented Scientific Workflows for Integrating and Analyzing Biological Data, Timothy McPhillips, Shawn Bowers, Bertram Ludaescher. 3rd International Workshop on Data Integration in the Life Sciences (DILS'06), 2006.

How the collection-oriented actors (coactors) work. Our collection-oriented workflow framework provides generic support for operating over nested collections (i.e., trees) of scientific data. Coactors differ from conventional Kepler actors (such as those used in the RWS solution to this Provenance Challenge) in that rather than operating on flat, homogeneous streams of tokens, coactors operate on trees of heterogenous data. A coactor is invoked whenever a subtree of the input stream matching certain criteria (e.g., the declared scope of the coactor) is received. During an invocation, the coactor may optionally add or delete nodes within the subtree upon which it was invoked. The figure below illustrates how the AlignWarp actor operates on an AnatomyImage collection, adding a WarpParamSet to this collection. All data received by AlignWarp outside of its scope passes through the coactor transparently.

In Kepler, collections are serialized and streamed through coactors. Because actor execution is pipelined based on each actor’s scope, this approach enables concurrent processing of nested data collections as shown below. The figure illustrates how delimiter tokens (in blue and green) are used to bracket nested collections of associated data (in white), metadata (in red) and actor parameters (not shown).

Input collections drive workflow execution. The collection-oriented implementation of the Challenge workflow may be configured to operate on different numbers of input anatomy images, not by modifying the workflow definition, but by customizing the input to the workflow. We tested our provenance system using two different input data sets represented by two XML files. The first input file, input1.xml, corresponds exactly to the Challenge workflow and contains four AnatomyImage collections within a single ImageCollection collection (see tree representation below). The second input file, input2.xml, contains three ImageCollections comprising four, three, and two AnatomyImage collections respectively. In other words, our implementation can operate on varying numbers of anatomy images within a single run of the workflow. Moreover, parameter values for particular actors also may be embedded within the workflow input in order to override default parameter values for particular sub-collections of data (note Parameter elements in the two input XML files).

As illustrated above, data and invocation dependencies are represented in the trace as special XML elements describing the provenance of other elements. Insertion elements record the actor, actor invocation count, and direct data dependencies associated with event that created the element following it in the document. InvocationDependency elements record which invocations of preceding actors created data or modified collections used in the current actor invocation. Insertion and invocation dependency information is passed through the workflow as special tokens during workflow execution. Coactors declare data dependencies explicitly during execution, whereas invocation dependencies are inferred and inserted into the token stream by the framework automatically. The figure below illustrates two data dependencies graphically.

Provenance Challenge Template

<!-- >div class="twikiToc"&

• Provenance Challenge Template
  • Participating Team
  • Workflow Representation
  • Provenance Trace
  • Provenance Queries
  • Suggested Workflow Variants
  • Suggested Queries
  • Categorisation of queries
  • Conclusions

Participating Team

• Short team name: DAKS

• Participant names: Shawn Bowers, Tim McPhillips, Bertram Ludaescher in collaboration with Norbert Podhorszki and Ilkay Altintas.

• Project URL:

• Project Overview: The Data and Knowledge Systems (DAKS) group at UC Davis is developing the Collection-Oriented Workflow paradigm and implementing this approach in the Kepler Workflow System. Our framework provides support for workflows that operate over nested collections (trees) of data. Actors in a collection-oriented workflow receive input trees

See publications (McPhillips & Bowers, 2005) and (McPhillips et al, 2006) listed below for more information.

• Provenance-specific Overview: Among other benefits, collection-oriented workflows enable comprehensive data and process lineage information to be recorded and passed through the workflow along with data. We demonstrate this capability in this challenge. Our approach is an adaptation of the RWS provenance model described in the publication (Bowers et al, 2006) listed below.

• Relevant Publications:
  • An Approach for Pipelining Nested Collections in Scientific Workflows, Timothy McPhillips and Shawn Bowers, SIGMOD Record 34, 12-17, 2005.
  • A Model for User-Oriented Data Provenance in Pipelined Scientific Workflows, Shawn Bowers, Timothy McPhillips, Bertram Ludaescher, Shirley Cohen, Susan B. Davidson. International Provenance and Annotation Workshop (IPAW'06), 2006.
  • Collection-Oriented Scientific Workflows for Integrating and Analyzing Biological Data, Timothy McPhillips^?, Shawn Bowers, Bertram Ludaescher. 3rd International Workshop on Data Integration in the Life Sciences (DILS'06), 2006.

Workflow Representation

Provide here a description of how you have encoded the Challenge workflow.

Provenance Trace

Upload a representation of the information you captured when executing the workflow. Explain the structure (provide pointers to documents describing your schemas etc.)

Provenance Queries

We have implemented a query engine prototype for collection-oriented traces in Prolog. The engine can accept multiple traces (traces can be "added" and "dropped" from the engine), and provides various operations for accessing traces and inferred provenance dependency graphs.

Core Provenance Queries

1. Find the process that led to Atlas X Graphic / everything that caused Atlas X Graphic to be as it is. This should tell us the new brain images from which the averaged atlas was generated, the warping performed etc.

For this question, we return the portion of the provenance lineage graph that "ends" at the Atlas X Graphic node of the trace. Given the Atlas X Graphic node Node and the trace Trace, the following expression returns the corresponding portion of the graph:

   lineage_edges(Trace, [Node], Edges)

where lineage_edges is a provided operation by the provenance query engine that computes the set of edges from the given set of nodes.

The following selects the first trace and the Atlas X Graphic node of the trace, computes the corresponding provenance graph, and draws the edges of the graph.

   q1 :-
      trace_id('1', Trace), 
      node_for_id(Trace, '341', Node),
      lineage_edges(Trace, [Node], Edges), 
      draw_trace_edges(Edges, 'pq1', gif).

The resulting graph is shown below.

The second trace we experimented with consists of three atlas graphic sets. The following query computes and draws the corresponding provenance graph for the second trace.

   pq1_trace2 :-
      trace_id('2', Trace), 
      node_for_id(Trace, '973', Node1),   
      node_for_id(Trace, '1093', Node2),   
      node_for_id(Trace, '1193', Node3),   
      lineage_edges(Trace, [Node3, Node2, Node1], Edges), 
      draw_trace_edges(Edges, 'pq1_trace2', gif).

The resulting graph is shown below.

2. Find the process that led to Atlas X Graphic, excluding everything prior to the averaging of images with softmean.

For this question, we again return a portion of the provenance lineage graph. Here, we filter out the edges that occur prior to the SoftMean computation using the filter_before_actor operation.

   pq2 :- 
      trace_id('1', Trace), 
      node_for_id(Trace, '341', Node),
      lineage_edges(Trace, [Node], Edges), 
      filter_before_actor(Trace, Edges, 'SoftMean', FilteredEdges), 
      draw_trace_edges(FilteredEdges, 'pq2', gif).

The result of this query is shown below.

3. Find the Stage 3, 4 and 5 details of the process that led to Atlas X Graphic.

Note that this question is identical to question 2. However, here we provide a different method for computing the result. In particular, instead of filtering out edges prior to SoftMean, we select only edges that occur after to the ResliceWarp computation using the select_after_actor operation.

   pq3 :- 
      trace_id('1', Trace), 
      node_for_id(Trace, '341', Node),   % AtlasXGraphic
      lineage_edges(Trace, [Node], Edges), 
      select_after_actor(Trace, Edges, 'ResliceWarp', FilteredEdges), 
      draw_trace_edges(FilteredEdges, 'pq3', gif).

The result of the query is identical to query 2 above.

For each query, if your system can support your query, provide a description of how you implement the query, what result is returned; otherwise, explain whether the query is in the remit of your system.

Also, make sure you complete the ProvenanceQueriesMatrix.

Suggested Workflow Variants

Suggest variants of the workflow that can exhibit capabilities that your system support.

Suggested Queries

Suggest significant queries that your system can support and are not in the proposed list of queries, and how you have implemented/would implement them. These queries may be with regards to a variant of the workflow suggested above.

Categorisation of queries

According to your provenance approach, you may be able to provide a categorisation of queries. Can you elaborate on the categorisation and its rationale.

Conclusions

Provide here your conclusions on the challenge, and issues that you like to see discussed at a face to face meeting.

-- LucMoreau - 31 May 2006