Decentralizing the Web means that users gain the ability to store their data wherever they want, users can store their data in their web browsers. Web browsers allow decentralized applications to be deployed in one click and enable interaction with end-users. However, querying data stored in a large network of web browsers remains challenging. A network of web browsers gathers a very large number of browsers hosting small data. The network is highly dynamic, many web browsers are now running on mobile devices with limited resources, this raises issues on energy consumption. In this paper, we propose Snob, a query execution model for SPARQL query over RDF data hosted in a network of browsers. The execution of a query in a browser is similar to the execution of a federated SPARQL query over remote data sources. In Snob, direct neighbours in the network are the data sources and results received from neighbours are stored locally as intermediate results. As data sources are renewed every shuffling, the query continues to progress and could produce new results after each shuffling without congesting the network. To speed up query execution, browsers processing similar queries are connected through a semantic overlay network. Experimentation shows that the number of answers produced by queries grows with the number of executed queries in the network while the number of exchanged messages is always bounded per user.
Decentralizing the applications and the data is a powerful paradigm to provide more control to users on their digital life 3. A decentralized application runs on resources owned by multiple authorities and provides a service even in presence of failures of any authority. Data are decentralized if authorities are free to store their data wherever they want. In this paper, we focus on how a decentralized 3 This work will be published as part of the book "Emerging Topics in Semantic Technologies. ISWC 2018 Satellite Events. E. Demidova, A.J. Zaveri, E. Simperl (Eds.), ISBN: 978-3-89838-736-1, 2018, AKA Verlag Berlin." application running in web browsers is able to provide a SPARQL service over data stored in browsers.
We focus on browsers as they are certainly the most deployed programming environment in the world. Decentralized applications can be deployed in oneclick, they are in direct contact with end-users, they are able to capture their location, their history of browsing or their perceptions of the real world. Browsers already integrate APIs to store data locally and are often used by web applications to provide off-line functionalities. However, querying data over a large-scale network of browsers is challenging.
Many works address the problems of data management in Peer-to-Peer
networks [
In this paper, we propose Snob, an approach for executing SPARQL queries
over a network of browsersWe assume that browsers are connected in an
unstructured network based on periodic peer-sampling [
This paper presents the following contributions: 1. Snob a SPARQL query execution model over data hosted in a network of browsers. Snob ensures a fair usage of resources by communicating only with direct neighbours at each shuffling. 2. A semantic overlay network based on query containment. 3. Experimentation shows that the completeness of queries grows with the number of running queries in the network. The semantic overlay network is able to speed up completeness when fewer queries are running simultaneously.
The section 2 describes the related works. Section 3 describes our proposal. Section 4 presents preliminaries experimental results. Section 5 concludes contributions and presents future works. 2
In our previous work [
The Solid project [
WebDamLog [
Mastodon 5 or Diaspora 6 are representative of distributed social networks [
The term "decentralized applications” is also used in the crypto-currencies communities such as bitcoins or ethereum 7. Such applications use blockchains to store data and cryptographic tokens to store values. As some blockchains rely on public P2P networks that anyone can join, the application is called "decentralized". In this case, users do not really choose where data are stored. In this paper, we focus on an approach where data placement and control are managed by users at run-time.
A network of browsers is strongly related to P2P data management [
this approach does not scale and hardly delivers complete results. Flooding can
be avoided with super-peer maintaining routing indices as in Edutella [
In this paper, we propose Snob an approach to execute SPARQL queries over a
network of browsers. Snob relies on three key ideas:
1. To address issues of dynamicity, we build an unstructured network based on
periodic peer-sampling [
First, sharing intermediate results replicates and aggregates data.
Consequently, the probability that a query communicates with relevant
intermediate results is improved [
We consider a network of web browsers based on WebRTC. A WebRTC node has no address and WebRTC has no routing. So a node cannot send messages to a particular node in the network. However, it can send messages to direct
SON RPS neighbours. This strong constraint prevents browsers from dereferencing hosted RDF data.
We build two overlay networks as proposed in [
Figure 1 shows browsers, browsers B1 − B4 has data Diseasome, B6 − B9 has data on LinkedMDB and B5 has data on both. The RPS network ensures that all browsers are connected through a random graph, browsers profiles make the clustered network converging towards two communities. B1 − B4 will be highly connected because they have data over Diseasome, while B6 − B9 will be grouped together due their interest in LinkedMDB. B5 could be connected to both communities because it hosts data from both datasets.
Algorithm 1: Ranking Algorithm
Input: P : Profile, P rof iles: set of Profiles, k: number of top ranked profiles Output: TopK ranked profiles 1 rank(P, P rof iles): 2 sortedP rof ile = sort(P , prof iles, compare) 3 return SelectTopk(k, sortedProfiles) 4 compare(P , P1 ∈ P rof iles, P2 ∈ P rof ile): 5 return Scoring(P, P2) − Scoring(P, P1) The Semantic Overlay Network clusters browsers with similar profiles. A profile is defined as a set of triple patterns of queries that are executed by the browser. Profiles are used for ranking browsers. We use triple patterns containment to define similarities among profiles
result of execution of query T P over an RDF dataset D. Let T P1 and T P2 be two triple pattern queries. We say that T P1 is contained in T P2, denoted by T P1 v T P2, if for any RDF dataset D, T P1(D) ⊆ T P2(D). We say that T P1 is equivalent to T P2 denoted T P1 ≡ T P2 iff T P1 v T P2 and T P2 v T P1.
Testing triple pattern containment meant finding substitution of variables
in the triple patterns [
To rank neighbours, we assign weights to the containment relationship using the following order: (T P1 ≡ T P2) (T P1 v T P2) (T P1 w T P2) (1)
We assume that equivalence has the highest weight, i.e. the browser is considered as the best relevant data source. We assign the weight ∞ to ≡, 2 for v and 1 for w, therefore, the profile with at least one equivalence will always be preferred to other profiles.
The algorithm 1 uses the order defined in (1) to keep the k best-ranked profiles of neighbours.
The compare function (lines 4-5) compares two different profiles by using the scoring function. The scoring function (lines 6-21) assigns weights based on the order defined in (1). Finally, the ranking function returns the top k sorted profiles. 3.3
In Snob, a browser hosts a small dataset, e.g. thousands of triples. At a given time, a browser Bi has a fixed number of neighbours: k neighbours in the random peer sampling layer, and l neighbours in the semantic overlay network. Typical values of k and l are logarithmic to the size of the whole network. Each browser exposes to its neighbours a triple pattern interface. The browser is able to process an incoming triple pattern query and return results to the triple pattern query originator. Incoming triple pattern queries are processed over local data and intermediate results. Therefore, a browser can share local data and intermediate results of running queries.
Suppose that the browser Bi processes the query Qi. Qi is processed like a federated query over its k + l neighbors considered as data sources. However, there are few differences with federated query processing: 1. The federation is incomplete, i.e., the federation will change at the next shuffling. Therefore, we need to keep intermediate results for continuing processing when new sources are discovered. 2. Shuffling can bring already visited data sources. However, as intermediate results may have been progressed, queries have to be re-executed.
For instance, the browser Bi executes Qi after each periodic shuffling window, then waits for the next shuffling for re-executing Qi. During the shuffling window, the browser only answers to triple pattern queries from direct neighbours.
The Snob approach has several properties: Constant number of messages We suppose a round corresponds to the shuffling window. Suppose the browser Bi processes one query Qi. In one round, (k + l) messages are sent to neighbours with the list of triple patterns of the query Qi. The browser waits for answers and then process its query Qi with new intermediate results. So the number of messages exchanged in the whole network of n participants is bounded to (k + l) ∗ n per round. This prevents congestion of the network, saves bandwidth and energy.
Continuous progress Thanks to shuffling properties, the RPS layer will bring
periodically to Bi uniform sampling of the network, and potentially nodes
that Bi has never met before. So the query will progress. As we know the
size of the network 8, Bi is able to estimate the ratio of explored nodes with
respect to the total size of the network and decides to terminate or continue
the query execution. This is a form of Pay-as-you-go query processing. This
approach can be compared to Link Traversal approach [
Automatic Clustering As the query progress, Bi meets other browsers with similar profiles, they automatically create a a community that crawls the data space thanks to shuffling. Consequently, the more browsers execute similar queries, the more they improve their crawling capacity.
Browsers Data
B1 B2 B3 B4 a P1 a b P1 a c P1 a a P2 a d P1 a a P1 b e P1 a (c) Initial Browsers Data
B1 ?s P1 a a P1 b
B3
B2 ?s P1 a ?s P1 a a ?p b
B4
B1 ?s P1 a a P1 b
B3
B2 ?s P1 a ?s P1 a a ?p b
B4 (a) Network state after the first shuffling (b) Network state after the second shuffling
To illustrate Snob query execution model, consider a subset of a network of browsers with a random peer sampling network (black link) and a semantic overlay network (blue link) in Fig. 2a. In this example, each browser Bi has at least one query to execute. For simplicity, the example is centred on the browser B1 for a period of two shuffling windows. In Fig. 2a, B1 has only one neighbor B2 in the SON and no neighbor in the RPS. B1 executes the query Q1 which has one triple pattern: T P1 : ?s P1 a, therefore the profile of B1 contains T P1.
B1 sends T P1 to B2. B2 answers with the triples matching T P1 in its local
data store (cf. 2c). Once B1 receives answers, B1 inserts intermediate results
into its local data store and executes Q1 which will result in two triples. Then,
B1 suspends Q1 execution until the next shuffling. During this time, B1 only
answers neighbours triple pattern queries.
8 We use an estimation of the size of the network as proposed in [
After the second shuffling, in Fig 2b, B1 has now more neighbors, B2, B3 and B4. In red new the established links, solid links are for RPS neighbours and dashed ones for SON. B1 sends to all neighbors T P1. Neighbours answer B1 request with matching triples in their local store and intermediate results collected from their neighbours. B1 stores received intermediate results and reexecutes Q1. At this state B1 has explored all browsers and the execution of Q1 will produce five triples, which is the complete answers for Q1 with respect to the data sources available in this network.
Other browsers executing queries follow the same cycles as B1. In Fig. 2a, B2 and B4 also execute queries with the same triple pattern as browser B1, i.e, ?s P1 a. De facto, in a bigger network, browsers B1, B2 and B4 will share their crawling capacity i.e, they will rely on their respective intermediate results and their different exploration of the network to answer faster their queries. 4
The goal of the experimental study is to evaluate the effectiveness of Snob. We
expect to see that the SON of Snob overcomes the RPS in terms of the number
of produced answers and the number of messages is constant between rounds
and always bounded to the number of edges in the network.
We use RDFStore-js [
We use the real datasets: Diseasome10 and Linked Movies Database11 (LinkedMDB). We generate 100 queries per dataset using PATH and STAR shaped templates with two to eight triple patterns that are instantiated with random values from the dataset. We removed the queries that caused the query engine to abort execution. This results in 100 queries from LinkedMDB and 96 queries from Diseasome. For these queries, we extracted triple patterns, each triple pattern of the query is executed as a SPARQL construct query and produces a fragment that we split into two sub-fragments. Sub-fragments are randomly distributed across the clients, each client hosts at least one fragment.
We set up a network of 196 clients. Each client can execute at most one query, we vary the number of queries executed in the network to observe the impact on the network clustering. We choose one query per client (all), half of the clients executing queries (half) and a quarter of clients executing queries (quarter). The quarter is a subset of the half-selected queries. Table 1 presents the different parameters used in the experiment. We vary the value of parameters according to the objective of the experimentations as explained in the following sections. The shuffle time is fixed to 10 minutes for all experiments.
Evaluation Metrics: i) Continuous Progress: is the number of completed queries. ii) Constant Messages number : is the number of messages produced 10 https://old.datahub.io/dataset/fu-berlin-diseasome 11 http://data.linkedmdb.org/ by round. iii) Automatic Clustering: is the clustering of clients running similar queries.
Results presented for all metrics are the average of three successive executions of 100 rounds. A round corresponds to a query execution after a periodic shuffle where the shuffling time is set to 10 minutes. 4.2
Continuous progression To study the impact of the number of queries in the network on the progress of queries execution, we used different number of queries.
Fig. 3 presents the completeness of query answers per round for three different configurations. Firstly for 49 queries (quarter), secondly for 98 queries (half) and finally for 196 queries (all). A round corresponds to a query execution after a periodic shuffle where the shuffling time is set to 10 minutes. As we can see, only RPS+SON provides better query completeness.
For the Half and Quarter at round 100, the RPS produces respectively 22.48% and 18.91% of complete answers. Compared to the RPS, the RPS+SON produces respectively 30.28% and 19.60%. We notice that the RPS+SON produce a better completeness rather than just relying on the RPS. However, the gap between RPS and RPS+SON is drastically reduced for 196 queries. This is because while executing queries, intermediate results are materialized, when the number of queries increases, the number of intermediate results is naturally
(a) RPS Graph at Round 100
(b) SON Graph at Round 1 (c) SON Graph at Round 50 (d) SON Graph at Round 100 increased. Thus, as intermediate results can be used to answer triple patterns queries, the replication of intermediate results helps to find relevant fragments faster. This is why we can sometimes notice a curve crossing between the RPS and RPS+SON curves.
Constant message number In all configuration, the number of messages is always bounded to (k + l) ∗ |queries| as only one triple pattern query is sent to a neighbour. For example, in Fig. 4 all configuration (196 queries), the average number of message at round 100 is 1834 bounded to 1960 ((k + l) = 10 and |queries| = 196). As expected, we can notice for each configuration that the average number of results is always smaller than the limit. Note here that we do not take into account messages produced by RPS and SON for their establishment and their maintenance. Only Snob messages are taken into account.
Automatic clustering In Fig. 5, the directed graph represents the RPS and the clustering overlay network where a node represents a client in the network and an edge represents the connection between clients. For example, an edge 1 → 2 means that the client 1 has the client 2 in its SON view. Fig. 5a shows clearly that the RPS network groups nodes randomly. However, Figures 5b, 5c and 5d demonstrate that Snob SON network is able to cluster clients according to their queries similarities, the clusters are clearly distinguished at round 100 where a greater value of rounds promotes the clustering. 5
In this paper, we described how a decentralized application running in web browsers is able to provide a SPARQL service over data stored in browsers. We proposed Snob, a query execution model for SPARQL query over RDF data hosted in a network of browsers. The execution of a query in a browser is similar to the execution of a federated SPARQL query over remote data sources. In Snob, direct neighbours in the network are the data sources and results received from neighbours are stored locally as intermediate results. As data sources are renewed every shuffling, the query continues to progress and could produce new results after each shuffling without congesting the network. To speed up query execution, browsers processing similar queries are connected through a semantic overlay network. Experimentation shows that the number of answers produced by queries grows with the number of executed queries in the network while the number of exchanged messages is always bounded per user.
This work opens several perspectives. First, data exchange between browsers has to be optimized when a data source is revisited to optimize the traffic. Second, intermediate results could be streamed on the semantic overlay network. Finally, a DHT service could be implemented in browsers to speed up the discovery of similar queries in the network. 6
This work was partially funded by the French ANR project O’Browser (ANR16-CE25-0005-01). Mr. Grall is funded by the GFI Informatique compagny (145 Boulevard Victor Hugo, 93400, Saint Ouen, France).