## 3 Semantic Expression of Relational Data Provenance
### Representation of Provenance Transformation
#### 3.4.2 Representing Provenance Transformation in SQL with Meta-Transformation  
We SQL-revised PET to support full-featured SQL, and we present how PET represents SQLs in this section. For the sake of discussion, assume that the main body of a query is the SQL of ASP)-CTE-Win-Sub with selection and filter, projection, join, group aggregation, CTE (common table expression), window function, and set operation. Furthermore, PET supports the query language of small features (such as Sort, Limit, and Distinct). For each SQL feature, the representation method based on meta-transformations is described as follows. To illustrate this, we use \(subExpr_{i},i=1,2,\ldots,n\) to represent the transformation expressions that function as the subexpressions of the operations discussed below. 1. Ordinary import. Ordinary import is treated as a query on constant relation tables and expressed as \(ONull(\bot)\). 2. Selection and filter. The filtering operation does not perform any transformation on tuples, so the corresponding transformation expression is \(ONull(subExpr)\). 3. Group aggregation, projection, and union are expressed as \(OAggr\), \(OPro\)), and \(ONull\), respectively. 4. Joins (both input sets contribute to the output) include inner joins, left/right outer joins, and full outer joins. The Cartesian product operation can be treated as an inner join if join conditions always hold. The join transformation is expressed as: Inner join: \(OJoin(subExpr_{1},subExpr_{2})\); Left outer join: \(OJoin(subExpr_{1},\mathit{subExpr_{2}})\) or \(OJoin(subExpr_{1},\bot)\); Right outer join: \(OJoin(subExpr_{1},subExpr_{2})\) or \(OJoin(\bot,subExpr_{2})\); Full outer join: \(OJoin(subExpr_{1},subExpr_{2})\), \(OJoin(subExpr_{1},\bot)\) or \(OJoin(\bot,subExpr_{2})\). 5. Join (when only one of the two input sets contribute to the output). In this case, the other input set plays the role of a filter. Assume that only the left input set contributes, then the join transformation is expressed as \(subExpr_{1}\) or \(\bot\) (right outer join and full outer join will make the left input set a constant relational table). 6. Window function. The window function is an extension of group aggregation in SQL and can be equivalently represented by group aggregation and join. Therefore, the window function is equivalent to \(OJoin(subExpr,OAggr(subExpr))\). 7. Except operation (Except, \(Q_{1}-Q_{2}\)). The output tuples only come from \(Q_{1}\), so the except operation is expressed as \(subExpr_{1}\). 8. Intersect operation (Intersect, \(Q_{1}\cap Q_{2}\)). The output tuples are from \(Q_{1}\) and \(Q_{2}\). In this case, there are two kinds of parallel provenance transformations, denoted as \(subExpr_{1}\) and \(subExpr_{2}\). 9. CTE (Including recursive CTE and non-recursive CTE). Non-recursive CTE can be regarded as a nested subquery. Recursive CTE is divided into a base query and a recursive query on the language structure. The input of the recursive query may be the output of the base query or the output of the previous recursion. The output of the CTE can be regarded as the union of a base query, a recursive query with the base query as the input, and a recursive query with the output of the previous recursion as the input. Therefore, recursive CTE is expressed as \(baseExpr\), \(recursiveExpr(baseExpr)^{*}\) (the asterisk indicates using the out  
Figure 3: The query \(Q_{2}\) and its output tagged with tuple-level where-prov. put of the last recursion as the input) or \(OUnion(baseExpr,recursiveExpr(baseExpr),\)\(recursiveExpr(baseExpr)^{*})\) among the third item that has the premise that the current expression works as a subexpression of the aggregation operation. **Example 3**. : _Suppose we have the following query \(Q_{3}\) calculating the revenue for suppliers with a window function. The query \(Q_{3}\) and its output are shown in Figure 4._  
The first output column derives from the table \(\mathit{Shipment}\), and the second column represents an aggregation of each supplier's revenue on each project.