On the Expressiveness of Implicit Provenance in Query and Update Languages
Lecture notes in computer sciencePublished 1 January 2006Open access
Peter Buneman, James Cheney, Stijn Vansummeren
Citations41
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Information concerning the origin of data \n(that is, its provenance) is important in many areas, especially scientific recordkeeping. Currently, provenance information must be maintained explicitly, by added effort of the \ndatabase maintainer. Since such maintenance is tedious and error-prone, it is desirable to provide support for provenance in the database system itself. In order to provide such support, however, it is important to provide a clear explanation of the behavior and meaning of existing database operations, both queries and \nupdates, with respect to provenance. In this paper we take the view that a query or update implicitly defines a provenance mapping linking components of the output to the originating components in the input. Our key result is that the proposed semantics are expressively complete relative to natural classes of queries that explicitly manipulate provenance.
Keywords
Computer ScienceDecision Sciences
Foundations of databases
3,400 Citations1994Serge Abiteboul, Richard Hull +1 more
Lecture notes in computer scienceWhy and Where: A Characterization of Data Provenance
1,310 Citations2001Peter Buneman, Sanjeev Khanna +1 more
An approach to computing provenance when the data of interest has been created by a database query is described, adopting a syntactic approach and present results for a general data model that applies to relational databases as well as to hierarchical data such as XML.
ACM SIGMOD RecordA survey of data provenance in e-science
1,157 Citations2005Yogesh Simmhan, Beth Plale +1 more
The main aspect of the taxonomy categorizes provenance systems based on why they record provenance, what they describe, how they represent and storeprovenance, and ways to disseminate it.
Very Large Data BasesULDBs: databases with uncertainty and lineage
459 Citations2006Omar Benjelloun, Anish Das Sarma +2 more
It is shown that the ULDB representation is complete, and that it permits straightforward implementation of many relational operations, and how ULDBs enable a new approach to query processing in probabilistic databases.
ACM Transactions on Database SystemsTracing the lineage of view data in a warehousing environment
436 Citations2000Yingwei Cui, Jennifer Widom +1 more
The lineage problem is formally defined, lineage tracing algorithms for relational views with aggregation are developed, and mechanisms for performing consistent lineage tracing in a multisource data warehousing environment are proposed.
ACM Computing SurveysLineage retrieval for scientific data processing: a survey
415 Citations2005Rajendra Bose, James Frew
Based on a comprehensive survey of lineage research and previous prototypes, a metamodel is presented to help identify and assess the basic components of systems that provide lineage retrieval for scientific data products.
Provenance management in curated databases
296 Citations2006Peter Buneman, Adriane Chapman +1 more
This paper describes an approach in which the user's actions are tracked while browsing source databases and copying data into a curated database, in order to record theuser's actions in a convenient, queryable form and uses it to evaluate the feasibility of database support for provenance management.
The VLDB JournalAn annotation management system for relational databases
277 Citations2005Deepavali Bhagwat, Laura Chiticariu +2 more
An annotation management system for relational databases where every piece of data in a relation is assumed to have zero or more annotations associated with it and annotations are propagated along, from the source to the output, as data is being transformed through a query.
Theoretical Computer SciencePrinciples of programming with complex objects and collection types
261 Citations1995Peter Buneman, Shamim A. Naqvi +2 more
A new principle for the development of database query languages that the primitive operations should be organized around types is presented, in which a number of well-known languages are to be found as natural sublanguages.
RePEc: Research Papers in EconomicsA Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective
172 Citations1990Y. Richard Wang, Stuart Madnick
A polygen model for resolving the Data Source Tagging and Intermediate source Tagging problems is presented and a data-driven query translation mechanism for mapping a polygen query into a set of local queries dynamically is presented.
MONDRIAN: Annotating and Querying Databases through Colors and Blocks
121 Citations2006Floris Geerts, Anastasios Kementsietsidis +1 more
An annotation-oriented data model for the manipulation and querying of both data and annotations, which allows for the specification of annotations on sets of values and for effectively querying the information on their association is introduced.
Research Problems in Data Provenance.
74 Citations2004Wang Chiew Tan
The problem of supporting data provenance in scientific database applications is motivated and the DBNotes prototype developed at UC Santa Cruz is described that can be used to “eagerly” trace the provenance and flow of relational data.
Elsevier eBooksAn Annotation Management System for Relational Databases
49 Citations2004Deepavali Bhagwat, Laura Chiticariu +2 more
Lecture notes in computer scienceContainment of Relational Queries with Annotation Propagation
45 Citations2004Wang-Chiew Tan
This work says that a query is annotation-contained in another if the annotated output of the former is contained in the latter on every possible annotated input databases, and shows that annotation-containment is a more refined notion in general.
Specifying updates in biomedical databases
9 Citations2003Hartmut Liefke, Susan B. Davidson
This work describes an extension of the Collection Programming Language (CPL) called CPL+ which provides an intuitive framework for updates on complex values and presents various optimizations that can substantially improve the performance of complex updates.