Source-linked AI summary
Putting Lipstick on Pig: Enabling Database-style Workflow Provenance
Yael Amsterdamer, Susan B. Davidson, Daniel Deutch, Tova Milo, Julia Stoyanovich, Val Tannen
TL;DR
The paper addresses workflow provenance that overlooks fine-grained input dependencies and changing module state. It uses Pig Latin and compact provenance graphs to capture these aspects and support richer queries, implemented in Lipstick. The authors report that tracking and querying fine-grained workflow provenance is feasible.
Problem
Standard black-box workflow provenance assumes outputs depend on all inputs and does not model module state, limiting fine-grained dependency analysis.
Method
The framework uses Pig Latin to expose module functionality and provenance graphs to represent fine-grained dependencies, module invocations, and state changes.
Results
The Lipstick implementation and benchmark demonstrate the feasibility of tracking and querying fine-grained workflow provenance.
Takeaways & Limitations
Graph transformations support switching provenance granularity and answering what-if workflow questions unavailable under standard coarse-grained provenance.
Takeaways & Limitations
The approach cannot fully expose modules whose functionality requires complex User Defined Functions, so those portions retain coarse-grained provenance.
Abstract
from arXiv · showhide
Workflow provenance typically assumes that each module is a "black-box", so that each output depends on all inputs (coarse-grained dependencies). Furthermore, it does not model the internal state of a module, which can change between repeated executions. In practice, however, an output may depend on only a small subset of the inputs (fine-grained dependencies) as well as on the internal state of the module. We present a novel provenance framework that marries database-style and workflow-style provenance, by using Pig Latin to expose the functionality of modules, thus capturing internal state and fine-grained dependencies. A critical ingredient in our solution is the use of a novel form of provenance graph that models module invocations and yields a compact representation of fine-grained workflow provenance. It also enables a number of novel graph transformation operations, allowing to choose the desired level of granularity in provenance querying (ZoomIn and ZoomOut), and supporting "what-if" workflow analytic queries. We implemented our approach in the Lipstick system and developed a benchmark in support of a systematic performance evaluation. Our results demonstrate the feasibility of tracking and querying fine-grained workflow provenance.
1. INTRODUCTION
The paper addresses the limits of black-box workflow provenance by combining database-style fine-grained dependencies with workflow module invocations and state. It introduces Pig Latin-based provenance, compact provenance graphs, graph transformations, and the Lipstick system to support richer workflow analysis.
- Motivation: Black-box provenance wrongly treats every output as depending on all module inputs and misses dependencies on internal state from previous executions.Fine-grained dependencies may involve only subsets of inputs, while learning or stateful modules can incorporate earlier inputs.
- Motivation: In the dealership workflow, coarse-grained provenance cannot identify which cars, sales histories, or previous bids affected a bid or sale.Consequently, questions about counterfactual car availability and the causes of winning bids remain unsupported.
- Approach: Pig Latin exposes module functionality for deriving fine-grained provenance, while opaque User Defined Functions retain coarse-grained provenance where functionality cannot be fully exposed.The framework supports collection-oriented processing while allowing complex functions to remain opaque.
- Approach: Pig Latin expressions can be translated into bag-semantics nested relational calculus, providing the foundation for provenance derivation.This translation is the paper’s first specific contribution.
- Provenance representation: A compact provenance graph represents fine-grained workflow provenance while capturing module invocations and module-state changes.The representation addresses the potentially prohibitive size of provenance from workflows with many modules and executions.
- Analysis and evaluation: ZoomIn, ZoomOut, and deletion propagation support mixed-granularity provenance views and what-if workflow queries.The Lipstick system implements provenance tracking and querying, and experiments show that fine-grained provenance tracking and querying is feasible.
2. PRELIMINARIES
This section introduces Pig Latin, the module and workflow model, and workflow execution over relational inputs, outputs, and mutable module state. Workflows are DAGs whose modules may be invoked repeatedly, with bounded looping representable by unfolding.
- Pig Latin: Pig Latin combines declarative querying with procedural programming and map-reduce-style parallelization over nested relations.The paper focuses on homogeneous nested relations and non-update constructs.
- Pig Latin: Pig Latin expressions without UDFs translate to bag-semantics nested relational calculus, forming the basis for provenance derivation.
- Modules: A module is specified by input, state, and output schemas plus Pig Latin queries that update state and produce outputs.Its state may affect later invocations.
- Workflows: A workflow is a connected DAG whose nodes name modules and whose edges pass compatible relations between module inputs and outputs.The same module may occur multiple times, and input nodes receive data externally.
- Execution: The formal treatment requires acyclic workflows, while bounded loops can be unfolded into acyclic ones.Recursive workflows are excluded because their semantics may not terminate.
- Execution: Workflow execution follows a topological order, applying each module’s state and output queries before copying produced relations along outgoing edges.
3. PROVENANCE FOR WORKFLOWS
The paper constructs workflow provenance graphs in coarse- and fine-grained forms. Fine-grained graphs expose module state and database-style computations while graph sharing preserves a compact representation integrated with workflow-level module invocations.
- Coarse-grained provenance: Coarse-grained provenance records module invocations, logical flow, and input-output relations, but hides state, operations, and data dependencies.
- Fine-grained provenance: The graph representation is more compact because shared graph parts can represent alternative tuple derivations and fit within the workflow provenance graph.
- Fine-grained provenance: Fine-grained provenance represents relational derivations and module state with provenance and value nodes connected by operation-labeled graph structure.State nodes capture tuples stored in a module’s state and their joint dependence on invocations.
- Fine-grained provenance: Pig Latin operations such as projection, join, and grouping generate provenance nodes that record which input or state tuples contribute to each result.The paper illustrates these constructions through the car-dealership workflow.
- Fine-grained provenance: The framework extends provenance generation to additional non-update Pig Latin operations, while treating ORDER as post-processing rather than graph structure.Updates are excluded from the presented treatment.
4. QUERYING PROVENANCE GRAPHS
The provenance graph supports querying at different granularities and analyzing hypothetical deletions. Zoom operations expose or hide module internals, while deletion propagation tests dependency relationships in the workflow graph.
- Zoom: ZoomIn and ZoomOut let analysts choose fine-grained provenance for some modules and coarse-grained provenance for others.
- Zoom: ZoomOut removes intermediate computations and state nodes for selected modules, replacing each invocation with a single module node.Because invocations may share state, all relevant invocations of a module must be zoomed out together.
- Zoom: ZoomIn is the inverse of ZoomOut, restoring the detailed graph for the selected modules.
- Deletion propagation: Deletion propagation recursively removes nodes whose derivations lose required inputs, modeling which downstream tuples depend on a deleted tuple.The resulting graph may not correspond to an actual workflow execution, so it serves analytical purposes.
- Deletion propagation: Dependency queries can test whether a node depends on another by checking whether it remains after propagating the latter’s deletion.The approach also extends to sets of nodes.
- Examples: In the dealership example, deleting car C2 does not remove the bid, whereas deleting request I1 removes the bid calculation.
5. EXPERIMENTS
Experiments show that Lipstick tracks fine-grained provenance with manageable execution overhead, feasible graph construction, and efficient provenance queries across workflow sizes and topologies.
- Experimental setup: Lipstick consists of Provenance Tracker and Query Processor, with experiments evaluating tracking overhead, graph construction, and query efficiency.WorkflowGen provides the benchmark workloads.
- Tracking overhead: Additional parallelism improves Car dealerships execution by about 50% with 2–4 reducers, both with and without provenance.Three reducers offer the reported trade-off sweet spot, while small differences between tracking conditions are insignificant.
- Results summary: Overall, provenance tracking overhead is manageable, graph construction is feasible across workflow sizes and topologies, and provenance graphs can be queried efficiently.Lipstick’s Pig Latin implementation also exploits Hadoop parallelism for larger-scale execution.
- Graph construction: For Car dealerships, provenance graph-building time is linear in graph size and remains below 8 sec, while graph nodes grow approximately linearly with workflow executions.Similar graph-building behavior was observed for Arctic stations.
- Graph construction: Lower selectivity increases provenance graph edges and construction cost; graph-building time varies little across topologies, shortest for serial and longest for dense workflows.The topology ordering is serial, parallel, then dense, with increasing fan-out.
- Graph construction: Fine-grained provenance reduces each Car dealerships sale’s dependencies to 1.8%–2.2% of state tuples and two input tuples, versus coarse-grained dependence on 100% and all 10,000 user inputs.The comparison uses 20,000 cars and 10,000 executions.
- Query processing: ZoomOut and subgraph queries scale approximately linearly, with ZoomOut under 2.02 sec and subgraph queries under 0.2 sec in the reported cases.Delete queries were usually below 1 ms and at most 10–13 ms per node; overall, most tested queries completed in under one second.
6. CONCLUSIONS
The paper presents a Pig Latin-based model for fine-grained workflow provenance and demonstrates that it supports practical analyses unavailable with coarse-grained provenance. The study establishes feasibility experimentally while leaving representation, query-language, and workflow-construct extensions for future work.
- The framework models fine-grained provenance for workflows whose modules are implemented in Pig Latin.
- It extends provenance modeling from individual Pig Latin queries to entire workflow executions.
- The approach answers practical workflow-analysis questions that standard coarse-grained provenance cannot answer.
- The evaluation demonstrates the feasibility of the fine-grained provenance model.
- Future work includes optimizing representations and query algorithms, extending the query language, and supporting fork and loop constructs.