Ariadne: Managing fine-grained provenance on data streams

Managing fine-grained provenance is a critical requirement for data stream management systems (DSMS) to be able to address complex applications that require diagnostic capabilities and assurance as well as serving as a supporting technology for other tasks such as revision processing. In this paper, based on an example use case, we motivate the need for fine-grained provenance in stream processing and analyze its requirements. Inspired by these requirements, we investigate different techniques to generate and retrieve stream provenance, and propose a new technique that is based on operator in-strumentation. Ariadne, our provenance-aware DSMS implements this technique on top of the Borealis system. We propose new optimization techniques to reduce the computational overhead of provenance generation and retrieval. Our experiments confirm that by applying these optimizations, Ariadne can provide fine-grained provenance with acceptable overhead.