## 3 Semantic Expression of Relational Data Provenance
### Representation of Provenance Transformation
#### 3.4.1 Tuple and Value Provenance Transformation  
Tuples are operating objects in computing the provenance transformation of tuples. Modern DBMS provides a variety of powerful function operations for complex queries. Essentially, such operations can be converted to operations on two-dimensional tables. Our purpose is to eliminate the influence of sophisticated features of query language and, more  
Figure 2: The query \(Q_{1}\) and its output. importantly, to support data provenance for any SQL-like and procedural language with a control structure. Hence, we utilize and standardize five basic operations to construct transformation expressions. We call them meta-transformation, including null transformation (ONull), projection transformation (OProj), group aggregation transformation (OAggr), join transformation (OJoin), and union transformation (OUnion). It is worth noting that these transformations are mainly relational algebraic operations, so it is easy to express SQL-like languages. **Definition 5**. : _Copy-based meta-transformations:_  
1. Null transformation \(ONull\), \(ONull(Q)=Q\). 2. Projection transformation \(OProj\), \(OProj(Q)=Q^{\prime},Q^{\prime}(I)=\{t|t=u[\varepsilon(A)],\;u\in Q(I),\;A\in Q\}\). 3. Group aggregation transformation \(OAggr\), \(OAggr(Q)=Q^{\prime}\), \(Q^{\prime}(I)=\{t|t=g\oplus aggr\;(G[\mathcal{C}]^{*}),G\in Q(I),\forall u\subseteq G,g=e(u[B])\}\)
4. Join transformation \(OJoin,OJoin(Q_{1},Q_{2})=Q^{\prime},Q^{\prime}(I)=\{t|t=u[A]\oplus v[B],u\in Q _{1}(I),\;v\in Q_{2}(I),A\subseteq Q_{1},B\subseteq Q_{2}\}\)
5. Union transformation \(OUnion,OUnion(Q_{1},Q_{2})=Q^{\prime},Q^{\prime}(I)=Q_{1}(I)\cup Q_{2}(I)\}\)  
In the above meta transformations, the Null transformation operation, including the direct copy in Definition 1, filter operations, and other database operations not involving copy transformation do not modify the input tuples, so the input is the output. The projection transformation retains tuples in the specified fields. The group aggregation transformation divides input tuples into groups by specific attribute values, aggregates each group with specified attributes, and outputs the results, where each input group corresponds to an output tuple. The join transformation discovers matched tuples meeting the join condition, and the union transformation merges two input sets into an output. Both join and union operations are binary operations and extendable to multivariate operations. The tuple provenance transformation PET combines the above basic operations to express the provenance transformation process and complex SQL operations in the database. Using the above meta transformations, we define PET as follows. **Definition 6**. : \(PET(Q,t)\)_, provenance transformation of tuple \(t\):_  
1. \(PET(\{t\},t)=expr<R>,where\{t\}\subseteq R\)
2. \(PET(ONull(Q),t)=expr<PET(Q,t)>\)
3. \(PET(OProj(Q),t)=expr<OProj(PET(Q,u))>\)
4. \(PET(OAggr(Q),t)=expr<OAggr(PET(Q,u))>\)
5. \(PET(OJoin(Q_{1},Q_{2}),t)=expr<OJoin(PET(Q_{1},u),PET(Q_{2},v))\)
6. \(PET(OUnion(Q_{1},Q_{2}),t)=\left\{ \begin{array}{l}expr<PET(Q_{1},t)>where \;t\in Q_{1}(I)-Q_{2}(I)\\ expr<PET(Q_{2},t)>where\;t\in Q_{2}(I)-Q_{1}(I)\\ expr<PET(Q_{1},t)>or\;expr<PET(Q_{2},t)>,else\\ \end{array} \right.\)
7. \(PET(OAggr(OUnion(Q_{1},Q_{2})),t)=expr<OAggr(OUnion(PET(Q_{1},u),PET(Q_{2}, v)))>\)  
In Definition 6, \(expr<tf>\) is an expression for the transformation instead of transformation operation \(tf\) itself. Take \(Q_{1}\) as an example. For \(\forall u\subseteq Q_{1}\), the provenance transformation of tuple \(u\) can be expressed as \(OJoin(Supplies,Projects)\), namely, \(Pet(Q_{1},u)=OJoin(Supplies,Projects)\). It is worth pointing out that in the above transformations, only the \(OAggr\) transformation can aggregate multiple tuples into one tuple. In this case, an output tuple may simultaneously derive from both \(Q_{1}\) and \(Q_{2}\). Therefore, in the process of transforming queries, the output of \(OUnion\) must be used as the input of \(OAggr\).