Polynomials for Multidimensional Provenance in Graph Databases
Date & Time:
September 17th, 2021 @ 1:00 PM
Location:
Zoom
Examining Committee:
Dr. Joey Paquet
(Chair)
Dr. Nematollaah Shiri
(Supervisor)
Dr. Gregory Butler
(Examiner)
Dr. Joey Paquet
(Examiner)
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, 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 the existing research. We present an algorithm that computes single-source provenances for graph databases, and also propose a potential application, by using parse tree techniques and deriving results for various application provenance.