## 4 Representing Data Provenance in DBMS
### Implementation of Data Provenance in PostgreSQL  
We implemented the model of provenance graph and provenance route in PostgreSQL and provided a client to query and visualized the provenance information. We refer to this improved system as ProvPg. ProvPg has a graphical client known as ProvPg-GUI. The primary function modules added in ProvPg include the extraction and query of provenance information. The provenance information extraction is implemented by the provenance extraction subsystem. In addition, ProvPg provides a series of query interfaces in the client to support provenance information query and visualization. ProvPg (Figure 9) is accomplished by using the Hook mechanism of PostgreSQL to add extended functions, and the source code of the Executor is modified. For the plan tree of a query, the processing flow is: (a) Before executing the query, a schema provenance graph (SPGraph) is extracted and produced with the help of the structural information of the plan tree. (b) During the execution of the plan tree, each time a tuple is an output, the corresponding provenance route (TupPRoute) is extracted in the form of a bitmap array. The bitmap array will be inserted into the output tuple as an additional field value. Finally,  
Figure 8: The field provenance graphs of the query \(Q_{2}\). (a) and (b) correspond to \(FPGraph(Q_{2},\mathit{Info})\) and \(FPGraph(Q_{2},\mathit{Sm})\), respectively. the client will receive two result sets. One is the output tuple set (with the provenance route), and the other is a provenance graph in the format of JSON. The graphical client ProvPg-GUI is used to receive the SQL input by the user, display the returned query results, and visualize the provenance graph and provenance route. In order to evaluate the impact of ProvPg on PostgreSQL's query engine, we conduct TEC Benchmark(tm) H [47] (TPC-H) test on ProvPg and PostgreSQL. The computation overload of ProvPg on PostgreSQL is analyzed. Our TPC-H instance contains eight relational tables, and we test 22 customized pieces of SQL on this instance (Standard SQL 92). Although the 22 SQLs are missing some features, such as CTE, and are not involved in the stored procedure, the performance of the query engine mainly depends on underlying physical operations, such as tuple scanning, join, and sort. The 22 SQLs have covered the primary calculation process of the query engine. The major significant load of stored procedure in PostgreSQL lies in the execution of a query plan. Therefore, the TPC-H criterion is sufficient to compare ProvPg with the original PostgreSQL. We construct three datasets ranging from 1G to 4G and 10G for the query tests. The specific running environment is (a) CPU: 64-bit, Intel(R)Core (TM) i5-4460 3.20 GHz; (b) memory: 12G; (c) operating system: Ubuntu 12.04 for operating system; (d) kernel: Linux 3.5.0; (e) PostgreSQL: version 9.5.0. Table S1 shows the query execution time of PostgreSQL and ProvPg on the above dataset. Figure S1 shows the ratios of overhead imposed by the data provenance module. The experiment results indicate the following:  
The overall extra cost is relatively small and within acceptable limits. The experiments show that, except for Q2, Q10, Q13, and Q18, the extra cost resulting from the provenance module for each SQL is less than 5%, and the average overhead for three kinds of load sizes is all below 3%. Taking the benefits from data provenance into consideration, we believe that the additional cost is acceptable. There is no positive correlation between the extra cost and load size. For different-sized datasets, the extra cost of ProvPg on PostgreSQL is stable overall and does not dramatically fluctuate according to data scale. Therefore, we think the extra cost of a query is predictable and estimated. We also analyze the correlation between the extra cost ratio and execution strategy of the database engine.