Abstract

In this thesis, we study the provenance of querying graph databases. Compared to using the semiring of polynomials as the most general form of provenance for relational databases (Green, Karvounarakis, & Tannen, 2007), we show that the most general provenance for querying graph databases can be represented by regular expressions over paths in the database. In this work we focus on the single-source provenance, which is a more general representation and contains more information than the single-source, single-target problem considered in (Ramusat, Maniu, & Senellart, 2018). We present an algorithm that computes single-source multidimensional provenances for graph databases, where each dimension represents an application provenance semiring, and also propose a potential application, by using parse tree techniques and deriving results for various application provenances.