## 3 Semantic Expression of Relational Data Provenance
### Representation of Provenance Transformation
#### 3.4.1 Tuple and Value Provenance Transformation
Namely, \(OUnion\) must be used as a subexpression in the expression of \(OAggr\). Otherwise, \(OUnion\) has no meaning in the transformation expression, and we can replace it with either \(expr<Pet(Q_{1},t)>\) or \(expr<Pet(Q_{2},t)>\) or both. Value can be regarded as a tuple with only one field, so the value-level provenance transformation can be derived from the tuple-level provenance transformation. In this paper, we refer to this derivative version as VPET (Value PET). Similar to PET, the expression of VPET is also formed based on meta-transformation. In the context of VPET, the granularity of the data unit is a value rather than a tuple, which is the exact difference between VPET and PET. **Definition 7**. : \(VPET(Q,t[A])\)_. The value provenance transformation of tuple \(t\) on field \(A\):_  
1. \(VPET(\{t\},t[A])=expr<A>,A\subseteq\textbf{R}\)__
2. \(VPET(ONull(Q),t[A])=expr<VPET(Q,t[A])>\)__
3. Given \(t[A]=e(u[B]),u\subseteq Q(I)\), we have_  
\[VPET(OProj(Q),t[A])=\left\{ \begin{matrix}expr<VPET(Q,u[B])>,if\ expr<e(u[B])> =expr<B>\\ expr<OProj(VPET(Q,u[B]))>,else\end{matrix} \right.\]
4. _Given B and C are group and aggregation fields, \(B^{\prime}\subseteq B\), \(C^{\prime}\subseteq C\), \(\forall u\in G\subseteq Q(I)\), \(g=e(u[B])\), we have_  
\[VPET(OAggr(Q),t[A])=\left\{\begin{matrix}expr<OAggr(VPET(Q,u[C^{\prime}]))>,if\ t[A]=aggr\big{(}G[C^{\prime}]^{*}\big{)}\\ expr<VPET(Q,u[B^{\prime}])>,if\ t[A]=e(u[B^{\prime}])\), \ expr<u[B^{\prime}]>\ expr<B^{\prime}>\\ expr<OProj(VPET(Q,u[B^{\prime}]))>,t[A]=e(u[B^{\prime}])\)_, else_
5. _Given B and C are group and aggregation fields, \(B^{\prime}\subseteq B\), \(C^{\prime}\subseteq C\), \(\forall s\in G\subseteq Q_{1}(I)\cup Q_{2}(I),g=(s[B])\), we have_  
\[VPET(OAggr(OUUnion(Q_{1},Q_{2})),t[A])\]  
\[=\left\{ \begin{matrix}expr<OAggr(VPET(OUUnion(Q_{1},Q_{2}),s[C^{\prime}]))>,if\ t[A]=aggr\big{(}G[C^{\prime}]^{*}\big{)}\\ expr<VPET(Q_{1},s[B^{\prime}])>,if\ t[A]=e(s[B^{\prime}])\), \(s\in Q_{1}(I),expr<e(s[B^{\prime}])>\ expr<B^{\prime}>\\ expr<OProj(VPET(Q,s[B^{\prime}]))>,t[A]=e(s[B^{\prime}]),s\in Q_{i}(I),i=1,2 \end{matrix} \right.\]
6. \(VPET(OJoin(Q_{1},Q_{2}),t[A])=\left\{ \begin{matrix}expr<VPET(Q_{1},u[B])>,t[A ]=u[B]\\ expr<VPET(Q_{2},v[C])>,t[A]=v[C]\end{matrix} \right.\)  
In Definition 7, for group and aggregation operation \(OAggr\), if \(t[A]\) only originates from the group fields, we can infer that the aggregation function contributes nothing to the result. In other words, the transformation of values is not the result of \(OAggr\) operation. **Example 2**. : _Consider a query \(Q_{2}\) computing the total price after discount for each project (assuming the excess parts can enjoy 20% off when the number of parts exceeds 200)._  
As shown in Figure 3, the tuple-level where-prov of the tuple \(k_{1}\) is \(\{h_{1},h_{2},p_{1},p_{2}\}\). Suppose \(Q_{2}^{\prime}\) is the CTE recursive subquery for \(Q_{2}\). The provenance transformations for all output tuples of \(Q_{2}^{\prime}\) are \(OProj(\mathit{Shipment})\) and \(OProj(\mathit{OProj}(\mathit{Shipment}))^{*}\). According to Definitions 6 and 7, the provenance transformation of \(k_{2}\) is \(PET(Q_{2},k_{2})\)\(=OJoin(OProj(\mathit{Shipment}),OAggr(OProj(OJoin(OProj(\mathit{Parts}),OUnion(OProj(\mathit{Shipment})),OProj(\mathit{OProj}(\mathit{Shipment})))^{*})))))))))))))))))))))) ))))))))}}\) \) \