A Research Of Data Provenance Technology And Its Implementation In PostgreSQL

Data provenance is the origin and history of data in its life cycle. The traditional relational database management systems mainly focus on how to provide users with efficient Query, Insert, Delete and Update methods and so on, and have not svoled the data provenance problem. Therefore, this paper makes a deep research on the data provenance in relational database, and traces the provenance information from three levels: schema level, attribute level and tuple level, respectively. Finally we implement the data provenance module in the PostgreSQL. The main contributions of this paper include:(1) A data transformation graph model based on SQL relational algebra was presented. The data transformation graph describes the schema level data process information. This paper gives 9 types of transformation based on the relational algebra in SQL subquery, and gives the analytical process of the source table, target table and the transformation node in the SQL syntaxes involved with data provenance.(2) The concept of attribute mapping based on the transformation was proposed. This paper gives the formal definition of attribute mapping graph, which is a refinement of data transformation graph. Based on the attribute mapping graph, this paper further proposed the data provenance graph which is the reduction of the transformation graph, and gives the reduction algorithm.(3) Based on the K-Relation this paper extends the provenance semi-ring model with group calculus of tuple labels, and gives the transmission rules of labels on the basis of the extended model.(4) Extend the PostgreSQL functionality and implement the data provenance module for schema level, attribute level and tuple level provenance tracing, which includes the provenance resolving, storage, querying and visualization process.Finally, the researches of this paper are summarized and the future works are presented.