• Short team name: ZOOM, Database Group, University of Pennsylvania

• Project URL: http://db.cis.upenn.edu/research/provwf.html

• instanceOf

• immStepContains

• containsStep

COMPOSTEP            STEP                 
---------------------------------
stepBox1-1           1                    
stepBox1-1           5                    
stepBox1-2           2                    
stepBox1-2           6                    
stepBox1-3           3                    
stepBox1-3           7                    
stepBox1-4           4                    
stepBox1-4           8                    
stepBox2-1           10                   
stepBox2-1           13                   
stepBox2-2           11                   
stepBox2-2           14                   
stepBox2-3           12                   
stepBox2-3           15                   
stepBox3-1           1                    
stepBox3-1           10                   
stepBox3-1           13                   
stepBox3-1           5                    
stepBox3-1           9                    
stepBox3-1           stepBox1-1           
stepBox3-1           stepBox2-1           

• • • Note: For security reasons, uBio does not know that only DATAIDs 1, 2, 9 and 10 are used by 1.align_warp.

• New Query: Find everything that caused “Resliced Image1” (ID 15) to be as it is?

• • Query for ‘uBlackBox’

• • • Result: no rows selected (uBlackBox cannot even see ‘Resliced Image1’)

• • Query for ‘uBio’

• • • Results obtained in a user friendly format:

• • Query for ‘uAdmin’

• • • Results obtained in a user friendly format:

Note that uAdmin can see that data id 11 (Warp Params 1) is part of the provenance while uBio cannot see it.

• tablesData-1.jpg:
  

• tablesData-2.jpg:
  

• tablesData-3.jpg:
  

• • Note: This query exploits the Connect by prior operator of Oracle which implements the transitive closure function. Transitive closure is necessary for returning all the data (recursively) that have been used to compute Atlas X Graphic. Basically, we use the Process table and search reccursively for the data used (output produced and input used, by mean of "connect by prior input=output").

• • Note: We follow the same process as previously but we remove (Minus operator) all the data used by "softmean".

• • Note: We follow the same idea than in query1 while focusing on stages 3, 4, and 5.

• • Note: The same results as query2 have been found. Query 2 and 3 are synonyms!

• • Note: We search for information about the step-class "align-warp" (first "Where" clause) such that there is a step whose parameter is "order=12" and "model=1365".

• Note: The dataAttributes table is used to find all Anatomy header data whose entry 'global maxiamum' is equal to 4095. Then, the same precess as previously is used (i.e. looking recursively for data).

• • Note: This query basically consists in a join between dataAttributes (which contains information about annotations), Process, and Data.

• • Note: Once again, this query consists in finding annotations in the dataAttributes table and to make joins to get other information.

Participating Team

• Participant names: Sarah Cohen-Boulakia, Shirley Cohen, Susan Davidson, Olivier Biton and Thunyarat (Bam) Amornpetchkul

• Query1

• Query3

• Query4

• • Result (User friendly view):

• Query5

• Query6
  • Query: _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." _

• Query7

• Query8

• Query9

COMPOSTEPCLASS       STEPCLASS 
---------------------------------  
box1                 align_warp           
box1                 reslice
box3                 box1         
box3                 align_warp           
box3                 reslice

• (i) to consider security levels (when the user is not allowed (a) to see the detail of a box and (b) to know which are the inputs used to produce a given output), and
• (ii) to focus on high-level information (when the user (a) is able to know which are the inputs used to produce a given output but (b) is not interested in knowing the details about the intermediate steps and data items).

The next query and the first version of new query will deal with (i) while the second version of new query will deal with (ii).

• Note: Only the first (DATAIDs 1 to 10) inputs of the workflow are seen by uBlackBox.

• • • Note: For security reasons, uBio does not know that only DATAIDs 1, 2, 9 and 10 are used by 1.align_wrap.

• • • Note: All the data are obtained (same results than for the very first version of query1).

• • First version (security) of the query for ‘uBlackBox’

• • Result (User friendly view):

• • Result (User friendly view):

• • Result (User friendly view):

• • • Result (SQL):

• Results obtained in a user friendly format:

• • • Results obtained in a user friendly format:

• • Second version (high-level) of the query for ‘uBio’

Aknowledgments

(* Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.)

• Participant names: Sarah Cohen-Boulakia, Shirley Cohen, Susan Davidson, Thunyarat (Bam) Amornpetchkul, and Olivier Biton

• Project Overview: This project aims to provide a formal model of provenance for scientific workflows which is both simple and general (i.e. can be used with existing workflow systems, such as Ptolemy/Kepler and myGrid) and sufficiently expressive to answer the provenance queries encountered in case studies. Interestingly, the proposed model not only takes into account the chained and complex structures of scientific workflows, but also allows for reasoning about provenance at different levels of abstraction through user views.

Note: The content of the tables is provided at the end of this page (see images tables1.png to tables4.png).

• Data

As an example, the data whose ID is 1 has the name “Anatomy Image1” and is of type Anatomy Image.

       DATAID               NAME                 TYPE   
-----------------------------------------------------              
1                    Anatomy Image1       Anatomy Image

• dataAttributes

      DATAID               ATTRIBUTE            VALUE   
-----------------------------------------------------  
1                    center               UChicago

• stepParam

