Causality and the Semantics of Provenance

James Cheney
(University of Edinburgh)

Provenance, or information about the sources, derivation, custody or history of data, has been studied recently in a number of contexts, including databases, scientific workflows and the Semantic Web. Many provenance mechanisms have been developed, motivated by informal notions such as influence, dependence, explanation and causality. However, there has been little study of whether these mechanisms formally satisfy appropriate policies or even how to formalize relevant motivating concepts such as causality. We contend that mathematical models of these concepts are needed to justify and compare provenance techniques. In this paper we review a theory of causality based on structural models that has been developed in artificial intelligence, and describe work in progress on using causality to give a semantics to provenance graphs.

In S. Barry Cooper, Prakash Panangaden and Elham Kashefi: Proceedings Sixth Workshop on Developments in Computational Models: Causality, Computation, and Physics (DCM 2010), Edinburgh, Scotland, 9-10th July 2010, Electronic Proceedings in Theoretical Computer Science 26, pp. 63–74.
Published: 9th June 2010.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: