Christine Froidevaux

Guangyu Chen

Weihua Li

Yandong He

Chen Bai

Cong Wang

Zeng

Keywords: scientic workows, provenance, provenance-equivalence, graph rewriting, series-parallel graphs, Taverna, anti-patterns

Bioinformatics experiments are usually performed using scientic workows in which tasks are chained together forming very intricate and nested graph structures. Scientic workow systems have then been developed to guide users in the design and execution of workows. An advantage of these systems over traditional approaches is their ability to automatically record the provenance (or lineage) of intermediate and nal data products generated during workow execution. The provenance of a data product contains information about how the product was derived, and it is crucial for enabling scientists to easily understand, reproduce, and verify scientic results. For several reasons, the complexity of workow and workow execution structures is increasing over time, which have a clear impact on scientic workows reuse.

The two main approaches of this thesis (namely, SPFlow and DistillFlow) are based on a provenance model that we have introduced to represent the provenance structure of the workow executions. The notion of provenance-equivalence which determines whether two workows have the same meaning is also at the center of our work. Our solutions have been systematically tested on large collections of real workows, especially from the Taverna system. Our approaches are available for use at https://www.lri.fr/∼chenj/.

The global aim of this thesis is to enhance workow reuse by providing strategies to reduce the complexity of workow structures while preserving provenance. Two strategies are introduced.

First, we propose an approach to rewrite the graph structure of any scientic workow (classically represented as a directed acyclic graph (DAG)) into a simpler structure, namely, a series-parallel (SP) structure while preserving provenance. SP-graphs are simple and layered, making the main phases of workow easier to distinguish. Additionally, from a more formal point of view, polynomialtime algorithms for performing complex graph-based operations (e.g., comparing workows, which is directly related to the problem of subgraph homomorphism) can be designed when workows have SP-structures while such operations are related to an NP-hard problem for DAG structures without any restriction on their structures. The SPFlow rewriting and provenance-preserving algorithm and its associated tool are thus introduced.

Second, we provide a methodology together with a technique able to reduce the redundancy present in workows (by removing unnecessary occurrences of tasks).

More precisely, we detect "anti-patterns", a term broadly used in program design to indicate the use of idiomatic forms that lead to over-complicated design, and which should therefore be avoided. We thus provide the DistillFlow algorithm able to transform a workow into a distilled semantically-equivalent workow, which is free or partly free of anti-patterns and has a more concise and simpler structure.

iii Résumé Les expériences bioinformatiques sont généralement eectuées à l'aide de workows scientiques dans lesquels les tâches sont enchaînées les unes aux autres pour former des structures de graphes très complexes et imbriquées. Les systèmes de workows scientiques ont ensuite été développés pour guider les utilisateurs dans la conception et l'exécution de workows. Un avantage de ces systèmes par rapport aux approches traditionnelles est leur capacité á mémoriser automatiquement la provenance (ou lignage) des produits de données intermédiaires et naux générés au cours de l'exécution du workow. La provenance d'un produit de données contient des informations sur la façon dont le produit est dérivé, et est cruciale pour permettre aux scientiques de comprendre, reproduire, et vérier les résultats scientiques facilement. Pour plusieurs raisons, la complexité du workow et des structures d'exécution du workow est en augmentation au l du temps, ce qui a un impact évident sur la réutilisation des workows scientiques. L'objectif global de cette thèse est d'améliorer la réutilisation des workows en fournissant des stratégies visant à réduire la complexité des structures de workow tout en préservant la provenance. Deux stratégies sont introduites. Tout d'abord, nous proposons une approche de réécriture de la structure du graphe de n'importe quel workow scientique (classiquement représentée comme un graphe acyclique orienté (DAG)) dans une structure plus simple, à savoir une structure séries-parallèle (SP) tout en préservant la provenance. Les SP-graphes sont simples et bien structurés, ce qui permet de mieux distinguer les principales étapes du workow. En outre, d'un point de vue plus formel, on peut utiliser des algorithmes polynomiaux pour eectuer des opérations complexes fondées sur les graphiques (par exemple, la comparaison de workows, ce qui est directement lié au problème d'homomorphisme de sous-graphes) lorsque les workows ont des SP-structures alors que ces opérations sont reliées à des problèmes NP-hard pour des graphes qui sont des DAG sans aucune restriction sur leur structure. Nous avons introduit la notion de préservation de la provenance, conçu l'algorithme de réécriture SPFlow et réalisé l'outil associé.

Deuxièmement, nous proposons une méthodologie avec une technique capable de réduire la redondance présente dans les workow (en supprimant les occurrences inutiles de tâches). Plus précisément, nous détectons des "anti-modèles ", un iv terme largement utilisé dans le domaine de la conception de programme, pour indiquer l'utilisation de formes idiomatiques qui mènent à une conception trop compliquée, et qui doit donc être évitée. Nous avons ainsi conçu l'algorithme DistillFlow qui est capable de transformer un workow donné en un workow sémantiquement équivalent "distillé", c'est-à-dire, qui est libre ou partiellement libre des anti-modèles et possède une structure plus concise et plus simple.

Les deux principales approches de cette thèse (à savoir, SPFlow et DistillFlow) sont basées sur un modèle de provenance que nous avons introduit pour représenter la structure de la provenance des exécutions du workowl. La notion de "provenance-équivalence" qui détermine si deux workows ont la même signication est également au centre de notre travail. Nos solutions ont été testées systématiquement sur de grandes collections de workows réels, en particulier avec le système Taverna. Nos outils sont disponibles à l'adresse: https://www.lri.fr/∼chenj/.

Mots-clés : workow scientique, provenance, provenance-équivalence, graphes séries-parallèles, SP-graphes, Taverna, anti-modèles. [LAB + 06], Chimera [START_REF] Foster | Chimera: A virtual data system for representing, querying, and automating data derivation[END_REF], Galaxy [GNT + 10], Wings [GRD + 07]) are increasingly being used by scientists to construct and execute complex scientic analyses. Such analyses are typically data-centric and involve "gluing" together data retrieval, computation, and visualization components into a single executable analysis pipeline [START_REF] Bowers | Structured composition of dataow and control-ow for reusable and robust scientic workows[END_REF]. Such a pipeline is represented by a workow which is modeled as a graph, where edges denote scheduling dependencies between computation tasks [START_REF] Hui | Workow model analysis based on time constraint petri nets[END_REF][START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF]. Intuitively, a workow specication is a framework for the execution of workows, which species the set of tasks that are performed and the order to be observed between the dierent tasks executions. According to the input data given to the workow specication and assignments of values to the task parameters, dierent workow runs are obtained. A run is then also represented as a graph where each vertex represents the execution of a task and edges are labeled by the data consumed and produced at each step. In this thesis, following what is in several workow systems, we will consider that the specications have a directed cyclic graph (DAG) structure and the runs have the same structures as their specications. The main goal of scientic workows, is with the increasing complexity of runs and the need for reproducibility of results, provenance has become an important research topic [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF]. The provenance (also referred to as lineage, and pedigree) of a data product contains information about the process and data used to derive the product [START_REF] Davidson | Provenance and scientic workows: challenges and opportunities[END_REF]. It is often organized as dependency graphs [MFF + 08]. The visualization of such dependency graphs is especially useful for scientic workow reuse, since the data, processes, and dependencies associated with a workow run can be clearly seen by workow users. By analysing and creating insightful visualizations of provenance data, 1.1. Motivation 3 scientists can debug their tasks and obtain a better understanding of their results. With the help of provenance, scientists who wish to perform new analyses should be able to nd workow specications with same or similar meanings of interest to reuse or modify. They can also search for executions associated with a specication to understand the meaning of the workow, or to correct/debug an erroneous specication. Furthermore, structural provenance queries can help scientists to determine what produced data might have been aected by its input, or to understand how and why the process that led to create a given data has actually failed. Therefore, provenance information is clearly useful for scientic workows users and systems. However, due to the complexity of workows, the provenance information which is organized into a graph becomes very large, for which understanding and exploring provenance information becomes a signicant challenge for users [DF08, MFF + 08]. While most systems record and store data and process dependencies, a few provide easy-to-use and ecient approaches for accessing provenance information [START_REF] Allen | Managing Provenance for Knowledge Discovery and Reuse[END_REF]. Additionally, some workow systems take complex data structure (e.g., lists [HWS + 06], trees [START_REF] Bowers | McPhillips et Bertram Ludäscher : Provenance in collection-oriented scientic workows[END_REF], • • • ) into account, which makes provenance presentation a very challenging point. However, to support better reuse of scientic workows, provenance should be more exploited to present the meaning of scientic workows for both workow systems and users.

In the last decade, considerable eort has been put into the improvement of sharing and reusing scientic workows. Workow reuse in e-Science is intrinsically linked to a desire that workows be shared and reused by the community as (part of) best practice scientic protocols [START_REF] Goderis | Seven bottlenecks to workow reuse and repurposing[END_REF]. It has the potential to [GSLG05, LRL + 12]: reduce workow authoring time (less "re-inventing the wheel"); improve quality through shared workow development (leveraging the expertise of previous users); and improve experimental provenance at the process level through reuse of established and validated workows (analogous to using proven algorithms or practices rather than inventing a new which is potentially error-prone). However, as stated by recent studies [SCBL12, CBL11, LRL + 12], while the number of available scientic workows is increasing along with their popularity, workows are not (re)used and shared as much as they could be. Several years ago, Goderis et al. [START_REF] Goderis | Seven bottlenecks to workow reuse and repurposing[END_REF] summarized several bottlenecks of workow Chapter 1. Introduction reuse and repurposing, in which they argue that the main reasons are the restrictions on service availability, lack of a comprehensive discovery model and the complexity of workows. According to Zhao et al. in [ZGPB + 12], one of the main impediments to workow reuse is due to the decayed or reduced ability of the resources required for executing workow, like services and data, which can be either local and hosted along with the workow or remote, such as public repositories or web services hosted by third parties. The causes of this impediments include: (1) it is dicult to volatile third-party resources; (2) missing example data (it is not always obvious which data can be used as inputs to the workow execution, and example inputs are often most helpful); (3) missing execution environment (the execution of a workow may rely on a particular local execution environment, e.g., a local R server or a specic version of workow execution software); (4) insucient descriptions about workows (sometimes a workow workbench cannot provide sucient information about what caused the failure of a workow run).

Several solutions for these causes can be found in [ZGPB + 12].