As an example, the table below expresses that the step whose id is 1 takes a nonlinear (linear=false), 12th order (order=12) parameter, and whose model is 1365 (model=1365). This parameter can be invoked by using “-m 12 –q” (description=-m 12 –q).

      STEP                 ATTRIBUTE            VALUE    
-----------------------------------------------------             
1                    linear               false                
1                    order                12                   
1                    model                1365                 
1                    description          -m 12 -q     

• input

As an example, Step 2 (2.align_warp) takes as inputs data whose ID is 3 (Anatomy Image2), 4 (Anatomy Header2), 9 (Reference Image), and 10 (Reference Header). Each input in the example was taken on the same date, 8/8/2006.

STEP                 DATAID               TS   
-----------------------------------------------------                
2                    3                    8/8/2006            
2                    4                    8/8/2006            
2                    9                    8/8/2006            
2                    10                   8/8/2006

* output output(step int, dataId int, ts Date) stores information about an output from a step and the timestamp it occurred.

As an example, Step 10 (10. slicer) produced one output with a DATAID of 25 (Atlas X Slice) on 08/17/2006.

STEP                 DATAID               TS                  
-----------------------------------------------------  
10                   25                   8/17/2006   

• instanceOf

As an example, steps 1, 2, 3, and 4 are executions of the step-class “align_warp.”

    STEP                 STEPCLASS            TS    
-----------------------------------------------------               
1                    align_warp           8/7/2006            
2                    align_warp           8/8/2006            
3                    align_warp           8/10/2006           
4                    align_warp           8/11/2006           

• stageInstance

stageInstance(step string, stage string) stores the relationship between a stage and a step. As an example, steps 1 through 4 are in stage 1.

STEP                 STAGE
-----------------------------------------------------       
1                    1          
2                    1          
3                    1          
4                    1       

• Process

CREATE VIEW Process 
AS 
    SELECT DISTINCT 
          instanceOf.step      step, 
          instanceOf.stepClass stepClass, 
          input.dataId         input, 
          dataInput.name       inputName,
          output.dataId        output, 
          dataOutput.name      outputName,
          input.ts             time 
     FROM 
           instanceOf, 
           input, 
           data dataInput,
           output,
           data dataOutput
     WHERE instanceOf.step = input.step 
       AND input.dataId = dataInput.dataId
       AND input.step = output.step 
       AND output.dataId = dataOutput.dataId
       AND input.ts <= output.ts

   STEP STEPCLASS  INPUT  INPUTNAME OUTPUT OUTPUTNAME  TIME 
---------------------------------------------------------------- 
  13   convert    25     Atlas X Slice 28  Atlas X Graphic 8/20/2006 

Provenance Queries

• Query1
  • Query: 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.

SELECT DISTINCT step, stepClass, input, inputName, output, outputName 
     FROM process 
     START WITH output = 
              (
               SELECT dataId FROM data WHERE name = 'Atlas X Graphic'
               ) 
     CONNECT BY PRIOR input = output 
     ORDER BY step

• Note: This query exploits the Connect by prior operator of Oracle which implements the transitive closure function. Transitive closure is necessary for returning all the data (recursively) that have been used to compute Atlas X Graphic.
  • Result (SQL):

STEP STEPCLASS   INPUT    INPUTNAME            OUTPUT OUTPUTNAME         
----------------------------------------------------------------  
1    align_warp  1        Anatomy Image1       11     Warp Parameters1    
1    align_warp  10       Reference Header     11     Warp Parameters1    
1    align_warp  2        Anatomy Header1      11     Warp Parameters1    
1    align_warp  9        Reference Image      11     Warp Parameters1    
10   slicer      23       Atlas Image          25     Atlas X Slice       
10   slicer      24       Atlas Header         25     Atlas X Slice       
13   convert     25       Atlas X Slice        28     Atlas X Graphic     
2    align_warp  10       Reference Header     12     Warp Parameters2    
2    align_warp  3        Anatomy Image2       12     Warp Parameters2    
2    align_warp  4        Anatomy Header2      12     Warp Parameters2    
2    align_warp  9        Reference Image      12     Warp Parameters2    
3    align_warp  10       Reference Header     13     Warp Parameters3    
3    align_warp  5        Anatomy Image3       13     Warp Parameters3    
3    align_warp  6        Anatomy Header3      13     Warp Parameters3    
3    align_warp  9        Reference Image      13     Warp Parameters3    
4    align_warp  10       Reference Header     14     Warp Parameters4    
4    align_warp  7        Anatomy Image4       14     Warp Parameters4    
4    align_warp  8        Anatomy Header4      14     Warp Parameters4    
4    align_warp  9        Reference Image      14     Warp Parameters4    
5    reslice     11       Warp Parameters1     15     Resliced Image1     
5    reslice     11       Warp Parameters1     16     Resliced Header1    
6    reslice     12       Warp Parameters2     17     Resliced Image2     
6    reslice     12       Warp Parameters2     18     Resliced Header2    
7    reslice     13       Warp Parameters3     19     Resliced Image3     
7    reslice     13       Warp Parameters3     20     Resliced Header3    
8    reslice     14       Warp Parameters4     21     Resliced Image4     
8    reslice     14       Warp Parameters4     22     Resliced Header4    
9    softmean    15       Resliced Image1      23     Atlas Image         
9    softmean    15       Resliced Image1      24     Atlas Header        
9    softmean    16       Resliced Header1     23     Atlas Image         
9    softmean    16       Resliced Header1     24     Atlas Header        
9    softmean    17       Resliced Image2      23     Atlas Image         
9    softmean    17       Resliced Image2      24     Atlas Header        
9    softmean    18       Resliced Header2     23     Atlas Image         
9    softmean    18       Resliced Header2     24     Atlas Header        
9    softmean    19       Resliced Image3      23     Atlas Image         
9    softmean    19       Resliced Image3      24     Atlas Header        
9    softmean    20       Resliced Header3     23     Atlas Image         
9    softmean    20       Resliced Header3     24     Atlas Header        
9    softmean    21       Resliced Image4      23     Atlas Image         
9    softmean    21       Resliced Image4      24     Atlas Header        
9    softmean    22       Resliced Header4     23     Atlas Image         
9    softmean    22       Resliced Header4     24     Atlas Header    

