Toward a Theory of Self-explaining Computation

James Cheney, Umut A. Acar, Roly Perera

Research output: Chapter in Book/Report/Conference proceedingChapter


Provenance techniques aim to increase the reliability of human judgments about data by making its origin and derivation process explicit. Originally motivated by the needs of scientific databases and scientific computation, provenance has also become a major issue for business and government data on the Web. However, so far provenance has been studied only in relatively restrictive settings: typically, for data stored in databases or scientific workflow systems, and processed by query or workflow languages of limited expressiveness. Long-term provenance solutions require an understanding of provenance in other settings, particularly the general-purpose programming or scripting languages that are used to glue different components such as databases, Web services and workflows together. Moreover, what is required is not only an account of mechanisms for recording provenance, but also a theory of what it means for provenance information to explain or justify a computation. In this paper, we begin to outline a such a theory of self-explaining computation. We introduce a model of provenance for a simple imperative language based on operational derivations and explore its properties.
Original languageEnglish
Title of host publicationIn Search of Elegance in the Theory and Practice of Computation
Subtitle of host publicationEssays Dedicated to Peter Buneman
EditorsVal Tannen, Limsoon Wong, Leonid Libkin, Wenfei Fan, Wang-Chiew Tan, Michael Fourman
PublisherSpringer Berlin Heidelberg
Number of pages24
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg


Dive into the research topics of 'Toward a Theory of Self-explaining Computation'. Together they form a unique fingerprint.

Cite this