Representation and deduction of provenance knowledge for XML queries

As an important knowledge, data provenance has been used in a variety of applications, such as information integration, scientific databases and Web intelligence. Capturing data provenance during data transformations is of great significance for the improvement of the service quality. So the issues of representing and deducing data provenance have received more and more attentions. This work provides a formal provenance representation framework for data in XQuery views. Firstly, based on existing relational provenance semirings, a novel provenance bi-semiring structure K for XML data is introduced, and a K-Tree model is proposed, in which all nodes are annotated with elements from K. Then, the generalized algebraic query evaluations on K-Tree are presented, and the representations and computations for Where-provenance and How-provenance semantics are given. Finally, the application analysis for provenance bi-semiring are provided, which demonstrates that the proposed provenance framework in the paper is a general representation structure which is widely used in the field of granular computing.