• • Result (user friendly view):

* Query2

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

SELECT DISTINCT step, stepClass, input, inputName, output, outputName            
     FROM Process                                                                
     START WITH output = (                                                       
               SELECT dataId FROM data WHERE name = 'Atlas X Graphic'            
          )                                                                      
     CONNECT BY PRIOR input = output                                             
 MINUS (                                                                         
     SELECT DISTINCT step, stepClass, input, inputName, output, outputName       
          FROM Process                                                           
               START WITH output IN (                                            
                    SELECT input FROM Process WHERE stepClass = 'softmean'       
               )                                                                 
     CONNECT BY PRIOR input = output                                             
 )                                                                              

• • Result (SQL):

STEP    STEPCLASS   INPUT INPUTNAME            OUTPUT OUTPUTNAME   
----------------------------------------------------------------     
10      slicer      23    Atlas Image          25     Atlas X Slice   
10      slicer      24    Atlas Header         25     Atlas X Slice   
13      convert     25    Atlas X Slice        28     Atlas X Graphic 
9       softmean    15    Resliced Image1      23     Atlas Image     
9       softmean    15    Resliced Image1      24     Atlas Header    
9       softmean    16    Resliced Header1     23     Atlas Image     
9       softmean    16    Resliced Header1     24     Atlas Header    
9       softmean    17    Resliced Image2      23     Atlas Image     
9       softmean    17    Resliced Image2      24     Atlas Header    
9       softmean    18    Resliced Header2     23     Atlas Image     
9       softmean    18    Resliced Header2     24     Atlas Header    
9       softmean    19    Resliced Image3      23     Atlas Image     
9       softmean    19    Resliced Image3      24     Atlas Header    
9       softmean    20    Resliced Header3     23     Atlas Image     
9       softmean    20    Resliced Header3     24     Atlas Header    
9       softmean    21    Resliced Image4      23     Atlas Image     
9       softmean    21    Resliced Image4      24     Atlas Header    
9       softmean    22    Resliced Header4     23     Atlas Image     
9       softmean    22    Resliced Header4     24     Atlas Header    

• • Result (User friendly view): To be included soon

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

SELECT DISTINCT step, stepClass, input, inputName, output, outputName 
     FROM process                                                     
     WHERE step IN (                                                  
          SELECT step FROM StageInstance                              
          WHERE (                                                     
               stage in (3,4,5)                                       
          )                                                           
     )                                                                
     START WITH output = (                                            
           SELECT dataId FROM data WHERE name = 'Atlas X Graphic'     
     )                                                                
     CONNECT BY PRIOR input = output                                 

• • Result (SQL):

STEP  STEPCLASS INPUT INPUTNAME         OUTPUT  OUTPUTNAME     
----------------------------------------------------------------       
9     softmean  19    Resliced Image3   23      Atlas Image          
9     softmean  21    Resliced Image4   23      Atlas Image          
9     softmean  17    Resliced Image2   24      Atlas Header         
9     softmean  20    Resliced Header3  24      Atlas Header         
9     softmean  15    Resliced Image1   24      Atlas Header         
9     softmean  19    Resliced Image3   24      Atlas Header         
13    convert   25    Atlas X Slice     28      Atlas X Graphic      
9     softmean  15    Resliced Image1   23      Atlas Image          
9     softmean  18    Resliced Header2  23      Atlas Image          
9     softmean  16    Resliced Header1  23      Atlas Image          
9     softmean  18    Resliced Header2  24      Atlas Header         
9     softmean  17    Resliced Image2   23      Atlas Image          
10    slicer    23    Atlas Image       25      Atlas X Slice        
9     softmean  22    Resliced Header4  23      Atlas Image          
9     softmean  16    Resliced Header1  24      Atlas Header         
9     softmean  22    Resliced Header4  24      Atlas Header         
9     softmean  20    Resliced Header3  23      Atlas Image          
10    slicer    24    Atlas Header      25      Atlas X Slice        
9     softmean  21    Resliced Image4   24      Atlas Header         

• • Result (User friendly view): To be included soon

* Query4

• • Query: 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.

SELECT step, stepClass, input, inputName, output, outputName, time    
     FROM process                                                     
     WHERE stepClass = 'align_warp'                                   
     AND EXISTS                                                       
        (                                                             
       SELECT value                                                   
         FROM stepParams                                              
       WHERE stepParams.step = process.step                           
         AND attribute='order'                                        
         AND value='12'                                               
       )                                                              
     AND EXISTS                                                       
        (                                                             
       SELECT value                                                   
         FROM stepParams                                              
       WHERE stepParams.step = process.step                           
         AND attribute='model'                                        
         AND value='1365'                                             
       )                                                              
    AND rtrim(to_char(time, 'DAY')) = 'MONDAY'                       

