## 2 Data Provenance
### Why-Provenance  
The set of source tuples contributing to the result tuples is its why-provenance. Different versions of the why-provenance are due to different definitions of \"contributing\". The source tuples sufficient to produce the result tuple are defined by the simplest one. Here, a result tuple is the set of tuples that make up the query results. In addition, the simplest refers to the minimum principle, which is the minimal set of tuples that can produce a result tuple. Many source tuples have no correlation with the presence of result tuples, resulting in a large number of such subsets.  
The authors of [12] tried to filter the \"irrelevant\" source tuples to avoid this problem. They [12] considered each source tuple that contributed to a result tuple, and such a maximum set of source  
\begin{table}
\begin{tabular}{l l l} \hline \hline
**ID** & **Name** & **Course No.** \\ \hline t1 & [PERSON] & 00602001 \\ t2 & [PERSON] & 03310117 \\ t3 & [PERSON] & 04110235 \\ t4 & [PERSON] & 05110208 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Relation \(R\).  
\begin{table}
\begin{tabular}{l l l} \hline \hline
**Name** & **Why-Provenance**[12] & **Minimal Why-Provenance**[11] \\ \hline [PERSON] & \(\{t_{1},t_{5},t_{6}\}\) & \(\{[t_{1},t_{5}],[t_{1},t_{6}]\}\) \\ [PERSON] & \(\{t_{2},t_{4},t_{7},t_{8}\}\) & \(\{[t_{2},t_{7}],[t_{4},t_{8}]\}\) \\ \hline
**Name** & **How-Provenance**[13] & **Where-Provenance**[11] \\ \hline [PERSON] & \(t_{1}.t_{5}+t_{1}.t_{6}\) & \(\{t_{1}.Name\}\) \\ [PERSON] & \(t_{2}.t_{7}+t_{4}.t_{8}\) & \(\{t_{2}.Name\},\{t_{4}.Name\}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Provenances of each result tuple in Example 1.  
tuples is the why-provenance. However, the why-provenance computed by [12] will cause an issue, namely it will contain unnecessary base tuples.  
Due to the why-provenance containing unnecessary source tuples, on the basis of a deterministic semi-structured data model and query language, the concept of why-provenance was defined in [11]. The definitions in [11] were adapted to the relational model and relational algebra by the authors of [15] (as shown below).  
**Definition 1**.: _Let \(I\) represent a database instance, \(Q\) represent a select-project-join-union query, and represent a result tuple in \(Q(I)\). In accordance with \(Q\) and \(I\), \(Why(Q,I,t)\) denotes the set of why-provenances of \(t\). Its definition is shown below:_  
* \(Why(\sigma_{\theta}(Q),I,t)=Why(Q,I,t),if\)__\(\theta(t)\)_._
* \(Why(\tau_{U}(Q),I,t)=\bigcup\{Why(Q,I,u)\mid u\in Q(I),t=u[U]\}\)_._
* \(Why(Q_{1}\bowtie Q_{2},I,t)=Why(Q_{1},I,t[U_{1}])\sqcup Why(Q_{2},I,t[U_{2}])\)_._
* \(Why(Q_{1}\bigcup Q_{2},I,t)=Why(Q_{1},I,t)\bigcup Why(Q_{2},I,t)\)_._  
Here, selections \(\sigma_{\theta}\) filter a relation by retaining tuples satisfying some predicate \(\theta\). Projections \(\pi_{U}(Q)\) replace each tuple \(t\) in a relation with \(t[U]\), discarding any other fields. Join (or natural join) \(Q_{1}\bowtie Q_{2}\) indicates a natural join between \(Q_{1}\) and \(Q_{2}\). Union \(Q_{1}\bigcup Q_{2}\) represents the union of \(Q_{1}\) and \(Q_{2}\). \(\sqcup\) takes all the pairwise unions of two collections. That is, \(A\sqcup B=\{a\bigcup b|a\in A,b\in B\}\).  
Minimal why-provenance means that the subset of results produced is minimal. Thus, in some cases, there may exist several minimal why-provenances. There are two minimal why-provenances of \(\langle John\rangle\): \(\{t_{1},t_{5}\}\) and \(\{t_{1},t_{6}\}\) in Table 3. Because \(\{t_{1},t_{6}\}\) generates \(\langle John\rangle\) and none of its proper subsets can generate \(\langle John\rangle\), it is a minimal why-provenance of \(\langle John\rangle\).