\section{DATA PROCESSING IN DATA-INTENSIVE WORKFLOWS}
\label{sec:prel}


In this section, we deal with major aspects and the state of the art of data processing in data-intensive workflows. We first introduce a classification of workflows regarding their data-intensiveness and the problem they solve and show the challenges of data processing in these workflows. Afterwards, we deal with different types of workflow languages that are used in such settings. We then present representative concepts for data management in workflows and relate them to the workflow classes. Based on this, we finally illustrate the main aspects by means of a sample scenario.


\subsection{Workflow Classes and their Challenges for Data Processing}
\label{sec:prel:WorkflowClasses}


Figure \ref{fig:WorkflowClassification} shows the classification of workflows regarding their data-intensiveness and the problem they solve. \h{Orchestration workflows} originate from the area of business applications where \mbox{\h{business workflows}} or production workflows orchestrate the execution of different and heterogeneous applications to realize and automate business processes \cite{ProductionWorkflows}. Here, the \mbox{Service} Oriented Architecture (SOA), in particular the Web Services technology, is used to integrate the applications. Similarly, \h{simulation management workflows} coordinate the interaction with simulation applications and resources that execute calculations and data management tasks for simulation processes \cite{SimTech-sWfMS}. See \cite{SIMPL} for a workflow of a bone remodeling simulation that is used to research skeletal disorders, \eg of a human femur.


\begin{figure}[tb]
	\centering
		\includegraphics[width=0.75\textwidth]{Preliminaries/WorkflowClassification.pdf}
	\caption{Classification of workflows regarding data-intensiveness and problem they solve. Workflow classes are shown in rectangles, whereas circles state scenarios or use cases the respective classes find application in.}
	\label{fig:WorkflowClassification}
\end{figure}


In contrast to orchestration workflows, \h{data-intensive workflows} treat data and their processing as first-class citizens. Such workflows typically process huge amounts of possibly distributed and heterogeneous data and carry out a multiplicity of complex data processing steps that may be directly reflected in the workflow definitions. The data may be processed on external resources or even within the workflow. A sub-class of data-intensive workflows are visualization or \h{data analysis workflows}. Their goal is to visualize previously generated data and/or to provide new insights from such data. Typical operations are object identification, feature discovery, and pattern recognition, \eg in a workflow using similarity search and classification to detect the patterns among chemical compounds or other materials \cite{SciDataAnalysis}. \h{Data modeling workflows} try to find a suitable model that describes a certain problem or try to search for patterns in such models. This workflow class includes applications such as model reductions that determine a reduced and thus less compute-intensive model of computation for a simulation problem, without loosing too much precision in the computation \cite{ModelReduction}. Other examples deal with modeling certain materials or searching for certain structures in material models, \eg protein or genome modeling or analysis workflows \cite{Biochemistry}, \cite{GenomeAnalysis}. Typical data management operations in such workflows are sampling and probing subsets of data and pattern matching. The third sub-class of data-intensive workflows constitute \h{extraction, transformation, and load (ETL) workflows}, \ie ETL processes that are modeled and executed using workflow technology \cite{SIMPL}, \cite{Workflow4ETL}. Their main goal is to provide a data integration or provisioning process for superordinate applications or workflows. For example, assume ETL workflows to upload data into a data warehouse or to capture and pre-process scientific data. These workflows include operations for loading or retrieving a bulk of data, filtering a data set, and joining two data sets. Recently, the term \h{scientific workflow} has been coined as generic term for some of these workflow classes \cite{Workflows4e-Science}. This includes simulation management workflows, data analysis workflows, and data modeling workflows (see \mbox{Figure \ref{fig:WorkflowClassification})}.


\subsection{Workflow Languages}
\label{sec:prel:WorkflowLanguages}


