-Provenance is a cornerstone element in the process of enabling quality assessment for the Web of Data. Applications consuming or generating Linked Data will need to become provenance-aware, i.e., being able to capture and consume provenance information associated with the data. This will bring provenance as a key requirement for a wide spectrum of applications. This work describes Prov4J, a framework which uses Semantic Web tools and standards to address the core challenges in the construction of a generic provenance management system. The work discusses key software engineering aspects for provenance capture and consumption and analyzes the suitability of the framework under the deployment of a real-world scenario.
INTRODUCTION
The Web is evolving into a complex information space where users have access to an unprecedent volume of information. The advent of Linked Data in the last years as the de-facto standard to publish data on the Web, and its uptake by early adopters12, defines a clear trend towards a Web where users will be able to easily aggregate, consume and republish data. With Linked Data, Web information can be repurposed with a new level of granularity and scale. In this scenario, tracking the provenance of an information artifact will play a fundamental role on the Web, enabling users to determine the suitability and quality of a piece of information.
As a direct consequence, Linked Data applications will demand mechanisms to track and manage provenance information. This new common requirement is inherent to the level of data integration provided by Linked Data and it is not found in most systems consuming information from „data silos‟, where the relationship among data sources and applications is, in general, more rigid.
Until now, provenance management has been a wide
concern in the domain of scientific workflow systems [
This work discusses provenance management from the perspective of this larger audience, describing Prov4J 4 , a general-purpose open source provenance management system. The framework uses Semantic Web standards and tools to deploy a generic and standards-based solution. The paper also discusses key software engineering aspects in the process of designing the framework.
The central goal behind the design of the framework is to provide a set of core functionalities that enable users to develop provenance-aware applications, both from the consumption (discovery/query/access) and from the capture (logging/ publishing) perspectives.
The paper is structured as follows: section II introduces a motivational scenario; sections III and IV describe general aspects of provenance management and the architecture behind Prov4J; sections V and VI cover the consumption and capture cycles of provenance management, discussing the application of Semantic Web standards and tools in the construction of the framework. Section VII provides a brief analysis of the framework using a real world scenario based on the motivational scenario; section VIII present related work and section IX conclusions and future work.
This work concentrates its contributions: (1) in the description and analysis of a generic provenance framework for the Web using Semantic Web standards and tools; (2) in the analysis of the suitability of these standards and tools in the process of building this framework.
II.
Financial analysts in an investment company are using information from the Web to help make investment decisions. Business related data aggregated from different Web sources is filtered, curated and analyzed, and financial reports about companies or investment areas are generated. Each report is a data mash-up and the provenance of each statement in the report should be tracked to its sources. The ecosystem of Web applications used for aggregating, filtering, curating, analyzing and visualizing the data should be provenance-aware, i.e. the 3 http://www.w3.org/2005/Incubator/prov/wiki/User_Requirements, W3C Provenance Incubator Group 4 http://prov4j.org historical trail of all the entities and processes behind the transformation of the original data need to be recorded and users should be able to access the provenance of data. The core goal behind Prov4J is the provision of a provenance management mechanism for the large set of applications which will increasingly need to capture and consume provenance information. As a result, Prov4J is targeted towards an application developer which needs to build provenance-aware applications.
According to Freire et al. [
W3P is a generic provenance ontology for tracking
provenance on the Web. W3P is designed to be a lightweight
provenance ontology, complementing and integrating
vocabularies such as Dublin Core 6 , and the ChangeSet 7
vocabulary. Other key features of W3P include the coverage of
social provenance [
IV.
ARCHITECTURE
In most applications, provenance represents a cross-cutting
concern where the functionalities to capture and consume
provenance are a complementary requirement to the core
functionalities of an application. A cross-cutting concern is a
common feature that is typically spread across objects in the
application, being difficult to decompose from other parts of
the system. Prov4J adopts a provenance architecture which
reflects the separation between the core concerns of the
application and the cross-cutting concern of provenance. The
architecture maximizes the encapsulation of provenance
capture and consumption functionalities in a separate layer
(figure 1). The architecture behind Prov4J contains many
elements in common with the general architecture proposed by
Groth [
However, differently from classical examples of
crosscutting concerns (e.g. message logging and user
authentication/access control), provenance capture and
consumption is typically more tightly coupled with the logic
structure of the calling application (process documentation
perspective [
6 http://dublincore.org
limits to the isolation of the provenance concern inside the calling application.
A common provenance scenario is the association of the information present in a procedural or object-oriented application to a data artifact in a generic data store (e.g. relational databases, XML or RDF data). The strategy used in Prov4J is to use RDF to represent provenance data and URIs to associate the described information resource in the core application layer with its provenance descriptor. This allows Prov4J to cope with both data representation independency and separation of concerns, important requirements for a generic provenance framework. A <provURI> is a connection point between the core application layer and the provenance layer, being an entry point into the provenance store. This allows an abstraction over the artifact type, which can be a relational tuple, RDF triples, a named graph, a XML element, a HTML element, etc.
The <provURI> mechanism also allows Prov4J to partially
track data provenance. Data provenance is defined as the
process of tracking the origins of data and its movement
between databases [
Prov4J also allows the discovery and consumption of provenance descriptors associated with different types of resources, including HTML pages, SPARQL endpoints, and RDF published as Linked Data. This allows Prov4J to respond to an important use case where an application is consuming provenance from third-party Web resources. Prov4J consists of two core components: ProvClient and ProvLogger (figure 2). ProvClient is responsible for the consumption cycle of the application, while ProvLogger provides an interface for provenance capture. A third element, ProvServer, is introduced in order to allow high performance provenance capture.
V.
The consumption cycle inside Prov4J starts with the specification of the information sources which will be consumed: users can specify the location (URIs) of information resources that have associated provenance descriptors or the URIs of provenance data sources. There are three types of supported provenance sources: provenance stores (which are SPARQL endpoints), linked provenance data (RDF published using the Linked Data principles 8 ) and provenance descriptors (RDF data embedded in different formats).
Each type of provenance data source has a different
consumption approach. Data in provenance stores are
consumed after a user query is defined over the API. Linked
provenance data is consumed using a navigational approach
[
The provenance graphs collected from different sources are then loaded into a memory model. The framework uses two basic internal provenance structures: a provenance graph (ProvGraph) and a provenance view (ProvView). A ProvGraph represents the basic fragment of provenance information associated with a data source. One or more different ProvGraphs can be loaded into a single model by using a ProvView. The ProvView is the model where users have a consolidated provenance view over a set of different provenance data sources.
After all provenance graphs are merged into provenance views, elements from different vocabularies are mapped into W3P entities using rules reasoning. Rules provide an expressive mechanism which allows complex mappings between different vocabularies which cannot be addressed by owl:equivalentClass or owl:equivalentProperty. Examples of
more complex mappings across different provenance
representations can be found in Miles [
Once the vocabularies are mapped into W3P elements, the
framework applies RDFS/OWL reasoning over the
provenance model. owl:TransitiveProperty and
owl:InverseProperty are used in W3P to improve the number
of provenance queries answered by the framework (subsection
B in this section). The consumption process is dependent on
the type of provenance data source: for provenance stores and
linked provenance data, the reasoning is done at query time,
while for descriptors the discovery-parsing-reasoning is done
during the definition of data sources on the interface. Prov4J
uses the Jena framework 10 in its core and Pellet [
The provenance consumption API (ProvClient) provides the core operations over the provenance views. The ProvClient API contains key interface methods for a set of provenance queries, minimizing the interaction from users with SPARQL. A SPARQL query interface is also exposed to allow nonpredefined types of queries over the model. The framework supports five query categories: SPARQL based queries: Provenance queries supported by the elements of the SPARQL specification 11 are accessible by using the direct query over the provenance model or by using API methods for common queries. Prov4J SPARQL also includes syntactic extensions: GROUP BY, HAVING and aggregation. ARQ with syntactic extensions 12 is the core query engine behind Prov4J.
Queries supported by reasoning: Some key provenance queries over W3P can be addressed by applying OWL reasoning over provenance data. Examples of queries of this type involve the determination of indirect relationships/dependencies in a workflow chain, such as “list all artifacts which were used directly or indirectly in artifact X”. Similarly, rules can be applied to improve query expressivity.
Path queries: One important feature for provenance queries is
the ability to query paths over provenance trails. A typical path
query is “show all the processes between artifacts A and B” or
more specifically “list all the trails containing a process which
uses artifact C between artifacts A and B”. Regular expressions
queries over RDF elements can be used for expressing
provenance path patterns. Prov4J uses the Gleen SPARQL
extension described in [
Navigational queries: In some scenarios the primary way to
consume provenance information is through RDF published as
Linked Data. In this case Prov4J provides two interfaces: one
for users browsing provenance data and the other for
navigational queries. In the first case, the first level provenance
descriptor of an artifact is available as a de-referentiable URI.
The RDF provenance data can be consumed by the application
and further de-referentiations are directed by user input (in this
case Prov4J provides a simple interface for node
dereferentiations). A second type of navigation provided by the
framework is through the provision of iterators to provenance
nodes where provenance properties are used to determine
which provenance nodes to de-reference. For example, the
iterator defined by the property w3p:used can be used to
navigate through a chain of artifact dependencies. The third
functionality is defined by the idea of navigational queries,
which are mechanisms to query Linked Data by launching a
SPARQL query over a collection of RDF graphs collected from
a de-referentiable URI entry point [
Similarity queries: One type of provenance query refers to the
similarity analysis between two provenance graphs. This type
of comparison can be used in the determination of similar
workflow conditions and have potential applications in quality
assessment scenarios. A user may trust a specific workflow and
may want to query for similar or identical conditions. The
matching process used in Prov4J is based on the approach
described by Oldakowsky & Bizer [
Provenance Discovery consists in automatically
discovering the provenance given an information resource and
it is an important requirement for a generic provenance
management framework for consuming provenance data on
the Web. Information resources can be HTML pages, elements
inside the page, SPARQL endpoints, RDF files or
dereferentiable URIs. A provenance discovery mechanism
should not rely on centralized crawled provenance
repositories: it should always be possible to navigate from the
artifact to its provenance descriptor. Prov4J supports four
mechanisms to discover provenance on the Web:
Semantic Sitemaps + robots.txt: Used to discover the
provenance descriptor of a dataset having as a starting point a
domain name. As covered in [
Linked Provenance Data: Provenance descriptors can be published as Linked Data in two ways: (1) the URI represents an artifact and links directly to other provenance properties, (2) a provenance property such as w3p:provenance links the URI to the starting point of a provenance descriptor (a mirror to the provenance layer representation of the artifact). Embedded RDFa: Provenance data can be embedded as RDFa in HTML pages.
POWDER: POWDER (Protocol for Web Description Resources) 13 is a W3C recommendation which provides a standard for describing general Web resources. Provenance descriptors can be embedded as RDF payloads in POWDER files.
VI.
One key challenge in the process of building a generic
provenance capture framework is the process of providing a
simple yet expressive provenance interface. The ability to
express provenance accurately and with the mimimum amount
of intervention in the application is a fundamental feature in
the process of introducing the provenance functionality in
existing applications. In order to achieve this objective, the
provenance capture engine was built using the following
principles:
Pushback capture: Provenance capture or logging can be
implemented as pushback operation, where, from the capture
interface perspective, new provenance information is inserted
but never deleted or updated. This assumption is consistent
with the fact that provenance maps to the actual temporal
execution flow of the application. Instead of allowing a full
interaction with the provenance store, the ProvLogger
interface is primarily designed for pushing back fragmented
provenance logs, which are reconstructed in the provenance
store (concept present in [
Minimization of adaptations: Prov4J capture interface can be
used to implement adaptations, a concept defined by Munroe
[
Provenance URIs: In some cases, provenance entities can be interconnected with elements in different parts of the workflow (e.g. a process consuming an artifact that was generated by another process at a different time). The logger interface provides a mechanism to interconnect provenance entities in different execution scopes. Users can associate different provenance entities by using internally the concept of ApplicationId-URI mapping, which associates Ids inside the application to provenance URIs. These associations can also be done directly by referencing directly provenance URIs. To 13 http://www.w3.org/TR/powder-dr/ minimize the performance impact, this mechanism relies in the construction of a provenance URI cache in the capture mechanism.
Annotations: Java Annotations provide a mechanism to map the structure of an application to provenance elements. Annotations also allow users to provide provenance relationships valid in a specific scope. Provenance entities inside the scope of a method may be directly associated with an entity represented in the annotation, depending upon their relationship (figure 3). The design of ProvLogger allows users to express provenance information by maximizing the mapping between the application object structure and the provenance elements. In this case, classes, methods and member variables can directly map to provenance artifacts, processes and agents by using annotations.
The ProvLogger interface uses the concepts of aspect oriented programming (AOP) and Java annotations to maximize the isolation between cross-cutting concerns, allowing users to separate distinct functionalities of a software. AOP combined with Java Annotations can provide a powerful mechanism to implement the separation of concerns in provenance capture.
After the information is collected in the capture interface, the provenance log information is sent to the ProvServer and translated into a SPARQL/Update query to the provenance store. Prov4J relies on Scribe 14, a high-performance logging mechanism for the communication and distribution of provenance logs.
The framework was analyzed using the scenario described in section II. A provenance dataset was generated using real financial data aggregated from multiple data sources, which focused on news and opinions about businesses collected from the Web. These data elements defined the ground artifacts which were further aggregated, curated and analyzed in a financial analysis workflow simulator. The output of the workflow is a report for a specific company, which is a mashup of business data15. The provenance of the final report and 14 http://sourceforge.net/projects/scribeserver/ 15 http://prov4j.org/w3p/scenario/financial.html each of its artifacts is tracked down to their original sources. In the experiment, business reports were generated with data collected for 100/500/1000 companies with up to 100/500/1000 news respectively for each company. Details about the experiment are outlined in table I. The experiment sought to determine the performance of the framework in a realistic scenario.
Data set 1000 500 100
Reasoning level
# triples
The experiment was run in a 2.53 GHz Intel Core 2 Duo computer with 4 GB of memory. The minimum level of reasoning enabled was vocabulary rules mapping (voc) and the maximum added OWL features and 5 additional rules (voc+owl+rules). The input provenance data was consumed from 2 RDF files which were merged inside the framework. In the experiment path-based queries showed the highest execution time (max query), being highly sensitive to reasoning. SPARQL queries over basic elements of the ontology accounted for the lowest execution time (min query). Most of the queries (aggregate included) showed low execution time increase after the reasoning was enabled. Navigational and similarity queries were not tested. The 1000/1000 dataset counted 53.844 processes, 20.179 artifacts and 30 agents. The framework was able to do reasoning and answer the majority of provenance queries present in the API with acceptable runtime latencies. The scalability of reasoning could, however, represent a problem for larger provenance datasets.
Different approaches for provenance management have
been described in the literature. Pegasus [
Compared to existing works, Prov4J stands out as most heavily leveraging Semantic Web standards and tools, using RDF as its core provenance representation and both OWL and rules reasoning over provenance data. In addition, Prov4J extends existing SPARQL query capabilities: a Java API, SPARQL aggregate functions, regular expression path queries and similarity queries together with reasoning provide additional query expressivity. Prov4J also incorporates important requirements for the Web: provenance discovery and Linked Data navigation. Compared to PrOM, which is targeted towards the provision of a scalable query mechanism for an eScience scenario, Prov4J focuses on generic provenance management for the Web including both provenance capture and discovery. Similarly to the combination PreServ + Python Provenance Client Library, Prov4J is designed as an independent provenance layer, being designed for the provision provenance-awareness to generic applications.
In [
IX.
CONCLUSION & FUTURE WORK
This work described Prov4J, a generic provenance management framework. The design of the framework focused on the following features: (1) the provision of expressive provenance queries; (2) the maximization of the use of Semantic Web standards to address the challenges of managing provenance data; (3) software engineering aspects for provenance capture; (4) discovery mechanisms for provenance descriptors on the Web. The use of Semantic Web tools and standards to address these challenges played a fundamental role in the construction of the framework. Prov4J benefited largely from: the use SWRL-like rules to map and align different provenance vocabularies; OWL reasoning to address a subset of provenance queries; use of different publishing protocols (POWDER, semantic sitemaps, etc) for provenance discovery on the Web; SWRL-like rules applied to the enrichment of the provenance structure; RDF to represent the bulk of provenance data, SPARQL as a query mechanism and Linked Data as a publication mechanism for the Web. The use of nonstandardized extensions over existing standards such as aggregate SPARQL queries, SPARQL/Update and path queries provided important features for the framework. The ensemble of these technologies proved to achieve a good performance under a realistic provenance scenario.
From the software engineering perspective, Prov4J orchestrates different strategies to maximize the separation between provenance aspects and core concerns and to reduce the number of application adaptations for provenance capture.
Future work will include a detailed analysis of the query expressivity and query performance of the framework. A mapping mechanism from W3P to OPM profiles using rules is planned. One current limitation of the framework is related to the deployment of security and integrity mechanisms. In addition, an in-depth comparative study across existing provenance management systems is planned. Improvements over the framework to transform Prov4J from an experimental to a robust provenance solution are set as a priority.
The work presented in this article has been funded substantially by Science Foundation Ireland under Grant No. SFI/08/CE/I1380 (Lion-2). The authors want to express their gratitude to Tomas Knap and Micah Herstand for their support in the elaboration of this work.