An optimal labeling scheme for workflow provenance using skeleton labels


Conference Paper

We develop a compact and efficient reachability labeling scheme for answering provenance queries on workflow runs that conform to a given specification. Even though a workflow run can be structurally more complex and can be arbitrarily larger than the specification due to fork (parallel) and loop executions, we show that a compact reachability labeling for a run can be efficiently computed using the fact that it originates from a fixed specification. Our labeling scheme is optimal in the sense that it uses labels of logarithmic length, runs in linear time, and answers any reachability query in constant time. Our approach is based on using the reachability labeling for the specification as an effective skeleton for designing the reachability labeling for workflow runs. We also demonstrate empirically the effectiveness of our skeleton-based labeling approach. © 2010 ACM.

Full Text

Duke Authors

Cited Authors

  • Bao, Z; Davidson, SB; Khanna, S; Roy, S

Published Date

  • July 23, 2010

Published In

Start / End Page

  • 711 - 722

International Standard Serial Number (ISSN)

  • 0730-8078

International Standard Book Number 13 (ISBN-13)

  • 9781450300322

Digital Object Identifier (DOI)

  • 10.1145/1807167.1807244

Citation Source

  • Scopus