A Generic Provenance Middleware for Database Queries, Updates, and Transactions

Abstract

We present an architecture and prototype implementation for a generic provenance database middleware (GProM) that is based on the concept of query rewrites, which are applied to an algebraic graph representation of database operations. The system supports a wide range of provenance types and representations for queries, updates, transactions, and operations spanning multiple transac-tions. GProM supports several strategies for provenance genera-tion, e.g., on-demand, rule-based, and “always on”. To the best of our knowledge, we are the first to present a solution for comput-ing the provenance of concurrent database transactions. Our solu-tion can retroactively trace transaction provenance as long as an audit log and time travel functionality are available (both are sup-ported by most DBMS). Other noteworthy features of GProM in-clude: extensibility through a declarative rewrite rule specification language, support for multiple database backends, and an optimizer for rewritten queries.