Optimizing user views for workflows
A technique called user views has recently been proposed to focus user attention on relevant information in response to provenance queries over workflow executions [1, 2]: Given user input on what modules in the workflow specification are relevant to the user, a user view is a concise representation that clusters together modules to create a small number of composite modules (or clusters) such that (1) each composite module in a user view contains at most one relevant (atomic) module, thus assuming the "meaning" ofthat module; and (2) no control or data dependencies (either direct or indirect) are introduced (soundness) or removed (completeness) between relevant modules. The goal is to find a user view with a smallest number of composite modules. We show that for workflow specifications that are general graphs, regardless of the number of distinct modules in the input workflow and the structure of interaction between them, there always exists a user view of size at most (2k-1 - k)2 + k, where k is the number of relevant modules. Moreover, a good user view with at most (2k-1 - k) 2 + k clusters can be computed in polynomial time in the size of the graph. We also show that this upper bound is tight. Thus in general graphs, the number of composite modules can be exponentially large in k even in an optimum user view for the specification. We also give a characterization of a good user view in terms of structural properties of each cluster in the user view. However, for series-parallel workflow graphs, we show that there is always a user-view with at most 2k - 3 composite modules; further, there exist series-parallel graphs where every user view requires at least 2k - 3 composite modules. Such graphs capture the structure of many scientific and other workflows that we have encountered in practice. For this class of graphs, we give a simple, linear time algorithm for constructing an optimum user view for a given specification. Copyright 2009 ACM.
Biton, O; Davidson, SB; Khanna, S; Roy, S
Acm International Conference Proceeding Series
Volume / Issue
Start / End Page
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)