The different workflow classes exhibit different kinds of workflow languages. In particular, we distinguish between data-flow-oriented and control-flow-oriented languages. A data flow defines data dependencies between workflow tasks. These data dependencies correspond to unidirectional channels over which data streams are sent. Each task is assigned with input queues for buffering individual data items of such data streams. As soon as the input queues of a task are filled with a certain number or combination of data items, the task processes theses items according to its functional definition. For example, it transforms data items to another format or filters specific items. It then forwards the resulting data items to the input queues of tasks succeeding in the data flow. %Concurrently, it may continue processing further data items that have meanwhile been sent to its own input queues. To ensure reliable data transfer in a distributed environment, a task may also be associated with output queues to buffer data items while sending them over the data flow.
Such data-flow-oriented languages are frequently used to describe all kinds of data-intensive workflows. There already exist market-proven products that show specific solutions in terms of modeling languages, optimization techniques, and execution engines for data-flow-oriented problems, \eg IBM InfoSphere Streams\footnote{IBM InfoSphere Streams: http://www-01.ibm.com/software/data/infosphere/streams/}.

A control flow usually forms a directed, acyclic graph (DAG) whose nodes are the tasks and whose edges constitute causal dependencies between these tasks. Each task is executed at most once and its execution may only start after all preceding tasks within the DAG have successfully and completely finished their execution. Some workflow languages also allow their tasks to be procedural elements that each may contain another DAG of tasks as sub-workflow and that define certain execution semantics of such sub-workflows. For example, loops may define the repeated execution of the inner tasks as long as a certain condition holds \cite{ProductionWorkflows}. As control-flow-oriented workflow languages are increasingly adapted to the needs of data-intensive workflows \cite{Boehm}, \cite{AdaptBPEL2ScWF}, we focus on this setting. In particular, we focus on the local data processing in such workflows. This local data processing is based on handling process variables as described in the following section.


\subsection{Data Management in Workflows}
\label{sec:prel:DM4Workflows}



\begin{center}
\begin{table}[tb]
	\caption{Classification of data management concepts for workflows.}
	\label{table:DM4Workflows:Dimensions}

\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
\begin{center}
\begin{tabular}{|l||c|c|}

\hline
	
\diaghead{Definition Data Management}
{\textbf{Execution of}\\\textbf{Data Management}}{\textbf{Definition of Data}\\\textbf{Management}}
& \h{Within Workflow} & \h{External to Workflow}

\\ \hline\hline


\h{Within Workflow System} & Integrated Case & --


\\ \hline


\h{External to Workflow System} & Hybrid Case & Separate Case

\\ \hline


\end{tabular}
\end{center}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}
\end{center}