• • Result (SQL):

STEP  STEPCLASS    INPUT  INPUTNAME         OUTPUT  OUTPUTNAME        TIME 
----------------------------------------------------------------      
1     align_warp   1      Anatomy Image1    11      Warp Parameters1  8/7/2006  
1     align_warp   2      Anatomy Header1   11      Warp Parameters1  8/7/2006  
1     align_warp   10     Reference Header  11      Warp Parameters1  8/7/2006  
1     align_warp   9      Reference Image   11      Warp Parameters1  8/7/2006  

• • Result (User friendly view): To be included soon

• Query5
  • Query: Find all Atlas Graphic images outputted from workflows where at least one of the input Anatomy Headers had an entry global maximum=4095.

SELECT name                                                             
  FROM data                                                             
  WHERE dataId IN                                                       
          (                                                             
        SELECT output                                                   
          FROM process                                                  
          START WITH input IN (                                         
                    SELECT data.dataId                                  
                      FROM data, dataAttributes                         
                      WHERE data.dataId = dataAttributes.dataId         
                        AND data.type = 'Anatomy Header'                
                      AND dataAttributes.attribute = 'global maximum'   
                      AND dataAttributes.value = '4095'                 
                   )                                                    
          CONNECT BY PRIOR output=input                                 
         )                                                              
  AND type = 'Atlas Graphic'            

• Result (SQL):

NAME 
---------------------             
Atlas X Graphic      
Atlas Y Graphic      
Atlas Z Graphic

• Query6
  • _Query: 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." _

SELECT distinct pred.orig,  data.name               
  FROM                                              
       (                                            
    SELECT distinct CONNECT_BY_ROOT step orig, step 
      FROM process                                  
      START WITH stepClass='softmean'               
      CONNECT BY PRIOR input=output                 
     ) pred,                                        
     output,                                        
     data                                           
  WHERE                                             
    EXISTS (                                        
              SELECT *                              
          FROM stepParams                           
                WHERE attribute = 'order'           
                AND value = 12                      
              AND stepParams.step = pred.step       
           )                                        
     AND EXISTS                                     
         (                                          
              SELECT *                              
          FROM stepParams                           
                WHERE attribute = 'model'           
          AND value = 1365                          
          AND stepParams.step = pred.step           
           )                                        
  AND pred.orig = output.step                       
  AND output.dataId = data.dataId                  

• • Result (SQL):

ORIG                 NAME  
---------------------------------               
9                    Atlas Header         
9                    Atlas Image          

• Query7
  • Query:_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. _

• • Note: Computing the difference between two workflows or two workflow executions will be possible in our next implementation. Query 7 is a very simple example of the problem. However, when the difference between the data used by a step or produced by a step is considered, the problem becomes much harder. We would be very interested in talking about this problem with the workshop attendees.

• Query8
  • Query: _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. _

SELECT distinct data.name                      
  FROM process, dataAttributes, data           
  WHERE process.stepClass='align_warp'         
    AND process.input = dataAttributes.dataId  
  AND dataAttributes.attribute = 'center'      
  AND dataAttributes.value = 'UChicago'        
  AND process.output = data.dataId            

• • Result:

NAME     
------------------            
Warp Parameters2     
Warp Parameters1  

• Query9
  • Query: 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.

SELECT distinct data.dataId, data.name, attribute, value                      
  FROM data, dataAttributes, attribute, value                                 
  WHERE                                                     
    data.type='Atlas Graphic'                               
  AND data.dataId = dataAttributes.dataId                   
  AND dataAttributes.attribute = 'studyModality'            
  AND dataAttributes.value IN ('speech', 'visual', 'audio')

• • Result:

DATAID               NAME                 ATTRIBUTE            VALUE   
---------------------------------------------------------------------             
29                   Atlas Y Graphic      studyModality        audio                
29                   Atlas Y Graphic      studyModality        visual               
30                   Atlas Z Graphic      studyModality        speech  

Given a workflow specification, the user view of a user (or class of users) U, userView(U), is the set of lowest-level step classes that U is entitled to see.

Note that a user view cannot contain two step classes such that one is contained in the other. We also assume that the user view is valid, i.e. that each of the highest-level step classes in the workflow specification is either in the view, or that at some lower-level all of its contained substeps are in the user view.

To answer questions of provenance, we must take the user view into account and reason about the input and output to steps which are instances of step-classes that are in the user view. We must know the containment relationship between step-classes and the relationship between each user and the step-classes he is entitled to see.

In the following, we introduce the part of our model which deals with user views and we will give examples based on a variation of the provenance workflow in the challenge. In the following discussion, we refer to composite steps as “boxes”.

Figure 2 – Workflow for the challenge with user views (boxes 1 to 3)

UserView Application

In this section, we introduce some additional tables which are needed for reasoning about provenance in the context of user views:

• immContains

As an example, box 1 covers all the step-class align_warp and reslice

COMPOSTEPCLASS       STEPCLASS 
---------------------------------           
box1                 align_warp           
box1                 reslice

• contains

