Problem statement Data processing in distributed environments is often across heterogeneous systems, bearing the need to exchange provenance information, such as, how and when data was generated, combined, recombined, and processed. Distributed systems involve multiple participants and data sources which can produce unreliable, erroneous data. Besides, there maybe exists oceans amount of data to deal with, e.g., in elds such as Internet of Things (IoT) and Smart Cities. Therefore, dynamic stream-based data processing mechanisms are more reasonable in these environments. Hence, we propose provenance and recovery-aware data management techniques that take dynamic, incomplete streams as inputs, and simultaneously recover the missing data and compute the provenance over the reconstructed streams. Unlike traditional provenance management techniques, which are applied on complete and static data, our research focuses on dynamic and incomplete heterogeneous data.
Provenance provides the knowledge of how a piece of data or query results were
produced. Provenance is especially important in open environments such as the
IoT where data can be discovered, modi ed or mashed-up by arbitrary parties.
In fact, the IoT involves many uncoordinated data producers, which generate
vast amounts of data with high velocity (e.g., from sensors, mobile devices).
This variety of data streams yields very heterogeneous and incomplete data. In
this context, it is crucial to establish the trust and the transparency of the data
to facilitate reliable insight to the end user. Linked Data [
The outcomes of the research proposed in this paper will be applicable over a range of domains and will bene t users handling di erent data analysis tasks (e.g., prediction, trend analysis), real-time events streams processing, as well as stream reasoning over Linked Data. Such environments are vulnerable to the error propagation problem since these errors cannot be traced without any knowledge of provenance. In these elds, our approach will allow end-users to mitigate the in uence of incomplete or erroneous data on their applications. Our solution will allow users to better grasp how the data and query results were produced, which is a key element in establishing transparency and data governance. 3
Various types of provenance information have been formalized semantically in
the Open Provenance Model [
On the systems side, Glavic et al. introduced Perm [
Provenance of Linked Data is often attached to a dataset descriptor that
is typically embedded in a Vocabulary of Interlinked Dataset (VoID) le [
Zimmermann et al. [
The implementations described above of annotated RDF provenance approaches often do not address \provenance-tracing", i.e., how a query result was
constructed. Moreover, these implementations are only applied to small (around 10 million triples), static, and complete datasets which focus on inferred triples but do not aim at reporting provenance evolution (e.g., with provenance polynomials, which are algebraic structures representing how data was combined) for SPARQL query results.
Wylot et al. in their system TripleProv [
None of the approaches described above speci cally target incomplete Linked Data Streams. These approaches were designed for static data, therefor they do not take into account dynamics of input streams and they do not allow users to execute continuous queries over such streams. Moreover, due to the employed storage models (multiple indicies and provenance annotations) their performance deteriorates for dynamic data. Besides, all these techniques assume that data is complete; to the best of our knowledge there are no methods to deal with incomplete or re-constructed dynamic Linked Data. 4
In this research, we will investigate two questions in provenance management: (Q1) How can we enable dynamic provenance tracing in the context of incomplete Linked Data Streams? This question will investigate means to deliver the user a continuous provenance, i.e., a dynamic provenance trace of the continuous query that executes over a long period of time on dynamic data. The returned provenance trace represents how particular pieces of data were produced and combined to deliver the results. We will also introduce methods to track provenance of the recovery process, i.e., to provide recovery-aware provenance for continuous queries over multiple incomplete Linked Data Streams. (Q2) How can we derive probabilistic provenance graphs on recovered data? Continuing with tracking provenance of the recovery process for di erent sources of incomplete Linked Data Streams in Q1, this question will investigate methodology to derive probabilistic provenance graph based on Linked Data Streams before and after recovery. To achieve this goal, we will use a moving correlation on di erent sources of Linked Data Streams and will compute their fractional contributions to the recovered data, i.e., the fractional provenance of the recovered pieces of data. Afterwards, we will trace back the provenance graphs of the source elements (elements used in the recovery from di erent sources) and use them to reconstruct a provenance graph of the recovered pieces of data to assess the probability of the reconstructed provenance graph (see Section 6 for details).
An accurate provenance of query results over incomplete and recovered data in
dynamic distributed environments can be computed at low costs in terms of
memory consumption and query execution time (bound complexity).
State-ofthe-art research [
Our main goal is to e ciently handle incomplete and dynamic data. Such data has to be recovered online and the lineage, i.e., full history of what happened to data as it went through diverse processes, of the recovered data has to be provided. We will also include the information of the recovery process in the provenance description of query results, such that users will be able to know how recovered pieces of data have in uenced the results of their query.
To achieve this goal, we propose the following research contributions to answer the two research questions (Q):
Continuous Provenance Polynomial for describing provenance in a dynamic setting (Q1) Online provenance-aware recovery of incomplete Data for recovering incomplete data and tracing provenance of the recovery process (Q1) Fractional provenance of recovered incomplete Linked Data streams for discovering provenance of data recovered with external recovery techniques (Q2)
Continuous provenance polynomial over Linked Data streams. The
goal of this task is to provide a dynamic provenance trace of continuous queries,
i.e., a continuous provenance polynomial. This task builds on TripleProv [
The main challenge of this task relates to dealing with the velocity of the input data. The provenance polynomial has to satisfy two requirements: i) It has to be computed e ciently in a continuous fashion along with the execution of the query, and ii) it has to show how the query execution process evolves over time.
Figure 1 illustrates a system that consists of a knowledge base with data on drivers and companies they work for (KB=(driver1, worksFor, company1),(driver2, worksFor, company1),(driver3, worksFor, company2)). Each driver is equipped with a device streaming his position (triples vn = (drivern; position; locationi)). Sjinjn denotes an input stream for the driver n. A triple in the stream has its provenance: device id, physical state of the device, con guration parameters, etc. The provenance of the triple is grouped under a provenance annotation gj. We want to notify two truck drivers working for the same company when they are within a given distance, e.g., 1km. We also want to be able to trace back how the noti cation was generated. To detect spatial locations we use a query Tn = (?drivern; detectedAt; ?locationi). Let n be the result of such query for the nth driver. ./ denotes a natural join, to obtain information on the proximity of the two drivers.
S|out| (gB⊗gC)⊗gX r1
r2 (gA⊗gD)⊗gX r3
rn Γ5( (gB⊗gC)⊗gX )
⋈34 Γ3(gB⊗gC)
⋈12 Γ1(gB) T1(S)
T2(S) Γ2(gC) gA v1
v2 gB v3
vn S|in|1 gC v1
v2 gD v3 vn S|in|2
T3(KB) Γ4(gX)
Online provenance-aware recovery of incomplete Linked Data Streams. The goal of this task is to develop techniques that will allow us to trace detailed information on the recovery process over incomplete Linked Data streams. The core challenges related to this task are: i) how to detect the incompleteness of the input Linked Data streams, ii) how to handle the dynamics of the input Linked Data streams, and iii) how to devise highly e cient serialization strategies for continuous provenance information. Furthermore, in a heterogeneous integrated environment, the information on the recovery process has to be exchanged between multiple participants to support the accurate derivation of the nal provenance.
Fractional provenance of incomplete Linked Data streams. The goal of this task is to determine the fractional provenance of recovered pieces of data, i.e., computing probabilistic information about pieces of data which have contributed to the recovery process and their impact on the recovered piece of data.
The main challenges of this task are dealing with the velocity of the data, as well as, the need to exchange information on fractional provenance between di erent participants in a Linked Data streams environment. The computation of fractional provenance has to be accurate and e cient. In addition, the information on fractional provenance has to be exchanged in a compact and e cient way.
r1,3 r4,3 r2,3
S1 S2 S3 S4
R E C O V E R Y
S1 S2 S3 S4
v1 c1 c2 v2 v3 c4 v4 We will evaluate our approaches in three aspects, 1) extra costs for provenance tracking and tracing, 2) adaptability to changing sources3 of Linked Data Streams, 3) The accuracy of our query and recovery provenance tracing mechanisms. We will use open Linked Data collections and open collections of time series that contain heterogeneous unstructured data. We will integrate these data collections to our system as static knowledge and stream data. We will also design a set of workload queries using static and dynamic data. The collections of integrated Linked Data and time series data we will employ in our experiments are: 3 Data sources in distributed systems are very often unstable, which embodies in two aspects: 1) some of the sources can feed data for a period of time, afterwards, disappear completely (e.g., because of some unexpected abnormalities), however, maybe reconnect after a resetting. 2) di erent sources may have di erent data generation speed.
DBpedia4 is a crowdsourced community e ort to extract structured information from Wikipedia and make this information available on the Web. The dataset consists of 6.9 billion RDF triples extracted from Wikipedia. These datasets will be used to evaluate our provenance computation over incomplete Linked Data Streams techniques.
The Web Data Commons project5 extracts structured data from the Common Crawl, the largest web corpus available to the public. The dataset contains more than 20 billion RDF triples extracted from the Web. These datasets will be used to evaluate the scalability of our techniques with big data collections of di erent structure.
LinkedSensorData6 is an RDF dataset containing expressive descriptions of 20,000 weather stations in the United States. The dataset contains nearly 2 billion RDF triples describing 160 million observations. These datasets will be used to evaluate the scalability of our methods using real-world sensor data.
The Swiss Federal O ce for the Environment (FOEN)7 o ers access to streams of time series that describe weather phenomena (temperature, air pressure, humidity, precipitation, etc.). The time series contain from 200'000 up to few millions of values each. These datasets will be useful for the evaluation of the compression scalability with the length of time series. 8
Large distributed systems with billions of connected devices generate enormous amounts of values every minute. These values are produced in multiple ways for a speci c scenario, under di erent circumstances, with di erent reputation, etc. This heterogeneous environment requires assessments of quality, reliability, and trustworthiness. With the Linked Data approaches dynamic data can be combined with static knowledge to enable complex data analysis. This combination, however, introduces incomplete and possibly erroneous data to a knowledge base. The number of elements in the physical infrastructure, failures and uncertainty cannot be avoided, such as sensor failures, power outages, sensor to central server transmission problems, etc. In such scenarios we need additional provenance information describing the data involved in the recovery of the missing elements and its fractional contribution. This process increases the overall requirement of transparency from simple physical device information to algorithmic methods, pieces of data involved in producing a value, the probabilistic contribution of correlated elements to the recovery, i.e., the fractional provenance.
To the best of our knowledge, our research is one of the pioneers in the area of handling provenance over incomplete Linked Data Streams.
I would like to express my deep gratitude to my supervisors Prof. Dr. Manfred Hauswirth and Dr. Marcin Wylot for their patient guidance, constructive suggestions of this research proposal.