Provenance tracking for database aggregation queries in semirings with monus
Provenance of HAVING Queries in Semirings with Monus
Databases
Summary
Tracking how database query results come about is important in many applications. When queries use counting and conditions on these counts (called HAVING queries), existing methods become complicated and leave the usual mathematical framework. This paper shows how to handle these queries within a familiar algebraic structure called semirings with monus, simplifying the approach. The authors also present algorithms and demonstrate that their approach works efficiently on real data.
What this means in practice
- •For database engineers: Integrate improved provenance tracking for aggregation queries with conditions into database systems for better query debugging and auditing.
- •For probabilistic data analysts: Evaluate probabilistic queries involving aggregations using the proposed semantics to obtain accurate confidence computations.
Authors
Aryak Sen, Pratik Karmakar, Silviu Maniu, Angelo Saadeh, Pierre Senellart
Abstract
The semiring framework and its extensions form the basis of a rich collection of theoretical results and implementations for provenance tracking of database queries. Many real-world queries use aggregation and conditions on the aggregate values. Support for such queries has been proposed by introducing semimodule elements as aggregate values and formal comparisons between aggregate values as tuple annotations, which takes the approach outside the standard semiring framework. In this work, we show how to introduce a semantics for the provenance of such queries in arbitrary commutative semirings with monus (or m-semirings), without the need for additional operators. This semantics is shown to agree with the standard provenance of the aggregation-free self-join rewriting of HAVING COUNT(*) queries in semirings that are absorptive and where times distributes over monus. We derive algorithms for this semantics and implement them within the ProvSQL system, with viable performance on a real-world dataset for probabilistic query evaluation.