Providing flexible tradeoff for provenance tracking

The description of the origins of a piece of data and the transformations by which it arrived in a database is called data provenance, lineage or pedigree. The two major approaches to represent provenance information use annotations and inversion. Annotations are flexible in representing diverse provenance metadata but the complete provenance data may outsize the data itself. The inversion method is concise by using a single inverse query or function but the provenance needs to be computed on-the-fly which can be expensive. This paper proposes a new approach of provenance storage which combines the two methods and is adaptive to storage constraint