CREATE VIEW
AS  
   SELECT DISTINCT CONNECT_BY_ROOT compoStepClass as compoStepClass, stepClass
     FROM immcontains
     CONNECT BY PRIOR stepClass=compoStepClass
     ORDER BY compoStepClass

• virtualInstanceOf

CREATE VIEW virtualInstanceOf
AS
  SELECT step step, stepClass, ts
    FROM instanceOf   
  UNION  
  select min(step) || '-' || compoStepClass, compoStepClass, min(ts)
    from contains, instanceOf
   where contains.stepClass = instanceOf.stepClass
    group By compoStepClass                                     

STEP      STEPCLASS   TS
-------------------------------         
1         align_warp  8/7/2006   
1-box1    box1        8/7/2006   

• userView

As an example, the user ‘uBlackBox’ sees the whole workflow as one step. The user ‘uBio’ cannot see the detail of step-class align_warp and reslice separately (he sees box1 instead). He cannot see the details of step-class slicer or convert (he sees box2 instead). However, he can see the step-class softmean. UAdmin can see all step-classes.

USR                  STEPCLASS  
--------------------------------          
uBlackBox            box3                 
uBio                 box1                 
uBio                 softmean             
uBio                 box2                 
uAdmin               align_warp           
uAdmin               reslice              
uAdmin               softmean             
uAdmin               slicer               
uAdmin               convert    

The following two tables, Cinput and Coutput are input and output extended to composite steps.

• Cinput

CREATE VIEW cInput           
AS              
 -- First union operand: "For each containment, the input is an input of  
   -- the higher level step class if and only if this input was not an output 
   -- from another of its sub steps        
   SELECT inst2.step, input.dataId, min(input.ts) ts      
    FROM input,            
     instanceOf inst1,          
       contains,           
       virtualInstanceOf inst2         
    WHERE             
     input.step = inst1.step         
      AND inst1.stepClass = contains.stepClass       
      AND contains.compoStepClass = inst2.stepClass      
      AND NOT EXISTS           
            (             
             SELECT o.step          
             FROM output o, instanceOf inst3, contains c2     
             WHERE o.dataId = input.dataId       
              AND o.step = inst3.step        
                AND inst3.stepClass = c2.stepClass       
                AND c2.compoStepClass = contains.compoStepClass    
          )             
    GROUP BY inst2.step, input.dataId        
   -- Second union operand          
   -- We want to keep the direct input relations       
   UNION             
   SELECT step, dataId, ts          
    FROM input            

STEP    DATAID  TS    
--------------------------              
10-box2 23      8/17/2006           
10-box2 24      8/17/2006           

• Coutput

CREATE VIEW coutput                     
AS                          
  -- First union operand: "For each containment, the output is an output of 
  -- the higher level step class if and only if this output is used as an   
  -- input for another step class which is not contained in the same step class 
  -- or if this is a final output of the workflow           
   SELECT inst2.step, output.dataId, output.ts             
  FROM output,                      
   instanceOf inst1,                  
   contains,                      
   virtualInstanceOf inst2                  
  WHERE                         
    output.step = inst1.step                
      AND inst1.stepClass = contains.stepClass            
      AND contains.compoStepClass = inst2.stepClass           
      AND EXISTS                      
       (                         
      /* Step class is used as an entry of 
       *  at least one step       
       * class which is not a substep of 
         this step class */       
         SELECT i.step                    
         FROM input i, instanceOf inst3             
         WHERE i.dataId = output.dataId             
                  AND i.step = inst3.step                
         AND NOT EXISTS                   
            (                      
             SELECT contains.compoStepClass            
             FROM contains                 
             WHERE contains.stepClass = inst3.stepClass        
             AND contains.compoStepClass = inst2.stepClass       
            )                      
         UNION                      
          -- Step class is a final output?            
         (                       
         SELECT output.dataId                
         FROM dual                   
         MINUS                     
         SELECT i.dataId                   
         FROM input i                  
         )                       
        )                       
   UNION                         
   -- Second union operand                   
   -- We want to keep the direct output relations          
   SELECT step, dataId, ts                   
  FROM output        

STEP         DATAID  TS  
---------------------------- 
10-box2      28 8/20/2006           
10-box2      29 8/21/2006           
10-box2      30 8/22/2006

• UProcess

CREATE VIEW UProcess                                    
AS                                                      
    SELECT DISTINCT                                     
        userView.usr            usr,                        
        instanceOf.step         step,                     
        instanceOf.stepClass    stepClass,              
        input.dataId            input,                        
        dataInput.name          inputName,                
        output.dataId           output,                     
        dataOutput.name         outputName,               
        input.ts                time                            
     FROM                                               
           userView,                                    
         virtualInstanceOf instanceOf,                  
           cinput input,                                
           data dataInput,                              
           coutput output,                              
           data dataOutput                              
     WHERE                                              
               userView.stepClass = instanceOf.stepClass
         AND instanceOf.step = input.step               
       AND input.dataId = dataInput.dataId              
       AND input.step = output.step                     
       AND output.dataId = dataOutput.dataId            
       AND input.ts <= output.ts                        
   --ORDER BY usr, step, input                          

The user ‘uAdmin’ can see all the steps of the workflow. First, he can see the wrap param images produced (DATAID 11 to 14). Then, he can see that only data ID 1, 2, 9, and 10 are used as inputs to step 1.

Suggested Queries

In this section, we answer query 1 considering user views and we introduce two other queries to emphasize the benefit of our approach. We will show that user views allow

