## 3 Semantic Expression of Relational Data Provenance
### Terminology and Symbols  
In order to facilitate the definition of methods and models, we introduce symbols and the relational algebra used in the subsequent sections.  
Let \(\varpi\) be a collection of field names (or attribute names) \(\{A_{1},\ldots,A_{n}\}\), \(U\) and \(V\) are finite subsets of \(\varpi\), \(D_{i}(i=1,2,\ldots,n)\) is a finite domain of attribute \(A_{i}\). A record (or tuple) \(t,t_{1},t_{2},t^{\prime},u,\ldots\) is a function \(U\to\{D_{1},\ldots,D_{n}\}\), written as \((A_{1}:D_{1},\ldots,A_{n}:D_{n})\). Then, \(t\cdot A\) is the value of field \(A\), and \(t[U]\) restricts the tuple \(t\) to fields set \(U\).  
A relation or table \(r:U\) is a finite set of tuples over \(U\). Let \(\Re\) be a finite collection of relation names \(\{R_{1},\ldots,R_{n}\}\). A schema \(R\) is a mapping \((R_{1}:U_{1},\ldots,R_{n}:U_{n})\) from \(\Re\) to finite subsets of \(\varpi\). A database (or instance) \(I:(R_{1}:U_{1},\ldots,R_{n}:U_{n})\) is a function mapping each \(R_{i}:U_{i}\in R\) to a relation \(r_{i}\) over \(U_{i}\). For relation table \(r_{i}\) and attribute set \(A,B,C,\in U_{i}\), \(t[A]\) is the value of tuple \(t\) (\(t\subseteq r_{i}\)) on field set \(A\) and \(r_{i}[A]=\{t[A]|t\subseteq r_{i}\}\).  
We also define _tuple locations_ as tuples tagged with relation names, written as (\(R\), \(t\)). Similarly, field locations are written as a triple (\(R\), \(t\), \(A\)). If the context is clear, the triple (\(R\), \(t\), \(A\)) is simplified to \((R,t[A])\). Moreover, \(t=u\oplus v\) denotes the concatenation of tuple \(u\) and \(v\), and the result is tuple \(t\).  
Constant data involved in SQL, including constants, constant tuples, such as VALUES (101, 'abc'), or data in external text files, are uniformly replaced by the notation \(\bot\) to minimize the impact of the tedious constant data on the discussion. For instance, \"\(A+func(B,\bot)-\bot\)\" is a simplification of \"\(A+func(B,1)-2\)\".  
We use the expression \(Q(I)\) as a query for a database instance \(I\) and for any output tuple \(t,t\in Q(I)\). \(R(I)\) is a relational table in the instance \(I\). Particularly, a query is written as \(Q\) in the context where the instance \(I\) is clear. In query \(Q=\)\(<q,R>\)\(R=\{R_{1},\ldots,R_{n}\}\), \(q\) is the language structure that corresponds to SQL, stored procedural language, and other data processing script languages. \(R_{i}\) is the relational table name involved in the query \(Q\). In particular, \(R_{i}(I)\) only references the relational table \(R_{i}\).  
We use the following notation for (monotone) relational algebra queries:  
\[Q::=\{t\}|\sigma_{\theta}(Q)|\tau_{U}(Q)|Q_{1}\infty Q_{2}|Q_{1}\cup Q_{2}|\alpha _{A,B}(Q)\]  
Here, \(\{t\}\) is a set of constant tuples, and the following symbols denote selection, projections, join (or natural join), union, and group and aggregation operation, respectively. The group and aggregation operation is represented as \(\alpha_{A,B}(Q)=g\oplus aggr(G[B]^{*})\), where \(\mathrm{g}=e(A)\) (\(A\in G\)), \(e\) is an expression parameterized by the grouping filed \(A\), \(g\) is the set of the output tuples, and \(aggr(G[B]^{*})\) denotes that the aggregation function \(aggr\) that takes the values of tuples in the group \(G\) over the aggregation field \(B\) as the input. The final output tuples are the concatenation performed on the output result of the calculation expression and aggregation operation.  
To illustrate the semantics of our method with examples, we considered the suppliers-parts-projects database, reproduced for convenience in Figure 1, where \(s_{i}\), \(j_{i}\), \(p_{i}\), and \(h_{i}\) are used to identify the tuples.