Database Theory in Action: Making Provenance and Probabilistic Database Theory Work in Practice

A notable and fruitful form of provenance framework is that of provenance semirings [16]. A semiring is an algebraic structure formed of a set $𝕂$ with two binary operations ($\oplus$ and $\otimes$) and two distinguished elements ($\mathrm{𝟘}$ and $\mathrm{𝟙}$), such that: $\oplus$ is commutative and associative; $\otimes$ is associative; $\otimes$ distributes over $\oplus$; $\mathrm{𝟘}$ is neutral for $\oplus$ and annihilator for $\otimes$; and $\mathrm{𝟙}$ is neutral for $\otimes$. Many common algebraic structures are semirings, such as:

1. 1.

   the set $\mathbb{N}$ of natural numbers with the usual addition and multiplication;

2. 2.

   the tropical semiring consisting of ${ℝ}^{+}\cup \{+\mathrm{\infty }\}$ with minimum as $\oplus$ and addition as $\otimes$;

3. 3.

   the set $ℬ[X]$ of Boolean functions over a finite set $X$ of propositional variables with Boolean $\vee$ and $\wedge$ operations;

4. 4.

   the set $\mathbb{N}[X]$ of polynomials over a finite set $X$ of variables with natural integer coefficients, with the usual polynomial addition and multiplication.

For the relational model, [16] defines $𝕂$-relations for a given $𝕂$ semiring by associating every tuple of a relation with an element of $𝕂$. They show that one can define a semantics for the operators of the positive relational algebra over $𝕂$-relations such that:

• $\mathrm{■}$

  semiring homomorphisms commute with this provenance semantics;

• $\mathrm{■}$

  the provenance semantics for $ℬ[X]$ coincides with a natural semantics for Boolean provenance where the provenance of a tuple in the query output is a Boolean function that evaluates to true if the query produces this tuple when run over the subdatabase where all tuples whose provenance evaluates to false are removed.

Furthermore, $\mathbb{N}[X]$ is a universal semiring for provenance: there exists a unique homomorphism from $\mathbb{N}[X]$ to any semiring $K$ extending a given function from $X$ to $K$.

Provenance semirings have been extended in various ways, notably by adding a monus $\ominus$ operator that captures the semantics of the full relational algebra [15]; and by combining semiring annotations with aggregation monoid values through a semimodule construction [6] to provide a provenance semantics for aggregate queries.

The framework of $𝕂$-relations (extended to semirings with monus for the whole relational algebra, and to semimodule provenance for aggregate queries) can be readily implemented in a provenance-aware system by adding an extra column to all relations. Before the user query is sent to the planner, it is rewritten to ensure that the provenance semantics is applied to this extra column. ProvSQL exploits the fact that semiring homomorphisms commute with the provenance semantics to store all provenance annotations in the universal semiring, which means provenance computations can be done only once, without having to choose the application semiring at query time. For efficiency, it is very important to store provenance annotations in a compact form. We use provenance circuits, as in [14], to avoid duplicating parts of provenance expressions. Unique identifiers are automatically generated for all gates of the circuits, and these identifiers are stored in the extra provenance column. The circuit itself is stored in memory-mapped files accessed by the database management system. As a result of this architecture, provenance computation adds a very reasonable overhead (a small constant factor, in our experiments) to query evaluation.

The semiring operators $\oplus$ and $\otimes$ cas be thought of as specific instances of the operations required to answer any source-to-target query in graphs: the query result is the aggregation over all possible paths. Our findings in [24, 25] demonstrate that semiring provenance can effectively handle this. Formally, in a graph $G=(V,E)$, where each edge $e_i\in E$ has a weight $w[e_i]$ – represented as an element of a semiring – the provenance of a source-to-target query is the (potentially infinite) sum over the set of all paths between $x$ and $y$ in $G$, $P_{xy}(G)$: ${\mathrm{𝗉𝗋𝗈𝗏}}_{𝕂}(G)(x,y):=w\left[P_{xy}(G)\right]={⨁}_{\pi \in P_{xy}(G)}w[\pi ]={⨁}_{\pi \in P_{xy}(G)}{⨂}_{e_i\in \pi }w[e_i].$