• (i) to consider security levels (when the user is not allowed to see the details of a box and which are the inputs used to produced a given output), see the next query and the first version of new query, and
• (ii) to focus on high-level information (when the user is able to know which are the inputs used to produced a given output but is not interested in knowing the details about the intermediate steps), see the second version of new query.

* Query1 for each user

• • Results obtained in a user friendly format (to be included soon)
  • Query for user “uBlackbox”
    • Query:

SELECT DISTINCT step, stepClass, input, inputName, output, outputName     
     FROM uProcess                                                        
   WHERE usr='uBlackBox'                                                     
     START WITH output = (                                                
               SELECT dataId FROM data WHERE name = 'Atlas X Graphic'     
               )                                                          
     CONNECT BY PRIOR input = output                                      
     ORDER BY step;                                                        

• • • Result:

STEP       STEPCLASS   INPUT    INPUTNAME            OUTPUT   OUTPUTNAME        
-----------------------------------------------------------------------------
1-box3     box3        1        Anatomy Image1       28       Atlas X Graphic   
1-box3     box3        10       Reference Header     28       Atlas X Graphic   
1-box3     box3        2        Anatomy Header1      28       Atlas X Graphic   
1-box3     box3        3        Anatomy Image2       28       Atlas X Graphic   
1-box3     box3        4        Anatomy Header2      28       Atlas X Graphic   
1-box3     box3        5        Anatomy Image3       28       Atlas X Graphic   
1-box3     box3        6        Anatomy Header3      28       Atlas X Graphic   
1-box3     box3        7        Anatomy Image4       28       Atlas X Graphic   
1-box3     box3        8        Anatomy Header4      28       Atlas X Graphic   
1-box3     box3        9        Reference Image      28       Atlas X Graphic    

• • • Note: Only the first (DATAIDs 1 to 10) inputs of the workflow are seen by UBlackBox^?.
  • Query for user “uBio”
    • Query: As previously with WHERE users = ‘uBio’
    • Result:

