The goal of this research project is to investigate techniques and develop effective tools for tracing the provenance and flow of data in a network of inter-related databases where each database may be constantly evolving. The following three key areas are investigated: (1) Reasoning about provenance for relational/XML data through constraints. The relationships between databases or versions of databases can often be described by high-level abstractions such as constraints. Hence, tracing the provenance or flow of a piece of data involves reasoning about the movement of a piece of data through constraints. (2) An annotation management system based on provenance. This system provides an alternative method for computing provenance. It does so "eagerly" by carrying provenance along as annotations when data is transformed. (3) An archiving toolkit based on key constraints. A set of utilities for efficiently archiving and managing evolving databases in a semantically meaningful way is provided. The archive is such that the provenance of a piece of data can be easily traced. The results of this project have potential applications in many domains, in particular in scientific databases such as bioinformatics. Whenever applicable, results of this project will be prototyped and experimental evaluations will be conducted on both synthetic and real datasets in order to evaluate the effectiveness of the results. The results will also be integrated into an advanced database topics course on data provenance that will be developed and taught at UC Santa Cruz. Project website www.cs.ucsc.edu/~wctan/provenance/ will be used for wide dissemination of all course materials, publications, and software that result from this project.