The semantics of the sum varies based on the chosen semiring. In the tropical semiring, it corresponds to the shortest distance between nodes $x$ and $y$ in $G$. In $\mathbb{N}$, it denotes the number of paths between $x$ and $y$. In $ℬ[X]$, it indicates whether $y$ is reachable from $x$, based on the truth values assigned to the edges.

The choice of provenance semiring influences the computational complexity of provenance algorithms. For semirings where cycles in the graph do not affect the sum (known as $0$-closed semirings, such as the tropical semiring) and that define a total order, the provenance can be computed in quasi-linear time using an analogous of Dijkstra’s algorithm. For semirings where the sum is finite, a node elimination algorithm can be used, having a cubic worst-case time complexity. Such algorithms enable efficient practical provenance computation beyond SQL queries.

Probabilistic databases are compact representations of a probability distribution over a set of possible databases. In principle, distributions can be finite, continuous [1], or discrete but infinite [7, 18]. Correlations across data items (tuples in the relational setting) may be disallowed (as in the tuple independent, TID, setting [12]), limited (e.g., block independent databases, BIDs [11]) or fully arbitrary (as in probabilistic c-tables [17]). The main problem studied over probabilistic databases is probabilistic query evaluation: computing the (marginal) probability of a tuple in the output of the query; or, when aggregate queries are involved, computing the distribution of data values in the output, or summaries thereof.

Unfortunately, even in a very simple relational setting where distributions are finite and there are no correlations across tuples, probabilistic query evaluation is $\mathrm{\#}𝖯$-hard, even for simple conjunctive queries. It becomes tractable when:

• $\mathrm{■}$

  its $ℬ[X]$ provenance is in some tractable form (read-once, deterministic and decomposable circuits, etc.) [20] – it is easy to see that the probability of a query output is the probability of its $ℬ[X]$ provenance, when variables in $𝒳$ are assigned the probabilities of input tuples;

• $\mathrm{■}$

  the query is a safe UCQ [13] over TIDs (with a fairly complex algorithm to recognize safety);

• $\mathrm{■}$

  the query is a safe CQ without self-joins [11] over BIDs;

• $\mathrm{■}$

  the data has bounded treewidth over BIDs [4], for any MSO query;

• $\mathrm{■}$

  the data and correlations have joint bounded treewidth [3], for any MSO query.

ProvSQL allows representation of finite probability distributions with arbitrary correlations. Probabilistic query evaluation relies on: first, computing its provenance; second, applying a semiring homomorphism to turn this provenance into a $ℬ[X]$-provenance circuit; third, computing the probability of this circuit. This approach, sometimes called the intensional approach [30] to probabilistic query evaluation, does not permit exploiting specific algorithms for specific query types (in particular, safe queries). However, it decouples the hard problem of probability computation from the query evaluation problem.

To compute the probability of a Boolean circuit, ProvSQL relies on a combination of techniques:

• $\mathrm{■}$

  if the circuit happens to be read-once, the probability is easily computed;

• $\mathrm{■}$

  if the circuit has low treewidth, we use an algorithm from [5] to extract a deterministic and decomposable circuit, on which the probability is easily computed;

• $\mathrm{■}$

  otherwise, we use an external knowledge compiler [21] that turns the circuit into a tractable class.

Knowledge compilers are specialized tools that incorporate many heuristics, similarly to SAT solvers. As the Boolean circuits are not arbitrary, they manage to produce tractable small circuits in many cases. Though ProvSQL cannot guarantee efficiency of probabilistic query evaluation, our tests reveal that our approach works in practice for many queries and scale to databases of several GBs. In addition, we also allow standard Monte-Carlo sampling methods for probabilistic query evaluation, for cases where exact computation is not critical.

A potential avenue for tractable probabilistic query evaluation is to exploit the shape of data. As previously mentioned, this is the case when the data (and correlations) has low treewidth, i.e., if it is structurally close to a tree.

Requiring a graph – or a graph representation of a database – to have bounded treewidth is a strong assumption. Our experimental results in [23] bring evidence that real-world graphs typically have high treewidth, with the possible exception of graphs representing physical networks, such as roads and power grids. However, practical efficiency is possible via partial decompositions. In our ProbTree work [22], we introduce algorithms decomposing only the low-treewidth portion of the graph. This can significantly speed up probability computations. Extending this partial decomposition approach to general provenance computation is an area for future research.