Nowadays, huge quantities of data are produced and published on the Web, coming from individuals, connected objects, and organizations. Uncertainty happens when combining data from di erent sources that contain heterogeneous, contradictory, or incomplete information. Today, there is still a lack of solutions in order to represent uncertainty that appears on the Web. In this paper, we introduce the concept of uncertain RESTful resource and propose a model and an algebra to interpret such resources.
Nowadays, individuals, organizations, and connected objects produce and
publish a huge amount of data on the Web [
The main objective of this paper is to propose a theoretical framework for describing, manipulating, and exposing uncertain data on the Web. We present a model to de ne and interpret uncertain Web resources. We de ne an interpretation model and an algebra to compute uncertainty in the context of classical hypertext navigation and in the context of data query evaluation. The paper is structured as follows: Section 2 describes our uncertainty model and interpretation. Section 3 explains how we interpret query evaluation in this uncertaintyaware context. Section 4 presents our implementation details and evaluation. Section 5 presents other approaches that handle uncertainty. Finally, section 6 concludes and presents some future work.
The semantics of uncertain Web resources can be explained based on the theory
of possible worlds [
Pi
1g >
Where repi are the possible representations of Re. Since multiple representations
of a resource cannot coexist at the same URI, these representations are mutually
n
exclusive, and we have Pi 2]0; 1]. Having P Pi 1 indicates that other
repi=1
resentations may exist but their actual content is unknown (or does not exist).
As an example, Fig. 1a shows that the two possible representations of our book
resource generate three Webs in which representations are certain. We rely on
the popular uncertain database model Block-Independent Disjoint (BID) [
(a) composition
(b) generated worlds Fig. 1: Uncertain Resource Example 1
In this subsection, we introduce the notion of uncertainty-aware client, which is a client who is able to manipulate uncertain resources. In order to respect the Web principles, and to adapt to every client, we rely on content negotiation. Content negotiation is an HTTP mechanism that allows to serve di erent versions of the same resource representation (i.e., at the same URI), to t with the client. Doing so, the client who does not know, or does not care, how to process uncertain resources, can receive a certain (but arbitrary) version of the resource representation1. In this paper, we make a di erence between classical and uncertainty-aware GET requests. We propose the notation GgET to describes a GET request from an uncertain-aware client. Let Re be an uncertain resource deployed at urir, we de ned the following expected behaviors:
GgET (urir) := f< rep1; P1 >; : : : ; < repn; Pn >g In case, where the client performs a GgET request over a certain resource, the response will provide the representation with a probability of 1. In our approach GgET is not de ning a new HTTP method. GgET acts as a standard GET with a speci c HTTP header which we de ne in Section 4 as X Accept U ncertain : true. We choose to de ne a speci c header to avoid interference with the standardized usage of the accept header. Indeed, the Accept header is the classical header for content negotiation, as it is used to specify an expected mime-type for the resource representation. The good practice is then to specify an adhoc speci c header to respect the HTTP standards (see RFC7231 2). 2.2
In a composition of Web resources, each combinaton of possible resource representations generates a new possible Web P Wx, whose probability is computed as follows:
P (P Wx) =
prob(repi)
Y i2[1;n] where repi 2 Card(P Wx), and Card(P Wx) being the representations involved in P Wx. The probability of the unknown representations of a resource Ra is n computed as follows: prob repax = 1 P prob(repia) where repia are the difi=1 ferent representations of resource Ra. Fig. 2a shows a more complex example, where resources are certain and uncertain, generating the possible Webs shown in Fig. 2b. As an example, the probability of possible Webs P W4 is prob(P W4) = prob(A2) prob(C1) prob(H) prob(E) = 0:2 0:5 1 1 = 0:1. In the next section, we describe how to interpret and compute a query in an uncertain composition. 1 NB: how providers de ne the certain representation of an uncertain resource is not a problem we address in the scope of this paper. We only provide the possibility to do it 2 https://tools.ietf.org/html/rfc7231#section-5.3.2 4
P W1; 0:42 B2 A1
C P W2; 0:12 (a) composition
C B B1
A1
C
BX
A1
A2
C2
B
AX
C F G D E H I
F G D E H I
F G D E H I
F G D E H I F G D E H I
F G D E H I
F G D E H I
P W7; 0:2 P W3; 0:06 B
A2
C1
P W5; 0:08 B
A2
CX P W4; 0:1
P W6; 0:02 (b) generated Webs In this section, we present our approach to aggregate data from uncertain resources thanks to hypertext navigation. Formally, we de ne a data query as an ordered set of resource requests, following the same path through the di erent generated possible Webs. Each Web will provide a unique result, which are then aggregated. Generating each of these possible Webs, i.e., combining and storing each combination in memory to compute the query in each one, is a time and memory-consuming task.
When dealing with uncertain resources, we follow our query path through the possible resource representations. This navigation creates a possibility tree pattern, where branches are possible Webs associated with their probability. Fig. 3 shows the tree pattern created from our book scenario.
We propose an algorithm, cf. Algorithm 1, to compute resulting probabilities without possible Web generation. This algorithm implements an operator, which we call GETp, who follows a stage-by-stage routing inside the possibility tree.
PA1 = 0:6
A1:author
A1 A
PA2 = 0:2A2 PAx = 0:2 ;
A2:author
Paris, 0.52 Results: Lyon, 0.12
Tours, 0.08
GETp takes as input a list of URIs from an nth stage of the tree, and returns the possible resource representations from the (n+1)th stage. The GETp operator executes the necessary sequence of HTTP requests over the given URIs, applies the probability formula and returns the set of representation-probability couples.
As an example, we have a list of author URIs, extracted from possible book representations, each with a probability. GETp gives us the possibility to retrieve the representation of each authors (with their probabilities) and to apply book probabilities to them. This will produce a set of author representations with global probabilities. The mutually exclusive status of representations guarantees a safe composition, which means resulting probabilities are coherent and their sum does not exceed 1. Finally, our computation algorithm, see Algorithm 2, uses GETp to recursively process through the di erent stages of the probability tree. According to a query, and the URI of the rst resource, our algorithm processes its way through the resource path, using object properties to nd its way. In the end, the resulting data set contains all the values with their probabilities. 4
We proposed an implementation for the GETp algorithm and the computation algorithm. Here is an example of an HTTP request, using content negotiation, to an uncertain resource: Algorithm 2 Computation Algorithm In order to keep our approach reusable, and to allow integration with other RESTful approaches, we implemented the GETp and COM P U T E algorithms as RESTful services. Service calls are made through POST, and GET retrieves a user-friendly description of the service. We propose a Web interface to execute simple SPARQL queries. Our prototype, resources and scenarios are publicly available for testing at the following URL: http://liris.cnrs.fr/~pdevetto/ uncert/index.php.
In order to evaluate our approach, we focus on processing time of our
algorithms. For this purpose, we hosted RESTful services serving uncertain Web
resources in JSON-LD [
In this section, we present several approaches that handle data uncertainty,
formerly in databases, and more recently in data services. In the context of
databases, existing approaches can rely on the notion of containment [
In this paper, we address the need for a solution to handle data uncertainty while referencing and navigating resources on the Web. We propose a model for uncertain Web resources, as resources which may have several mutually exclusive representations with probabilities. On top of that, we propose an algebra to interpret and evaluate data query in uncertain resource compositions.
Future work includes opening our approach in order to deal with more complex scenarios, where possible representations could be actual Web resources with URIs. This way, we could construct a model based on hypertext navigation to de ne a resource according to a set of others, giving a possibility to represent the probable equivalence of resources.