Efficient Stream Provenance via Operator Instrumentation
Authors
Boris Glavic, Kyumars Sheykh Esmaili, Peter M. Fischer, Nesime Tatbul
Abstract
Managing fine-grained provenance is a critical requirement for data stream management systems (DSMS), not only to address complex applications that require diagnostic capabilities and assurance, but also for providing advanced functionality such as revision processing or query debugging. This paper introduces a novel approach that uses operator instrumentation, i.e., modifying the behavior of operators, to generate and propagate fine-grained provenance through several operators of a query network. In addition to applying this technique to compute provenance eagerly during query execution, we also study how to decouple provenance computation from query processing to reduce run-time overhead and avoid unnecessary provenance retrieval. Our proposals include computing a concise superset of the provenance (to allow lazily replaying a query and reconstruct its provenance) as well as lazy retrieval (to avoid unnecessary reconstruction of provenance). We develop stream-specific compression methods to reduce the computational and storage overhead of provenance generation and retrieval. Ariadne, our provenance-aware extension of the Borealis DSMS implements these techniques. Our experiments confirm that Ariadne manages provenance with minor overhead and clearly outperforms query rewrite, the current state-of-the-art.
Links
Reference
Efficient Stream Provenance via Operator Instrumentation (Boris Glavic, Kyumars Sheykh Esmaili, Peter M. Fischer, Nesime Tatbul), In Transactions on Internet Technology (TOIT), volume 13, 2014.
Bibtex Entry
@article{GE14,
	Abstract = {Managing fine-grained provenance is a critical requirement for data stream management systems (DSMS), not only to address complex applications that require diagnostic capabilities and assurance, but also for providing advanced functionality such as revision processing or query debugging. This paper introduces a novel approach that uses operator instrumentation, i.e., modifying the behavior of operators, to generate and propagate fine-grained provenance through several operators of a query network. In addition to applying this technique to compute provenance eagerly during query execution, we also study how to decouple provenance computation from query processing to reduce run-time overhead and avoid unnecessary provenance retrieval. Our proposals include computing a concise superset of the provenance (to allow lazily replaying a query and reconstruct its provenance) as well as lazy retrieval (to avoid unnecessary reconstruction of provenance). We develop stream-specific compression methods to reduce the computational and storage overhead of provenance generation and retrieval. Ariadne, our provenance-aware extension of the Borealis DSMS implements these techniques. Our experiments confirm that Ariadne manages provenance with minor overhead and clearly outperforms query rewrite, the current state-of-the-art.},
	Author = {Boris Glavic and Kyumars Sheykh Esmaili and Peter M. Fischer and Nesime Tatbul},
	Date-Added = {2014-05-11 17:49:19 +0000},
	Date-Modified = {2014-05-11 17:55:40 +0000},
	Journal = {Transactions on Internet Technology (TOIT)},
	Keywords = {Ariadne; Provenance},
	Number = {1},
	Pages = {7:1-7:26},
	Title = {Efficient Stream Provenance via Operator Instrumentation},
	Url = {http://cs.iit.edu/%7edbgroup/pdfpubls/GE14.pdf},
	Venueshort = {TOIT},
	Volume = {13},
	Year = {2014},
	Bdsk-Url-1 = {http://cs.iit.edu/%7edbgroup/pdfpubls/GE14.pdf}}
Powered by bibtexbrowser