Concepts for data management in workflows are characterized along two dimensions: \mbox{(1) whether} the data management operations are defined within the workflow or external to it and \mbox{(2) whether} they are executed within the workflow system or external to it (see \mbox{Table \ref{table:DM4Workflows:Dimensions}}). The first concept, the \h{separate case}, originates from control-flow-oriented settings of SOA-based business workflows. \mbox{In this spirit,} services may encapsulate access to one or more data sources and provide operations on this data, \eg for data extraction or manipulation. Such services are typically called data services or data walls as they hide the data sources and the data processing from the workflow that invokes the services. % They realize a function shipping approach insofar as the function to be processed on the data or an identifier or description of this function is transferred from the workflow over a service to the data sources. The service then sends the result data to the workflow or a notification whether the function has been processed successfully or not.
So, data processing is strictly separated from workflow processing, \ie the data management is both defined and executed by services or external data sources. Scientific applications recently adopted the SOA paradigm as well \cite{Workflows4e-Science}. %A prominent solution for service-based data management in scientific applications is the Open Grid Services Architecture - Data Access and Integration\footnote{OGSA-DAI: http://www.ogsadai.org.uk/index.php} framework (OGSA-DAI).
Most of today's scientific workflow systems offer some kind of activities to invoke services, \eg see \cite{Kepler}, \cite{Trident}, and \cite{SimTech-sWfMS}, and may thus use services for data management.

The \h{integrated case}, on which we focus in this paper, reflects local data processing within workflow systems. So, data and workflow processing are integrated together. Here, data is first shipped to the execution context of the relevant workflow, \ie to input queues of workflow tasks in a data-flow-oriented setting or to process variables in case of control-flow-oriented languages. Workflow tasks embed or define data management operations that are executed locally on the shipped data within the workflow execution environment. As shown in Figure \ref{fig:DataProcessingInWorkflows}, this environment may integrate a database system or other kinds of local data processing units that store or manage the shipped data as well as its processing by the workflow. %To ensure the synchronization between the local data and its external origin, a data consistency mechanism could be used.
%In this paper, we focus on this case as it is especially important for data-intensive workflows that are modeled using control-flow-oriented workflow languages. Such workflows may process huge amounts of data directly within the workflow context, but specific optimization opportunities for this integrated case have largely been neglected in previous work.

The third concept is an approach using data management activities that directly embed data management operations. When such an activity is executed, it seamlessly accesses the specified external data source to issue its embedded operation against this source. So, this forms a \h{hybrid case} as data management operations are defined within workflows as in the integrated case, but are executed by external data sources as in the separate case. These data management activities may also be part of separate ETL workflows that encapsulate data integration or provisioning processes for superordinate workflows. They mainly come from business workflow solutions, \eg the workflow products of IBM, Microsoft, and Oracle that allow for the integration of SQL statements into BPEL processes \cite{SQL_in_BPEL_Overview}. Nevertheless, the same also holds for the scientific workflow solutions Microsoft Trident \cite{Trident} and Kepler \cite{Kepler}. The latter even allows to access proprietary file systems and sensor networks. The Business Process Execution Language extension for Data \mbox{Management} (BPEL-DM) is a data-source-independent approach to embed any kind of data management operation for any kind of data source directly within workflows \cite{SIMPL}.



\subsection{Sample Scenario for Data-Intensive Workflows}
\label{sec:prel:SampleScenario}


\begin{figure}[tb]
	\centering
		\includegraphics[width=0.85\textwidth]{Preliminaries/SampleScenario.pdf}
	\caption{Protein modeling workflow in Business Process Modeling Notation (BPMN).}
	\label{fig:SampleScenario}
\end{figure}


Figure \ref{fig:SampleScenario} shows the activities and their control flow of a workflow for protein modeling \cite{Biochemistry}. This workflow uses pattern matching to find important regions within protein sequences or families, \eg amino acids that are relevant for a certain chemical reaction. In doing so, it identifies or investigates proteins that can solve a certain chemical or biological problem. The workflow first gets input parameters from the client such as identifiers for data sources storing the protein sequences to be investigated. Afterwards, it calls a service to retrieve a list of the relevant protein sequences. This list is stored in a process variable within the workflow. The latter then iterates over the list and searches for a certain pattern within each protein sequence, \eg by means of a regular expression. \mbox{If a sequence} matches the pattern, the workflow adds the sequence header to a list of headers in another process variable. Otherwise, it increments a counter for negative sequences. After having processed all protein sequences in this way, it sends both the number of negative sequences and the list of sequence headers of positive sequences back to the client.

According to our definition of a data-intensive workflow, the protein modeling workflow carries out several data processing steps including data retrievals, variable assignments, and pattern matching. This way, it treats data and their processing as first-class citizens. Most of the data are processed directly within the workflow, \ie in its process variables. The data sizes may range from a few hundred KBs to several MBs or even GBs. The workflow benefits from the control-flow-oriented workflow technology in various ways. For example, we get one common level of abstraction for this workflow and for superordinate simulation management workflows that repeatedly call the protein modeling workflow in order to investigate or to model a set of protein sequences or families. This enables a comprehensive re-engineering or optimization across all involved workflows \cite{BIA}, \cite{PGM/F_Approach}, \cite{Boehm}. Furthermore, we can re-use the protein modeling workflow for various simulation management workflows or other workflows in a generic way. %Furthermore, when dealing with several GBs of data for the protein sequences, this workflow may last several hours or even days. The control-flow-oriented workflow technology helps to ensure a reliable and fault-tolerant execution of such long-running workflows.
However, using control-flow-oriented languages for this kind of workflow sometimes leads to an increased execution time compared to data-flow-oriented approaches. In the next section, we show how to improve the data processing within such workflows and thus to reduce their execution time.