STEP   STEPCLASS INPUT INPUTNAME        OUTPUT OUTPUTNAME      
1-box1 box1      1     Anatomy Image1   15     Resliced Image1 
1-box1 box1      1     Anatomy Image1   16     Resliced Header1
1-box1 box1      1     Anatomy Image1   17     Resliced Image2 
1-box1 box1      1     Anatomy Image1   18     Resliced Header2
1-box1 box1      1     Anatomy Image1   19     Resliced Image3 
1-box1 box1      1     Anatomy Image1   20     Resliced Header3
1-box1 box1      1     Anatomy Image1   21     Resliced Image4 
1-box1 box1      1     Anatomy Image1   22     Resliced Header4
1-box1 box1      10    Reference Header 15     Resliced Image1 
1-box1 box1      10    Reference Header 16     Resliced Header1
1-box1 box1      10    Reference Header 17     Resliced Image2 
1-box1 box1      10    Reference Header 18     Resliced Header2
1-box1 box1      10    Reference Header 19     Resliced Image3 
1-box1 box1      10    Reference Header 20     Resliced Header3
1-box1 box1      10    Reference Header 21     Resliced Image4 
1-box1 box1      10    Reference Header 22     Resliced Header4
1-box1 box1      2     Anatomy Header1  15     Resliced Image1 
1-box1 box1      2     Anatomy Header1  16     Resliced Header1
1-box1 box1      2     Anatomy Header1  17     Resliced Image2 
1-box1 box1      2     Anatomy Header1  18     Resliced Header2
1-box1 box1      2     Anatomy Header1  19     Resliced Image3 
1-box1 box1      2     Anatomy Header1  20     Resliced Header3
1-box1 box1      2     Anatomy Header1  21     Resliced Image4 
1-box1 box1      2     Anatomy Header1  22     Resliced Header4
1-box1 box1      3     Anatomy Image2   15     Resliced Image1 
1-box1 box1      3     Anatomy Image2   16     Resliced Header1
1-box1 box1      3     Anatomy Image2   17     Resliced Image2 
1-box1 box1      3     Anatomy Image2   18     Resliced Header2
1-box1 box1      3     Anatomy Image2   19     Resliced Image3 
1-box1 box1      3     Anatomy Image2   20     Resliced Header3
1-box1 box1      3     Anatomy Image2   21     Resliced Image4 
1-box1 box1      3     Anatomy Image2   22     Resliced Header4
1-box1 box1      4     Anatomy Header2  15     Resliced Image1 
1-box1 box1      4     Anatomy Header2  16     Resliced Header1
1-box1 box1      4     Anatomy Header2  17     Resliced Image2 
1-box1 box1      4     Anatomy Header2  18     Resliced Header2
1-box1 box1      4     Anatomy Header2  19     Resliced Image3 
1-box1 box1      4     Anatomy Header2  20     Resliced Header3
1-box1 box1      4     Anatomy Header2  21     Resliced Image4 
1-box1 box1      4     Anatomy Header2  22     Resliced Header4
1-box1 box1      5     Anatomy Image3   15     Resliced Image1 
1-box1 box1      5     Anatomy Image3   16     Resliced Header1
1-box1 box1      5     Anatomy Image3   17     Resliced Image2 
1-box1 box1      5     Anatomy Image3   18     Resliced Header2
1-box1 box1      5     Anatomy Image3   19     Resliced Image3 
1-box1 box1      5     Anatomy Image3   20     Resliced Header3
1-box1 box1      5     Anatomy Image3   21     Resliced Image4 
1-box1 box1      5     Anatomy Image3   22     Resliced Header4
1-box1 box1      6     Anatomy Header3  15     Resliced Image1 
1-box1 box1      6     Anatomy Header3  16     Resliced Header1
1-box1 box1      6     Anatomy Header3  17     Resliced Image2 
1-box1 box1      6     Anatomy Header3  18     Resliced Header2
1-box1 box1      6     Anatomy Header3  19     Resliced Image3 
1-box1 box1      6     Anatomy Header3  20     Resliced Header3
1-box1 box1      6     Anatomy Header3  21     Resliced Image4 
1-box1 box1      6     Anatomy Header3  22     Resliced Header4
1-box1 box1      7     Anatomy Image4   15     Resliced Image1 
1-box1 box1      7     Anatomy Image4   16     Resliced Header1
1-box1 box1      7     Anatomy Image4   17     Resliced Image2 
1-box1 box1      7     Anatomy Image4   18     Resliced Header2
1-box1 box1      7     Anatomy Image4   19     Resliced Image3 
1-box1 box1      7     Anatomy Image4   20     Resliced Header3
1-box1 box1      7     Anatomy Image4   21     Resliced Image4 
1-box1 box1      7     Anatomy Image4   22     Resliced Header4
1-box1 box1      8     Anatomy Header4  15     Resliced Image1 
1-box1 box1      8     Anatomy Header4  16     Resliced Header1
1-box1 box1      8     Anatomy Header4  17     Resliced Image2 
1-box1 box1      8     Anatomy Header4  18     Resliced Header2
1-box1 box1      8     Anatomy Header4  19     Resliced Image3 
1-box1 box1      8     Anatomy Header4  20     Resliced Header3
1-box1 box1      8     Anatomy Header4  21     Resliced Image4 
1-box1 box1      8     Anatomy Header4  22     Resliced Header4
1-box1 box1      9     Reference Image  15     Resliced Image1 
1-box1 box1      9     Reference Image  16     Resliced Header1
1-box1 box1      9     Reference Image  17     Resliced Image2 
1-box1 box1      9     Reference Image  18     Resliced Header2
1-box1 box1      9     Reference Image  19     Resliced Image3 
1-box1 box1      9     Reference Image  20     Resliced Header3
1-box1 box1      9     Reference Image  21     Resliced Image4 
1-box1 box1      9     Reference Image  22     Resliced Header4
10-box2box2      23    Atlas Image      28     Atlas X Graphic 
10-box2box2      24    Atlas Header     28     Atlas X Graphic 
9      softmean  15    Resliced Image1  23     Atlas Image     
9      softmean  15    Resliced Image1  24     Atlas Header    
9      softmean  16    Resliced Header1 23     Atlas Image     
9      softmean  16    Resliced Header1 24     Atlas Header    
9      softmean  17    Resliced Image2  23     Atlas Image     
9      softmean  17    Resliced Image2  24     Atlas Header    
9      softmean  18    Resliced Header2 23     Atlas Image     
9      softmean  18    Resliced Header2 24     Atlas Header    
9      softmean  19    Resliced Image3  23     Atlas Image     
9      softmean  19    Resliced Image3  24     Atlas Header    
9      softmean  20    Resliced Header3 23     Atlas Image     
9      softmean  20    Resliced Header3 24     Atlas Header    
9      softmean  21    Resliced Image4  23     Atlas Image     
9      softmean  21    Resliced Image4  24     Atlas Header    
9      softmean  22    Resliced Header4 23     Atlas Image     
9      softmean  22    Resliced Header4 24     Atlas Header    

• • • Note: UBio does not know that only DATAIDs 1, 2, 9 and 10 are used by 1.align_wrap. He thinks that DATAIDs 1 through 10 are necessary. The same can be said for the steps inside box1 and box2.
  • Query for user “uAdmin”
    • Query: As previously with WHERE users = ‘uAdmin’
    • Result:

