Lessons Learned - User-Level Workflow Design: A Bioinformatics Perspective - page 139

7.1.1 Solutions

For assessing the impact of the constraints on the (number of) synthesis
solutions, the numbers of synthesis solutions for the different constraint com-
bination are plotted for the individual search depths. By this means Figures
7.1, 7.2, 7.3 and 7.4 in this section show that the exponential growth of solu-
tions that is typically observed for unconstrained syntheses can effectively be
restrained through the application of constraints that concisely express the
intended workflow structure.
The main reasons for the exponential increase of solutions are:

• Similar services :

The synthesis algorithm generates sequences of services based on the com-
patibility of their input and output types. Accordingly, if no constraints
are provided, all sequences that are technically possible are returned. How-
ever, also in the presence of additional constraints, the services' input/out-
put specification is the main source of information for their combination.
Most application domains, and in particular the domain models for the
bioinformatics scenarios considered in this topic, contain many similar ser-
vices in the sense that they work on similar input types, produce similar
output types, or even simply modify a data item so that the input and
output data types are identical. Obviously, this provides extremely many
possibilities for their combination.

• Accumulation of data:

Most services in the considered application domains generate new data
as they process their inputs to produce their outputs. Accordingly, the
amount of available data (types) increases with the length of the solution,
offering more and more possibilities which services to use.

• Infinite behavior:

Often, individual services or sequences of services can be used repeatedly,
constituting loops that can be repeated infinitely often. Consequently, it
is usually impossible to explore the solution space completely, and the
domain models typically comprise the possibility of infinite workflows.
Although it is principally possible to apply constraints that explicitly
suppress the repeated use of (individual) services, this is not adequate for
all services in general.

Figure 7.1 summarizes the development of the numbers of solutions for
the different sets of constraints applied in the EMBOSS scenario discussed in
Section 3.3. The left plot gives the numbers in normal scale, the plot at the
right contains the same number in logarithmic scale for better discrimination
of the smaller numbers. The legend within the left plot shows which lines in
the plots correspond to which sets of constraints.
As already discussed in Section 3.3, in the unconstrained case the max-
imum capacity of the PROPHETS solution store used in the applications
(1,000,000 solutions) is reached in a search depth of 4. Accordingly, the plot