In this thesis, we have focused specically on the Taverna workow management system, which for the past ten years, has been popular within the bioinformatics community [HWS + 06]. Despite the fact that hundreds of Taverna workows have been available for years through the myExperiment public workow repository [START_REF] De Roure | The design and realisation of the myExperiment virtual research environment for social sharing of workows[END_REF] (http://www.myexperiment.org), their reuse by scientists other than the original author is generally limited [START_REF] Cohen-Boulakia | Search, adapt, and reuse: the future of scientic workows[END_REF]. Recently, several studies [SCBL12, CBL11, LRL + 12, TZF10] highlight the complexity of workow structures as one of the main reason of the limited reuse of (Taverna) scientic workows. The complexity of workow structure, involves the number of nodes and links but is also related to intricate workow structure features [CBCG + 13].

Again, several factors may explain such a structural complexity including the fact that the bioinformatics process to be implemented is intrinsically complex, or the workow system may not provide appropriate expressivity, forcing users to design arbitrary complex workows. Therefore, to obtain a simpler workow structure for a complex workow while preserving the meaning (provenance/semantics) becomes especially important.

Motivated by the facts above, rewriting complex scientic workow structures into simpler ones to make them easier to (re)use thus is the main topic of this 1.2. Problem Statement 5 thesis. In the next section, we will state the problems on this topic in details.

Problem Statement

In this thesis, our aim is to provide strategies to design scientic workows.

The originality of our approach lies in considering two notions, namely, provenance and workow structures. Our contributions have been introduced in our published papers [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF] and [CBCG + 13]. In this document, we recall them and provide detailed explanations and discussion on our work.

As provenance provides support in scientic workow reuse, a signicant number of tools for managing the vast amounts of data provenance have been designed to assist the storage of provenance data (e.g., indexing...), query the data (e.g., dierence between executions, search for patterns), visualize the workow provenance or (re)schedule executions... These tools all make intrinsically complex operations on graph structures (search for subgraphs in a graph, comparing graphs, ...), which, if carried out on Directed Acyclic Graphs (DAGs), with no other restriction of structure, may lead to NP-hard problems. Instead, these problems can be solved in polynomial time when specic restrictions are imposed on graphs, such as considering series-parallel (SP) structures [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF]. Some provenance management approaches from [BBD + 09, BBDH08, BCC + 05] have therefore chosen to restrict workow graphs to SP structures. However, in general, workows obtained using workow systems are DAGs with any structure. Providing a procedure to rewrite any workow graph into an SP graph while preserving provenance information would allow to better exploit the provenance management tools and should make scientic workows easier to (re)use. This is the rst goal of this research. The rst research question addressed in this thesis is:

(1) How to rewrite any workow graph into SP graph while preserving provenance?

The second main contribution of our work focuses on scientic workow structures themselves. We argue that one of the contributing factors for the diculties in reuse, is the presence of certain design "anti-patterns", a term broadly used in business process modelling and program design, to indicate the use of idiomatic Chapter 1. Introduction forms that lead to over-complicated design, and which should therefore be avoided.

Our preliminary analysis of the structure of 1,400 scientic workows collected from myExperiments reveals that, in numerous cases, such a complexity is due mainly to redundancy, which is in turn an indication of over-complicated design, and thus there is a chance for a reduction in complexity which does not alter the workow semantics. Our main contention in this fact is that such a reduction in complexity can be performed automatically, and that it will be benecial both in terms of user experience (easier design and maintenance), and in terms of operational eciency (easier to manage, and sometimes to exploit the latent parallelism amongst the tasks). So, the second research question addressed in this thesis is:

(2) How to rewrite scientic workows to make them free or partly free of redundancy without altering the workow semantics?

The solutions for these two research questions are respectively presented in Chapter 4 and Chapter 5. The next section describes in more details the actual contributions.

Contributions

Our main contributions are summarized as below.

First series of contributions (have been published in the 8th IEEE International Conference on eScience 2012 [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF] and the 28th Journees de Bases de Donnees Avancees (BDA) 2012 [START_REF] Cohen-Boulakia | Reecriture de workows scientiques et provenance[END_REF]):

• We propose a model to represent scientic workows and provenance generated in their execution.

• We give a denition of the notion of provenance-equivalence which can be used to identify whether two workows have the same meaning.

• We review several rewriting strategies for transforming non-SP graphs into SP graphs and prove that they are not provenance-equivalent.

• We design a provenance-equivalent algorithm, named "SPFlow", to translate non-SP workows into SP workows.

Thesis Structure

7

• We illustrate our algorithm by providing an evaluation of our approach on a thousand of scientic workows.

• We develop a tool based on SPFlow, which takes in a non-SP Taverna workow and provide an SP version of the workow usable in Taverna.

Second series of contributions (have been published in the "BMC Bioinformatics" Journal [CBCG + 13] and the 12th International Workshop on Network Tools and Applications in Biology, Nettab 2012 (poster) [CCBF + 12]):

• We identify and automatically detect a set of anti-patterns that contribute to the structural workow complexity.

• We design a series of refactoring transformations to replace each anti-pattern by a new semantically-equivalent pattern with less redundancy and simplied structure.

• We introduce a distilling algorithm that takes in a workow and produces a distilled semantically-equivalent workow.

• We provide an implementation of our refactoring approach that we evaluate on both the public Taverna workows and on a private collection of workows from the BioVel project.

Thesis Structure

This thesis is organized as follows:

• Chapter 1 gives the introduction of this thesis by stating the motivation, research problems and contributions.

• Chapter 2 presents a collection of mathematical notations used throughout the rest of this dissertation (2.1). Based on such notations, the workow model used in this dissertation is introduced (2.2). We then give an introduction to series-parallel graphs and their properties (2.3). At the end of chapter 2, we provide an introduction to the workows of Taverna system, which is the system that we have chosen to mainly work on.

Chapter 1. Introduction

• Chapter 3 starts with related work on provenance models (3.1), and then proposes a model to represent the provenance of workow executions (3.2).

Later we give a denition of the notion of provenance-equivalence which can be used to identify whether two workows have the same meaning (3.3).

Finally, a discussion about extending our provenance model to better support lists of data is given (3.4).

• Chapter 4 rst gives an in-depth explanation of the motivation of rewriting non-SP workows into SP workows (4.1). Then we introduce the concept of measuring the distance from non-SP to SP, which inspires some transformation techniques of rewriting non-SP graphs into SP graphs. (4.2). We then analyze the existing strategies to identify whether they are provenancepreserving and propose a new provenance-equivalent strategy (4.3). We introduce the SPFlow algorithm for transforming non-SP graphs into SP graphs and discuss the complexity and soundness of the algorithm in 4.4.

We demonstrate the feasibility of our approach on real scientic workows in 4.5. We nally present a tool with the same name of our algorithm, which takes in a non SP Taverna workow and provide an SP version of the workow usable in Taverna (4.6).

• Chapter 5 rst gives a deep explanation of the second research problem we have considered by presenting several use cases (5.1). Then we introduce the anti-patterns we have identied and the transformations we propose to do while ensuring that the semantics of the workow remains unchanged (5.2). We then introduce the DistillFlow refactoring algorithm (5.3). In 5.4, we provide the results obtained by our approach on a large set of real workows. Finally, we discuss several points related to our approach.

• Chapter 6 gives the conclusions and the future works. Workows in general, and scientic workows in particular, are directed graphs where the nodes represent tasks, and the edges represent the relations between the tasks [START_REF] Taylor | Workows for e-science: scientic workows for grids[END_REF]. Various operations can be performed on scientic workows, such as designing workows, visualizing them, querying repositories of workows, executing workows (involving scheduling executions, indexing executions, • • • ). Each of the operations is then intrinsically related to complex operations on graph structures: clustering graphs, comparing graphs, leading to the problem of (sub)graph isomorphism. Such operations are then very time-consuming on general graph structures while they can be sloved more easily when a particular structure of graphs is considered. With this respect, a special kind of graphs named "seriesparallel" graphs (SP graphs) is a useful class of graphs which are simple and layered, and their edges do not intersect, making the main phases of workow easier to distinguish. More ecient solutions for workow operations can thus be carried out when SP structures are considered.

Chapter 2. Preliminaries

This chapter mainly presents a collection of mathematical notations used throughout the rest of this dissertation (2.1). Based on such notations, the workow model used in this dissertation is introduced (2.2). We then give an introduction to seriesparallel graphs and their properties (2.3). At the end of this chapter, we provide an introduction to the workows of Taverna system, which is the system that we have chosen to mainly work on.

Basic graph concepts and notations

We dene here the basic concepts related to graphs and introduce the notations We allow multiple edges between the same two vertices in the graph. The graphs with multiple directed edges are called multidigraphs. Cycles will not be considered in our study. Thus, the graphs used in our study are Acyclic multidigraphs, abbreviated as multidag (cf. Denition 2.1.2 Let G = (V, E) be a multidag. For each edge e ∈ E ⊆ V × V , which is denoted by (u, v) or e(u, v), in E, u is the source of the edge and v is the target of the edge.

Denition 2.1.3 Let G = (V, E) be a multidag. For each vertex v ∈ V , the indegree, d -(v), is the number of edges that end by v (means v is the target of the edges) and the outdegree, d + (v) is the number of edges that start from v (means v is the source of the edges). More formally we have:

d -(v) = |{e(u, v) ∈ E}| d + (v) = |{e(v, u) ∈ E}| Example 2.1.1 In Figure 2.1 (a), d -(a) = 1 and d + (a) = 2. Denition 2.1.4 Let G = (V, E) be a multidag. The successors set of a vertex v ∈ V is the set of target vertices of edges outgoing from v, denoted by Succ(v).
The predecessors set of a vertex v is the set of source vertices of edges for which v is the target, denoted by P red(v). More formally we have: Chapter 2. Preliminaries Denition 2.1.5 Let G = (V, E) be a multidag. A source of a graph is a vertex

Succ(v) = {u : e(v, u) ∈ E} P red(v) = {u : e(u, v) ∈ E} Example 2.1.2 In
v with d -(v) = 0. A target of a graph is a vertex v with d + (v) = 0. S(G)
is the set of all sources in G, and T (G) is the set of all targets in G.

S(G) = {v ∈ V : d -(v) = 0} T (G) = {v ∈ V : d + (v) = 0} Example 2.1.3 As in Figure 2.1 (a), S(G) = {s} and T (G) = {t}. Denition 2.1.6 Let G = (V, E) be a multidag. A path is an ordered sequence of vertices p(v 1 , v k ) = [v 1 , v 2 , • • • , v k ] such that (v i , v i+1 ) ∈ E for 1 ≤ i < k.
To distinguish paths that have the same source and the same target, we use p (u, v) x to denote the path p(u, v) which contains vertex x. If there is only one single path from u to v or it consists of a single edge, we denote it as p(u, v).

A full path is a path p(u,v) where u is a source of G and v a target of G. Denition 2.1.7 [START_REF] González | Synchronization Architecture in Parallel Programming Models[END_REF] A vertex v is said to be reachable in the multidag G from another vertex v ′ i there exists a path p(v ′ , v).

Example 2.1.5 Consider Figure 2.1 (a) again. c is reachable from a, but c is not

reachable from b. Denition 2.1.8 [Val78, Esc03] A multidag G = (V, E) is transitive i if there is a path p(u, v) in G, there also exists an edge e(u, v). The transitive closure of G = (V, E) is another graph G tc = (V tc , E tc ) where V tc = V and E tc is the minimal subset of V × V that includes E and makes G tc transitive.
Denition 2.1.9 [START_REF] Valdes | Parsing owcharts and series-parallel graphs[END_REF][START_REF] González | Synchronization Architecture in Parallel Programming Models[END_REF] An edge e(u, v) of a multidag is redundant if there is a path p(u, v) not including the edge. The transitive reduction of a multidag is the multidag obtained by removing all the redundant edges. Example 2.1.7 Figure 2.1 (a) is an st-multidag with source s and target t.

A multidag may have several sources and targets. As we will see in the following, we will consider graphs with one source and one target (as classically when there is a need to compare graph structures). We will thus introduce the notion of generalized st-multidag to dene graphs that we "root". In such structures, any vertex will appear in a path from the source to the target. Denition 2.1.11 The generalized st-multidag

G st = (V st , E st ) of a multidag G = (V, E
) is a two-terminal multidag, constructed from G, by adding at most two vertices v s , v t and O(n) edges as follows: Property 2.1.1 Properties of st-multidags [START_REF] Valdes | Parsing owcharts and series-parallel graphs[END_REF][START_REF] González | Synchronization Architecture in Parallel Programming Models[END_REF] :

V st = V ∪ {v s } and E st = E ∪ {e(v s , v) : v ∈ S(G)} if |S(G)| > 1 V st = V ∪ {v t } and E st = E ∪ {e(v, v t ) : v ∈ T (G)} if |T (G)| > 1 If |S(G)| = 1 and |T (G)| = 1, then G st = G.
1. Any vertex in an st-multidag is reachable from the source.

2. The target of an st-multidag is reachable from any vertex in the graph.

3. For any vertex v ∈ V there exists at least one full path that contains v.

Chapter 2. Preliminaries Denition 2.1.12 [START_REF]Wikipedia : graph labeling[END_REF] Let G = (V, E). A labeling of G is a function ℓ : V ∪ E → L for some set L of labels. For every x in the domain of ℓ, the ℓ(x) ∈ L is called the label of x. Three of the most common types of labelings of a graph G are:

1. total labeling: ℓ is a total function (dened on all V ∪ E), 2. vertex labeling: the domain of ℓ is V , and 3. edge labeling: the domain of ℓ is E.

A labeled graph is a pair (G, ℓ) where G is a graph and ℓ is a labeling of G.

Example 2.1.9 Figure 2.1 (b) is a labelled graph for (a) in which

L = L V ∪ L e , with L v = {1, 2, 3, • • • , 13} and L e = {d 1 , d 2 , • • • , d 17 } and ℓ(a) = 2, ℓ(b) = 3, • • • and ℓ(e(s, a)) = d 0 , ℓ(e(s, b)) = d 1 , • • • .
We now have all the concepts needed to dene the workow model as the basis of our provenance model.

2.2. General workow model 15

General workow model

A workow model has two components [CCPP99, BBD + 09]: a specication that serves as a template for executions, and a set of runs for the given specication. Informally, a workow specication consists of a set of dierent modules and denes the order in which they can be executed. A workow run is a partial order of steps where each step is an instance of a module dened in the underlying specication, and the partial order conforms to the ordering constraints in the given specication. However, in this thesis we work on a workow structure together with its provenance information, and we consider the workow run that has the same graph structure as the workow specication based on the constraints of the Taverna system detailed in the last section.

Formally, we model a workow specication as a directed acyclic labeled multigraph whose vertices represent the workow tasks and edges represent the data ow between tasks.

As most scientic workow systems allow only stateless, functional behavior, and do not allow looping [START_REF] Davidson | Provenance and scientic workows: challenges and opportunities[END_REF], we consider st-multidags. Because scientic workows do not contain a unique source and a unique target, for each specication and its runs, we consider their generalized st-multidags, that is, we add when necessary one single source and one single target and corresponding edges to "root" the workow .

Denition 2.2.1 [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF] A workow specication is an st-multidag G spec = (V spec , E spec ) where vertices are labelled by the function L vs : V spec → L V S , with L V S a set of labels for vertices, which is related to task names.

Denition 2.2.2 [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF] A workow run is an st-multidag G run = (V run , E run )

with labeled vertices and labeled edges, using the functions L vr :

V run → L V R ,
where L V R is a set of labels of the vertices, which is related to task names and L er : E run → L ER , where L ER is a set of labels of edges, which is related to the data produced by tasks. We will note x the label of the vertex x, i.e. Another way to dene the class of SP graphs is to state that they do not contain a subgraph homeomorphic (intuitively, similar) to a "forbidden subgraph" shown in Figure 2.4. In other words, such a graph does not contain any series components or parallel components due to an "across edge" inside the subgraph. This forbidden subgraph represents the basic characteristic of non-SP graphs. More formally:

Denition 2.3.3 [Esc03] An induced subgraph G ′ = (V ′ , E ′ ) of another graph G = (V, E)
, is obtained by eliminating some vertices from V and eliminating from E the edges incident to those eliminated vertices, formally: Chapter 2. Preliminaries As said in the denition of the workow model, the labels for vertices are related to the tasks and the labels for edges are related to the data produced by the tasks. Moreover, it is important to save the label information which is related to the provenance trace during each reduction operation. Taking this into account, the reduction operators are dened as follows:

G ′ ⊆ G if f V ′ ⊆ V, E ′ = {(u, v) ∈ E : u, v ∈ V ′ } Denition 2.3.4 [Val78, Esc03] A graph G = (V, E) is homeomorphic to an- other graph G ′ i its transitive closure G tc contains G ′ as an induced subgraph: G homeomorphic to G ′ if f G tc ⊇ G ′ Theorem 2.3.1 [Duf64
Denition 2.3.5 Let G 1 = (V 1 , E 1 ) be an st-multidag whose vertices and edges are labeled by the functions

L 1vr : V 1 → L V R , and L 1er : E 1 → L ER . The elemen- tary operation op transforms G 1 into an st-multidag op(G 1 ) = G 2 = (V 2 , E 2 ),
whose vertices and edges are labeled by the functions L 2vr : V 2 → L V R , and gives the corresponding graph (nodes have been renamed for the shake of clarity).

L 2er : E 2 → (L V R ∪ L ER , +, •). 1. Series Reduction. Let u, v, w ∈ V 1 , such that e = (u, v) is
G 2 = (V 2 , E 2 ) is such that V 2 = V 1 -{v}, L 2vr is the restriction of L 1vr on V 2 , L 2er =L 1er on E 1 ∩ E 2 , and L 2er (g) = L 1er (f ) • L 1vr (v) • L 1er (e).
G 2 = (V 2 , E 2 ) is such that V 2 = V 1 , L 2vr = L 1vr , L 2er =L 1er on E 1 ∩ E 2 ,
Processors have named input and output ports, and each link connects one output port of a processor to one input port of another processor. A workow has itself a set of input and output ports, and thus it can be viewed as a processor within another workow, leading to structural recursion. Note that the input and output ports do not appear in the graph representation.

The triple ⟨ <workow name>, <workow inputs>, <workow outputs> ⟩ is called the signature of the workow.

Note that multiple outgoing links from processors or inputs are allowed, as is the case for the workow input of Figure 2.7 (a) which is used by two processors.

Also, not all output ports must be connected to downstream processors (e.g., the value on output port attachment_list in Get_Statistics is not sent anywhere), and symmetrically, not all inputs are required to receive an input data (but input ports with no incoming links should have a default value, or else the processor will not be activated).

Input ports are statically typed [START_REF] Missier | Belhajjame : Fine-grained and ecient lineage querying of collection-based workow provenance[END_REF], according to a simple type system that includes just atomic types (strings, numbers, etc.) and lists, possibly recursively nested (i.e. the type of a list element may be a list, with the constraint that all sub-lists must have the same depth). The functional aspects of Taverna come into play when one or more list-value inputs are bound to processor's ports which have an atomic type (or, more generally, whose nesting level is less than the nesting level of the input value). In order to reconcile this mismatch in list depth, Taverna automatically applies a higher-order function, the cross product, to the inputs. The workow designer may specify an alternative behavior by using a dot product operator instead. This produces a sequence of input tuples, each consisting of values that match the expected type of their input port. The processor is then activated on each tuple in the list. The resulting implicit iteration eect can be dened formally in terms of recursive application of the map operator [START_REF] Missier | Belhajjame : Fine-grained and ecient lineage querying of collection-based workow provenance[END_REF].

Summary

This chapter has introduced all the denitions which are at the basis of our work concerning graph structures and has provided a particular focus on Series-Parallel graphs (SP graphs). Such graphs have very interesting features since NP-hard graphs problems posed on general DAGs may be solved by polynomial time algorithms for SP structures. The last section of this chapter gave main terminology of concepts associated to the workows of the Taverna system, which are the workows we will mainly study in this thesis. In this thesis, we are interested in the meaning of the workow as given by the provenance of its execution outputs. Intuitively, the provenance of a data item is the ordered sequence of tasks performed to produce this data, and input data to each task. Two workows have the same meaning if, given some input data, they both produce the same intermediate and nal data i.e. they are provenance-equivalent. The aim of this chapter is to introduce a general provenance representation model which is suitable for comparing the structures of the workow executions which contain provenance information and then give the notion of provenance-equivalence between two workows.

At the beginning of this chapter, we introduce one simple provenance model

[ABML09] that we will call the "basic provenance model" in the following. We then discuss shortcomings of the basic provenance model in accurately capturing data dependencies in several computational scenarios and when complex data is used. We propose a general provenance model that naturally extends the basic provenance model by using regular expressions, to represent scientic workow Chapter 3. Provenance Model provenance. Based on this general provenance model, the denition of provenanceequivalence is described, which is the basis for evaluating correctness of the two approaches (Chapter 4 and 5) in this dissertation. Finally, a discussion on several "problematic" data dependencies cases is given and possible solutions are drawn.

Related work

This section aims to show the characteristics of existing provenance models.

These characteristics can help us to develop an underlying provenance model for identifying whether two runs are provenance-equivalent. Anand et al [START_REF] Kumar Anand | M-cPhillips et Bertram Ludäscher : Exploring scientic workow provenance using hybrid queries over nested data and lineage graphs[END_REF] have compared many workow systems (e.g., Vistrail [START_REF] Silva | Provenance for visualizations: Reproducibility and beyond[END_REF], Kepler [START_REF] Altintas | Provenance collection support in the kepler scientic workow system[END_REF],

Taverna [START_REF] Zhao | Mining taverna's semantic web of provenance[END_REF] and others [BCC + 05, ZWF06, OCE In most systems, each input and output of an execution of a processor can be organized into complex structures: lists in Taverna [HWS + 06], trees in Kepler 3.1. Related work 25 [START_REF] Bowers | McPhillips et Bertram Ludäscher : Provenance in collection-oriented scientic workows[END_REF], etc. Also, the processors may contain unobservable events, such as ltering input data as a subtask in a processor. But in the basic model described above, we should ignore all the unobservable events and consider processors as black-boxes.

As discussed in [ABML09, [START_REF] Cui | Lineage tracing for general data warehouse transformations[END_REF][START_REF] Kumar | Managing Scientic Workow Provenance[END_REF], this basic provenance model is suitable for representing data and process dependencies of scientic workows which

(1) produce new outputs from their inputs (i.e. they do not contain any function that does not change the incoming data); (2) use all inputs to derive their outputs (i.e. all outputs of a processor depend fully on all the inputs to the processor). In all of the systems that we have studied, data dependencies are explicitly declared rather than automatically generated from the module functionality specication. We aim to capture all the provenance information for a run to identify its equivalent runs, searching for a simpler structure for a scientic workow. As the in-relation corresponds to an input edge and the out-relation corresponds to an output edge, the basic model can be adopted for representing the graph structure of a run which contains provenance information. To capture the whole structure of a run, we need a new representation model to organize all the in-relations and out-relations. We thus continue investigating current approaches to nd a method that can meet this need.

As in the context of relational databases, provenance representations extend the relational data model with annotations [START_REF] Chiticariu | Dbnotes: a post-it system for relational databases based on provenance[END_REF], provenance and uncertainty [ABS + 06], and semirings of polynomials [START_REF] Green | Provenance semirings[END_REF]. In these approaches, we are mainly interested in the concept of provenance semirings proposed by Green et al.

in [START_REF] Green | Provenance semirings[END_REF], in which every tuple of the database is annotated with an element of a provenance semiring, and annotations are propagated through query evaluation.

For example, semiring addition corresponds to alternative derivation of a tuple, thus, the union of two relations corresponds to adding up the annotations of tuples appearing in both relations. Similarly, multiplication corresponds to joint derivation, thus, a tuple appearing in the result of a join will be annotated with the product of the annotations of the two joined tuples. As it is suitable for searching provenance structures and achieving the whole provenance information, which ts our aims, we thus take this concept into account and propose to represent provenance information by regular expressions.

As a result, our approach takes benets both from the basic model and the concept of using regular expressions to represent provenance. In the next section, we introduce our provenance model, which uses regular expressions to organize all the in-relations and out-relations for representing provenance trace. The resulting model will be suitable for dening the notion of provenance-equivalence.

Our Provenance Model

As discussed in the previous section, our aim is to capture the conventional view of scientic workows, which considers simple task dependency over atomic data and atomic (single invocation) processes. Our new provenance model is naturally compatible with the "basic model" and OPM, and it is based on the graph structures of the scientic workows.

In the following, we provide denitions of provenance.

Formally, let G run = (V run , E run ) be a run, with its sets of labels for vertices and edges. We consider regular expressions built on L V R ∪ L ER , using operations "+" and "•". Both operations are associative, "+" is commutative and "•" is right distributive over "+". Operation "•" allows to track the succession of the tasks, while "+" denotes the alternative data paths reaching a task. Indeed, the "+" operation is commutative because several parallel input data can be considered in any order and the "•" operation is not commutative, because the execution order must be taken into account in our context [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF].

We distinguish immediate provenance to describe the last step of production and deep provenance to describe the entire sequence of steps that produced the Denition 3.1: Provenance of a data item.

Let u ∈ V run , u ̸ = s(G run ), with L vr (u) = u; f ∈ E run one outgoing edge of u with L er (f ) = d; e i ∈ E run , 1 ≤ i ≤ p the incoming edges of u, with L er (e i ) = d i . The Immediate Provenance of f in G run is dened by imP rov : E run → (L V R ∪ L ER , +, •), with: imP rov(f ) = u • (d 1 + • • • + d p )
The Deep Provenance of f in G run is recursively dened by DP rov :

E run → (L V R ∪ L ER , +, •), with: DP rov(f ) = u • (d 1 • DP rov(e 1 ) + • • • + d p • DP rov(e p ))
The base case occurs when u = s(G run ) and f is an outgoing edge of s: We also have:

DP rov(f ) = imP rov(f ) = s Example 3.2.1 Consider the graph G r of
DP rov(e 5 ) = ṽ • (d 2 • DP rov(e 2 ) + d 3 • DP rov(e 3 )) = ṽ • (d 2 • s + d 3 • [ũ • d 1 • s])
Chapter 3. Provenance Model

This formula expresses that the data d 5 owing in edge e 5 has been obtained from task v which took d 2 and d 3 as inputs, in which d 2 is obtained directly from the source s while d 3 requires one more additional recursion step of u which took d 1 , obtained by the source s, as input.

It may be interesting to only know the data involved in the production of a given item regardless of the order in which they were consumed or which tasks were executed.

Denition 3.2.1 Given a run G run = (V run , E run ), let d be the label of an edge f in G run . Let d i be any edge label appearing in DP rov(f ), we say that d depends

on d i .
It is important to note that we cannot directly use the set of d i to evaluate the equivalence of two provenances, for it may have dierent dependencies among the set of d i , also the number of times of each data used is unknown. However, a workow run graph G run = (V run , E run ) also gives rise to a natural view, a data dependency graph

G d = (V d , E d )
, in which vertices represent data production and edges represent process dependencies, thus all the dependencies of each data are visualized. Formally, we have:

Denition 3.2.2 A data dependency graph G d = (V d , E d ) for a run G run = (V run , E run ) is a labeled multidag with V d = {L er (e)|e ∈ E run } and E d = {(u, v)|e 1 (
x, y), e 2 (y, z) ∈ E run and L er (e 1 ) = u, L er (e 2 ) = v}, with labelled edges, using the function

L ed : E d → L V R , where L V R is
Hist : V run → (L V R ∪ L ER , +, •): (i) if u = s(G run ), Hist(s) = ε (empty word) (ii) if u ̸ = s(G run ), let e i ∈ E run be the incoming edges of u (1 ≤ i ≤ p), with L er (e i ) = d i : Hist(u) = d 1 • DP rov(e 1 ) + . . . + d p • DP rov(e p ).
Example 3.2.2 Consider again the graph G r of Figure 3.2 (a):

Hist(v) = d 2 • s.
Denition 3.2.4 Output Provenance of a Run. Given a run G run , and its history function Hist, its output provenance is dened by: OutP rov(G run ) =

Hist(t(G run )).
Example 3.2.3 Continuing with Figure 3.2 (a), and using associativity of "•"

and "+" we get OutP rov

(G r ) = (d 4 • ũ • d 1 • s) + (d 5 • ṽ • (d 3 • ũ • d 1 • s + d 2 • s)).
The output provenance of (G r ) is the sum of the provenances of e 4 and e 5 .

Remarks on Provenance expressions. Several equivalent expressions for provenance are possible, due to associativity, commutativity and distributivity properties. As the deep provenance is recursively dened, the duplicated subexpressions in the provenance expression cannot be avoided, which will lead to redundancy in the expression. As in Figure 3.

2(a), OutP rov(G r ) = (d 4 • ũ • d 1 • s) + (d 5 • ṽ • (d 3 • ũ • d 1 • s + d 2 • s)).
We can nd that the name of d 1 and the name of u occur twice, like the sub-expression ũ • d 1 • s and the name of "s" occur three times.

It means that it is possible to obtain an equivalent expression by following several factoring rules to eliminate some redundancy of duplicated sub-expressions. Right distributive can be used to provide a concise representation of provenance through the following right factorization rule:

(α 1 • z • β + α 2 • z • β) → (α 1 + α 2 ) • z • β
where α 1 , α 2 and β are expressions built on vertex and edge labels using "+" and "•" and z is a vertex label. E.g., we have OutP rov

(G r ) = (d 4 • ũ • d 1 + d 5 • ṽ • (d 3 • ũ • d 1 + d 2 ))
• s, which is more concise than the one above.

Note that given a run G run and a vertex u, all the outgoing edges of u have the same provenance. I.e. all the outputs of the same task have the same provenance, as they were (recursively) obtained in the same way.

We now have all the concepts needed to dene the provenance-equivalence of two executions that is the subject of the following subsection.

Provenance-equivalence

In this research, we aim to transform a workow structure to an SP structure while ensuring that the transformed workow will work the same as the original workow. So, how to identify whether two workow executions have the same provenance structures becomes especially important. We thus introduce here the notion of provenance-equivalence of two workow executions, which is dened as follows.

Denition

3.3.1 Let G r1 , G r2 be two runs. G r1 and G r2 are provenance-equival ent, noted G r1 prov ⇐⇒ G r2 , i OutP rov(G r1 ) = OutP rov(G r2 ).
Example 3.3.1 Consider Graphs G r (a) and G ′ r (b) of Figure 3.2. G ′ r has been obtained from G r by duplicating vertex u into vertex u ′ with the same label. In the same way, edges e 1 and e ′ 1 have the same label, together with edges e 4 and e ′ 4 .

OutP rov(G

′ r ) = [L er (e ′ 4 ) • L vr (u ′ ) • L er (e ′ 1 ) • L vr (s)] + [L er (e 5 ) • L vr (v) • [L er (e 2 ) • L vr (s) + L er (e 3 ) • L vr (u) • Ler(e 1 ) • L vr (s)]]. As L vr (u ′ ) = L vr (u) = u, L er (e ′ 4 ) = L er (e 4 ) = d 4 and L er (e ′ 1 ) = L er (e 1 ) = d 1 , we have: OutP rov(G ′ r ) = [d 4 • u • d 1 • s] + [d 5 • v • (d 2 • s + d 3 • u • d 1 • s)], which is exactly OutP rov(G r ). Thus: OutP rov(G r ) = OutP rov(G r ′ ).
So, we say that G r and G ′ r in Figure 3.2 are provenance-equivalent.

Conclusion and Discussion

Conclusion

We (1) d • p we say in OPM that the artifact d wasGeneratedBy the process p.

(2) p • d we say in OPM that the process p used the artifact d.

(3) d 1 • p • d 2 we say in OPM that the artifact d 1 was derived from the artifact d 2 .

(4) p 1 • d • p 2 we say in OPM that the process p 1 was triggered by the process p 2 .

Our model is currently useful for representing data and processing dependencies of scientic workows consisting primarily of black-box transformations, which means that the output of a processor should fully depend on all the inputs. Also note that our model makes use of semirings with several constraints (e.g., "•" is not commutative) for the execution order must be taken into account in our context.

Chapter 3. Provenance Model

The regular expressions of provenance thus can well capture the whole structure of the executions, which can be used to compare whether two runs are equivalent.

However, not all the scientic workow systems follow the assumption that considers processors as black-boxes. For example, as discussed by Anand et al in [START_REF] Kumar Anand | M-cPhillips et Bertram Ludäscher : Exploring scientic workow provenance using hybrid queries over nested data and lineage graphs[END_REF], many systems (e.g., [MBZL09, MBZ + 08, QF07]) and approaches (e.g., [FCB07, KS07, MAA + 05, Wal07]) support processors that make only small changes or updates to incoming data, passing on some or all of their input to downstream processors. This means that a processor may take a collection of data values as inputs and produce a new collection as outputs, such as:

d x = [d 1 , d 2 , • • • , d x0 ], d y = [d 1 , d 2 , • • • , d y0 ]
In

d x = [d x1 , d x2 , • • • , d xp ], d y = [d y1 , d y2 , • • • , d yp ]
in which d xi is changed into d yi . Obviously, our model gives coarse-grained provenance information rather than ne-grained provenance information, which means that our model currently cannot achieve data items inside a collection when the collection is considered as a data structure in the scientic workow systems. Such coarse-grained data dependency can achieve the correct provenance structure for comparing two runs. However, when some special kinds of dependencies are combined with this kind of data dependency, it will lead to a not precise enough meaning of provenance. These special cases also have been mentioned by other works [BML + 06, Ana10], which include:

(a) processors having subtasks (such as ltering input data) prior to applying a scientic function, resulting in dependencies where each y i depends only on some of the x j ;

(b) processors that process each input data in turn (take a collection as input), resulting in dependencies where each y i depends on a single x j (j = i);

(c) processors that perform running aggregates over their input, resulting in dependencies where each y i depends on the set {x 1 , x 2 , • • • , x i }; and

(d) processors that apply functions over their input using sliding windows of a xed size w, resulting in dependencies where each y i depends on the window

{x i-w , x 2 , • • • , x i }.
Our work currently considers the Taverna system. The next subsection provides details of several special "problematic" data dependencies that may occur in Taverna. Some hints for extending the model are provided in 3.4.3.

Towards "problematic" data dependencies in Taverna

In Taverna, there exist two special processors named merge and split processors. A merge processor only merges several data items into a collection, while a split processor splits a collection of data items into single data [HWS + 06]. These kinds of processors do not perform any change on the input values and forward the input values to their destinations. We argue that there may be a misleading on the understanding of provenance information when these kinds of processors appear in a workow. in turn. Intuitively, for any processor, except the merge processor, in the two runs, the immediate data and the nal data produced are the same. And a merge processor does not do any change to any data value. As a result, without the merge processor, the two runs have the same meaning, i.e. they are provenanceequivalent. However, when querying output provenance on the two runs, we will

OutP rov(G 0 ) = (d y • v • d x • M • (d 1 + d 3 • u • d 2 ) + d 6 • u • d 2 ) • s OutP rov(G 1 ) = (d 4 • v • d 1 + (d 5 • v • d 3 + d 6 ) • u • d 2 ) • s It is obvious that OutP rov(G 1 ) ̸ = OutP rov(G 0 ).

OutP rov(G

0 ) = (d 5 • u • (d 1 + d 4 • x • d 2 • L • d x ) + d 6 • y • d 3 • L • d x
As shown in the data dependency graph Furthermore, the combination of merge processors and split processors may occur frequently in Taverna workows, as shown in gure 3.8. In (a), it is clear that the merge and split processors executed once while processor v executed twice.

The misleading meaning happens because many workow systems support processors that make small changes or no change to data values but reorganize the data structures (e.g., generate a collection or split a collection). These processors themselves (e.g., a ltering processor, a merge processor, a split processor, etc.) lead to "problematic" data dependencies for most current provenance models, and this situation cannot be avoided in most workow systems. So, how to address this problem remains an open question.

Possible solutions

Recently, Missier et al. [START_REF] Missier | Belhajjame : Fine-grained and ecient lineage querying of collection-based workow provenance[END_REF] have proposed a ne-grained provenance mod- el for Taverna system which considers all the in-relations and out-relations of each data value inside a collection of data values. The key problem of this solution is how to dene the regular expression used in our provenance model to support ne-grained provenance. Indeed, each data value in a collection is deterministic according to the processor, so that we can dene immediate provenance and deep provenance for each data value. In such a way, it will be possible for our provenance model to support all these "problematic" data dependencies in most workow systems.

As some workow systems include loop [START_REF] Bowers | McPhillips et Bertram Ludäscher : Provenance in collection-oriented scientic workows[END_REF] or fork executions, the use of the data dependency graph will also be considered as a possible direction to extend our model to deal with a restricted form of loops in the specications making runs having fork-loop structures.

Chapter 3. Provenance Model

Summary

In this chapter, we discussed the capacity of the "basic provenance model" [START_REF] Kumar Anand | M-cPhillips et Bertram Ludäscher : Exploring scientic workow provenance using hybrid queries over nested data and lineage graphs[END_REF] to accurately capture data dependencies in many computational scenarios and we introduced our provenance model which makes use of regular expressions to organize all the in-relations and out-relations to capture the provenance trace of a run. Our model is suitable for identifying the meaning of a workow and to compare the provenance structures of two workows. Based on the underlying model, we gave the notion of provenance-equivalence, which is the property used to evaluate whether two workows will always execute the same way.

In the end of this chapter, we discussed several "problematic" data dependencies which are caused by some special processors (such as a merge processor or a split processor). Finally, two research hints for extending our model are provided.

Based on the works introduced in this chapter, two main works will be introduced. Chapter 4 introduces approaches to transform a non-SP workow structure into an SP workow structure while preserving provenance. Chapter 5 discusses a new approach of rewriting scientic workows by removing some anti-patterns without alerting the semantics of the workows. Chapter 2 has introduced the main denitions related to structures of scientic workows. In particular, we have introduced the notion of SP-graphs which structure is well-known to have good properties (complex graph operations become less complex when SP-graphs are considered). Chapter 3 has introduced a provenance model for scientic workows and have proposed the denition of provenance-equivalent executions. The aim of this present chapter is to provide an approach for transforming any DAG workow to an SP-structured workow while ensuring that the transformation is provenance-equivalent.

Although strategies for rewriting non-SP graphs into SP graphs have been studied in literature, two important questions arise:

1. Do they preserve provenance?

2. Is it possible to design automatic transformation techniques to rewrite non-SP structures to SP structures while preserving provenance?

This chapter is organized as follows. We rst introduce several scenarios to give an in-depth explanation of our motivation for this work in section 4.1. After that, section 4.2 gives the concept of measuring the distance from non-SP to SP, which inspires some transformation techniques of rewriting non-SP graphs into SP graphs. Then, in section 4.3, we analyze the graph rewriting approaches of the literature by identifying whether they are provenance-preserving. In section 4.4, a detailed description of our full algorithm is carrying out, together with the discussion of complexity and soundness of the algorithm. Then we demonstrate the feasibility of our approach on real scientic workows in section 4.5. We present a tool which takes in a non-SP Taverna workow and provides an SP workow in section 4.6. Finally, we summarize our work and a discussion of ongoing work is given. As already motivated in the introduction of this manuscript, although scientic workows have been introduced to help sharing and reusing in-silico experiments, a recent study [START_REF] Starlinger | re) use in public scientic workow repositories[END_REF] showed that authors easily reuse their own workows but use more rarely workows of a third party. One explanation is that the graph structure of a scientic workow can be particularly complex, making the main steps of the analysis dicult to capture. Guiding developers to build workows that are simple to understand is fundamentally important to improve workows sharing and reuse. We believe that SP structures should be of great help in this context. Intuitively, and from a purely visual standpoint, SP structures are simple; SP graphs are layered, their edges do not intersect, making the main phases of the workow easier to distinguish. Consider the workow in Figure 4.1 (a) whose structure shown in Figure 4.1 (b) is not SP. It is relatively complex to visually distinguish the main stages of the workow and build independent subworkows. Figure 4.1 (d) shows the same workow in which task 1 has been duplicated into 1 and 1 ′ and task 4 has been duplicated into 4 and 4 ′ (the data catalogue is thus queried twice) making it being SP. First, restructured this way, the workow is easier to understand. In particular, designing sub-workows (A,B) can be performed more naturally. Second, the high level view of the workow (where subworkows are black boxes as in Figure 4.1 (e)) is simple and modular while the same type of construction on the original (non SP) workow would be more complex due to the cross edge e(4, 5) which will lead to an edge imposed between the sub-workows, making the sharing and reuse of the sub-workows less easy. Note that the original structure of the workow was not far from an SP structure. The benets of exploiting the SP structures increases with the complexity of the workow structures.

Motivating Scenarios

There are approaches dedicated to the design of sub-workows within workows. This is the case of ZOOM [START_REF] Biton | Querying and managing provenance through user views in scientic workows[END_REF] that takes in information about the tasks of interest to the user and builds automatically a user view providing a concise representation of the workow with sub-workows focused on the tasks of interest. The benet of considering SP structures has been shown in this context too: [START_REF] Biton | Optimizing user views for workows[END_REF] proved that computing the smallest user view (i.e. minimum number of composite tasks) cannot be systematically reached for arbitrary DAGs whereas it is the case when SP structures are considered. to derive algorithms that are exponential in the distance from the graph to an SP form, rather than in its size (the number of nodes) [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF]. Two complexity measure methods have already been proposed to measure the number of forbidden subgraphs in a graph, which are reductions and path expressions [START_REF] Valeska Naumann | Measuring the distance to series-parallelity by path expressions[END_REF][START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF].

Because the path expression complexity and reduction complexity are related, we introduce in this subsection the operations related to the reductions.

Vertex reduction

Any st-multidag G can be reduced to one single edge by means of three kinds of reductions, the series reduction, parallel reduction, and the vertex reduction Chapter 4. Rewriting scientic workows while preserving provenance

(1) Let v ∈ V 1 having a unique incoming edge e = (u, v) and k outgoing edges

f 1 = (v, w 1 ), • • • , f k = (v, w k ).
The operation of out-vertex reduction in v replaces v and its edges {e, f 1 , ..., f k } by k new edges {g 1 , ..., g k } where (2) The operation op of in-vertex reduction can be dened analogously, con- After applying all possible series-parallel reductions on all the vertices, any vertex can be chosen to be reduced under the vertex reduction operation except the source and the target of the graph. In the minimal forbidden subgraph, at least one child (in-degree is one) of the source can be reduced by out-vertex reduction and one child (out-degree is one) of the source can be reduced by in-vertex reduction. Thus, there are always vertices that can be reduced by vertex reduction.

g i = (u, w i ), for i ∈ [1, k]. G 2 = (V 2 , E 2 ) is such that V 2 ⊂ V 1 , L 2vr is the restriction of L 1vr on V 2 , L 2er = L 1er on E 1 ∩ E 2 , and L 2er (g i ) = L 1er (f i ) • L 1vr (v) • L 1er (e). (cf.
sidering node v with d +1 (v) = 1 and d -1 (v) > 1 (cf.
After applying a vertex reduction, it is possible again to apply new series-parallel reductions which should always be applied before any new vertex reduction.

The edges in an execution

of g 5 is d 4 • u • d 1 + d 5 • v • (d 2 + d 3 • u • d 1 )
. This label is an expression which is equal to OutP rov(G 0 )\s.

Property 4.2.1 The following reduction operations are provenance-preserving.

More precisely, considering again denition 2.21 and denition 4.1:

(1) Series reduction:

Hist(w) G 1 = Hist(w) G 2 ;
(2) Parallel reduction: Hist(w) G 1 = Hist(w) G 2 ;

(3) Out-Vertex reduction:

Hist(w i ) G 1 = Hist(w i ) G 2 for all i ∈ [1, k].
This property comes from the fact that we store in the label of the remaining edges the data ow (in reverse order) the labels of the edges and vertices that have been reduced.

Property 4.2.2 In-vertex reduction is not provenance-preserving.

A concrete counter-example will be provided in 4.3.1.

In the following, we will thus only consider out-vertex reduction.

Vertex duplication

The vertex reduction introduced above is directly related to an non-SP to SP transformation, which will be detailed discussed in next section. We propose to introduce new operations on vertices, namely vertex duplication. As shown in Figure 4.4, the vertex duplication creates multiple occurrences of the vertex.

Chapter 4. Rewriting scientic workows while preserving provenance

If series reductions are applied to the occurrences, the result is thus equal to the graph obtained by vertex reduction. As the duplication only copies the vertices and edges, no additional data dependence will be added to the graph, and once a vertex duplication operation has been applied to a reduction vertex, the "problematic" subgraph disappears.

Formally, the denition of vertex duplications are given as follow [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF]: edges

f 1 = (v, w 1 ), • • • , f k = (v, w k ).
(1) The out-vertex duplication of v transforms G 1 into G 2 = (V 2 , E 2 ), whose vertices and edges are labeled by (2) The operation of in-vertex duplication can be dened analogously, considering node v with d +1 (v) = 1 and d -1 (v) > 1. So that, V 2 is the union of V 1 and the set of new vertices v 1 , ..., v k-1 , which are copies of vertex v.

L 2vr : V 2 → L V R and L 2er : E 2 → (L V R ∪ L ER , +, •), such that V 2 is the union of V 1 and the set of new vertices v 1 , ..., v k-1 , which are copies of vertex v. L 2vr is an extension of L 1vr on V 2 , which matches with L 1vr on V 1 ∩ V 2 , L 2vr (v i ) = L 1vr (v) for all i ∈ [1, k -1]. E 2 = E 1 ∪ {e 1 , ..., e k-1 }, with e i = (u, v i ) for all i ∈ [1, k -1],
i = (v i-1 , w i ) for i ∈ [2, k]. L 2er = L 1er on E 1 ∩ E 2 , L 2er (e i-1 ) = L 1er (e), and
L 2er (g i ) = L 1er (f i ) for i ∈ [2, k]. (cf.
L 2vr is an extension of L 1vr on V 2 , which matches with

L 1vr on V 1 ∩ V 2 ,
4.2. Distance from non-SP to SP graphs 49 More precisely, with the notations above, we have: A concrete counter-example will be provided in 4.3.1.

L 2vr (v i ) = L 1vr (v) for all i ∈ [1, k -1]. E 2 = E 1 ∪ {f 1 , ..., f k-1 }, with f i = (v i , w) for all i ∈ [1, k -1],
i = (u i-1 , v i ) for i ∈ [2, k]. L 2er = L 1er on E 1 ∩ E 2 , L 2er (f i-1 ) = L 1er (f ), and L 2er (g i ) = L 1er (e i-1 ) for i ∈ [2, k].(cf.
Hist G 1 (w i ) = Hist G 2 (w i ) for all i ∈ [1, k] (cf.

Complexity measures

As said in section 4.2.1, the number of times the vertex reduction operations are used can give an idea of the distance from a non-SP to an SP structure.

Intuitively, the highest number of times vertex reductions are used the farthest from an SP structure it is.

Graph rewriting problems (non-SP to SP)

In this section, we investigate the basis of full transformation methods to rewrite an non-SP graph into an SP graph.

Review of existing approaches

We are interested in methods of transforming non-SP graphs to SP forms that keep the provenance information of the original graph. Additionally, we will have a special interest in reducing the number of duplicated vertices. Several transformation techniques have been found in literature, which are all based on adding dependencies, while another strategy based on vertex duplication is possible too. These two dierent approaches are detailed as follow.

Adding dependencies

The rst set of strategies found in the literature to rewrite non-SP graphs into SP graphs are based on the concept of adding dependencies. The approach of Escribano [START_REF] González | Synchronization Architecture in Parallel Programming Models[END_REF] is part of such approaches and based on the notion of (re)synchronization. Informally, the idea is "to layer" the graph by adding articial vertices (and edges), which act as synchronization tasks. Three main synchronization strategies (see the incoming data of w, which is not the case in (a).

Note that in the strategy of across-synchronization, we can add a new data forward vertex which only forward data values to the right processors. As discussed in chapter 3, this kind of processor will lead to an unclear data dependency, which will lead to a dierent provenance meaning. And this pattern is currently unsupported by our provenance model. So we don't take this approach into account.

Duplication of vertex

Another family of approaches to transform non-SP to SP graphs is based on vertex duplication. The main interest of this kind of transformation is that it does not add any additional dependency to any task of the original graph, because it only copies the task and its original dependency. However, our aim of preserving provenance raises the following questions which is related to transforming an non-SP graph into an SP graph.

1) Do duplication operations provide an SP graph?

Yes. In Figure 4.6 (b), two series reductions remove the vertices v and v ′ , then one parallel removes the double edges between u and t. Thus, one parallel can 52 Chapter 4. Rewriting scientic workows while preserving provenance be applied to the edges between s and t, followed by two series reductions on u and v. Finally, it is a BSP. The same for (c), when applying series and parallel on the graph, nally we obtain a BSP. As a result, we obtain two BSP. So, the two rewritten subgraphs are SP.

2) Does in-vertex duplication preserve provenance?

No (c.f. property 4.4). Consider 3) Does out-vertex duplication preserve provenance? 4.3. Graph rewriting problems (non-SP to SP) 53 Yes (c.f. property 4.3). As shown in Figure 4.6 (c), the task u is duplicated into u ′ and each copy receives the same input (u is not modied). As the tasks are deterministic, they thus provide the same output. Also, it is clear in Figure 4.7 (a) and (c) have the same structure (same vertices and same edges). So, they are provenance-equivalent.

We have now provenance-preserving operations of reductions able to locally provide SP structures. The rest of this subsection aims at providing a general provenance-preserving approach to transform a non-SP to SP structure while minimizing the number of duplicated vertices. The next subsection will thus introduce notions useful to choose the order of reduction operations to perform.

Compositions of forbidden graphs

Transforming a non-SP graph G to an SP graph requires eliminating all the forbidden subgraphs in graph G. When a graph contains several forbidden subgraphs, these subgraphs may be composed. In [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF] and [START_REF] González | Synchronization Architecture in Parallel Programming Models[END_REF], three composed forbidden subgraphs are studied to decide which reduction vertices must be chosen to get a shorter reduction sequence. The reduction sequences of these compositions are based on both in-vertex and out-vertex reductions.

However, in the present work, we only consider out-vertex duplication which is provenance-preserving (contrary to in-vertex duplication which is not). We thus summarized three compositions of forbidden subgraphs, which are dierent from the compositions introduced in [BKS92] and [START_REF] González | Synchronization Architecture in Parallel Programming Models[END_REF], according to the reduction vertices to which we can apply out-vertex reductions. The impact of the order of reduction operations chosen to perform for each composition is then discussed.

2 : (1) G 1 ∩G 2 = ∅; (2) G 1 ∩G 2 ̸ = ∅. It is obvious that if G 1 ∩G 2 = ∅, G 1 will never aect G 2 ,
and any order of reduction operations will give the same result. So, we introduce here the second situation by identifying three compositions. Single non-SP composition: There exist several similar forbidden subgraphs, which are induced by one single reduction vertex.

In the single composition (cf. Figure 4.8), there is only one reduction vertex which is related to several forbidden subgraphs. The solution for eliminating these kinds of compositions is to duplicate the reduction vertex following one reduction operation. So, the forbidden subgraphs will never aect each other.

Series non-SP composition:

There exist several similar forbidden subgraphs, in which the reduction vertices (Out-vertex reduction) form a series composition.

Three kinds of series non-SP compositions are possible.

Let v 1 , v 2 be two reduction vertices of graph G, G 1 be a forbidden subgraph induced by v 1 and G 2 be a subgraph induced by v 2 . For the sake of readability, labels are omitted.

(1)path p(v 1 , v 2 ) ⊂ (G 1 ∩ G 2 ) (c.f. Figure 4.9 (a)).

Example of series non-SP composition (1) is shown in Figure 4.9 (a). In this composition, G 1 and G 2 are induced by v 1 and v 2 . Although v 1 appears in the path p(s, v 2 ), the elimination of the two forbidden subgraphs do not aect each other. It means that the duplication operations following any reduction sequence will give the same result. (2)G 1 ⊂ G 2 (c.f. Figure 4.10 (a)).

In series composition (2), as shown in Figure 4.10 (a), G 1 appears in the subgraph which forms all the paths from s to v 2 . In such a case, if we duplicate v 2 rst as in Figure 4.10 (c), and then duplicate v 1 , following the reduction sequence v 2 , v 1 , the whole forbidden subgraph G 1 may be duplicated, which will make the result unreliable, because it copied a non-SP problem. As a result, in this kind of compositions, the reduction sequence may aect the result, which should be carefully considered.

( As shown in Figure 4.12 (a), u 1 and u 2 form a parallel composition and the forbidden subgraphs induced by them will never aect each other. induced by u 2 . The forbidden subgraphs can be eliminated by duplicating path p(s, u 1 ) and p(s, u 2 ). As p(s, u 1 ) ∩ p(s, u 2 ) = ∅, so which vertices are duplicated rst is not important.

)v 1 = s(G 2 ) (c.f. 3
For simple combinations of forbidden subgraphs (single composition or parallel composition), any reduction sequence may be appropriate. But for some series compositions, the reduction sequence may aect the number of duplicated vertices and even create new reduction vertices. Next section will give an in-depth description of our full algorithm, together with the discussion of choosing a shorter reduction sequence, according to which the transformation will duplicate less vertices.

SPFlow: a new provenance-equivalent rewriting algorithm for workows

This section gives the description of the SPFlow algorithm, a full algorithm based on out-vertex duplication discussed in section 4.3.1, which can be used to rewrite any non-SP workow to an SP structure while preserving provenance.

First, we introduce SPFlow. Then, we illustrate the way SPFlow works with an example. Finally, the complexity and the soundness of SPFlow are discussed.

Principle of SPFlow

We present here our full "SP-ization" algorithm based on vertex duplication, which rewrites a non-SP graph G into a new SP graph, called SP G obtained from G by duplicating vertices of G, while ensuring that G and SPG are provenanceequivalent. As discussed in section 4.2, vertex duplication depends on vertex reduction. Two graphs will be used, one is for vertex reduction which is called G red and the other (SPG) is for vertex duplication, to eliminate the forbidden subgraphs. In our approach, we are interesting in getting a reduction sequence, so that each reduction operation never creates new forbidden subgraphs. For this 58 Chapter 4. Rewriting scientic workows while preserving provenance

Reduction sequence

As discussed in section 4.3.2, the reduction sequence will aect the result of the non-SP to SP transformation. This subsection gives a discussion on how to choose a reduction sequence that will lead to a duplicated graph with less redundancy of duplicated vertices.

In is an SP graph(property 4.2), we can ensure that no reduction vertex remains in the duplicated subgraph and no non-SP subgraph will be copied.

Property 4.4.2 Let G be an non-SP graph, and let us apply maximal seriesparallel reductions on G until no series and parallel reduction can be applied.

There exists at least one successor v of s(G) which is a reduction vertex

with d -(v) = 1 and d + (v) > 1. Proof: Let s = s(G), Succ(s) = {v 1 , v 2 , • • • , v k } be the set of successors of s, v i ̸ = t(G).
Assume that all the successors of s have an in-degree greater than one, with

d -(v i ) = n > 1, v i ∈ Succ(s).
If s and its out going edges are removed, new in-degree of v i is d -(v i ) = n -1 ≥ 1, which means that there does not exist any vertex with in-degree equals to zero. There does not exist any topological order provenance for graph G, which means there exist circles in G. However, G is an st-multidag.

This contradiction shows that there must exist at least one successor v of s with

d -(v) = 1.
For v, we have d + (v) > 1, or it should be reduced by series reduction.

So, we can conclude that there exists at least one successor of s with in-degree one and out-degree greater than one.

Any autonomous subgraph should be considered as a new st-multidag and should be reduced rst by reduction operations, and then go back to G red to nd another reduction vertex.

Reducing redundancy of duplicated vertices

Although we can achieve a reduction sequence which can lead to a transformation with less duplicated vertices by introducing the notion of autonomous subgraph, the risk of redundancy still exists. As shown in Figure 4.15, G 0 is a graph without any autonomous subgraph, but can be transformed into two dierent graphs by vertex duplication following dierent reduction sequences. As discussed in section 4.3, vertex duplication approach is provenance-preserving. So two runs which have the same graph structure as G 1 and G 2 are provenance-equivalent. But G 2 obviously has less vertices than G 1 , because G 2 follows a minimal reduction sequence and nally vertex a no longer be a reduction vertex. As well-studied, no technique for providing such a minimal reduction sequence has been proposed, and it is dicult to automatically obtain such a sequence. To solve this problem, we remind here the factorization rule which we have proposed in chapter 2. The idea is to eliminate the unnecessary vertices following the factorization rule. For example, in G 1 , the copies of vertex a highlighted in yellow can be merged and nally we can obtain another graph G ′ 1 equal to G 2 . As discussed in 3.2, only right distributivity can be used to provide a concise representation of provenance for the execution order is important in the workow. Corresponding to the factorization rule for the provenance expression, the factorization rule for graphs is shown in Figure 4.16.

To ensure that the factorization never creates new non-SP subgraphs, our algorithm only performs the factorization operation during each parallel reduction.

Once a parallel reduction is applied to G red , the algorithm will check redundancy of vertices in the duplicated subgraphs induced by the edges which are reduced so that the edge outgoing from s(IFG) with in-degree of 1 (edge from s to y 1 will be duplicated an exponential number of times).

Proof:

G is irreducible. There is a single reduction vertex, that is y 1 . We perform outvertex reduction on y 1 . Then we can perform out-vertex reduction on the single possible reduction vertex x 1 . We iterate the process. Assume that we have reduced

y 1 , x 1 , y 2 , x 2 , ..., y i-1 , x i-1 .
Let us call α i the new label of the edge from s to x i and β i the label of the new edge from s to y i (cf. Figure 4.19 (b)).

Base case:

α 1 = a 1 and β 1 = b 1 Induction case: for 0 < i < n -1, after reduction of vertices y 1 , x 1 , • • • , y i (cf.
α i+1 = (α i + β i • c i ) • a i+1
(label of the new edge from s to x i+1 )

β i+1 = ((α i + β i • c i ) • d i+1 ) + β i • b i+1
(label of the new edge from s to y i+1 .)

In the following, we focus on the duplication of the edge from s to y 1 in the 4.4. SPFlow: a new provenance-equivalent rewriting algorithm for workows 67 (1)

u i+1 = u i + v i , for 2 ≤ i ≤ n -1 (2) v i+1 = u i + 2v i , for 1 ≤ i ≤ n -1,
with v 1 = 1 and u 1 = 0, u 2 = 1. Solving these equations, we get:

v n = (γ 1 * ( (3+ √ 5) 2 ) n + γ 2 * ( (3- √ 5) 2
) n ) with γ 1 = 0.28 and γ 2 = 0.72.

For example, if n = 20 (resp. n = 50), this edge will be duplicated more than 107 (resp. 1,020) times. The next section of experimental study will show that on real workows, the complexity is reasonable.

Chapter 4. Rewriting scientic workows while preserving provenance

Soundness of vertex duplication algorithm

As a central result we get that the main output of SPFlow is SP and is provenance-equivalent to the non-SP graph taken as input. Additionally, the output provenance of the initial graph is directly obtained from the nal label of the unique edge of G red .

More precisely, we establish the following properties by induction on the number of reduction steps of G red in the algorithm. (1) SP G is an SP graph ;

(2) OutP rov(G) = OutP rov(SP G) ;

(3) let f be the unique edge from s to t in G red , then OutP rov(G)= L 2er (f ) • s. and considering only well-formed workows). In this section, we study their structures and evaluate SPFlow.

Sketch of proof:

Workow Structures

We have represented workows by st-multidags (adding a source and a sink)

and have implemented a basic SP structure detection algorithm.

Proportion of SP and non-SP workows

Our rst result (Table 4.1) shows that there is a majority of SP structures and the proportion of SP-graphs is stable over time. Table 4.2 provides the distribution of SP vs non-SP workows, considering three families of workows. The gures obtained are particularly clear: while intermediate workows are almost all SP, the proportion of SP structures in workows falls over 10 vertices with only 6.2% of SP workows in very complex workows.

Chapter 4. Rewriting scientic workows while preserving provenance

Features of non-SP workows

In this second experiment, we evaluate the distance between non-SP and SP structures, given by the number of vertex reductions to be applied to get the basic graph BSP [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF].

Evaluating SPFlow

We now evaluate the behavior of SPFlow on real data, considering the set of 621 non-SP Taverna workows available in myExperiment (whose size ranges from 4 to 333 vertices). Figure 4.21 gives the relationship between the size (number of vertices) of the initial graph and the rewritten graph. Although 10 graphs have an important number of duplicated vertices, half of the very large majority of graphs, including huge workows (having more than 100 vertices), have a small ratio, lower than 5. Additionally, the time to rewrite each workow is negligible for the current structures of workows: on a dual core@2.2GHz and 2GB of RAM desktop, the maximum time is 434 ms.

Implementation of the algorithm

In this section, we introduce a java application tool based on the algorithm described in section 4. Finally, the TavernaLoader module produces the rewritten workow into the Taverna XML format and makes it available to the user.

Users communicate with the system by loading and interacting with original and rewritten workows.

Functionalities of SPFlow

Our implementation of SPFlow is able to provide the following features.

Loading Data: Users may load a workow specication into the system (see Rewriting of the workow: SPFlow (using SPBuilder) transforms any non-SP workow into an SP workow (see Figure 4.24). Both workows will be displayed and duplicated vertices highlighted.

Provenance information: By clicking on an edge between two tasks, the user 4.6. Implementation of the algorithm 73 Figure 4.24: Provenance information in SPFlow can visualize the provenance information (see Figure 4.24) of the data owing on that edge not only on the initial workow but also on the rewritten workow (showing that both workows are provenance-equivalent). The formal expression associated to provenance information is also displayed (bottom panel).

Running rewritten workows: Any workow rewritten by SPFlow can be opened in Taverna. We will show how it can be run and we will demonstrate that both workow versions (non-SP and SP) provide the same results for the same input (equivalence property).

On the benet of using SP-workows: We will take the example of the Zoom*userview system (ZOOM for short) [START_REF] Biton | Querying and managing provenance through user views in scientic workows[END_REF] that takes in a workow and a set of tasks of interest for the user (other tasks are usually formatting tasks) and provides a user view, that is, a view of the workow composed of a set of composite tasks. Each composite task contains at most one signicant task and takes its meaning. The diculty for ZOOM lies in ensuring that no data dependencies between signicant composite tasks is introduced or lost by the grouping process (i.e. consider two relevant tasks t 1 and t 2 : t 1 consumes the data produced by t 2 if and only if the composite task containing t 1 consumes the data produced by the composite task containing t 2 ).

In Figure 4.25, the user has specied two tasks of interest to him (namely, blast-report and Fasta-sequence). Based on the original workow (gure 4.25 (A)), 74 Chapter 4. Rewriting scientic workows while preserving provenance and M 3 ). Note that introducing the tasks of NR-1 into one of the two signicant composite tasks would have introduced misleading data dependencies: e.g., if M 3 and M 6 were put into R-fastaSequence then from the user view perspective the edge e 3 would have been displayed from R-fastaSequence to R-blast report, giving the feeling to the user that data provided by R-fastaSequence is used by R-blast report while it was not the case in the original workow. It has been proved

in [START_REF] Biton | Optimizing user views for workows[END_REF] that such a situation (having to introduce a composite task without any signicance for the user to preserve provenance) can be avoided when SP structures are used while it is not possible for general DAGs.

In

Discussion

Scientic workows are complex graphs that need to be designed, visualized, queried, run, or scheduled. These actions are inherently complex and lead to NP-hard problems when conducted on DAGs like are usual scientic workows.

Instead, these problems can be solved in polynomial time when the structure is series-parallel (SP). Rewriting a non-SP to SP workow is particularly useful especially if the provenance is preserved. The major contribution of this work is the introduction of an original algorithm for rewriting workows preserving provenance. More particularly, we: (1) reviewed existing approaches and discussed whether they are provenance-preserving, (2) designed the provenance-equivalent SPFlow algorithm, (3) demonstrated the feasibility of our approach on real sci-76 Chapter 4. Rewriting scientic workows while preserving provenance We now provide one direction of extension for our work.

Extending SPFlow to deal with split and merge processors. As discussed in Chapter 3, there are some special cases which are currently not supported by SPFlow, such as when a merge processor or a split processor appears in a workow (they are currently considered as any other processor). As the two processors are closely related, we only discuss the case concerning the merge processor.

Let us consider Figure 4.26, G 0 is a non-SP graph with parallel composition and let us consider that v is a merge processor and

d 6 = [d ′ 6 , d ′′ 6 ]. G 1 , G 2 , G 3 are dierent SP solutions for G 0 . G 1 is obtained from G 0 based on out-vertex reduction. G 2 is
obtained from G 0 based on in-vertex reduction and G 3 is based on the strategy of adding dependencies. Let us observe these SP graphs and the original graph, we could nd that they all produce the same intermediate and nal data. So, they should be provenance-equivalent. It is obvious that G 2 and G 3 have less vertices duplicated than G 1 . This implies that it is possible to reduce the number of duplicated vertices when considering some special processors such as a merge processor.

More importantly, the merge processor, contrary to any other processor does not need to get all its inputs to provide one output. As a consequence, solutions based on in-vertex duplications (as in G 2 ) may be more appropriate than solutions based 4.8. Summary 77 on out-vertex duplications (as in G 1 ) when lists of data are considered. So, nding a strategy to deal with these specic processors can help us to obtain new SP workows with less duplicated vertices and unambiguous provenance meaning (cf. G 0 ). How to extend our provenance model and SPFlow to support lists of data and consider these special processors is one direction of our ongoing work.

Summary

In this chapter, we have presented SPFlow a provenance-based strategy for rewriting any non-SP graph into SP graph. After having studied several current approaches, we have identied that all of them are not provenance-preserving. So that they cannot be directly used to rewrite workows into equivalent ones. Our approach based on out-vertex duplication which is provenance-preserving was then proposed. We also demonstrated the feasibility of our approach on real scientic workows. Finally, we gave an introduction of the tool we developed, which takes in a non-SP Taverna workow and provides an SP version of the workow useable in Taverna.

As studied in this chapter, we are able to rewrite any scientic workow into SP structure. A new question is whether it is possible to rewrite a scientic workow into a new one which is free or partly free of vertices redundancy and without alerting its meaning. In the next chapter, we will inspect the features of Taverna workows themselves and then provide a refactoring approach to relax redundancy of vertices and make workows close to SP structures.

Chapter 4 has introduced a provenance-based technique for rewriting any non-SP workow into an SP workow. Still in the aim of transforming workow structures to make them easier to reuse, the present chapter introduces techniques for reducing redundancies in the structure of scientic workows. Our approach provides workows which are free or partly free of redundant vertices without alerting their original meaning. Interestingly, we will see that our approach tends to make non-SP workfows closer to SP structures.

More precisely, our approach aims at automatically detecting parts of the workow structure which can be simplied by removing explicit redundancy and proposing a possible workow rewriting. As mentioned earlier, our preliminary analysis of the structure of 1,400 scientic workows of Taverna collected from myExperiments reveals that, in numerous cases, such a complexity is due mainly to redundancy, which is in turn an indication of over-complicated design, and thus there is a chance for a reduction in complexity which does not alter the workow semantics. Our main contention in this work is that such a reduction in complexity can be performed automatically, and that it will be benecial both in terms of user experience (easier design and maintenance), and in terms of operational eciency (easier to manage, and sometimes to exploit the latent parallelism amongst the tasks).

The specic contribution of this chapter is a method for the automated detection and correction of certain Taverna workow structures which can benet from refactoring. We call these idiomatic structures "anti-patterns", that is, patterns that should be avoided. Our approach involves the detection of several antipatterns and the rewriting of the oending graph fragment using a new pattern that exhibits less redundancy and simpler structure while preserving the semantics of the original workow. We have then designed the DistillFlow algorithm and evaluated its eectiveness both on a public collection of Taverna workows and on a private collection of workows from the BioVel project.

As the Taverna workow system features have already summarized in chapter 2, the present chapter begins by illustrating the two main types of anti-patterns found by our workow study, by means of two use cases (5.1). The formalization 5.1. Use cases 81 of the anti-patterns and the transformations we propose to do while ensuring that the semantics of the workow remains unchanged will be then introduced (5.2).

After giving a presentation to the anti-patterns, we will introduce the DistillFlow refactoring algorithm (5.3). In the experimental study Section (5.4), we provide the results obtained by our approach on a large set of real workows. Finally a discussion of this work will be carried out, together with the conclusion.

Use cases

The rst use case (Figure 5.1 (i)) involves the duplication of a linear chain of connected processors GetStatistics_input, GetStatistics and GetStatistics_output.

The last processor in the chain reveals the rationale for this design, namely to use one output port from each copy of the processor. Clearly, this is unnecessary, and the version in Figure 1 (ii) achieves the same eect much more economically, by drawing both output values from the same copy of the processor. In the second use case (Figure 5.2(i)), the workow begins with three distinct processing steps on the same input sequence. We observe that the three steps that follow those are really all copies of a master Get_image_F rom_U RL task. This suggests that their three inputs can be collected into a list, and the three occurrences can be factored into a single occurrence which consumes the list. By virtue of the Taverna list processing feature described earlier, the single occurrence Chapter 5. Distilling Structure in Taverna Scientic Workows: A refactoring approach will be activated three times, one for each element in the input list. Also, the outputs of the repeated calls of Get_image_F rom_U RL will be in the same order as items in the list. Therefore this new pattern achieves the same result as the original workow. Note that collecting the three outputs into a list requires a new built-in merge node (the circle icon in Figure 5.2(ii)). Similarly, a Split processor has been introduced to decompose the outputs (list of values) into three single outputs.

Anti-patterns and Transformations

The transformations aim at reducing the complexity of the workow by replacing several occurrences of the same processor with one single occurrence whenever possible. Although new processors are sometimes introduced in the process (i.e.

merge and split operators), on balance we expect a cleaner design, better use of the functional features of Taverna (automated list processing) and lower redundancy, and thus fewer maintenance problems.

5.2. Anti-patterns and Transformations 83

Assumptions

The following four assumptions must hold for processor instances to be candidates for the transformations described below.

1. A processor must be deterministic: it should always produce the same output given the same input.

2. Only processors implemented using the exact same code can be merged.

Determining that two processors are equivalent is an open problem (see e.g. [START_REF] Starlinger | re) use in public scientic workow repositories[END_REF] for a discussion on that point) since it is directly associated to determining the equivalence of programs. In our setting, two processors are equivalent if they represent identical web service calls, or they contain the same script, or they are bound to the same executable Java program. In practice, this condition is often realized, because processors are duplicated during workow design by means of a graphical copy and paste operation.

3. Only copies of processors that do not depend on each other can be merged, that is, if P (1) and P (2) are two occurrences of the same processor P , then there should not be any directed path between P (1) and P (2) , for P (1) and P (2) to be merged.

4. We will consider only two cases where we can be sure that the same input value L i can be bound to the input port a i of r copies of P : (a) the input port a i is bound to a constant value which is identical across executions (that is, among dierent copies) of P , or (b) L i has been produced by the output port of some processor Q i and has been distributed to the r copies of P .

Transformations

The two proposed transformations are shown in Figures 5.3 Anti-pattern A: In the rst anti-pattern (Figure 5.3), the input ports a i of each processor occurrence P (l) are all bound to the same value L i , for 1 ≤ i ≤ k, 1 ≤ l ≤ r. It follows from our assumption of determinism that the output ports b j all present the same output value O j across all P (l) , for 1 ≤ j ≤ q.

The rewriting replaces all P (l) with a single occurrence, P .

Treatment of the outputs: Outgoing links are then added to ports b j as needed.

Treatment of the inputs: For each input port a i of P , the unique input value L i bound to a i is now either the constant value as previously in the (original)

anti-pattern (cf. assumption 4.(a)), or it is one of the distributed values bound to some output port of some processor Q i (assumption 4.(b)) and in this last case processor Q i does not need to distribute this output value more than once anymore.

Illustration: One example of anti-pattern A is depicted on Figure 5.1(i) where the same workow input is sent to two exact copies of the processor GetStatistics_input.

The workow input plays the role of processor Q. GetStatistics_input and GetStatistics_2_input are thus merged and the workow input (Name) is sent only once to the downstream of the workow, that is, to the (now) single GetStat istics_input processor. Outputs are linked to the rest of the workow and transformations must be applied as many times as necessary. In this example, three successive transformations are applied thus giving the workow of Figure 5.1(ii).

Anti-pattern B: In the second pattern (Figure 5.4), the input ports a i of each processor occurrence P (l) are bound to the same value L i , for 1 ≤ i ≤ t while the input ports a t+1 to a k of each processor occurrence P (l) are bound to dierent inputs L l t+1 to L l k among occurrences, 1 ≤ l ≤ r. As for output values, let O l i = P (l) | bi (L 1 , ..., L t , L l t+1 , ..., L l k ) denotes the output value produced by output port b i of the l-th occurrence of P . For the sake of generality, we consider here that processor P applies cross product to values on ports a 1 to a t and dot product to values on ports a t+1 through a k .

The rewriting replaces all P (l) with a single occurrence, P .

Input data that dier from one occurrence to another (L l t+1 to L l k ) have been merged using the merge processors provided by Taverna (the circle icon in Figure 5.4) to construct lists of data from the original data items to exploit the implicit iterative process of Taverna. As a consequence, the outputs of P are lists of data instead of single values in the original pattern. Since P follows a dot strategy on ports a t+1 ...

a k , O ′ i is the list O ′ i = [P | bi (L 1 , ..., L t , L 1 t+1 , ..., L 1 k ), ..., P | bi (L 1 , ..., L t , L l t+1 , ..., L l k ),...,P | bi (L 1 , ..., L t , L r t+1 , ..., L r k )], for output port b i , 1 ≤ i ≤ q.
Treatment of the outputs: For each output port b i of P , the rewritten pattern contains a list split processor called SP LIT r to decompose the list obtained into r pieces so that the downstream fragment of the workow remains unchanged. We get:

O ′ l i = P | bi (L 1 , ..., L t , L l t+1 , ..., L l k ) (1 ≤ l ≤ r).
Treatment of the inputs: Note that for each input port a t+1 ,...,a k , input values L l i are used in the same way both before and after the transformation (1 ≤ l ≤ r, t + 1 ≤ i ≤ k). As for input ports a 1 to a t , instead of having r occurrences, each L i has now one single occurrence, 1 ≤ i ≤ t (similarly to anti-pattern A).

Illustration: One example of anti-pattern B is depicted on Figure 5.2(i) where there are three copies of processor Get_image_F rom_U RL, each copy receiving input data from distinct processors. The three copies are then merged into one single copy.

The next section will provide more details on how the transformations are extended to the entire workow.

Safe Transformations

In this subsection, we introduce the notion of safe transformation. Intuitively, a transformation is safe if the semantics of the workow is preserved (the outputs produced remain the same).

More formally, let W 1 be a fragment of a workow W consisting of r occurrences P (1) ...P (r) of a processor P such that there is no directed path between P (i) and P (j) (1 ≤ i ̸ = j ≤ r). Let W 2 be a fragment of the workow W consisting in one It is straightforward to prove that the two transformations we propose to perform are safe.

Refactoring approach

The previous section has introduced transformations able to locally remove anti-patterns. In this section, we will present the complete refactoring procedure we propose to follow. In particular, we have chosen not to remove all possible anti-patterns when such rewriting operations can make the transformed structures becoming more intricate than the original structures. Example of "simple" structures are series-parallel (SP) graphs as introduced in the previous chapters.

The challenge of our refactoring approach then lies in minimizing the presence of anti-patterns while ensuring that the number of structures which are not SP will not increase. Note that it may be the case that our procedure transforms some non-SP structures into SP structures.

As said in the previous chapter, non-SP structures have some specic nodes called reduction nodes which cause the structure to be non-SP. Reduction nodes are typically involved in structures illustrated in the subgraph of Figure 5.15 (iii) where u is one reduction node. We will see how we apply our transformations to such nodes and we go back to this point in the Discussion section.

Additionally, in the following, we will also make use of the notion of autonomous subgraph introduced in the context of SP structures in Chapter 2.

In the same spirit as in the SPFlow approach, the autonomous subgraphs allow to restrict the initial graph to smaller components such that no edge comes in or goes out of the autonomous subgraph (except edges coming in the source of the autonomous subgraph or going out of its target). Recall that several autonomous subgraphs can be nested. Consider the graph G in G[3, 24]. We will use this notion in order to apply transformations locally, without interaction with the rest of the graph.

Principle of the algorithm

The Refactoring algorithm takes in an st-DAG G and produces an st-DAG DSG from G by transforming the anti-patterns that can be removed from G while preserving its SP property. For it, the algorithm starts by identifying the set SetAU of autonomous subgraphs, and distills each of them, starting with the minimal ones, in a recursive way. Once each autonomous subgraph has been distilled, the whole graph G must be distilled in turn. Calls of the procedure Distill are done from a starting node x that can be either the source of an autonomous subgraph or a reduction node, or the source of G. We consider all the successors p of x, and search among all the other successors (and then descendants of x) whether there is a processor q that would be a copy of p. If it the case, we merge p and q according to the transformation for anti-patterns (A) and (B). Every time a transformation is performed, merging copies of a processor may give rise to new autonomous subgraphs, that lead to new distillations in turn. This last job is done by the procedure Down-Distillation. is introduced here after: OKT ransf ormation(p, q, GG) which species the conditions for nodes p and q to be merged. It is true i the following conditions are satised: (i) p and q are copies of each other; (ii) p and q are involved in some anti-pattern (A) or (B) in GG; (iii) for any autonomous subgraph G ′ of GG, every time p appears in G ′ , q appears in G ′ too. This last condition ensures that we do not remove an anti-pattern by a transformation that would make an SP-graph becoming non-SP. The function SameOrientedP ath(p, q, GG) is true i there is at least a directed path dp in GG such that p and q belong to dp.

V isited is a function allowing to mark nodes as visited or unvisited.

Illustration of the algorithm

We propose to illustrate the execution of the DistillFlow algorithm on the workow depicted in Figure 5.8(a). We can see that it potentially contains several anti-patterns. Indeed, it duplicates processors many times: #3, #4, #9, #10, /* f lagp allows to consider all the unvisited descendant of p 1 if necessary */ Distilled ← false /* Distilled says if some transformation on p 1 has been done */ foreach successor q of x in GG, such that q ̸ = p 1 do /* successors of x different from p 1 are potentially copies of p 1 */ q 1 ← q; f lagq ← true; ! while f lagq do /* f lagq allows to consider all the unvisited descendant of q 1 if necessary */ " if Visited(q 1 )=false and SameOrientedPath(p 1 ,q 1 , GG)=false then # if OKTransformation(p 1 ,q 1 ,GG)=true then /* q 1 is a copy of p 1 in some anti-pattern and transformation can be performed */ $ transformation on DSGG, replacing q 1 by mergeq; % f lagq ← false; distilled ← true; /* loop on q is stopped */ & else /* no transformation has been done on p 1 and q 1 */ ' if outDegree(q 1 ) ̸ = 1 then if there exists a single autonomous subgraph GG[q 1 , y] in SetAU then q 1 ← y; /* the loop on q 1 is continued with the sink of the unique autonomous subgraph */ else /* there is no autonomous subgraph GG[q 1 , y] in SetAU or more than one */ ! if q 1 is a reduction node in Listred then /* search for anti-patterns from reduction node

q 1 */ " DownDistillation(GG[q 1 , v], DSGG, q 1 , SetAU , ListRed); # Visited(GG[q 1 , v]) ← false; $ if outdegree(q 1 ) > 1 then f lagq ← false;; % else & f lagq ← false;
/* q 1 is not a reduction node or there is no autonomous subgraph GG[q 1 , y] in SetAU the loop on q is stopped */ ' end ! end ! q 1 ← the successor of q 1 /* outDegree(q

1 ) = 1 */ ! end !! end !" f lagq ← f alse; !# end !$ end !% end !& /*

Experimental Study

We have implemented DistillFlow into a tool that is presented in more detail in Appendix A.

Anti-patterns in workow sets

In our study, we have applied the refactoring approach on two workow sets:

the public workows from myExperiments and the private workows of the BioVel project (www.biovel.eu). BioVel is a consortium of fteen partners from nine countries which aims at developing a virtual e-laboratory to facilitate research on biodiversity. BioVel promotes workow sharing and aims at providing a library of workows in the domain of biodiversity data analysis. Access to the repository to contributors, however, is restricted and controlled. Because of the restricted access and the focus on a specic domain of these workows, they are broadly expected to be curated and thus of higher quality than the general myExperiment population.

For each workow set, the total number of workows, the number of workows having at least one anti-pattern (of kind (A) or (B)) are provided in Table 5.1.

Note that it is possible that the same workow contains the two kinds of antipattern.

Results obtained by DistillFlow

Table 5.2 provides the results obtained by DistillFlow in the two workow sets: the number of workows in which there is no remaining anti-patterns after applying the DistillFlow procedure, the number of workows in which at least one anti-pattern has been removed. myExperiment data set. In the set from myExperiment, DistillFlow is able to remove all the anti-patterns in 80.7% of the cases and at least one anti-pattern in 98% of the cases. 72 workows are not completely free of anti-patterns after the DistillFlow process. However, the majority of these workows has only one or two remaining patterns as indicated in Figure 5.9. More generally, Figure 5.9 shows that the number of remaining anti-patterns is low compared to the number of anti-patterns in original versions of workows. Interestingly, additional experiments showed that on average three copies of processors are removed per workow and this number is even particularly high for some workows (up to 31).

Biovel data set. In the BioVel data set, DistillFlow is able to remove all the anti-patterns in 82.7% of the cases and at least one anti-pattern in all the workows (100 %). Only ve (particularly big) workows have remaining anti-patterns.

All of them have actually one remaining anti-pattern, as indicated in Figure 5.10.

Additional experiments allowed us to state that on this corpus, DistillFlow removes one node per workow on average, compared to three in myExperiment. In very large workows of BioVel (these are as large as the largest workows in myExperiment), up to 15 nodes are removed, compared to 31 in myExperiment.

In conclusion, the additional curation steps that occur in the BioVel community clearly make the produced workows being of better quality; however some of these workows could still benet from our distilling approach.

Discussion

In this section, we discuss several points related to our approach: we provide additional examples to underline the fact that the distilled structures are less intricate (5.5.1); we discuss the impact of our refactoring approach on the SP feature of the workow structures (5.5.2); we then propose several other kinds of (anti-)patterns which may be directly the cause of non-SP structure (5.5.3); we nally discuss the place of the refactoring approach in the context of provenanceequivalent transformations. rewritten subgraph that is particularly simpler compared to the same fragment of the workow in the original setting. In Figure 5.12, the global structure is also simpler. Processors have been numbered so that the relationship between the two workows (before and after the refactoring process) can be seen: in the original workow p i denotes the i th occurrence of processor p and in the rewritten workow, p i -... -pj denotes the node resulting of the merging of occurrences p i -... -pj. For example, f 1 , f 2 , f 3 , f 4 , f 5 , f 6 are all occurrences of the same processor which are replaced by one occurrence in the rewritten workow (noted

f 1 -f 2 -f 3 -f 4 -f 5 -f 6 in the rewritten workow).
As a result of the refactoring process on the workow of Figure 5.12, three split processors have been introduced while 18 unnecessary duplications of processors have been removed.

SP structures

As explained in the previous sections, DistillFlow acts carefully on the workow structures, by removing anti-patterns (A) and (B) while never introducing new intricate structures as non-SP structures may be. We will discuss now two situations. In the rst one, we describe situations in which the refactoring al- More generally, in the myExperiment corpus, a total of 15 workows had a non-SP structure before applying the refactoring algorithm and have an SP structure after.

Let us now try to provide an intuition on some situations where refactoring naturally removes reduction vertices. Let us consider another example of non-SP workow in which two forbidden subgraphs are induced by one reduction vertex, which has been discussed in section 4.3. We claim that merging the successors of a reduction vertex may naturally remove this reduction vertex. Figure 5.13 (i) is an example of such a situation. In the example, we know that processors "XP ath_F rom_T ext0" and "XP ath_F rom_T ext" have the exact same code (so that they can be merged). A similar situation occurs in the workow of Figure 5.12 in which nodes #e1-e2-e3 and #e4-e5-e6 cannot be merged by DistillFlow in order to avoid introducing one additional reduction node.

Towards other kinds of (anti-)patterns

Another kind of situation that may occur is when the SP feature is not correlated at all with anti-patterns: the transformed workows are free of anti-pattern but they still have non-SP structures.

A deep inspection of such workows reveals that other kinds of patterns may be directly the cause of non-SP structures [CCBF + 12]. These patterns have a dierent nature from the anti-patterns considered so far in this chapter in the sense that they cannot be removed while keeping the same workow semantics. One of the most interesting pattern is probably the presence of intermediate processors which are directly linked to the workow outputs. This situation occurs merely when users want to keep track of intermediate results and forward such results

to the workow outputs. We call such intermediate processors trace nodes and their outgoing edges linked to the workow outputs are called trace links.

On the total number of workows in myExperiment, we found 2464 reduction vertices including 853 trace nodes: 34.6% of the reduction vertices have trace links. In the Biovel data set, we found 334 reduction vertices including 60 trace nodes, meaning that 18% reduction vertices have trace links. Trace links are thus important to be considered.

More precisely, several workows depicted in this chapter have trace links.

For example, in Figure 5.12 on the top, the link that goes from the processor g 6 directly to the workow output O α is a trace link: when the workow will be executed, the same data (produced by g 6 ) will be sent both directly to the workow output O α and to the downstream part of the workow. By doing this, the workow designer may want to keep track of the data produced by g 6 . However, as the processor get_gi will consume O α to produce to its turn some data, these produced data will have O α in their provenance information. O α will thus be automatically tracked by the provenance module of Taverna. The trace link from g 6 to O α is then useless and could be removed. This removal should actually be done very carefully since removing trace links implies removing part of the workow outputs. As a consequence, the signature of the workow (the number of outputs) is changed which may have several consequences if the transformed workow is used as a subworkow within another bigger workow that expects the subworkow to provide given outputs. This kind of transformation should then be done in collaboration with the user so that s/he can estimate the impact of the changes.

Provenance-equivalence

In Chapter 2, we have presented a provenance model and dened the notion of provenance-equivalent runs. As discussed in 3.4 our current provenance model is coarse grain and in particular it does not consider the specicity of Merge and 5.6. Related Work 101 Split tasks which deal with lists of data items. As a consequence, the refactoring approach cannot be proved to be provenance-preserving in the sense of the denition given in section 3.3 (which does not consider merge and split tasks).

However, we have proved in section 5.2 that DistillFlow transforms any workow into a semantically-equivalent workow. The extension of our provenance model drawn in section 3.4, together with an extention of the notion of provenanceequivalence in such a new context, should make it possible to state that DistillFlow is provenance-equivalent.

Related Work

To the best of our knowledge, this is the rst attempt at introducing a refactoring approach aiming at reducing workow redundancy in the scientic workows setting based on the study of workow structure.

More research is available from the business workows community, where several analysis techniques have proposed to discover control-ow errors in workow designs (see [vdAvHtH + 11] for references). More recent work in this community has even focused on data-ow verication [START_REF] Tr£ka | Data-ow anti-patterns: Discovering data-ow errors in workows[END_REF]. However, this work is aimed primarily at detecting access concurrency problems in workows using temporal logics, making both aims and approach dierent from ours. Also, it would be hard to transfer those results to the realm of scientic workows, which are missing the complex control constructs of business workows, and instead follow a dataow model (a recent study [START_REF] Migliorini | Pattern-based evaluation of scientic workow management systems[END_REF] has shown that scientic workows involve dataow patterns that cannot be met in business workows).

With the increase in popularity of workow-based science, and bioinformatics in particular, the study of scientic workow structures is becoming a timely

Conclusion

This work proposes two strategies, respectively based on provenance and workow structure, for rewriting scientic workows into simpler structures, in order to make scientic workow easier to (re)use. This conclusion presents a summary of completed contributions.

Note that the rst strategy related to rewriting non-SP scientic workows into SP workows is introduced in chapter 4 and has been published in eScience 2012 [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF] and BDA 2012 [START_REF] Cohen-Boulakia | Reecriture de workows scientiques et provenance[END_REF]; and the second strategy related to rewriting scientic workows by removing some anti-patterns to reduce redundancy of them is introduced in chapter 5 and has been published in the "BMC Bioinformatics" Journal [CBCG + 13] and a poster at NETTAB 2012 [CCBF + 12].

Here, we recall the contributions that have been introduced in chapter 1.

Broadly stating, the main contributions of this work include the design of ( The fourth direction includes enriching the distilling approach with new patterns (such as trace links) and making it possible to choose whether or not such patterns should be transformed, in an interactive process. In such a framework, users might even have the choice to remove some anti-patterns even if the resulting workow is non-SP, thus relaxing the SP-constraint. One of the challenges of such an approach will be to provide users with means to estimate the impact of their choices on the workow structure and its future use.

Instead of considering an automatic procedure, the distilling procedure would be used during the design phase in a semi-automatic way. The refactoring approach would thus be built into the scientic workow system design environment.

It may then be complementary to approaches like [START_REF] Ingo | Designing workows on the y using e-bioow[END_REF] which help users nd and connect tasks following an on-the-y approach during the design phase or [GGW + 09] which supports workow design by oering an intuitive environment able to convert the users' interactions with data and Web Services into a more conventional workow specication.

We are also seeking to better understand the reasons why some workows are not SP. Appendix B provides a preliminary study on the kind of processors which may be more inclined to the reduction nodes and thus to make the workow structure being not SP.

The longer term goal would then be to propose guidelines for workow authors to more directly design distilled workows. This work will be achieved in close collaboration with workow authors and will involve conducting a complete user study to collect their feedback on the distilling approach and possibly resulting in nding again new anti-patterns.

List of Figures

1.1 anti-patterns using Anti-pattern Remover.

Note that this collaboration feature will provide the possibility of extending DistillFlow to support other anti-patterns which can be removed in collaboration with workow users.

b. Refactoring once-for-all: DistillFlow allows to automatically remove all the anti-patterns suggested to be removed by the system. To do so, the user has just to click on the "Remove All anti-patterns" main button (top of The panels (a2) and (b2) respectively display metadata of the two versions of workows (number of processors, links, authorship information etc.) while panel (c) provides the metadata of the two graphs displayed in (a1) and (b1) (number of total nodes, links etc.). The panel (d) is particularly important and provides a table of all the anti-patterns detected in the original workow. Here, the user has clicked on anti-pattern "13-11-12" in the anti-pattern information panel (d) which has automatically highlighted the corresponding anti-pattern both in the initial workow (panel (a1)) in which three vertices are involved and in the distilled workow (panel (b1)) in which the anti-pattern has been removed by the system, merging vertices "13", "11" and "12", resulting in only one vertex, numbered 13.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1 Motivation Scientic workow management systems, (e.g., Taverna [HWS + 06], Kepler

2

  Chapter 1. Introduction to represent in-silico experiments, which entails frequent reuse and repurposing throughout their life-cycle [CM11].

Figure 1 .

 1 Figure 1.1 provides (a) an example of workow specication from Taverna [HWS + 06], (b) its representation as a graph and (c) an example of run. Faced

  used in this dissertation, mainly adapted from [BKS92, Val78, Esc03]. We use upper case alphabetic characters (A, B, C, • • • ) to denote sets, and use lower case (a, b, c, • • • ) to denote the elements of a set.

Figure 2 . 1 :

 21 Figure 2.1: Example of dag. (a) a dag, (b) a labeled graph of (a).

  abbreviated as multidag (cf. Figure 2.1 (a) with multi edges between vertices b and e).

  Figure 2.1 (a), Succ(f ) = {h} and P red(f ) = {a, c, d, g}.

  Example 2.1.4 In Figure 2.1 (a), p(a, f ) is the single path consists of edge e(a, f ) and p(a, f ) c = [a, c, f ] while p(a, f ) d = [a, d, f ], and path p(s, t) c = [s, a, c, f, h, t] is a full path.

2. 1 .

 1 Basic graph concepts and notations 13 Example 2.1.6 The edge e(a, f ) in Figure 2.1 (a) is redundant, because there are paths p(a, f ) c and p(a, f ) d which do not include edge e(a, f ).Denition 2.1.10 [BKS92] A multidag G is an st-multidag, also called twoterminal multidag, if there exists exactly one source and exactly one target in G.

  Example 2.1.8 Let us consider Figure 2.2 with only solid lines. In (a), S(G) = {1, 2}, T (G) = {t}, because |S(G)| = 2 > 1, we should add a single source "s"and edges e(s, 1), e(s, 2) to G 0 (represented with dashed lines). We do the same process for (b),(c) and (d). In (d), nothing is added. It means that G 3 itself has already a single source and a single target, thus G 3 is an st-multidag.

Figure 2 . 2 :

 22 Figure 2.2: Example of generalized st-multidags. For each graph, the vertices and edges drawn in dashed lines are the vertices and edges that should be added to the initial graph which is drawn in solid lines to get an st-multidag. (a) adding a source; (b) adding a target; (c) adding both a source and a target; (d) the graph is an st-multidag.

2. 3 .

 3 Figure 2.3: Recursive construction of SP graphs: (a) Basic SP graph (BSP), (b) parallel composition, (c) series composition.

Figure 2

 2 Figure 2.1 (a) is homeomorphic to the forbidden subgraph of Figure 2.4, as a consequence Figure 2.1 (a) depicts a graph which is a non-SP graph.

Figure 2 . 4 :

 24 Figure 2.4: The forbidden subgraph for SP-graphs

  the unique incoming edge of v and f = (v, w) is the unique outgoing edge of v. The operation op sr of Series Reduction in v replaces e and f by g = (u, w).

  2. Parallel Reduction. Let v, w ∈ V 1 linked by k edges e 1 • • • e k . The operation op pr of parallel reduction in v and w replaces the k edges by a unique edge g = (v, w) and leaves all the remaining edges unchanged.

  and L 2er (g) = (L 1er (e 1 ) + ... + L 1er (e k )).

Figure 2 . 5 :

 25 Figure 2.5: (a) Series reduction; (b) Parallel reduction

  Figure 2.7 (a) provides one example of workow and Figure 2.7 (b)

Figure 2 . 7 :

 27 Figure 2.7: An example of Taverna workow ((b) is the specication graph for (a))

  Figure 3.1: A run of a simple workow

Figure 3 . 2 :

 32 Figure 3.2: Two graph illustrating provenance related notions

  Figure 3.2 (a). The immediate provenance of data d 5 owing in edge e 5 is given by task v, directly taking d 2 and d 3 as its inputs. This information can be represented as: imP rov(e 5 ) = ṽ • (d 2 + d 3 ).

  the set of labels of the vertices of G run . We will note L vr (y) the label of the edge e = (u, v) ∈ E d such that e 1 (x, y), e 2 (y, z) ∈ E run and L er (e 1 ) = u, L er (e 2 ) = v, i.e. L ed (e(u, v)) = L vr (y).

Figure 3 .

 3 Figure3.3 shows the data dependency graphs for the runs in Figure3.2. Dependency graphs are natural views of runs, they have the same data and process dependencies. Of course, all the dependencies of data and processes can be directly obtained from a run itself, by considering in the run all the data items as vertices and all the tasks as edges which link two data items together by taking one data item as input and producing another one as output. Obviously, the two runs have the same structures of data dependency graphs.

Figure 3 . 3 :

 33 Figure 3.3: Data dependency graphs for runs in Figure 3.2. (a) data dependency graph for G r ; (b) data dependency graph for G r ′

  have introduced a model of provenance which is compatible with the Open Provenance Model (OPM) [OPM]. In the OPM, an atomic data structure d is called an artifact, an invocation of a processor p is called a process, an in-edge e to a processor p with L er (e) = d corresponds to an used edge d used p, and an out-edge f from a processor p with L er (f ) = d corresponds to a wasGeneratedBy edge p genBy d. Similarly, the above expressions built on vertex and edge labels using "+" and "•" has several patterns:

  Firstly, we consider Figure 3.4, its data dependency graph is shown in Figure 3.5. It is obvious that the sets of intermediate and nal data produced by these two runs are the same, which are d 1 , d 2 , • • • , d 6 . The only dierence is that the run G 0 contains a merge processor which merges d 1 , d 3 into a collection d x = [d 1 , d 3 ], then processor v takes this collection as input and produces another collection d y = [d 4 , d 5 ] as output. But in G 1 , processor v separately produces d 4 and d 5

Figure 3 . 4 :

 34 Figure 3.4: Example of a run which contains a merge processor (a) initial run (d x = [d 1 , d 3 ], d y = [d 4 , d 5 ]); (b) an equivalent run of (a).

  obtain:

Figure 3 .

 3 Figure 3.5 shows the data dependency graphs for the runs in Figure 3.4. In Figure 3.5 (a), we can obtain that d y = [d 4 , d 5 ] depends on d 1 and d 3 . It will raise a risk of misleading a meaning that d 4 depends on d 1 and d 3 or d 5 depends on d 1 and d 3 too, which is not correct since v produced d 4 and d 5 in turn when taking d 1 and d 3 as inputs. However, in Figure 3.5 (b), all the data dependencies are unambiguous. Indeed, the two runs in Figure 3.4 are equivalent, because they produced the same intermediate and nal data. It implies that the output provenance expressions of the two runs should be equivalent. Figure 3.4 also indicates that a run like (a) can be transformed into (b), so that it will have an unambiguous provenance meaning (ne-grained provenance) following the representation of regular expression. How to extend our model to obtain equivalent output provenance expressions from G 0 and G 1 in Figure 3.4 currently remains an open question.

3. 4 .

 4 Figure 3.5: Data dependency graphs of runs in Figure 3.4

Figure 3

 3 Figure 3.6: Example of a run which contains a split processor (a) initial run (d x = [d 2 , d 3 ]); (b) an equivalent run of (a).

  Figure 3.7: Data dependency graphs of graphs in Figure 3.6

Figure 3

 3 Figure 3.6(b) is the equivalent run of (a), in which the immediate and nal data are the same because a split processor does not do any change to the data.

3. 4 .

 4 Figure 3.8: Combination of a merge processor and a split processor. (a) initial graph G r (d x = [d 3 , d 2 ], d y = [d 5 , d 6 ]); (b) an equivalent graph of G r

Chapter 4 .

 4 Rewriting scientic workows while preserving provenance

Figure 4 .

 4 Figure 4.1: (a) Example of simple workow from Taverna, (b) graph structure of the workow (non SP); (c) possible SP graph structure; (d) proposal of composite vertices; (e) high-level graph obtained

[

  BKS92]. It has already been introduced in Chapter 2 that series and parallel reductions can be used to eliminate all the SP components (series components and parallel components) of the graph. After applying such transformations, only vertices and edges associated with forbidden subgraphs remain. Then one can use the operator of vertex reduction to eliminate the vertices which induced the forbidden subgraphs. The vertex reductions can be divided into two classes, outvertex reduction and in-vertex reduction. In the rst situation, the vertex has only one input link and a collection of output links. In the second situation, it substitutes a vertex with only one output link and a collection of input links. The eect of vertex reduction in both cases, is shown in Figure 4.2.

Figure 4 .

 4 Figure 4.2: (a) Out-vertex reduction; (b) In-vertex reduction

Figure 4 .

 4 2 (a)).

Figure 4 .

 4 2 (b)).

  G r indicate the data dependencies and the labels of an edge represent data production. Recall that our aim is to transform graphs while preserving provenance information. During each transformation we need to keep track of the vertices and edges removed. Following in the denition of outvertex reduction, the label of a new edge is replaced by the data ow information consists of the eliminated vertex and its edges. In that way, after the graph being reduced to one single edge, the label of the edge remained saves all the data ow information of G r which related to the expression of the output provenance of the execution graph. Example 4.2.1 Consider Figure 4.3. Initially, each edge has a single label, and after applying a vertex reduction operation on u, edges e 1 , e 4 are replaced by g 2 and e 1 , e 3 are replaced by g 1 . The label of g 1 is replaced by the data ow information which consists of the labels of e 3 , e 1 and u, which is d 3 • u • d 1 . The label of g 2 is replaced by the labels of e 4 , e 1 and u, which is d 4 • u • d 1 . The same way for series and parallel reductions according to their denitions. Finally, as in G 4 , the label

Figure 4 . 3 :

 43 Figure 4.3: Example of reduction operations applied to G 0 .

Figure 4 . 4 :

 44 Figure 4.4: (a) Out-vertex duplication; (b) In-vertex duplication

Figure 4 .

 4 4 (a))

Figure 4 . 4 (

 44 b)).Property 4.2.3 The operation of out-vertex duplication preserves provenance.

  Figure 4.4 (a)). Property 4.2.4 The operation of in-vertex duplication does not preserve provenance.

Denition 4 .

 4 2.3 The reduction complexity of a graph G, denoted by µ(G), is the minimal number of vertex reductions sucient(along with series and parallel reductions) to reduce G to a BSP graph. (This denition comes from [BKS92]) Denition 4.2.4 The sequence of µ(G) vertices (v 1 , v 2 , • • • , v c ) that reduce the graph G to a BSP graph is called reduction sequence. As was shown by Bein, Kamburowsky and Stallman in [BKS92], it is possible to compute µ(G) and reduction sequence in polynomial time complexity. As a result, the maximum distance of a graph to an SP form is limited by the number of vertices: µ(G) ≤ n -3

Figure 4 . 5 )

 45 are possible. From the forbidden graph in (a), the operations of up-, down-and across-synchronization provide respectively graphs (b), (c) and (d). In (b), the edges e(u, v) and e(v, t) are added to forward data value d 4 . In (c), edges e(s, u) and e(u, v) are added. And in (d), one zero loaded vertex w is added, which forwards data values d 1 , d 2 , d 4 to the right destination. Does it provide an SP graph? Yes. Consider the up-synchronization of

Figure 4 .

 4 Figure 4.5(b). Two parallel reductions remove the double edges between u and v and between v and y. Then one series reduction removing vertex u, followed by one parallel reduction between x and v, and a series reduction on v nally provide the BSP graph. The same for (c) and (d), when applying series and parallel reductions on these graphs, nally, we will obviously obtain two BSP. As a result, (b),(c) and (d) all can provide an SP graph.

4. 3 .Figure 4 . 5 :

 345 Figure 4.5: Resynchronization. (a) forbidden subgraph; (b) up-synchronization; (c) down-synchronization; (d) across-synchronization.

Figure 4 . 6 :

 46 Figure 4.6: From the (a) Forbidden graph, use of (b) in-Vertex Duplication and (c) out-Vertex Duplication.

Figure 4 . 7 :

 47 Figure 4.7: Data dependency graphs for runs in Figure 4.6.

Figure 4 .

 4 6 (b). The deep provenance of e 5 has changed in (b): it does not involve data d 2 any more. The major problem is that one input of task v have been removed so that the task cannot deliver results. Its data dependency graph in Figure 4.7 (b) shows that the data value of d 5 disappeared, but two new data d ′ 5 and d ′′ 5 are produced. It is obviously graph (a) and (b) in Figure 4.6 are not provenance-equivalent.

Denition 4 .

 4 3.1 If a forbidden subgraph G contains a reduction vertex v, wesay that G is induced by v.Several forbidden subgraphs can be induced by one reduction vertex. (cf.

Figure

4. 8 )

 8 There are two situations where a graph contains two forbidden subgraphs G 1 and G

54 Chapter 4 .

 4 Rewriting scientic workows while preserving provenance

Figure 4 . 8 :

 48 Figure 4.8: Two forbidden subgraphs induced by one reduction vertex. (a) graph with one reduction vertex u; (b) one forbidden subgraph induced by u; (c) another forbidden subgraph induced by u.

4. 3 .Figure 4 . 9 :

 349 Figure 4.9: Solutions for graphs homeomorphic to Series-non-SP composition (1). (a) a non-SP graph with reduction vertices v 1 and v 2 ; (b) SP transformation of the forbidden subgraph induced by v 1 in (a); (c) SP transformation of the forbidden subgraph induced by v 2 ; (d) SP solution for (a).

Figure 4 . 56 Chapter 4 .

 4564 11 (a)).In series composition (3), only one forbidden subgraph can be found. There are two solutions for this kind of compositions, as shown in Figure 4.11 (b) and (c). In (b), vertices v 1 and v 2 both are duplicated following the reduction sequence v 1 , v 2 . But in (c), only v 2 is duplicated and nally the graph becomes an SP graph. It implies that the reduction sequence also may aect the redundancy of duplicated vertices in the rewritten graphs. It is obvious that (c) has less vertices than (a).Parallel non-SP composition:There exist several similar forbidden subgraphs, in which the reduction vertices(out-vertex reduction) form a parallel composition. Rewriting scientic workows while preserving provenance

Figure 4 .

 4 Figure 4.10: Solutions for graphs homeomorphic to Series-non-SP composition (2).(a) a non-SP graph with reduction vertices v 1 and v 2 ; (b) SP transformation of the forbidden subgraph induced by v 1 in (a); (c) SP transformation of the forbidden subgraph induced by v 2 ; (d) SP solution for (a). For the sake of readability, we give the same name for the duplicated vertices in (d).

Figure 4 . 12 (

 412 b) is the SP graph obtained by duplicating vertex u 1 in the forbidden subgraph induced by u 1 and (c) is the SP graph obtained from the forbidden subgraph

4. 4 .Figure 4 .

 44 Figure 4.11: Solutions for graphs homeomorphic to Series-non-SP composition (3).(a) a non-SP graph with reduction vertices v 1 and v 2 ; (b) one SP solution for (a); (d) another SP solution for (a).

Figure 4 . 12 :

 412 Figure 4.12: Solutions for graphs homeomorphic to Parallel-non-SP composition.

Property 4 .

 4 4.1 A duplicated subgraph is an SP graph.

4. 4 .

 4 SPFlow: a new provenance-equivalent rewriting algorithm for workows 59Proof: A duplicated subgraph corresponds to an edge in G red , i.e. the duplicated subgraph can be reduced to an edge by applying a maximal reduction operation to it. According to denition 2.2, the duplicated subgraph is obviously an SP graph.

Figure 4 . 13 :

 413 Figure 4.13: Example of duplicated subgraphs. (a)SP G; (b)G red of SP G; (c)duplicated subgraph from SP G induced by edge e(s, v) in G red .

Figure 4 .

 4 14, graph G 0 is a graph in which no series or parallel reduction can be applied. Vertices a,u,c,x are reduction vertices in G 0 . Dierent SP graphs obtained by vertex duplication following dierent reduction sequences are shown in Figure4.14 (G 1 , G 2 ). The reduction sequence can be a,u,c,x or u,x etc. G 1 obviously has more duplicated vertices than G 2 . When comparing G 1 to G 2 , it provenance is not dicult to nd that vertices a and c do not need to be duplicated. To distinguish the class of vertices which have the same situation as vertices a and c in G 0 , our algorithm makes use of the notion of autonomous subgraph[START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF].

Figure 4 .

 4 Figure 4.14: Graphs obtained by vertex duplication following dierent reduction sequences (reduction sequence on G 1 : a, u, c, x; reduction sequence on G 2 : u, x).

4. 4 .

 4 SPFlow: a new provenance-equivalent rewriting algorithm for workows 61 Example 4.4.1 In Figure 4.14, G 0 has several autonomous subgraphs such as G[a, b], G[c, d] and G [ s, b] whose separation pairs are (a, b), (c, d) and (s, b). As G[s, b] and G[a, b] have the same forbidden subgraphs, we only consider the minimal autonomous subgraphs for our approach. In this case, G[a, b] and G[c, d] are the minimal autonomous subgraphs, and G[s, b], G[a, t], G[s, d], G[c, t] are not the minimal ones. An autonomous subgraph G[v, w], which is a non-SP graph, can be reduced into a single edge e(v, w), following vertex reduction operations. The reduction vertices v and w may disappear after all the other reduction vertices have been reduced. If v and w are reduction vertices, they may no longer be reduction vertices when all the reduction vertices within the autonomous subgraph are reduced. This implies that the reduction vertices included into an autonomous subgraph should be eliminated rst and then the autonomous subgraph can become SP and be represented as one single edge in G red . Following this process, we can obtain one shorter reduction sequence which will lead to a transformation with less duplicated vertices.To assure that reduction operations never create any new forbidden subgraphs, we constrain the vertex reduction operation to only start from the source of the maximal reduced graph G red . In other words, we always start from the source to choose a successor v of s(G red ) which is a reduction vertex in order to eliminate forbidden subgraphs. Because the duplicated subgraph induced by edge e(s(G red ), v)

4. 4 .Figure 4 .

 44 Figure 4.15: G 1 and G 2 are two solutions of rewritting G 0 , where G 0 does not contain any autonomous subgraph. (reduction sequence of G 1 : a, u, v; reduction sequence of G 2 : v, u).

Figure 4 .

 4 Figure 4.16: Factorization rule for graphs.

Figure 4 .

 4 Figure 4.18: Example of one execution step of SPFlow where G[s, x] has already been transformed, giving the edge (s, x) in G red after vertex reduction on u and providing SP G 1 [s, x] within SP G 1 , after vertex duplication of u. The algorithm then considers x as a successor of s in G red . As (x, t) is a separation pair, it calls again SP F low considering x as source. Vertex y is the successor of x in G red to which a vertex reduction is applied (in G red ). Duplication of y in SP G 1 then leads to SP G 2 . For the sake of readability, labels are omitted.

Figure 4 .

 4 Figure 4.19 (c)) and then reduction of vertex x i (cf Figure 4.19 (d)), we get :

Figure 4 .

 4 Figure 4.19: Example of iterated forbidden graph (IFG).

Property 4 .

 4 4.3 (i) At any step of the algorithm: M axRed(G red ) = M axRed(SP G).(ii) For each vertex w of G red in SP G and G: Hist SP G (w) = Hist G (w)=Hist G red (w). Indeed, to each edge (u, v) of G red correspond a subgraph SP G[u, v]which is SP and to the vertex reduction in G red corresponds a duplication in SP G Property 4.4.4 For all vertex w of G red in SP G and in G we have: Hist(w) SP G = Hist(w) G =Hist(w) G red . This property is a consequence of the properties of reduction operations in section 2.3 and 4.2. Theorem 4.4.1 At the end of the SPFlow algorithm:

1.

  At the end of the algorithm, G red = BSP and G red = M axRed(G red ). Besides, M axRed(G red ) = M axRed(SP G) (property 4.4). Thus M axRed(SP G) = BSP . 2. OutP rov(G) = Hist(t) G ; besides Hist(t) G = Hist(t) G red =Hist(t) G SP G (property 4.5). Then Hist(t) G = Hist(t) SP G = OutP rov(SP G).

4. 5 .

 5 Experimental study 69

Figure 4 .

 4 20 shows that among non-SP workows, 27% of them have one reduction vertex, 62% have only 1 to 3 reduction vertices. They are thus not very far from SP structures.

Figure 4 .

 4 Figure 4.20: Percentage of workows with a given number of reduction vertices in non-SP structures.

4. 6 .Figure 4 .

 64 Figure 4.21: Ratio between the number of vertices in the rewritten graph (G ′ ) and the initial graph (G) in function of the size of G.

  4 and in [CCBF13], named SPFlow, which aims at rewriting a non SP workow into an SP workow while preserving provenance. Current version of SPFlow supports Taverna 2 and ZoomUserView input worows.4.6.1 SPFlow architecture

Figure 4 .

 4 Figure 4.22: Architecture of SPFlow

Figure 4 .

 4 Figure 4.23: Loading a workow in SPFlow

Figure 4 .

 4 Figure 4.23). SPFlow will display the original picture of the workow from my-Experiment [RGS09] if available (left panel), determine (using SPChecker) the reduction nodes (if any) and highlight them (central panel). A report on graph features is produced (metadata on the workow, right panel).

Figure 4 .

 4 Figure 4.25: Provenance information in (A) non-SP and (B) SP version of the workow in ZOOM. User views are displayed on the right while full workows are on the left.

Figure 4 .

 4 25 (B), the rewriting process of SPFlow has duplicated M 6 and M 3 from workow (A) into M 11 , M 8 and M 9 , M 12 in workow (B). As a consequence, the user view designed by ZOOM is only based on signicant composite tasks (Rblast report which contains M 11 , M 13 , M 9 , M 7 , M 15 and M 14 , and R-fastaSequence which contains M 8 , M 12 and M 10 ). Such a workow is then more user-friendly. In particular, each of the two composite tasks takes in now only user input and is then clearly easier to share and (re)use in another context.

Figure 4 .

 4 Figure 4.26: Example of dierent solutions for unsupported patterns.

Figure 5 . 1 :

 51 Figure 5.1: Example of workow (myExperiment 2383)

Figure 5 . 2 :

 52 Figure 5.2: Example of workow (myExperiment 804)

  and 5.4, where each P(l) (1 ≤ l ≤ r) denotes an occurrence (i.e. a copy) of processor P , with input and output ports a 1 , ..., a k and b 1 , ..., b q , respectively.

Figure 5 . 3 :

 53 Figure 5.3: Transformation for anti-pattern (A)

Figure 5 . 4 :

 54 Figure 5.4: Transformation for anti-pattern (B)

Figure 5 .

 5 8(b), examples of autonomous subgraphs are G[7, 24], G[8, 25] and G[3, 24], where G[7, 24] is nested in

Figure 5 .

 5 Figure 5.5 presents the main DistillFlow algorithm while the two procedures it uses, namely DownDistillation and Distill, for transforming workows are available in Figures 5.6 and 5.7. One major and additional function used by the procedure

Figure 5 . 5 :

 55 Figure 5.5: Pseudo-code of the DistillFlow algorithm for removing antipatterns in workows

Figure 5 .Figure 5 . 8 :

 558 Figure 5.7: Pseudo-code of the Distill procedure

Figure 5 .

 5 Figure 5.8 (d) shows the nal workow where almost all the anti-patterns have been removed.

Figure 5 . 9 :

 59 Figure 5.9: Distribution of number of anti-patterns among workows in myExperiment, before and after applying DistillFlow.

Figure 5 .

 5 Figure 5.10: Distribution of number of anti-patterns among workows in BioVel, before and after applying DistillFlow (NB: no workow of this set has 6 antipatterns).

5. 5 . 1

 51 Figure 5.11: Example where the rewritten workow becomes SP (original workow on the top and rewritten workow on the bottom).

Figure 5 . 12 :

 512 Figure 5.12: Example of transformation obtained using DistillFlow (original workow on the top and rewritten workow on the bottom).

Figure 5 .Figure 5 .

 55 Figure 5.13 (ii)). Note that the two forbidden subgraphs are no longer present. More precisely, let us notice that in the induced forbidden subgraph of Figure 5.14 (i).(b), when the nodes #6 and #7 are merged, then the node #4 has only one input and one output (one series reduction operation can thus be applied). At the same time, the forbidden subgraph in Figure 5.14 (i).(c) is naturally eliminated.