STEP   STEPCLASS      INPUT  INPUTNAME            OUTPUT  OUTPUTNAME        
--------------------------------------------------------------------------
1      align_warp     1      Anatomy Image1       11      Warp Parameters1  
1      align_warp     10     Reference Header     11      Warp Parameters1  
1      align_warp     2      Anatomy Header1      11      Warp Parameters1  
1      align_warp     9      Reference Image      11      Warp Parameters1  
10     slicer         23     Atlas Image          25      Atlas X Slice     
10     slicer         24     Atlas Header         25      Atlas X Slice     
13     convert        25     Atlas X Slice        28      Atlas X Graphic   
2      align_warp     10     Reference Header     12      Warp Parameters2  
2      align_warp     3      Anatomy Image2       12      Warp Parameters2  
2      align_warp     4      Anatomy Header2      12      Warp Parameters2  
2      align_warp     9      Reference Image      12      Warp Parameters2  
3      align_warp     10     Reference Header     13      Warp Parameters3  
3      align_warp     5      Anatomy Image3       13      Warp Parameters3  
3      align_warp     6      Anatomy Header3      13      Warp Parameters3  
3      align_warp     9      Reference Image      13      Warp Parameters3  
4      align_warp     10     Reference Header     14      Warp Parameters4  
4      align_warp     7      Anatomy Image4       14      Warp Parameters4  
4      align_warp     8      Anatomy Header4      14      Warp Parameters4  
4      align_warp     9      Reference Image      14      Warp Parameters4  
5      reslice        11     Warp Parameters1     15      Resliced Image1   
5      reslice        11     Warp Parameters1     16      Resliced Header1  
6      reslice        12     Warp Parameters2     17      Resliced Image2   
6      reslice        12     Warp Parameters2     18      Resliced Header2  
7      reslice        13     Warp Parameters3     19      Resliced Image3   
7      reslice        13     Warp Parameters3     20      Resliced Header3  
8      reslice        14     Warp Parameters4     21      Resliced Image4   
8      reslice        14     Warp Parameters4     22      Resliced Header4  
9      softmean       15     Resliced Image1      23      Atlas Image       
9      softmean       15     Resliced Image1      24      Atlas Header      
9      softmean       16     Resliced Header1     23      Atlas Image       
9      softmean       16     Resliced Header1     24      Atlas Header      
9      softmean       17     Resliced Image2      23      Atlas Image       
9      softmean       17     Resliced Image2      24      Atlas Header      
9      softmean       18     Resliced Header2     23      Atlas Image       
9      softmean       18     Resliced Header2     24      Atlas Header      
9      softmean       19     Resliced Image3      23      Atlas Image       
9      softmean       19     Resliced Image3      24      Atlas Header      
9      softmean       20     Resliced Header3     23      Atlas Image       
9      softmean       20     Resliced Header3     24      Atlas Header      
9      softmean       21     Resliced Image4      23      Atlas Image       
9      softmean       21     Resliced Image4      24      Atlas Header      
9      softmean       22     Resliced Header4     23      Atlas Image       
9      softmean       22     Resliced Header4     24      Atlas Header      

• • • Note: All the data are obtained.

• New Query: What are the inputs that “Resliced Image1” (ID 15) depends on?

• • First version (security) of the query for ‘uBlack’
    • Query:

SELECT *
  FROM uProcess  upc 
     WHERE usr = 'uBlack'
     START WITH outputName = 'Resliced Image1'
     CONNECT BY PRIOR upc.output = upc.input;  

• • • Result: no rows selected

• • First version of the query for ‘uBio’
    • Query: Idem with ‘uBio’
    • Result:

  INPUT
----------
         1
         2
         3
         4
         5
         6
         7
         8
         9
        10

• • First version (security) of the query for ‘uAdmin’
    • Query: Idem with ‘uAdmin’
    • Result:

INPUT
----------
         1
         2
         9
        10
        11

• • Second version (high-level) of the query for ‘uBlack’
    • Query:

• • • Result: no rows selected

• • Second version (high-level) of the query for ‘uBio’
    • Query: Idem with ‘uBio’
    • Result:

INPUT
----------
         1
         2
         9
        10
        11

• • Second version (high-level) of the query for ‘uAdmin’
    • Query: Idem with ‘uAdmin’
    • Result:

INPUT
----------
         1
         2
         9
        10
        11

Generally speaking, our provenance queries can be categorized as such:

• step vs data provenance: depending on whether the user is interested in knowing the step(s) or the data that have been used to produce a given data item.
• immediate vs deep provenance: depending on whether the user is interested in knowing only the previous step (and possibly the data used by this step) or the whole sequence of steps (and possibly the data used by these steps) used to produced a given data item.

According to our classification, all the queries proposed in this challenge are deep provenance queries, they are both step and data provenance queries.

We would be interested in discussing with the workshop attendees about three points: (i) the meaning of a stage in a workflow (and in particular, how to interpret this notion with respect to user views), (ii) the biological significance of the procedures that can compose a workflow (in the workflow provided, what are the “significant” steps for a biologist?) and (iii) the (general) problem of computing a difference between two workflows (cf. query 7).

-- SarahCohenBoulakia - 10 Sep 2006

• tables1.png:
  

• tables2.png:
  

• tables3.png:
  

• tables4.png:
  

• Relevant Publications: Shirley Cohen, Sarah Cohen-Boulakia and Susan Davidson. Towards a Model of Scientific workflows and User Views. Proceedings of DILS'06, Data Integration for the Life Sciences, Springer-Verlag, Lecture Notes in Bioinformatics (LNBI) Num. 4075, pp. 264-279.

Provenance Challenge Template

Participating Team (Under construction)

• Short team name: Database Group, University of Pennsylvania
• Participant names: Sarah Cohen-Boulakia, Shirley Cohen, Susan Davidson, Thunyarat (Bam) Amornpetchkul
• Project URL: http://db.cis.upenn.edu
• Project Overview: This project aims to provide a formal model of provenance for scientific workflows which is simple and general (i.e. can be used with existing workflow systems, such as Kepler and myGrid) and sufficiently expressive to answer the provenance queries encountered in case studies. Interestingly, our model not only takes into account the chained and complex structure of scientific workflows, but allows asks for provenance at different levels of abstraction using user views.
• Provenance-specific Overview: See above.
• Relevant Publications: Shirley Cohen, Sarah Cohen-Boulakia and Susan Davidson. Towards a Model of Scientific workflows and User Views. Proceedings of DILS'06, Data Integration for the Life Sciences,

The following will be updated soon!

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

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.

-- SarahCohenBoulakia - 06 Sep 2006