## 4 Representing Data Provenance in DBMS
### Schema-Level Provenance Representation  
Schema-level data provenance is coarser and more suitable for applications that do not focus on the details. In a transformation-intensive database environment, the relational table instances are the results of relation interactions, which reflect the dependencies between tables at the schema level. Since provenance data between schemas does not have a formal definition, this paper introduces a representation model for schema-level provenance. Schema-level provenance is a directed graph, \(G=<V_{R}\), \(V_{O}\), \(E>\), where \(V_{R}\) represents relation table nodes, \(V_{O}\) denotes the transformation operation nodes, and \(E\) is the directed edges set representing the dependencies among \(V_{O}\), and the dependencies between \(V_{R}\) and \(V_{O}\). Specifically, we have:  
**Definition 8**. : _(1) Tuple Provenance Graph (TupPGraph), \(TupPGraph(Q_{i},I,t)=<V_{tr},V_{t_{o}},Et>\) (2) Schema Provenance Graph of \(\mathbf{T}\) (SPGraph), \(SPGraph(I,\mathbf{T})=<V_{r},V_{o},E>\), where \(V_{r}=\cup Vt_{r},V_{o}=\cup Vt_{o},E=\cup Et,\forall t\in T,TupPGraph(Q_{i},I,t )=<Vt_{r},Vt_{o},Et>\) (3) Schema Provenance Graph of database 1 (SPGraph), \(SPGraph(I)=<Vt_{r},Vt_{o},EI>\), where \(Vt_{r}=\cup V_{r},Vt_{o}=\cup V_{o},EI=\cup E,\forall T\in\Re\)._  
From the above definition, the schema provenance graph not only includes the provenance transformation of each tuple but also explains the transformation process between the target relation schema and source relation schema. Similarly, the overall schema provenance graph \(SPGraph(I)\) merges all the schema provenance graphs of the database and can explain the specific dependencies between different relation schemas. Every output tuple has a tuple provenance graph, and multiple output tuples may have the same tuple provenance graph for a query \(Q\), indicating that output tuples can share a tuple provenance graph. Furthermore, two tuple provenance graphs in the same query \(Q\) may have the common subgraph, indicating that merging tuple provenance graphs is possible. Therefore, we keep one tuple provenance graph for multiple output tuples and combine different tuple provenance graphs to obtain the schema provenance graph. During the merging process, some nodes may lose information, such as the number of operations or operation objects of the lower nodes. To avoid this, we introduce the \"Option\" node without transformation meaning, which means multiple possible branches for this node. For example, the tuple provenance graph of transformation expression \(PET(Q_{i},t)\in T\) can be expressed as \(G<R^{\prime},O,\eta>\), \(R^{\prime}=\{R_{1},R_{2},\ldots,R_{m}\}\), \(O=\{Op_{1},Op_{2},\ldots,Op_{n}\}\), where \(Op_{j}\) is the \(j^{th}\) basic transformation (\(Op_{1}\) is the top-level operation), and \(\eta\) is a set containing the relations among operations and the relations between operations and reference relation tables. Figure 5 shows the possible tuple provenance graphs of the output tuples of table \(QTY\) in query \(Q_{2}\) in Example 2, which is output by the subquery \(Q_{2}^{\prime}\). Figure 5a-c displays tuple provenance subgraphs of the tuple \(k_{1}\) and \(k_{4}\), tuples \(k_{3}\), and tuples \(k_{2}\) and \(k_{5}\), respectively. Notably, the tuple provenance graph in Figure 5c is actually the SPGraph of the query \(Q_{2}^{\prime}\). Figure 5: (**a**) Tuple provenance subgraphs of the tuple \(k_{1}\) and \(k_{4}\). (**b**) Tuple provenance subgraphs of the tuple \(k_{3}\). (**c**) Tuple provenance subgraphs of the tuple \(k_{2}\) and \(k_{5}\). Nodes contain actual parameter information. The relational table node generally contains metadata, such as field names, and the operation node includes the expression and a reference to the input values. \"$.$.$\" refers to the \(k\)th field of the tuple, and in multivariate operations, “$i$” and “$.$.$.$.$.$.$.$. \" refer to the ith tuple and the \(k\)th field of the tuple, respectively. Hereafter, we use the same notation related to provenance graphs.