Figure 5 . 13 :Figure 5 .

 5135 Figure 5.13: Example of workow (myExperiment 941)

Figure 5 .

 5 Figure 5.8 is one such example: merging nodes #9 and #11 would introduce a new reduction node. In the original graph, node #9 appears in an autonomous subgraph while node #11 does not belong to this autonomous subgraph. If these two nodes were merged, the subgraph formed by all the paths from the split node to the node # 27 would have the structure of the subgraph responsible for non-SP structures (Figure 5.15 (iii)), and the merged node #9-11 would be the new reduction node.Figure 5.15 (i) shows a schematic view of a fragment of the original graph of Figure 5.8 while Figure 5.15 (ii) shows the structure obtained if nodes #9 and #11 were merged. The graph of Figure 5.15 (ii) is homeomorphic to the generic subgraph represented in Figure 5.15 (iii) which is the cause of non-SP structures (cf. Chapter 2).

  research topic. Classication models have been developed to detect additional patterns in structure, usage and data [RP10]. More high-level patterns, associated to specic cases of use (data curation, analysis) have been identied in Taverna and Wings workows [GAB + 12]. Complementary to this work, graph-based approaches have been considered for automatically combining several analysis steps to help the workow design process [RMMTS12] while workow summarization strategies have been developed to tackle workow complexity [PAK13, BBDH08].

  1) a model to present scientic workows and provenance; (2) SPFlow algorithm; (3) the implementation of the SPFlow system which takes in non-SP Taverna workows and produces provenance-equivalent SP workows; (4) the identication and automatic detection of a set of anti-patterns that contribute to the structural workow complexity; (5) a series of refactoring transformations to replace each anti-pattern by a new semantically-equivalent pattern with less redundancy and simplied structure; (6) a distilling algorithm named DistillFlow that takes in a Chapter 6. Conclusion and Future work

  (a) Taverna workow; (b) specication graph; (c) run graph . . . . 2.1 Example of dag. (a) a dag, (b) a labeled graph of (a). . . . . . . . . 2.2 Example of generalized st-multidags. For each graph, the vertices and edges drawn in dashed lines are the vertices and edges that should be added to the initial graph which is drawn in solid lines to get an st-multidag. (a) adding a source; (b) adding a target; (c) adding both a source and a target; (d) the graph is an st-multidag. 2.3 Recursive construction of SP graphs: (a) Basic SP graph (BSP), (b) parallel composition, (c) series composition. . . . . . . . . . . . 2.4 The forbidden subgraph for SP-graphs . . . . . . . . . . . . . . . . 2.5 (a) Series reduction; (b) Parallel reduction . . . . . . . . . . . . . . 2.6 Example of reduction operations applied to G 0 . . . . . . . . . . . . 2.7 An example of Taverna workow ((b) is the specication graph for (a)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 A run of a simple workow . . . . . . . . . . . . . . . . . . . . . . . 3.2 Two graph illustrating provenance related notions . . . . . . . . . . 3.3 Data dependency graphs for runs in Figure 3.2. (a) data dependency graph for G r ; (b) data dependency graph for G r ′ . . . . . . . . . 3.4 Example of a run which contains a merge processor (a) initial run (d x = [d 1 , d 3 ], d y = [d 4 , d 5 ]); (b) an equivalent run of (a). . . . . . . . 3.5 Data dependency graphs of runs in Figure 3.4 . . . . . . . . . . . . 3.6 Example of a run which contains a split processor (a) initial run (d x = [d 2 , d 3 ]); (b) an equivalent run of (a). . . . . . . . . . . . . . . 3.7 Data dependency graphs of graphs in Figure 3.6 . . . . . . . . . . . 3.8 Combination of a merge processor and a split processor. (a) initial graph G r (d x = [d 3 , d 2 ], d y = [d 5 , d 6 ]); (b) an equivalent graph of G r 4.1 (a) Example of simple workow from Taverna, (b) graph structure of the workow (non SP); (c) possible SP graph structure; (d) proposal of composite vertices; (e) high-level graph obtained . . . . . . (re)use (Tool)

Figure A. 2

 2 Figure A.2). Again using Anti-pattern Remover, DistillFlow transforms any complex workow with anti-patterns into a simpler workow which is free or partly free of anti-patterns (see Figure A.3 panel (b1)). Both workows will be displayed. Once the set of anti-patterns to be removed has been selected the user clicks on the "Result overview" button (top of Figure A.2) which automatically opens a new window entitled "Result Overview" and displays the original (Figure A.3 panel (a1)) and distilled workows (Figure A.3 panel (b1)).

  Basic graph concepts and notations . . . . . . . . . . . . . 10 2.2 General workow model . . . . . . . . . . . . . . . . . . . . 15 2.3 Series-Parallel graphs . . . . . . . . . . . . . . . . . . . . . . 16 2.3.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 SP reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.3 Properties of SP graphs related to their recognition . . . . . 19 2.4 Workows in Taverna . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

	Chapter 2
	Preliminaries
	Contents
	2.1

  L vr (x) = x and d i the label of the edge e i , i.e. L er (e i ) = d i .

	Chapter 2. Preliminaries
	2.3 Series-Parallel graphs
	In this subsection we examine series-parallel graphs (SP graphs) which are a
	common type of graph, and have been introduced by Dun [Duf64] to model
	electrical networks. They have a signicant use in several applications that make
	them interesting to examine. As stated in [DB99], using SP graphs we can suc-
	cessfully visualize ow diagrams [Wik13a], dependency charts [RG00], and PERT
	networks [PER]. The construction of series-parallel DAGs and their relation with
	general DAGs are the main focus of this section. We present here formal deni-
	tions and properties of this kind of graphs. The following denitions are adapted
	mainly from [BKS92, Val78].
	2.3.1 Denitions
	Denition 2.3.1 The class of series-parallel graphs (SP-graphs) is recur-
	sively dened as follows:
	1. Basic SP graph: G, the st-multidag that contains two vertices s and t
	joined by a single edge is an SP-graph (called "BSP");
	2. Series Composition: if G 1 (source s 1 and sink t 1 ) and G 2 (source s 2 and
	sink t 2 ) are two SP-graphs, G obtained by identifying s 2 =t 1 is an SP-graph
	with source s 1 and sink t 2 ;
	3. Parallel Composition: if G 1 (source s 1 and sink t 1 ) and G 2 (source s 2 and
	sink t 2 ) are two SP-graphs, G obtained by identifying s 1 = s 2 , t 1 = t 2 is an
	SP-graph with source s 1 and sink t 1 .
	The above denition can be understood by inspecting Figure 2.3. In this
	gure we construct the parallel composition of the basic graphs by joining the
	sources at the top and sinks at the bottom (see Figure 2.3 (b)). Similarly we
	construct the series composition by joining the sink with the source of the two
	basic graphs(see Figure 2.3 (c)). In the same way, we can compose more complex
	graphs by combining these compositions.
	Denition 2.3.2 A st-multidag is non-SP i it is not an SP graph.

  Denition 2.3.6 Let G be an st-multidag. G is maximally reduced ("MaxRed") if and only if no series or parallel reduction can be applied to it.

	20	2.4. Workows in Taverna	Chapter 2. Preliminaries	21
		for list data processing. Examples of Taverna workows are given throughout
		this dissertation, and especially in Chapter 5. A workow consists of a set of
		processors, which represent software components such as Web Services and may
		be connected to one another through data dependencies links. This can be viewed
		as a directed acyclic graph in which the nodes are processors, and the links specify
		the data ow.
		Denition 2.3.7 A maximal SP reduction graph of G, is another graph
		G red obtained by using all possible series and parallel reduction operations (i.e.
		MaxRed) on G:	Based on the properties
	G red = M axRed(G) of these graph classes, linear time complexity algorithms to recognize SP-graphs
	We now introduce a set of properties of SP graphs. are possible.
	Property 2.3.3 [Sch95, VTL82]: The recognition of a series-parallel DAG can 2.3.3 Properties of SP graphs related to their recognition be done in linear time.
	Determining whether a graph is SP is associated to several properties that we Ecient parallel algorithms for recognizing SP graphs have also been proposed provide below. in [BDF96, HHC99, HY87, Epp92].
		Property 2.3.1 [Val78]: Let G be an st-multidag. G is SP if and only if there Now that all the graph-related denitions have been introduced to represent
	exists a sequence of series and parallel reductions that reduces G to BSP . workows, the next subsection introduces the concrete form of workows we work
	on.	Property 2.3.2 Performing series and parallel reduction operations in any or-
		der on Graph G to get the BSP will allow to obtain the same resulting graph.
	(Church-Rosser property [VTL82]). 2.4 Workows in Taverna
		Figure 2.6 describes reductions performed on the st-multidag of G 0 . As only This subsection gives an introduction to Taverna workows, because our work
	series and parallel reductions are used to reduce graph G 0 to BSP , the initial currently is mainly based on the Taverna workow model [HWS + 06]. Taverna
	graph G 0 is thus SP. combines a dataow model of computation with a functional model that accounts

