Web integration systems are able to provide transparent and uniform access to heterogeneous Web data sources by integrating views of Linked Data, Web Service results, or data extracted from the Deep Web. However, given the potential large number of views, query engines of Web integration systems have to implement execution techniques able to scale up to real-world scenarios and e ciently execute queries. We tackle the problem of SPARQL query processing against RDF views, and propose a non-blocking query execution strategy that incrementally accesses and merges the views relevant to a SPARQL query in a parallel fashion. The proposed strategy is implemented on top of Jena 2.7.4, and empirically compared with SemLAV, a sequential SPARQL query engine on RDF views. Results suggest that our approach outperforms SemLAV in terms of the number of answers produced per unit of time.
Linked Open Data initiatives have motivated the integration of a large number
of RDF datasets into the Linking Open Data (LOD) cloud [
Two main approaches exist for data integration: data warehousing, and the
virtual mediators [
On the other hand, a mediator relies on a global schema to provide a uniform
interface for accessing the data sources. Global-As-View (GAV) and
Local-AsView (LAV), are the main paradigms for mapping data sources and the global
schema. In GAV mediators, entities of the global schema are described using
views over the data sources, but including or updating data sources may require
the modi cation of a large number of views [
SemLAV provides a new paradigm to execute SPARQL queries against LAV
views, but because relevant views are loaded sequentially, SemLAV may get
blocked loading large views. In the worst case, if the rst loaded view is huge and
it does not provide relevant data for the query answer, SemLAV will be blocked
without producing any answer. Following a sequential view loading strategy may
reduce the number of answer produced per unit of time, i.e., throughput, and
the time for rst answer. Loading several views in parallel may overcome these
limitations. However, a parallel view loading strategy will introduce the problem
of concurrent writing on the integrated RDF graph. In this paper, we propose
a non-blocking query execution strategy to integrate the data from the relevant
views into the integrated RDF graph in a parallel fashion. We implement the
proposed non-blocking strategy on the top of Jena 2.7.4; we name this new
SPARQL query engine parallel SemLAV. Further, an empirical evaluation is
conducted to study the new parallel strategy with respect to SemLAV. The
Berlin Benchmark [
The paper is organized as follows. Section 2 describes background and
motivation. Section 3 presents strategies for integrating relevant views into the
integrated RDF graph in a parallel fashion. Section 4 reports our experimental
results. Finally, conclusions and future work are outlined in Section 5.
SemLAV follows a mediator and wrapper architecture [
The bene ts of SemLAV are illustrated in the following example [
<h t t p : / /www. w3 . o r g /2000/01/ r d f schema#> <h t t p : / / xmlns . com/ f o a f /0.1/ > SELECT DISTINCT WHERE f ?P f o a f : member ?C . ?C r d f s : l a b e l " Semantic Web" . ?P f o a f : knows ?WKP . ?WKP f o a f : name ?N .
FILTER (?N=" D a l a i Lama" j j ?N=" Barack Obama" j j ?N=" Rihanna " ) g rdfs 6. Figure 2 presents a SPARQL query expressed using the global schema. Views are expressed as conjunctive queries, where RDF predicates are represented by binary predicates, e.g., label(C,L) corresponds to ?C rdf:label ?L and ?P foaf:name ?N is expressed as name(P,N). Listing 1 de nes ve LAV views. Triple patterns in the query are also seen as binary predicates and BGPs are represented as conjunctive queries; the running SPARQL query is composed of four subgoals on the predicates: member(P,C), label(C, \Semantic Web"), knows(P,WKP), and name(WKP,N). The lter expression is modeled as a disjunction of atomic expressions on the equality comparison operator.
Listing 1: Views s1-s5 for Query Q v1 (P , A , I , C , L): made (P , A) , a f f i l i a t i o n (P , I ) , member (P , C) , l a b e l (C , L ) v2 (A , T, P , N, C): t i t l e (A , T) , made (P , A) , name (P ,N) , member (P , C) v3 (P , N, R ,M): name (P ,N) , name (R ,M) , knows (P , R) v4 (P , N, G , R , C): name (P ,N) , g e n d e r (P , G) , knows (P , R) , member (P , C) v5 (P , N, R , C , L): name (P ,N) , knows (P , R) , member (P , C) , l a b e l (C , L )
Given a subgoal sg of a conjunctive query, e.g., label(C,\Semantic Web"), a view v is relevant for sg, if sg is part of the body of v, e.g., v1(P,A,I,C,L) and v5(P,N,R,C,L) are relevant for label(C,\Semantic Web"). Table 1a presents the set of relevant views for each query subgoal of query in Figure 2.
SemLAV sorts relevant views according to the number of the subgoals of the query that the view de nes, e.g., view v5 is sorted rst since it de nes all the subgoals. Table 1b represents the sorted relevant views for query in Figure 2.
SemLAV identi es and ranks the relevant views of a query, and executes the query over the data collected from the relevant views. Di erent strategies can be followed to contact the views and load the data. For example, following a blocking strategy, views are contacted one by one in order, and a view is not contacted until all the data from the previous contacted view have been downloaded completely. This is the strategy followed by SemLAV, which is illustrated in the Figure 3a, we can see that this strategy can be blocking if the rst view is huge. While the view v5 is loading we are not able to perform the query. This blocking issue can have a negative impact on the performance of the query en
member(P, C) label(C, L) knows(P, WKP) name(WKP, N) v1(P,A,I,C,L) v1(P,A,I,C,L) v3(P,N,R,M) v2(A,T,P,N,C) v2(A,T,P,N,C) v5(P,N,R,C,L) v4(P,N,G,R,C) v3(P,N,R,M) v4(P,N,G,R,C) v5(P,N,R,C,L v4(P,N,G,R,C) v5(P,N,R,C,L) v5(P,N,R,C,L)
(b) Sorted relevant views member(P, C) label(C, L) knows(P, WKP) name(WKP, N) v5(P,N,R,C,L) v5(P,N,R,C,L) v5(P,N,R,C,L) v5(P,N,R,C,L) v4(P,N,G,R,C) v1(P,A,I,C,L) v4(P,N,G,R,C) v4(P,N,G,R,C) v1(P,A,I,C,L) v3(P,N,R,M) v2(A,T,P,N,C) v2(A,T,P,N,C) v3(P,N,R,M) gine if the performance is measured in terms of the number of answers produced per unit of time, i.e., throughput.
To illustrate this problem, consider Figure 3a, where v5 is loaded rst. Even if v5 covers all the query subgoals, loading v5 rst reduces the throughput, because v5 is the biggest view and does not contribute to the result. On the other hand, loading both v1 and v4, which together cover all the subgoals takes less time and may produce query answers. If relevant views were loaded in parallel following a non-blocking strategy, this situation would not a ect the query engine performance. This solution is illustrated in Figure 3b, where there are ve threads and each of them loads one of the rst ve top ranked views at the time; views are allocated in di erent threads. Time to load v5 is greater than the time required to load v4 and v1 in parallel. Additionally, v4 and v1 cover all the subgoals of our running query; thus, answers are produced before loading v5 completely.
We propose a non-blocking strategy for executing SPARQL queries against views. Like SemLAV, this approach does not rely on statistics to rank and select the relevant views. The proposed strategy prevents the query engine from getting blocked until all the data are retrieved from the relevant views. 3
A non-blocking strategy to access the views in a parallel fashion is de ned. Although this strategy improves the performance of a query engine, loading the retrieved data into the integrated RDF graph in parallel, may generate concurrency problems, i.e., many processes may simultaneously add data to the integrated RDF graph. So, we de ne a new concurrent model for RDF, and we propose a non-blocking query execution strategy able to adapt query execution to di erent criteria, e.g., a query is executed after a certain number of triples
Query Q Query Q Query Q Query Q v5 v4 Query Q (a) Sequential loading (b) Parallel loading are loaded into the integrated RDF graph. We implement the concurrency model and the non-blocking query execution strategy on top of Jena 2.7.4 7 . 3.1
Regarding our approach, we need a model that can handle concurrent insertions. However, RDF stores like Jena do not handle concurrent insertions, they are only able to favor one type of operation, e.g., reads or insertions. This strategy is implemented thanks to locks, but read and insert locks are mutually exclusive, i.e., they cannot be simultaneously activated. Existing RDF stores assume that there are more readers than writers and follow the multiple-readers/single-writer strategy (MRSW)8. According to MRSW, many readers may read simultaneously, while a writer must have exclusive access. MRSW assumes writers have the priority to keep data up-to-date. Nevertheless, in our proposed approach, data insertions are going to be more frequent than data reads. A reader is the query engine that accesses the integrated RDF graph during query execution, while writers are the wrappers of the relevant views which load the data into the integrated RDF graph. The query engine cannot execute the query more often than loading views into the integrated RDF graph, because executing the query is expensive, and doing so too often may lead to performance degradation.
In other words, our proposed approach prioritizes read operations over
insertions, i.e., a single-reader/multiple-writers strategy (SRMW) [
We implement a non-blocking strategy that is able to execute a query according to the following criteria; the selection of the criteria can be either con gured or provided by the user during query execution.
{ View dependent: the reader is woken up after a new view is loaded; thus, if v is a new loaded view, then the query engine will re-execute the query against the integrated RDF graph. If enough data is loaded into the integrated RDF graph from v, then the query engine will be able to generate new results when it is executed. This criterion is also implemented by SemLAV. { Time dependent: the reader is woken up after a period of time t, i.e., if t is n milliseconds, the query engine will re-execute the query against the RDF graph every n milliseconds. If enough data is loaded into the integrated RDF graph during the period t, the query engine will be able to generate new results. But, the concurrency model prioritizes the reader over writers; thus, if the writers are stopped and not able to load enough data into the integrated RDF graph, the query will be ine ciently executed. { Data dependent: the reader is woken up after a certain number n of triples are inserted into the integrated RDF graph by the writers; thus, the query engine will re-execute the query against the RDF graph whenever n new triples are integrated. If the n new triples contribute to the results, then the query engine will be able to generate new answers when it is executed. { Two-phase execution: the reader is woken up either after a period of time t or a certain number n of triples are inserted into the integrated RDF graph by the writers. In the rst phase, the reader performs ASK queries to check if new results can be produced, if the answer is true, the second phase is launched. The second phase strategy will directly execute the query, then the reader will be woken up either after a period of time t or a certain number n of new triples have been inserted into the integrated RDF graph. 4
The Berlin SPARQL Benchmark (BSBM) [
Queries and views are described in Tables 2a and 2b. The size of the complete answer is computed by including all the views into the Jena RDF triple store and by executing the queries against this centralized RDF dataset. The Jena 2.7.4 library with main memory setup is used to store and query the integrated RDF graphs. We executed parallel SemLAV with a timeout of 10 minutes.
Experiments are also run on the same platform than SemLAV experiments, i.e., on a Linux server with 128 GB of memory, 124 processors where 20 GB of RAM are allocated for the experiments. Wrappers are implemented for each view and to load data from RDF les, i.e., 476 wrappers are available.
We use critical section and lock to implement the single-reader/multiple-writers SRMW concurrency model in Jena 2.7.4. The number of threads impacts the SPARQL engine performance; thus, we consider this number as one of the independent parameters of our study.
The goal of the experiment is to study the impact of the non-blocking query execution criteria on the query engine performance. We hypothesize that parallel SemLAV will outperform SemLAV in terms of throughput and time for the rst answer. We measure the following metrics: i) total time (TT) in milliseconds; ii) time for rst answer (TFA) in milliseconds; iii) throughput (answer/millisecond); and iv) number of times the original query is executed (#EQ).
We evaluate parallel SemLAV for the non-blocking query execution criteria de ned in Section 3 with di erent number of threads, i.e., the number of writers and the con guration of the non-blocking query execution strategy. We use setups with di erent number of threads 5, 10, and 20. Results suggest that 20 threads is the best number for writers. All the results are available at the project web site https://sites.google.com/site/semanticlav. The View Dependent Criterion: The thread which executes the query is woken up when a new view is loaded. Table 3 shows the result of SemLAV and parallel SemLAV using the view strategy, i.e., re-execute the query after a new view is loaded. Parallel SemLAV outperforms SemLAV in terms of throughput and total execution time. But surprisingly, the time for rst answer is increased, for all queries except queries 2, 13, and 18; for these queries the time for the rst answer is at most half of the SemLAV time. In most queries the time for rst answer is increased because the number of times the original query is executed (#EQ) in parallel SemLAV is less than in SemLAV; furthermore, parallel SemLAV breaks the views ranking established by SemLAV, i.e., SemLAV starts by loading the view ranked in rst place and executes the query. However, parallel SemLAV loads views in parallel, and the query is re-executed when a new view is loaded, which is not necessarily the rst ranked view by SemLAV. In setups with 5 and 10 threads, the time for rst answer is better than for 20 threads, but the throughput is lower as shown in Tables 4 and 5. The Time Dependent Criterion: The thread which executes the query is woken up each 500 milliseconds. Table 6 shows the result of SemLAV and parallel SemLAV using the time dependent strategy for 20 threads. The results also show that parallel SemLAV outperforms SemLAV in terms of throughput and total execution time; however, the time for rst results is increased as when the view dependent criterion is executed. The Data Dependent Criterion: The query thread is woken up each time the integrated RDF graph grows up to 500 new triples. Table 7 shows the results of SemLAV and parallel SemLAV using data dependent strategy for 20 threads. As in previous experiments, parallel SemLAV outperforms SemLAV in terms of throughput and total execution time for all queries; but the time for the rst result is increased for the majority of the queries.
The Two-phase Criterion: The rst phase of this strategy performs an ASK query and when it returns true, the second phase is conducted. First, the second phase executes the original query, then the query engine will be woken up either each n milliseconds or when n triples are inserted into the integrated RDF graph. Table 8 reports on the results for the two-phase strategy when the query is executed whenever 500 triples are inserted into the integrated RDF graph. Parallel SemLAV outperforms SemLAV in terms of throughput for all the queries, but throughput values of parallel SemLAV are lower than in previous experiments. Table 9 summarizes the results of the throughput with 20 threads in the di erent empirical evaluations. In all experiments, parallel SemLAV outperforms SemLAV in terms of the throughput and total execution time. However, none of the de ned execution criterion dominates other criterion. For instance, parallel SemLAV with query execution every 500 milliseconds is the best execution strategy for query2; whereas parallel SemLAV with execution strategy whenever 500 triples have been inserted into the integrated RDF graph is the most suitable strategy for query5. We repeat the experiments with di erent number of threads. In setup with 20 threads, parallel SemLAV outperforms SemLAV in terms of throughput and total execution time but it increases time for rst answer. Preliminary results suggest that there is a tradeo between throughput and time for rst answer. To con rm these results, in the future, we plan to evaluate parallel SemLAV with di erent time and data setups. 5
We tackle the problem of executing SPARQL queries against LAV views in a parallel fashion. The query execution model relies on an RDF graph that temporally materializes the data retrieved from the relevant views of a SPARQL query. The query engine respects a concurrency model that prioritizes the execution of queries against the integrated RDF graph over loading data from the views. Additionally, a non-blocking query execution strategy allows for the execution of a SPARQL query on an RDF graph depending on di erent criteria. Similarly than SemLAV, our proposed parallel query execution model, named parallel SemLAV, was implemented on top of Jena. We empirically compared parallel SemLAV and SemLAV in terms of the impact of the non-blocking strategy on the query engine throughput. The observed results suggest that independently of the criterion followed by the non-blocking query engine strategy, parallel SemLAV outperforms SemLAV in terms of throughput. One limitation of our current implementation is inherent from the techniques implemented by Jena to handle concurrent insertions in an RDF graph. To overcome this limitation, we plan to consider a graph database engine as the RDF store backend, in order to provide more robust concurrency management of the RDF graph for incremental query processing.
We thank Maxime Pauvert and Nicolas Brondin, both students of the Computer Science Department at the University of Nantes for implementing the non-blocking strategy.