## 3 Semantic Expression of Relational Data Provenance
### Representation of Provenance Data  
Where-prov is a copy contribution semantics describing the relationship between the inputs and outputs by defining propagation rules of attribute values on algebraic operations. To support full-featured SQL and procedural language queries, we extend the annotation propagation rules of [46] to group aggregation operation and formally define where-provenance on the filter, projection, join, union, and group aggregation operations (See Definition 1). Hereafter, we consider annotated relations and annotations propagating between _locations_ in the database. Assume that _location_ is denoted as triple \((R,t^{\prime},A)\), which carries a set of zero or more annotations. Figure 1: A sample database. Suppliers, parts, and projects are uniquely identified by supplier number (Sno), part number (Pno), and project number (Jno), respectively. The shipment relation stores the number of parts a supplier has supplied for a project, where the primary key is the combination of [Sno, Pno, Jno]. Selection. For \(t\in\sigma_{\theta}(R)\), an annotation on \((R,t^{\prime},A)\) propagates to \((\sigma_{\theta}(R),t,A)\) if \(t=t^{\prime}\). 2. Projection. For \(t\in\Pi_{U}(R)\), an annotation on \((R,t^{\prime},A)\) propagates to \((\Pi_{U}(R),t,U)\), where \(U\subseteq A\) and \(t=t^{\prime}[U]\). 3. Join. For \(t\in R_{1}\infty R_{2}\), annotations on \((R_{1},t_{1},A)\) and/or \((R_{2},t_{2},A)\) propagate to \((R_{1}\infty R_{2},t,A)\), where \(t[U_{1}]=t_{1}\) and \(t[U_{2}]=t_{2}\), \(U_{1}\) and \(U_{2}\) are the attributes of \(R_{1}\) and \(R_{2}\), respectively. 4. Union. For \(t\in R_{1}\cup R_{2}\), annotations on \((R_{1},t_{1},A)\) and/or \((R_{2},t_{2},A)\) propagate to \((R_{1}\cup R_{2},t,A)\) where \(t=t_{1}\) or \(t=t_{2}\). 5. Group Aggregation. For \(t\in\alpha_{B,C}(R)\), annotations on \((R,t_{1},B)\) or \((R,t_{2},C)\) propagate to \((\alpha_{B,C}(R),t,BC)\) if \(t[B]=e(t_{1}[B])\) (or \(t[C]=aggr(t_{2}[C])\)), where \(e\) and \(aggr\) denote a calculation expression and an aggregation function, respectively. The above rules indicate that the annotation propagation is based on the copy behavior. If the context is clear, the triple \((R,t,A)\) can be simplified to \((R,t[A])\). Definition 1 (Where-prov): Consider a database instance I, \(Q\) is a query on I, and \(t\in Q(I)\). Where-provenance is the value of \(t\) on field \(A\) according to \(Q\) and \(I\), denoted as \(\mathit{Where}(Q,t[A])\), and is defined as follows:  
1. [label=0., ref=0]
2. Direct copy. Where\((\{t\},t[A])=\{t[A]\}\)
3. Selection. Where\((\sigma_{\theta}(Q),t[A])=\mathit{Where}\{Q,t[A]\}\)
4. Projection. Where\((\Pi_{B}(Q),t[A])=\cup\mathit{Where}(Q,u[B^{\prime}]),u\in Q_{1}(I),A=B\in Q_{1}\)
5. Union. Where\((Q_{1}\cup Q_{2},t[A])= \begin{cases}\mathit{Where}(Q_{1},u[A]),u\in Q_{1}(I)-Q_{ 2}(I)\\ \mathit{Where}(Q_{2},v[A]),v\in Q_{2}(I)-Q_{1}(I)\\ \mathit{Where}(Q_{2},u[A])\cup\mathit{Where}(Q_{2},v[A]),\\ \mathit{u}=v\in Q_{2}(I)\cap\Omega_{1}(I)\end{cases} \)
6. Group Aggregation. \[\mathit{Where}(\alpha_{B,C}(Q),t[A])= \begin{cases}\cup\mathit{Where}(Q,u[B^{ \prime}]),B^{\prime}\subseteq B,t[B^{\prime}]=e(u[B^{\prime}])\\ \cup\mathit{Where}(Q,u[C^{\prime}]),C^{\prime}\subseteq C,t[C^{\prime}]=aggr \big{(}G[C^{\prime}]^{*}\big{)},u\in G\subseteq Q\end{cases} \]  
Definition 1 shows that the lineage of values propagates and outputs under the rules, making a copy semantic contribution to the final output value. Example 1: Consider a query finding all identifier numbers of suppliers and projects located in the same city.