The time of answering a SPARQL query with its all exact solutions in large scale RDF dataset possibly exceeds users' tolerable waiting time, especially when it contains the OPT operations. It becomes essential to make a trade-o between the query response time and solution accuracy. We propose PRONA - an plugin for well-designed approximate queries in Jena, which provides help for users to answer well-designed SPARQL queries by approximate computation. The main features of PRONA comprise SPARQL query engine with approximate queries, as well as various approximate degrees for users to choose.
Resource Description Framework (RDF) is the standard data model in the Semantic Web. SPARQL recommended by W3C has become the standard language for querying RDF data since 2008.
OPT operation takes an core role in UNION-free well-designed patterns. For
simpli cation, we directly call well-designed patterns instead of UNION-free
welldesigned patterns. OPT operation aims to extend solutions for users[
Q = ((?x; rdf:type; artist) OPT ((?x; country; ?y) OPT (?x; company; ?z))).
Based on this natural idea, there are two approximate patterns with less OPT operators as follows: { Q1 = (?x; rdf:type; artist); { Q2 = ((?x; rdf:type; artist) OPT (?x; country; ?y)).
However, consider Q3 = ((?x; rdf:type; artist) OPT (?xcompany; ?z)), it is not
approximate query since (?x; company; ?z) directly depends on (?x; country; ?y).
The notion of approximation has been proposed in [
In this paper, we focus on well-designed SPARQL queries, whose \optional"
parts are really optional. Moreover, it is maximal among all fragments of LSQ
[
OPT Normal Form A UNION-free pattern P is in OPT normal form [
For instance, the pattern Q stated in Section 1 is in OPT normal form.
Three rewriting rules[
Well-Designed Patterns A UNION-free pattern P is well-designed if the followings hold: { P is safe, that is, each subpattern of the form Q FILTER C of P holds the condition: var (C) var (Q). { for every subpattern P 0 = (P1 OPT P2) of P and for every variable ?x occurring in P , the following condition hold: If ?x occurs both inside P2 and outside P 0, then it also occurs in P1.
For instance, the pattern Q in Section 1 is a well-designed pattern.
Note that the OPT operation provides really optional left-outer join due to
the weak monotonicity [
OPT-depth in OPT Normal Form To characterize the di erent levels of optional patterns, we de ne OPT-depth of patterns in OPT normal form. De nition 1 (OPT-depth). Let P be a pattern in OPT normal form. We use dep(P ) to denote its OPT-depth as follows: { dep(P ) = 0 if P is an AF -pattern; { dep(P ) = maxfdep(P1); : : : ; dep(Pm)g + 1 if O(P ) = fP1; : : : ; Pmg.
For instance, the OPT-depth of the pattern Q stated in Section 1 is 2.
Approximate Queries Intuitively, approximate patterns are subpatterns obtained by reducing their OPT-depths.
De nition 2 (k-approximation). Let P be a pattern in OPT normal form (P0 OPT P1 OPT : : : OPT Pm) and k be a natural number. The k-approximate pattern of P (written as P (k)) can be obtained in the following inductive way: 1;
P (k) is more closed to P with higher value of k. For instance, in Section 1, Q(0) = Q1 and Q(1) = Q2. 4
PRONA Overview PRONA is written in Java in a 3-tier design shown in Figure 1(a). The bottom layer consists of the Jena framework and the ARQ4 query engine, both used as a black box for evaluating queries. Before answering SPARQL queries, the second layer provides the rewriting process and approximation evaluation, which lead to the generation of approximate queries.
GUI is shown in Figure 1(b). For single query solution s, we denote its amount of domain as dom(s). For instance, consider solution = f?x ! a; ?y ! bg, dom( )=2. Given an approximate query solution S, which contains solution s1, s2, , sn. It is notable that the total of domain (dom(s1) + dom(s2) + + dom(sn)) re ects solution precision.
(a) PRONA architecture
(b) PRONA GUI
Experiments The purpose of our experiments is to evaluate (1) the performance improvement of approximate well-designed SPARQL queries, and (2) the solution precision percentage after approximate queries.
In our experiments, LUBM5 is used as dataset. Two 4-approximation welldesigned SPARQL queries are designed. Q1 contains 4 OPT operators, 6 triple patterns and 6 variables. Q2 contains 14 OPT operators, 17 triple patterns and 16 variables. Approximate solution precision dividing original query solution precision leads to the solution precision percentage.
It has shown in Figure 2 and Figure 3 that both query response time and solution precision reduce with the increment of approximate degree (k value 4 http://jena.sourceforge.net/ARQ 5 http://swat.cse.lehigh.edu/projects/lubm decreases). Solution precision percentage decreases about 10% with 25% query response time decreasing when k changes from 4 to 3 in Figure 3. 100
LUBM1 LUBM5
LUBM10 0 1 2 3
k (a) Performance (b) Solution Precision Percentage(%)
In this paper, we propose PRONA which helps users answer well-designed SPARQL queries by approximate computation. In the future, we are going to handle other non-well-designed patterns and deal with more operations such as UNION. Acknowledgement. This work is supported by the program of the National Key Research and Development Program of China (2016YFB1000603) and the National Natural Science Foundation of China (NSFC) (61502336).