The Karma Service API supports 2 kinds of provenance retrieval: Data Provenance and Process Provenance. It also supports variations of these that can retrieve RecursiveDataProvenance^?, DataUsage^?, and WorkflowTrace^?. Results of these provenance queries on the given workflow are shown here:

Limited support for queries over annotations is present and has been used to answer the challenge queries that include annotations (except for #9). Some of them has required us to query the provenance service's backend relational database, since support for queries over annotation is not present through the service API yet.

Karma team

*

*

*

*

* Complete support not available through Karma's Web-Service API. SQL query on backend database required.

void PrintRecursiveDataProvenanceUntil^?(DataProductID^? dataProduct, URI processID) 1. let $dataList := [dataProduct]

1. SQL Query to locate align_warp invocations (invoker+invokee pairs) that match input parameter of "-m 12" that ran on a Monday

      SELECT 
         invokee.workflow_id, invokee.service_id, invokee.workflow_node_id, invokee.workflow_timestep,
      invoker.workflow_id, invoker.service_id, invoker.workflow_node_id, invoker.workflow_timestep
      FROM 
         invocation_state_table invocation, entity_table invokee, entity_table invoker, notification_table notifications
      WHERE
      invokee.entity_id = invocation.invokee_id AND
      invoker.entity_id = invocation.invoker_id AND
      notifications.source_id = invocation.invokee_id AND
      notifications.notification_type = 'ServiceInvoked' AND
      invokee.service_id = 'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService' AND
      notifications.notification_xml LIKE '%<ModelMenuNumber>12</ModelMenuNumber>%' AND
      DAYOFWEEK(invocation.request_receive_time) = 2; // 1=Sunday, 2=Monday, ...
   

   In our example (assuming the workflow was run on a Monday instead of actually Sunday), this query returns:

   Entity	workflow_id	service_id	workflow_node_id	workflow_timestep
   Invokee 1	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService'	6
   Invokee 2	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService_2'	8
   Invokee 3	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService_3'	10
   Invokee 4	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService_4'	12
   Invoker	-	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	-	-

1. Using the invoker and invokee information from the above query, the client can use the getProcessProvenance API to query for the description of the matching align_warp services. The result of this is show in query4.txt.

1. SQL Query to locate align_warp invocations (invoker+invokee pairs) that have annotation of "global_maximum=4095"

      SELECT
         invokee.workflow_id, invokee.service_id, invokee.workflow_node_id, invokee.workflow_timestep,
      invoker.workflow_id, invoker.service_id, invoker.workflow_node_id, invoker.workflow_timestep
      FROM
         entity_table invokee, entity_table invoker, notification_table notifications, invocation_state_table invocation
      WHERE
      invokee.entity_id = invocation.invokee_id AND
      invoker.entity_id = invocation.invoker_id AND
      notifications.source_id = invocation.invokee_id AND
      notifications.notification_type = 'ServiceInvoked' AND
      invokee.service_id = 'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService' AND
      notifications.notification_xml LIKE '%global_maximum=4095%'
   

   In our example, this query returns:

   Entity	workflow_id	service_id	workflow_node_id	workflow_timestep
   Invokee_1	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService'	6
   Invokee_2	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService_2'	8
   Invokee_3	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService_3'	10
   Invokee_4	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService'	'AlignWarpService_4'	12
   Invoker_0	-	'tag:gpel.leadproject.org,2006:69B/ProvenanceChallengeBrainWorkflow17/instance1'	-	-

1. Using the invoker and invokee information from the above query, the client can start a recursive descent down the process provenance tree to look for output data files that are images generated by the convert service.

PrintRecursiveDataUsageFor(Invokee_0, Invokee_1, 'urn:qname:...:ConvertService');

void PrintRecursiveDataUsageFor(EntityID invoker, EntityID invokee, URI processID)
   // get initial process's provenance
1. let $processProv := karma.getProcessProvenance(invoker, invokee)       
1. let $processList := [$processProv], $visitedDataList := [], $outputDataList := []
   // start recursing down the data usage tree iteratively
2. while ($processList != empty) do
   a. foreach ($processProv in $processList) do 
          // test if any of the processes in the current list was 'ConvertService'. If so, print it's output image files.
      i.  if $processProv.getInvokee().getServiceID() == processID Print $processProv.getProducingData()
          // add data products that were produced to the list of output to recurse into
      ii. Add all $processProv.getProducingData() to $outputDataList
      // we're done with these processes
   b. $processList := []
   c. foreach ($outputData in $outputDataList) do 
          // get the data usage list for the output data produced
      i.  let $dataUsage := karma.getDataUsage($outputData)
          // get the process provenance for each process that used the output data and add them to process list
      ii. foreach ($usedByProcess in $dataUsage.getUsageList())
          - let $processProv := karma.getProcessProvenance($usedByProcess.invoker, $usedByProcess.invokee)
          - Add $processProv to $processList
      // we're done with these data
   d. let $dataList := []
3. End

The results of this operation is shown in query5.txt.

6. Find all output averaged images of softmean (average) procedures, where the warped images taken as input were align_warped using a twelfth order nonlinear 1365 parameter model, i.e. "where softmean was preceded in the workflow, directly or indirectly, by an align_warp procedure with argument -m 12."

This is a variation of query 4 and query 5. The SQL query used to retreive the align_warp services that had model menu number value of -12 is the same as the query in #4 with the exception of the DAYOFWEEK predicate. Similarly, the client's recursive procedure to locate output of all SoftmeanServices^? that were preceeded by these align_warps is similar to the recursive procedure outlined in query #5, with ConvertService being replaced by SoftmeanService. They're reproduced below.

1.    SELECT 
         invokee.workflow_id, invokee.service_id, invokee.workflow_node_id, invokee.workflow_timestep,
      invoker.workflow_id, invoker.service_id, invoker.workflow_node_id, invoker.workflow_timestep
      FROM 
         invocation_state_table invocation, entity_table invokee, entity_table invoker, notification_table notifications
      WHERE
      invokee.entity_id = invocation.invokee_id AND
      invoker.entity_id = invocation.invoker_id AND
      notifications.source_id = invocation.invokee_id AND
      notifications.notification_type = 'ServiceInvoked' AND
      invokee.service_id = 'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService' AND
      notifications.notification_xml LIKE '%<ModelMenuNumber>12</ModelMenuNumber>%';
   

PrintRecursiveDataUsageFor(Invokee_0, Invokee_1, 'urn:qname:...:SoftmeanService');

(See Query #5 for definition)

The results of this operation is shown in query6.txt.

void PrintWorkflowTraceDiff(WorkflowTrace trace1, WorkflowTrace trace2)
   // Workflow trace is an extension of process procenance document
1. let $processProv1 := trace1 as ProcessProvenance
2. let $processProv2 := trace2 as ProcessProvenance
3. PrintProcessProvenanceDiff($processProv1, $processProv2)
   // Each step in the workflow trace is a process provenance document
4. foreach($processProv1, $processProv2 in trace1.getTraceSteps(), trace2.getTraceSteps()
   a. PrintProcessProvenanceDiff($processProv1, $processProv2)
5. End

void PrintProcessProvenanceDiff(ProcessProvenance processProv1, ProcessProvenance processProv2)
1. Print "Diff of Processes: ", processProv1.getInvokee(), processProv2.getInvokee()
2. if (processProv1.getInvokee() != processProv2.getInvokee()) 
   a. Print "Invokees Differ: ", processProv1.getInvokee(), processProv2.getInvokee()   
3. if (processProv1.getInvoker() != processProv2.getInvoker()) 
   a. Print "Invokers Differ: ", processProv1.getInvoker(), processProv2.getInvoker()
4. if (processProv1.getStatus() != processProv2.getStatus()) 
   a. Print "Process Completion Status Differ: ", processProv1.getStatus(), processProv2.getInvoker()
5. if (processProv1.getRequestReceiveTime() != processProv2.getRequestReceiveTime()) 
   a. Print "Invocation Times Differ: ", processProv1.getRequestReceiveTime(), processProv2.getRequestReceiveTime()
6. foreach ($dataProd1, $dataProd2 in processProv1.getUsingData(), processProv2.getUsingData()) 
   a. PrintDataProductDiff($dataProd1, $dataProd2)
7. foreach ($dataProd1, $dataProd2 in processProv1.getProducingData(), processProv2.getProducingData()) 
   a. PrintDataProductDiff($dataProd1, $dataProd2)
8. End

void PrintDataProductDiff(DataProduct dataProd1, DataProduct dataProd2)
1. if (dataProd1.getDataProductID() != dataProd2.getDataProductID()) // trivial. IDs always differ.
   a. Print "Produced Data IDs Differ: ", dataProd1.getDataProductID(), dataProd2.getDataProductID()
2. if (dataProd1.getLocation() != dataProd2.getLocation()) 
   a. Print "Produced Data Locations Differ: ", dataProd1.getLocation(), dataProd2.getLocation()
3. if (dataProd1.getTimestamp() != dataProd2.getTimestamp()) 
   a. Print "Produced Data Timestamp Differ: ", dataProd1.getTimestamp(), dataProd2.getTimestamp()
4. End

The second workflow was not run and hence the query results for this are not available.

1. SQL Query to locate align_warp invocations (invoker+invokee pairs) whose input data products have annotaion "center=UChicago"

      SELECT 
         invokee.workflow_id, invokee.service_id, invokee.workflow_node_id, invokee.workflow_timestep,
      invoker.workflow_id, invoker.service_id, invoker.workflow_node_id, invoker.workflow_timestep
      FROM 
         invocation_state_table invocation, entity_table invokee, entity_table invoker, notification_table notifications
      WHERE
      invokee.entity_id = invocation.invokee_id AND
      invoker.entity_id = invocation.invoker_id AND
      notifications.source_id = invocation.invokee_id AND
      notifications.notification_type = 'ServiceInvoked' AND
      invokee.service_id = 'urn:qname:http://www.extreme.indiana.edu/karma/challenge06:AlignWarpService' AND
      notifications.notification_xml LIKE '%<Center>UChicago</Center>%';
   

1. We then call getProcessProvenance on the resulting invocations of the above query and print the produced data products elements. If all 4 align_warp services match, the results are shown in query8.txt.

• Workflows with loops.
• Workflows whose structure changes dynamically (or, as a simpler case, workflows with conditional branches).
• Hierarchical composition of workflows. (workflows invoking other workflows)

• Find all [workflows | processes] with a particular execution status [completed | failed | waiting for input]
• Show the client view and service view of the provenance and check for differences

• Provenance Structure
• Annotation

• karma.xsd: Karma v2.x schema describing provenance documents

• data_provenance.xml: Data Provenance retrieved for the atlas-x.gif data product

• recursive_data_provenance.xml: Data Provenance retrieved recursively for the atlas-x.gif data product and its ancestral data products

• process_provenance.xml: Process Provenance for a single service invocation of AlignWarpService

• workflow_trace.xml: Workflow Trace for all invocations in the ProvenanceChallengeBrainWorkflow

Teams	Queries
	Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8	Q9
Karma team

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.

The getRecursiveDataProvenance API provided by the Karma provenance service allows the retreival of the entire data provenance history of a data product. Invoking that method with the data product ID of Atlas X Graphic (in this case, 'lead:uuid:1157946992-atlas-x.gif') returns the complete process that led to its creation. The result of the provenance query is shown in recursive_data_provenance.xml.

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

This query is performed by the client by first invoking the getDataProvenance method on the Karma provenance service to retreive the immediate data provenance for Atlas X Graphic. The client then recursively calls getDataProvenance to get move up the provenance tree until the SoftmeanService is encountered in the data provenance results. The pseudo-code for the client looks like this:

1. let $dataList := ['lead:uuid:1157946992-atlas-x.gif']
2. while ($dataList != empty) do
   a. $dataProvenance = karma.getDataProvenance($dataList[0])           // get data provenance for this level
   b. Print $dataProvenance; $dataList.delete(0)                        // print process information & remove data from list
   c. if ($dataProvenance.getProducedBy() == 'SoftmeanService') break;  // found Softmean. Stop.
   d. foreach ($inputData in $dataProvenance.getUsingData()) do 
      // get input data used by this data product. recurse up the tree using iteration
      i. $dataList.add($inputData)  
3. End

The results of this operation is shown in query2.txt.

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

This query is different from #2 in that the provenance levels are relative to the file, instead of being specified explicitly as 'Softmean'. The getRecursiveDataProvenance API in the Karma provenance service has an optional parameter to specify the depth of recursion. By passing a recursion level of 3 in addition to the data product ID of Atlas X Graphic (in this case, 'lead:uuid:1157946992-atlas-x.gif'), it is possible to retreive the data provenance for stages 3,,4, and 5. The result of the provenance query is shown in query3.xml.

4. Find all invocations of procedure align_warp using a twelfth order nonlinear 1365 parameter model (see model menu describing possible values of parameter "-m 12" of align_warp) that ran on a Monday.

5. Find all Atlas Graphic images outputted 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.

6. Find all output averaged images of softmean (average) procedures, where the warped images taken as input were align_warped using a twelfth order nonlinear 1365 parameter model, i.e. "where softmean was preceded in the workflow, directly or indirectly, by an align_warp procedure with argument -m 12."

7. A user has run the workflow twice, in the second instance replacing each procedures (convert) in the final stage with two procedures: pgmtoppm, then pnmtojpeg. Find the differences between the two workflow runs. The exact level of detail in the difference that is detected by a system is up to each participant.

8. A user has annotated some anatomy images with a key-value pair center=UChicago. Find the outputs of align_warp where the inputs are annotated with center=UChicago.

9. A user has annotated some atlas graphics with key-value pair where the key is studyModality. Find all the graphical atlas sets that have metadata annotation studyModality with values speech, visual or audio, and return all other annotations to these files.

• KarmaBrainAtlasWF-bpel.xml: BPEL Script for Workflow
• KarmaBrainAtlasWF.xwf: Workflow representation that can be viewed/edited/launched from XBaya
  • Download XBaya

Provenance Challenge Template

In progress

Participating Team

• Short team name: Karma
• Participant names: YogeshSimmhan, Beth Plale, Dennis Gannon
• Project URL: http://www.extreme.indiana.edu/karma
• Project Overview: Collecting Provenance in Data-Centric Scientific Workflows. Applied to the Linked Environments for Atmospheric Discovery (LEAD) project
• Provenance-specific Overview:
• Relevant Publications:
  • A Framework for Collecting Provenance in Data-Centric Scientific Workflows, Y. L. Simmhan, B. Plale, and D. Gannon, International Conference on Web Service (ICWS) 2006.
  • Performance Evaluation of the Karma Provenance Framework for Scientific Workflows, Y. L. Simmhan, B. Plale, D. Gannon, and S. Marru, Lecture Notes in Computer Science 4145 - 0222, 2006 & International Provenance and Annotation Workshop (IPAW), 2006
  • A Survey of Data Provenance in e-Science, Y. L. Simmhan, B. Plale, and D. Gannon, SIGMOD Record, Vol. 34(3), 2005.

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

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 Wokflow 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.

Live systems

If your system can be accessed live (through portal, web page, web service, or other), provide relevant information here.

Further Comments

Provide here further comments.

Conclusions

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

-- YogeshSimmhan - 24 Jul 2006