Figure 2.6: Example of reduction operations applied to G 0 .

Interestingly, SP graphs are a subclass of planar graphs, and also a subclass of k-terminal graphs (see e.g.

[START_REF] Hans | Dynamic algorithms for graphs with treewidth 2[END_REF]

). SP graphs are equivalent to partial 2-trees, a subclass of bounded tree-width graphs (see e.g.

[START_REF] Hans | Dynamic algorithms for graphs with treewidth 2[END_REF]

).

  this case, d x0 is changed into d y0 and we assume that d y0 depends only on d x0 .

In our model, d y should fully depend on d x , which may imply that not only d y0 depends on d x0 , but also d y0 depends on the d i . As a result, it may lead to a wrong provenance meaning.

Furthermore, various patterns of data dependencies in collection-oriented approaches [CW03,MBK + 08,MBZ + 08,BML + 06,QF07] can arise, so that not all parts of the output depend on all parts of the input. Let us assume that a processor receives input d x and produces output d y as follows:

  Soundness of vertex duplication algorithm . . . . . . . . . . 68 4.5 Experimental study . . . . . . . . . . . . . . . . . . . . . . . 69 4.5.1 Workow Structures . . . . . . . . . . . . . . . . . . . . . . 69 4.5.2 Evaluating SPFlow . . . . . . . . . . . . . . . . . . . . . . . 70 4.6 Implementation of the algorithm . . . . . . . . . . . . . . . 71 4.6.1 SPFlow architecture . . . . . . . . . . . . . . . . . . . . . . 71 4.6.2 Functionalities of SPFlow . . . . . . . . . . . . . . . . . . . 72 4.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

	Chapter 4. Rewriting scientic workows while preserving
		provenance
	4.4.4	Chapter 4
	Rewriting scientic workows while
		preserving provenance
	Contents

  [START_REF] Blaha | Wien2k, an augmented plane wave plus local orbitals program for calculating crystal properties (karlheinz schwarz[END_REF], and the MeteoAG workow is a meteorology simulation application [SQN + 06], and the GRASIL workow calculates the spectral energy distribution of galaxies [SGB + 01]; this latter application has actually a fork-join graph. A last example is the fMRI workow [ZWF + 04], which is a cognitive

	neuroscience application.
	Motivated by the facts above, we would like to provide workows with series
	parallel structures for achieving more ecient solutions for workow operations

Interestingly, most of the business workow structures are captured by SP structures

[START_REF] Migliorini | Pattern-based evaluation of scientic workow management systems[END_REF]

. Several approaches

[START_REF] Biton | Querying and managing provenance through user views in scientic workows[END_REF][START_REF] González-Escribano | Gemund et Valentín Cardeñoso-Payo : Performance implications of synchronization structure in parallel programming[END_REF]

have shown that using SP workows allows to design more user-friendly workows and provide more ecient execution settings. Others [BBD + 09, CFS + 06], in particular in the domain of provenance information management, have even chosen to restrict workow graphs to SP structures. And in the domain of workow scheduling, many approaches [ZCHW11,MKK + 05,BRGRM11] restrict workow graphs to SP structures to solve some scheduling or mapping problems which can not work on DAGs in polynomial time, such as mapping workows onto chip multiprocessors

[START_REF] Benoit | Energy-aware mappings of series-parallel workows onto chip multiprocessors[END_REF]

. Furthermore, in

[START_REF] Qin | Advanced data ow support for scientic grid workow applications[END_REF]

, Qin and Fahringer discussed several scientic grid workow applications, which are all structured as SP graphs: the WIEN2k workow performs electronic structure calculations of solids using density functional theory [on graph structure (e.g., search for (sub)graphs, comparing graphs). This subsection provides scenarios to illustrate in more details the benets of considering SP structures for scientic workows.

  Chapter 4. Rewriting scientic workows while preserving provenance nomial time on such structures [LS88]. Another example of the type of queries involving operations on graphs is the search for dierences between workow structures [CFS + 06, BBD + 09]. Again the problem of calculating the dierence of two subgraphs of the same graph is NP-hard in the general case and polynomial for SPgraphs [BBD + 09]. The operation of querying structures or comparing structures in scientic workows may can benet from SP structures. Knowing the distance from non-SP to SP graphs gives a better understanding of the basic concept of designing automatic transformation techniques. In this section, we present formal methods, adapted from [BKS92], to dene and measure the distance from a non-SP graph to an SP graph. Such denitions are at the basis of the transformation techniques detailed in the next section.The distance from non-SP to an SP graph can be measured by the number of induced forbidden subgraphs that the non-SP graph has. This distance has shown

	4.1.3 Scheduling workows
	Orthogonally, SP structures can also be particularly interesting in the con-
	4.1.2 Querying workows
	Another way to design workows is to build on existing workows. The user
	can query a workow warehouse to nd workows having a particular structure
	or containing a given pattern. The need for the user to be able to do this type of
	research in warehouses has been expressed for several years [GFG + 09, CBL11, G-
	GB11] but is still not considered in the workows warehouses today, as this type

of research is directly associated with problems known to be NP-hard (subgraph isomorphism) on conventional DAGs. SP structures have again a clear advantage: nding a subgraph isomorphic to a given graph can be treated in poly-text of scheduling runs. In the broader eld of scheduling tasks in programs, SP structures have been exploited for decades

[START_REF] González-Escribano | Gemund et Valentín Cardeñoso-Payo : Performance implications of synchronization structure in parallel programming[END_REF]

, particularly because they have demonstrated their benets for program analysis

[START_REF] Lodaya | Series-parallel posets: algebra, automata and languages[END_REF]

, cost estimation

[vG97]

, and eectiveness of planning

[START_REF] Finta | Scheduling uet-uct series-parallel graphs on two processors[END_REF]

. Many current approaches [ZCHW11, MKK + 05, BRGRM11] also show that more ecient solutions can be carried out if scientic workows have SP structures. With the development of grid and cloud computing, running workows on multiple, distributed resources is of growing importance. As a combination of series and parallel components, SP-workows t particularly well with MapReduce environments.

4.2 Distance from non-SP to SP graphs

Recall that our aim in this chapter is to propose approaches able to rewrite any non-SP graph into an SP graph. to be a very important parameter of a graph. Many graph analysis problems are NP-hard, and hence there is probably no polynomial-time algorithm for any of them. But it has been shown that there exist feasible solutions for many of them if the graph is restricted to an SP graph

[START_REF] Valeska Naumann | Measuring the distance to series-parallelity by path expressions[END_REF][START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF]

. Nevertheless, it is possible

  and replacing edges {e 2 , ..., e k } by new edges {g 2 , ..., g k } with g

Table 4 .

 4 1: Evolution of SP structures in workows of myExperiment

	Date Number of	SP graphs	non-SP graphs
		workows (proportion)	(proportion)
	2010	681	429 (63%)	252 (37%)
	2011	879	554 (63%)	325 (37%)
	2012	1014	624 (61,5%)	390 (38,5%)
	2013	1454	833 (57,3%)	621 (42,7%)
	Table 4.2: non-SP vs SP structures in families
	Family (#vertices)	#workows % of SP structures
	Simple (1-10)	848	82.2 %
	Complex (11-20)	282	44 %
	Very complex (≻ 20)	324	6.2 %
	4.5 Experimental study

Our experiments run on a subset of 1,454 workows extracted from the Taverna workows available in myExperiment [GFG

+ 09]

in July 2013 (removing duplicates

  AU ← set of autonomous subgraphs of G ordered by inclusion; " foreach subgraph G[u, v] of AU , starting with minimal subgraphs do #

	START DistillFlow
	DSG ← G; s ← Source(G);
	! Distill(G[u, v], DSG, u)
	$ end
	% Distill(G, DSG, s);
	& END DistillFlow

  Distill(IN GG: graph; IN/OUT DSGG: graph; IN x: node) v ← sink(GG); ! ListRed ← set of reduction nodes of GG; " SetAU ← set of autonomous subgraphs of GG; # Visited(GG) ← false /* set all the nodes of GG unvisited */ $ foreach successor p of x in GG do

		/* search for copies of p */
	%	if Visited(p) ← false then
	&	p 1 ← p; f lagp ← true;
	'	while f lagp do

Table 5

 5

		.1: Initial number of anti-patterns in workow sets
	wf set	# wf # wf ≥ 1	# wf ≥ 1 anti-	# wf ≥ 1 anti-
			anti-pattern	pattern (A)	pattern (B)
	myExperiment 1,454 374 (25.7 %) 80 (5.5 %)	359 (94.5%)
	BioVel	71	29 (40.8 %)	0	29 (100%)

Interestingly, 25.7% of the workows of the myExperiment set contains at least one anti-pattern. Although anti-pattern A appears in only 5.5% of the total, it is particularly costly because it involves multiple executions of the same processor with the exact same input, therefore being able to remove it would be particularly benecial. The prevalence of pattern B suggests that workow designers may not know the list processing properties of Taverna (or functional languages).

As for the BioVel private workows, 40.8% include at least one anti-pattern, all of kind B and thus none contains any kind A. Additionally, other experiments allowed us to observe that a workow from BioVel contains, on average, fewer anti-patterns than, on average, a workow from myExperiment.

Table 5 .

 5 2: Results obtained by DistillFlow in the two workow sets

	wf set	# wf without any anti-	# wf with at least one
		pattern	anti-pattern removed
	myExperiment 302 (80.7%)	367 (98.1 %)
	BioVel	24 (82.7%)	29 (100%)

  5.7 SummaryIn this chapter, we have introduced a new strategy for reducing redundancies in the structure of scientic workows and have presented an algorithm, DistillFlow, which refactors Taverna workows in a way that removes explicit redundancy making them possibly easier to use and share. Currently, DistillFlow is able to detect two kinds of anti-patterns, and rewrites them as new patterns which better exhibit desirable properties such as maintenance, reuse, and possibly eciency of resource usage. Then we applied DistillFlow to two workow collections, the one consisting of myExperiment public workows, the other including private workows from the BioVel project. Finally, we have discussed several points related to our approach, in which, additional examples are provided.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 This chapter concludes our work presented in this dissertation, and nally our future directions are discussed.

	Chapter 6
	Conclusion and Future work
	Contents
	6.1

Acknowledgments

Chapter 4. Rewriting scientic workows while preserving provenance graph BSP . In SP G some vertices of G are duplicated, and these duplications are determined from the out-vertex reductions made in G red . The algorithm will use the procedure M axRed which takes in and out a graph G and applies iteratively on G series and parallel reductions until such reductions cannot be applied anymore.

Vertex duplication algorithm will also use (step 2.ii.3) the procedure Simpl that takes in and out SP G and merges some of its subgraphs using the factorization rule(cf. Step 2 (i) v is the source of an autonomous subgraph of sink w ∈ G red . Call SPFlow (G, G red , SP G, v,w), meaning that we consider G red [v, w] instead of G red (v is considered here as the new source of the reduced graph).

(ii) v is not the source of one autonomous subgraph. 2) Apply out-vertex reduction to v in G red .

3) G red ← M axRed(G red ); SP G ← Simpl(SP G)

End While End SPFlow 4.4. SPFlow: a new provenance-equivalent rewriting algorithm for workows 65

Example of use of SPFlow

We demonstrate the way our algorithm works with an example graph shown in Figure 4.17(a). Its maximal reduced graph G red is shown in Figure 4.17

Complexity

As expected, SPFlow has an exponential complexity in the worst case. The worst case occurs in the iterated forbidden graph IFG [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF] that has 2n + 2 vertices (see Figure 4.19). We cannot get BSP with less than 2n -1 outvertex reductions from IFG. This number is the maximal number vertex reductions established by [START_REF] Bein | Optimal reductions of two-terminal directed acyclic graphs[END_REF] for any graph of 2n + 2 vertices, also called the factoring complexity of the graph. The SPFlow algorithm will build the new SP graph SP G Chapter 6. Conclusion and Future work workow and produces a distilled semantically-equivalent workow; (7) a series of experiments to illustrate our approaches.

In particular, the contributions of this work are as follows:

(1) Workow model and provenance model. Our provenance model is naturally compatible with OPM and uses regular expressions to represent the graph structure of provenance information. This provenance model is currently useful for representing coarse-grained provenance structures. Based on this provenance model, we gave a denition of the notion of provenanceequivalence which can be used to identify whether two workows have the same meaning.

(2) Provenance-equivalent SPFlow algorithm. We reviewed several rewriting strategies for transforming non-SP graphs into SP graphs and proved that they were not provenance-equivalent. Then, we designed a new algorithm, SPFlow, which is a provenance-equivalent approach. It enables us to obtain new provenance-equivalent SP workows from non-SP workows.

(3) Implementation of the SPFlow system. (7) A series of experiments have been provided to illustrate our approaches. We have illustrated SPFlow by providing an evaluation of our approach on a thousand of the public Taverna workows. We also have provided an implementation of DistillFlow that we evaluated on both the public Taverna workows and on a private collection of workows from BioVel project.

With all these contributions, we are currently able to obtain (1) SP structures for scientic workows, on which complex workow operations can easier perform;

(2) distilled structures for scientic workows which are free or partly free of redundancy.

Future Work

We intend to continue this work in several directions. These directions have already proposed in [START_REF] Cohen-Boulakia | Scientic workow rewriting while preserving provenance[END_REF] and [CBCG + 13]. Here, we recall them and give a discussion on our ongoing work.

The rst direction of research focuses on extending our provenance model to support ne-grained provenance, in order to deal with "problematic" dependency discussed in chapter 2. We also intend to extend our provenance model to introduce a restricted form of loops in the specications making runs having SPFL structures (for Series-Parallel-Fork-Loop) which are structures sharing advantages of SP structures for some operations on graphs [BBD + 09].

Based on the extended provenance model, another direction of research deals with generalizing SPFlow to other workow systems.

The following directions are mainly related to DistillFlow.

The third direction of research deals with generalizing DistillFlow to other workow systems. In particular, in systems able to exploit multi-core infrastructures or run on Grids or Clouds environments [JCD + 13], our distilling approach could be highly benecial since it pushes the management of multiple activations to system runtime, which can more eciently parallelize their execution when deployed on a parallel architecture. Users communicate with the system by loading and interacting with original and rewritten workows. The functionalities of the system are described in more detail below.

List of Figures

A.2 Functionalities of DistillFlow

Our implementation of DistillFlow is able to provide the following features.

Loading Data: Users start using DistillFlow by loading a workow specication into the system (see to be more suitable to him.

Running the distilled workow: Any workow distilled by DistillFlow can be opened and run by Taverna. We can see that the distilled workow and the original workow provide the same output, if given the same input.

A.3 Extensibility of DistillFlow

This section introduces the extensibility of DistillFlow. Some points for extending DistillFlow have been considered in the architecture of DistillFlow.

We consider here three points:

(1) Extensible libraries: DistillFlow is equipped with two libraries: a library of anti-patterns and a library of distilling algorithms. Any anti-pattern should be registered into the anti-pattern library with several features including the workow systems they can be applied to and the distilling algorithm which can be chosen to deal with them. For example, anti-pattern A is useful for any workow system, while anti-pattern B is only useful for workow systems which support list processing.

Furthermore, for dierent anti-patterns, the distilling algorithms for detecting or removing all the anti-patterns may also be dierent. So, DistillFlow currently considers several features of each distilling algorithm, such as for which anti-patterns or workow system it is suitable. The algorithms should be registered into the algorithm library.

The Anti-pattern Checker and Anti-pattern Remover modules communicate with the two libraries to choose the appropriate anti-patterns to detect and those to distill according to the input workows. With the help of these libraries, DistillFlow can thus be extended to support other anti-patterns.

For example, trace links can be registered as a new kind of anti-pattern compatible with any workow system and any distilling algorithm.

( all the anti-patterns related to this workow in the anti-pattern library and search for the appropriate distilling algorithm in the algorithm library. Then Anti-pattern Checker will identify all the anti-patterns in the workow according to the anti-patterns found in the library by using the related algorithm.

(3) UserCollaboration: This module allows users to take part in the distilling process. Because dierent anti-patterns may require dierent user operations, DistillFlow provides an interface for extending user operations for dierent anti-patterns. For example, when removing a trace link, the user may want to replace it by a collaboration link (as it is not a real data link in the workow, it is not considered in the specication), which is used for querying intermediate data from the internal provenance database of the workow system.

All these features have been considered when DistillFlow has been designed and implemented, which makes DistillFlow able to be extended in our future work.

Appendix B

Why scientic workows have non-SP structures (Preliminary study)

Determining the reasons why some workows have non-SP structures may help users to directly design workows having a structure closer to SP structures. The SPFlow system presented in Chapter 4 may then also be used on less complex, distilled, workows. The aim of this appendix is to present the results obtained on the study that we have conducted on the set of Taverna workows available on myExperiment to analyze the reasons why workows have non-SP structures. A preliminary version of this study has been published in [CCBF + 12].

Our study has been conducted on a set of 1,454 distinct workows extracted from the Taverna workows available in myExperiment in July 2013. We used SPChecker which was a module included in SPFlow to detect whether workow graphs were SP. Among the 621 workows with non-SP structures (42,7%), we have focused on identifying reduction nodes and analyzed the forbidden patterns in which they were involved. ("local worker" to "cds"). Six types of processors (namely, "localworker", "beanshell", "dataow" (subworkow), "wsdl", "stringconstant", and "inputport") are the types of processors mainly used in Taverna, and represent 92.5% of all the nodes. Such kinds of processors represent 90.1% of the total number of reduction nodes. The distribution of nodes based on the type of processor is thus almost the same when considering reduction nodes only or any node.

For the rst 4 types, to our knowledge, SPFlow is currently the unique solution. For the last two types, namely "inputport" and "stringconstant"

(representing 22% of the reduction nodes) we may provide a simpler solution. Indeed, very interestingly, these two types are used as workow input in Taverna. As an input value can be sent to dierent processors, some of them usually have more than one output link. As introduced in Chapter 2, we add a single source (an additional node) to make the workow specication be an st-dag. So, the nodes of input values are thus possible to occur as reduction nodes.

The non-SP problem caused by such a kind of nodes (workow inputs) can be solved in a simple way, namely, by duplicating input values to make sure that each input value is sent to one processor. In such a way, the nodes of input values will never be reduction nodes. Furthermore, the nodes of input values are the children of the source, which makes them easier to be detected.

B.2 Trace links and trace nodes

The third series of experiments has focused on the notion of trace nodes and trace links as introduced in section 5.5.3. Recall that intuitively a trace link is a link from the output of a processor (vertex)

to the nal outputs of the workow that the user may use to keep the trace of some intermediate results produced (although the provenance module is already able to do it). A trace node is the vertex that has a trace link going out of it.

According to our denition (denition 2.3.1 in Chapter 2), trace links actually make the workow be non-SP (if one trace link is removed then the vertex it goes out of may be not a reduction node anymore (cf. Figure B.2)).

Trace nodes are thus very interesting kinds of reduction nodes to look at.

Among a total of 16,984 nodes in the set of non-SP workows, we found 2,464 reduction nodes including 853 "trace nodes" (representing 34.6% of the reduction nodes) and involved in 423 workows (representing 68.1% of non-SP workows).

The distribution of trace nodes in dierent kinds of processors is also shown in Recall that this removal should actually be done very carefully since removing trace links implies removing part of the workow outputs (see section 5.5.3).

In conclusion, we have identied several reasons why workows may not have an SP structure. The notion of trace node seems to be promising and from the type of processors point of view, we will study the behavior of some web services further. Following the solutions underlined, we will get distilled workows in which the number of reduction nodes should importantly be reduced and we hope that a large part of workows may become SP. In our approach, users do not have to consider structural constraints when they design workows; our aim is instead to provide them with designing guidelines ensuring that distilled workows are naturally produced.