ABSTRACT. We generalize three existing graph algorithms to compute the provenance of regular path queries over graph databases, in the framework of provenance semirings – algebraic structures that can capture different forms of provenance. Each algorithm yields a different trade-off between time complexity and generality, as each requires different properties over the semiring. Together, these algorithms cover a large class of semirings used for provenance (top-k, security, etc.). Experimental results suggest these approaches are complementary and practical for various kinds of provenance indications, even on a relatively large transport network.

ABSTRACT. SQL emphasizes the *What*, the declarative specification of complex computations over a database. *How* exactly the individual parts of an intricate query interact and contribute to the result, often remains in the dark, however. How-provenance helps to understand queries and build trust in their results. We propose a new approach that derives how-provenance for SQL at a fine granularity: (1) every single piece of the result provides information on how exactly it did get there, and (2) the contribution of any query construct to the overall output can be assessed—from entire subqueries down to the subexpression leaf level. The method applies to real-world dialects of SQL and, more generally, to the modern breed of database systems that pursue a compilation-based approach to query processing.