Tracing where and who provenance in Linked Data: A calculus
Theoretical Computer SciencePublished 23 June 2012Open access
Mariangiola Dezani-Ciancaglini, Ross Horne, Vladimiro Sassone
Citations22
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.
TL;DR
This work introduces a new approach to provenance for Linked Data, extending the simplest notion of provenance-viz.
Abstract
Linked Data provides some sensible guidelines for publishing and consuming data on the Web. Data published on the Web has no inherent truth, yet its quality can often be assessed based on its provenance. This work introduces a new approach to provenance for Linked Data. The simplest notion of provenance-viz., a named graph indicating where the data is now-is extended with a richer provenance format. The format reflects the behaviour of processes interacting with Linked Data, tracing where the data has been published and who published it. An executable model is presented based on abstract syntax and operational semantics, providing a proof of concept and the means to statically evaluate provenance driven access control using a type system.
Keywords
Computer ScienceDecision Sciences
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
IEEE Intelligent SystemsThe Semantic Web Revisited
1,788 Citations2006Nigel Shadbolt, Tim Berners‐Lee +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.
ACM Transactions on Database SystemsSemantics and complexity of SPARQL
1,137 Citations2009Jorge Eduardo Pérez Pérez, Marcelo Arenas +1 more
This article identifies a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently and shows that the evaluation problem is coNP-complete for well-designed patterns.
The even more irresistible SROIQ
845 Citations2006Ian Horrocks, Oliver Kutz +1 more
A rather elegant tableau-based reasoning algorithm that combines the use of automata to keep track of universal value restrictions with the techniques developed for SHOIQ, which has been adopted as the logical basis for the next iteration of OWL, OWL 1.1.
Future Generation Computer SystemsThe Open Provenance Model core specification (v1.1)
692 Citations2010Luc Moreau, Ben Clifford +12 more
This document contains the specification of the Open Provenance Model (v1.1) resulting from a community effort to achieve inter-operability in the Provenances Challenge series.
Journal of Web SemanticsA survey of trust in computer science and the Semantic Web
674 Citations2007Donovan Artz, Yolanda Gil
This paper gives an overview of existing trust research in computer science and the Semantic Web.
Foundations and Trends in DatabasesProvenance in Databases: Why, How, and Where
537 Citations2009James Cheney, Laura Chiticariu +1 more
Why, how, and where provenance is reviewed, the relationships among these notions of provenance are described, and some of their applications in confidence computation, maintenance and update, debugging, and annotation propagation are described.
Named graphs, provenance and trust
520 Citations2005Jeremy J. Carroll, Christian Bizer +2 more
The extension of RDF to Named Graphs provides a formally defined framework to be a foundation for the Semantic Web trust layer.
Digital Access to Scholarship at Harvard (DASH) (Harvard University)Provenance-aware storage systems
506 Citations2006Kiran‐Kumar Muniswamy‐Reddy, David A. Holland +2 more
It is shown that with reasonable overhead, a Provenance-Aware Storage System can provide useful functionality not available in today's file systems or provenance management systems.
ACM Transactions on Database SystemsConditional functional dependencies for capturing data inconsistencies
458 Citations2008Wenfei Fan, Floris Geerts +2 more
This work proposes a class of integrity constraints for relational databases, referred to as conditional functional dependencies (CFDs), and provides an inference system analogous to Armstrong's axioms for FDs, and shows that the implication problem is coNP-complete for CFDs in contrast to the linear-time complexity for their traditional counterpart.
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.
Addison-Wesley Longman Publishing Co., Inc. eBooksPrinciples of Compiler Design (Addison-Wesley series in computer science and information processing)
365 Citations1977Alfred V. Aho, Jeffrey D. Ullman
IEEE Intelligent SystemsThe Emerging Web of Linked Data
330 Citations2009Christian Bizer
The paper concludes by stating that the Web has succeeded as a single global information space that has dramatically changed the way the authors use information, disrupted business models, and led to profound societal change.
Foundations and Trends® in Web ScienceA Framework for Web Science
249 Citations2006Tim Berners‐Lee, Wendy Hall +4 more
This text sets out a series of approaches to the analysis and synthesis of the World Wide Web, and other web-like information structures, and a comprehensive set of research questions is outlined, together with a sub-disciplinary breakdown, emphasising the multi-faceted nature of the Web.
The case of the fake Picasso: preventing history forgery with secure provenance
207 Citations2009Ragib Hasan, Radu Sion +1 more
This paper describes a provenance-aware system prototype that implements provenance tracking of data writes at the application layer, which makes it extremely easy to deploy and presents empirical results that show the run-time overhead of the approach to recording provenance with confidentiality and integrity guarantees ranges from 1%-13%.
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.
Foundations and Trends® in Web ScienceThe Foundations for Provenance on the Web
162 Citations2010Luc Moreau
This monograph contends that provenance can and should reliably be tracked and exploited on the Web, and investigates the necessary foundations to achieve such a vision, as well as identifying an open approach and a model for provenance.
ScholarlyCommons (University of Pennsylvania)Update exchange with mappings and provenance
159 Citations2007Todd J. Green, Grigoris Karvounarakis +2 more
This paper extends techniques from data integration, data exchange, and incremental view maintenance to propagate updates along mappings, and integrates a novel model for tracking data provenance, such that curators may filter updates based on trust conditions over this provenance.
Lecture notes in computer scienceCombining Provenance with Trust in Social Networks for Semantic Web Content Filtering
149 Citations2006Jennifer Golbeck
This paper describes an algorithm for inferring trust relationships using provenance information and trust annotations in Semantic Web-based social networks, and presents an application, FilmTrust, that combines the computed trust values with the provenance of other annotations to personalize the website.
Journal of Web SemanticsA general framework for representing, reasoning and querying with annotated Semantic Web data
139 Citations2011Antoine Zimmermann, Nuno Lopes +2 more
A generic framework for representing and reasoning with annotated Semantic Web data is described, and a generic method for combining multiple annotation domains allowing to represent, e.g., temporally-annotated fuzzy RDF is provided.
ACM Transactions on StoragePreventing history forgery with secure provenance
134 Citations2009Ragib Hasan, Radu Sion +1 more
Sprov, a provenance-aware system prototype that implements provenance tracking of data writes at the application layer, is described, which makes Sprov extremely easy to deploy and empirical results show that, for real-life workloads, the runtime overhead of Sprov for recording provenance with confidentiality and integrity guarantees ranges from 1% to 13%.
Digital Access to Scholarship at Harvard (DASH) (Harvard University)Securing provenance
132 Citations2008Uri Braun, Avraham Shinnar +1 more
ePrints Soton (University of Southampton)An Architecture for Provenance Systems
121 Citations2006Paul Groth, Sheng Jiang +5 more
This document covers the logical and process architectures of provenance systems: the logical architecture identifies key roles and their interactions, whereas the process architecture discusses distribution and security.
Travesía (Ministerio de Educación, Cultura y Deporte)DCMI Abstract Model
107 Citations2005Andy Powell, Mikael Nilsson +3 more
This document specifies an abstract model for DCMI metadata [DCMI], to provide a reference model against which particular DC encoding guidelines can be compared and facilitates the development of better mappings and translations between different syntaxes.
ACM Transactions on Database SystemsOn the expressiveness of implicit provenance in query and update languages
106 Citations2008Peter Buneman, James Cheney +1 more
The model is also relevant to annotation propagation schemes in which annotations on the input to a query or update have to be transferred to the output or vice versa, and it is shown that provenance separates the expressive power of query and update languages.
ACM Transactions on Computational LogicAnnotated RDF
101 Citations2010Octavian Udrea, Diego Reforgiato Recupero +1 more
This paper presents Annotated RDF, in which RDF triples are annotated by members of a partially ordered set that can be selected in any way desired by the user, and develops algorithms to check consistency of aRDF theories and to answer queries to aR DF theories.
Lecture notes in computer scienceA Model for User-Oriented Data Provenance in Pipelined Scientific Workflows
99 Citations2006Shawn Bowers, Timothy McPhillips +3 more
This work develops a simple provenance model capable of supporting a wide range of scientific use cases even for complex models of computation such as process networks, and is capable of reconstructing complete data and invocation dependency graphs for a workflow run.
Concurrency and Computation Practice and ExperienceMining Taverna's semantic web of provenance
86 Citations2007Jun Zhao, Carole Goble +2 more
This paper shows how Ouzo can be mined by a provenance usage component, Provenance Query and Answer (ProQA), and how these features of Taverna's provenance support us in answering the questions from the provenance challenge workshop and a set of additional provenance queries.
Lecture notes in computer scienceSameAs Networks and Beyond: Analyzing Deployment Status and Implications of owl:sameAs in Linked Data
85 Citations2010Li Ding, Joshua Shinavier +2 more
This paper provides a quantitative analysis of owl:sameAs deployment status and uses these statistics to focus discussion around its usage in Linked Data.
Lecture notes in computer scienceSemantically Linking and Browsing Provenance Logs for E-science
77 Citations2004Jun Zhao, Carole Goble +2 more
This paper describes how to assemble a Semantic Web of workflow provenance logs that allows a bioinformatician to browse and navigate between experimental components by generating hyperlinks based on semantic annotations associated with them.
Evidence-Based Audit
72 Citations2008Jeffrey A. Vaughan, Limin Jia +2 more
AURA_0 is presented, an authorization logic based on a dependently-typed variant of DCC and it proves the metatheoretic properties of subject-reduction and normalization and shows the utility of proof-based auditing in a number of examples.
A gentle introduction to semantic subtyping
67 Citations2005Giuseppe Castagna, Alain Frisch
This work shows step by step how to define a subtyped relation semantically in the presence of functional types and dynamic dispatch on types, without the complexity of denotational models, and how to derive a complete subtyping algorithm.
Mathematical Structures in Computer ScienceProvenance as dependency analysis
60 Citations2011James Cheney, Amal Ahmed +1 more
It is argued that dependency analysis techniques familiar from program analysis and program slicing provide a formal foundation for forms of provenance that are intended to show how (part of) the output of a query depends on (parts of) its input.
A Formal Framework for Provenance Security
58 Citations2011James Cheney
A formal model of provenance is outlined, formalizations of security properties for provenance such as disclosure and obfuscation are proposed, and their implications in domains based on automata, database queries and workflow provenance graphs are explored.
Lecture notes in computer scienceColoring RDF Triples to Capture Provenance
57 Citations2009Giorgos Flouris, Irini Fundulaki +3 more
This paper relies on colored RDF triples represented as quadruples to capture and manipulate explicit provenance information in conjunction with declarative languages for querying and updating RDF graphs.
Concurrency and Computation Practice and ExperienceTracking provenance in a virtual data grid
55 Citations2007Ben Clifford, Ian Foster +3 more
This work implements the virtual data model in a Virtual Data Language (VDL) and associated supporting tools, which provide for both the storage, query, and retrieval ofvirtual data set descriptions, and the automated, on‐demand materialization of virtual data sets.
Lecture notes in computer scienceRules with Contextually Scoped Negation
50 Citations2006Axel Polleres, Cristina Feier +1 more
This work proposes logic programs with contexts and scoped negation and discusses two possible semantics with desirable properties and argues that this class of logic programs can be viewed as a rule extension to a subset of RDF(S).
IRIS Research product catalog (Sapienza University of Rome)Authenticity and provenance in long term digital preservation: modeling and implementation in preservation aware storage
43 Citations2009Michael Factor, Ealan Henis +6 more
This work presents a novel model for managing authenticity in long term digital preservation systems and a supporting archival storage component, and presents an example of managing authenticity of data objects during data transformation at the storage component.
ACM Transactions on the WebA Formal Account of the Open Provenance Model
42 Citations2015Natalia Kwaśnikowska, Luc Moreau +1 more
OPM graphs with an explicit distinction between precise and imprecise edges are extended, and a formal semantics for the thus enriched OPM graphs is proposed, by viewing O PM graphs as temporal theories on the temporal events represented in the graph.
Storing and Querying Scientific Workflow Provenance Metadata Using an RDBMS
42 Citations2007Artem Chebotko, Xubo Fei +3 more
This paper proposes an approach to provenance management that seamlessly integrates the interoperability, extensibility, and reasoning advantages of semantic Web technologies with the storage and querying power of an RDBMS.
Lecture notes in computer scienceA Core Calculus for Provenance
41 Citations2012Umut A. Acar, Amal Ahmed +2 more
OAR@UM (University of Malta)A formal model of provenance in distributed systems
33 Citations2009Issam Souilah, Adrian Francalanza +1 more
The main feature of the π-calculus is that all data products are annotated with metadata representing their provenance, which ensures that data provenance is updated as the computation proceeds.
Scalable access controls for lineage
26 Citations2009Arnon Rosenthal, Len Seligman +2 more
This work builds on prior work for security and privacy of lineage information, focusing on complex conditions and scalable administration, and uses Attribute-Based Access Control (ABAC) to express conditions based on many attributes, instead of roles.
Kairos: An Architecture for Securing Authorship and Temporal Information of Provenance Data in Grid-Enabled Workflow Management Systems
25 Citations2008Luiz Gadelha, Marta Mattoso
This work suggests an architecture to provide protection of authorship and temporal information in grid-enabled provenance systems that can be used in the resolution of conflicting intellectual property claims, and in the reliable chronological reconstitution of scientific experiments.
Towards semantics for provenance security
21 Citations2009Stephen Chong
This paper proposes extensional semantic definitions for provenance security, which require that provenance information released to the user does not reveal confidential data, and that neither theprovenance information given to the users, nor the program's output, reveal sensitive provenance Information.
Towards a social provenance model for the Web
21 Citations2007Andreas Harth, Axel Polleres +1 more
The established notion of provenance on the Semantic Web is presented, and the benefit of adding to the pure technical notion ofprovenance a social dimension to associate provenance with the originator (typically a person) of a given piece of information is argued for.
Research Portal (King's College London)PROV-AQ: Provenance Access and Query
17 Citations2013Graham Klyne, Paul Groth +8 more
This document specifies how to use standard Web protocols, including HTTP, to obtain information about the provenance of resources on the Web, and provenance query services for more complex deployments are described.
Oxford University Research Archive (ORA) (University of Oxford)Annotation algebras for RDFS
16 Citations2010Peter Buneman, Egor V. Kostylev
Steps toward managing lineage metadata in grid clusters
15 Citations2009Ashish Gehani, Minyoung Kim +1 more
This work reports on the exploration of mechanisms to manage the lineage metadata in Grid clusters, and develops operating system functionality for auditing filesystem activity to infer lineage relationships.
Lecture notes in computer scienceOperational Semantics for SPARQL Update
13 Citations2012Ross Horne, Vladimiro Sassone +1 more
An operational semantics for an update language for RDF, which models core features of SPARQL Update, is proposed, which specifies all possible operational behaviours of updates in the presence of an RDF store.
Lecture notes in computer scienceA Model for Sharing of Confidential Provenance Information in a Query Based System
11 Citations2008Meiyappan Nagappan, Mladen A. Vouk
A model for sharing provenance information when the confidentiality level is decided by the user dynamically is presented and the key feature of this model is the Query Sharing concept.
Lecture notes in computer scienceLeft-Handed Completeness
10 Citations2012Dexter Kozen, Alexandra Silva
A new, significantly shorter proof of the completeness of the left-handed star rule of Kleene algebra is given, exposing the rich interaction of algebra and coalgebra in the theory of Klee algebra.
Science of Computer ProgrammingA verified algebra for read–write Linked Data
9 Citations2013Ross Horne, Vladimiro Sassone
This work verifies an algebra for high level languages for reading and writing Linked Data, a collection of standards which aim to enhance the world’s data, by interlinking datasets through the Web.
Electronic Proceedings in Theoretical Computer ScienceA Verified Algebra for Linked Data
8 Citations2011Ross Horne, Vladimiro Sassone
This work focuses on emerging W3C standards which specify query languages for Linked Data, to provide an abstract syntax to capture linked data structures and queries, which are then internalised in a process calculus.
ePrints Soton (University of Southampton)Programming languages and principles for read-write linked data
8 Citations2011Ross Horne
This work provides an operational semantics for a Read–Write Linked Data architecture which is sufficiently general to capture the established standards, including queries and entailments, while raising some serious questions about W3C standards.
Integrity Constraints for Linked Data.
6 Citations2011Alan Jeffrey, Peter F. Patel‐Schneider
This work provides a definition of integrity constraint satisfaction in the presence of partitioning, and shows that it leads to a formal interpretation of dependency graphs which describe the hyperlinking relations between datasets.
ePrints Soton (University of Southampton)A Typed Model for Linked Data
4 Citations2011Ross Horne, Vladimiro Sassone
A calculus which models concurrent queries and updates over Linked Data is presented and exhibits operations essential for declaring rich atomic actions, which recover emergent structure in the loosely structured Web of Data.
Dynamic Provenance for {SPARQL} Updates Using Named Graphs
2 Citations2011Harry Halpin, James Cheney