The performance of query answering in an RDF database strongly depends on the data layout, that is, the way data is split in persistent data structures. We consider answering Basic Graph Pattern Queries (BGPQs), and in particular those with variables (also) in class and property positions, in the presence of RDFS ontologies, both through data saturation and query reformulation. We show that such demanding queries often lead to ine cient query answering on two popular storage layouts, so-called T and CP. We present novel query answering algorithms on the TCP layout, which combines T and CP. In exchange to occupying more storage space, e.g. on an inexpensive disk, TCP avoids the bad or even catastrophic performance that T and/or CP sometimes exhibit. We also introduce summary-based pruning, a novel technique based on existing RDF quotient summaries, which improves query answering performance on the T, CP and the more robust TCP layouts.
We consider the problem of e ciently querying an RDF database, which stores
RDF graphs persistently (e.g., on a disk) and allows queries and updates on the
graphs, possibly concurrently by several users. We are interested in answering
queries on a graph, taking into account an RDF Schema (RDFS, in short)
ontology and associated RDFS entailment. We consider general SPARQL
conjunctive queries (a.k.a. basic graph pattern queries, or BGPQs), which
allow variables in any subject, property, or object position of query triples. For
instance, in the query q(x; u) (x; :name; :Alice); (x; y; z); (z; rdf:type; u), where
x; y; z; u are variables and the other terms are IRIs, the property y in the second
triple is a variable, just like u which is the type of z. Such queries allow to fully
take advantage of the freedom RDF provides: one does not need to know the
relation between x and z, nor the exact type of z, to query the graph.
Answering a BGPQ in an RDF database requires translating it into a description
of work that the execution engine must perform; without loss of generality, we
call this work description a query plan, as is common in the database literature.
Speci cally, we distinguish a logical plan specifying the operations to use to
answer the query, from a physical (executable) plan, derived from the logical one
with the help of statistics and cost parameters characterizing the data (size,
value frequencies etc.) and the execution environment (hardware etc.)
Both plans start by accessing some data from the store and continue with various
other processing steps (e.g., ltering, combining multiple inputs etc.). The set of
persistent data structures that hold the data of an RDF graph in the database
are called storage layout. When a set of frequent BGPQs are known in advance,
they can be used to design a workload-aware layout, which optimizes data access
for these queries, e.g., [
In this work, we focus on translating BGPQs, including general ones, for query answering under RDFS ontologies and entailment, into logical plans, on workload-unaware layouts. We target logical plans for generality, since physical plans strongly depend on the RDF database implementation, the presence of indexes etc.; these decisions are best left to the optimization and execution layer, and we do not study them here. However, as we will show, the choice of the logical plan can massively impact the space of alternatives (physical plans) considered for the query, and thus the query answering performance. In particular, we translate our plans in SQL (if the RDF database has a relational back-end) or SPARQL (if a native RDF engine evaluates them), which enables to retain all bene ts of system-speci c optimization. We study translation for the two classical ways of taking the ontology into account for query answering: by materializing entailed triples in the RDF graph (graph saturation) or by compiling relevant parts of the ontology in the query, which yields a union of BGPQs (query reformulation ). Our contributions are the following: 1. We introduce the novel workload-unaware TCP layout, which combines the data structures of both T and CP, and an associated algebraic translation of BGPQs into logical plans over TCP. 2. We introduce summary-based pruning, an optimization technique of independent interest, that reduces query answering costs on the T, CP and TCP layouts, both when using graph saturation and query reformulation. 3. We experimentally validate the performance bene ts of the TCP layout and translation, and of summary-based pruning, on a relational and a native RDF database. Our experiments are detailed online5 with the code and data necessary in order to reproduce them.
Below, after the preliminaries, Section 3 recalls algebraic query translations for
the T and CP layouts. We explain why nave algebraic translation on CP leads
to poor performance, not only for general BGPQs (as noted since [
We distinguish schema triples from data ones. The former state RDF Schema (RDFS) constraints on classes and properties: subclass (specialization relation between classes), subproperty (specialization relation between properties), domain (typing of the rst attribute of a property), and range (typing of the second attribute of a property). An RDFS ontology (or ontology, in short) is a set of schema triples. The ontology of an RDF graph G is the set of schema triples of G. The other triples, i.e., data triples, describe data by typing resources with classes or stating how resources are related through properties. Table 1 introduces our short notations for schema and data triples.
Example 1 (Running example). Figure 1 shows a sample graph Gex, describing articles and their authors; some articles are Open Access (:OpenArt), a subclass of which are Green Open Access ones (:GOpenArt).
An entailment rule (or simply rule) r has the form body(r) ! head(r), where
body(r) and head(r) are RDF graphs, respectively called body and head of the
rule r. In this work, we consider the set of RDFS entailment rules R shown
in Table 2, which allow reasoning with an RDFS ontology; in the table, all values
except RDF reserved IRIs are blank nodes. These rules either combine schema
triples to entail schema triples (rdfs5, rdfs11, ext1 to ext4), or combine schema
triples together with data triples to entail data triples (rdfs2, rdfs3, rdfs7 and
rdfs9). The saturation of a graph G with the rule set R, denoted GR, allows
materializing its semantics, by iteratively augmenting it with the triples it entails
using R, until reaching a xpoint; this process is nite [
Example 2. The saturation of Gex with R (Table 2) is: (Gex)R = Gex [ f(:GOpenArt; sc; :Article); (:teaches; -d; :Person); (: rstAuth; ,!r; :Person); (:Alice; ; :Prof); (:Bob; ; :Person); (:art1; :author; :Alice); (:art1; ; :OpenArt); (:Alice; ; :Person); (:art1; ; :Article)g Given a set of variables V disjoint from I [ B [ L , a basic graph pattern (BGP in short) is a set of triple patterns (or triples in short, when nonambiguous) belonging to (I [ B [ V ) (I [ V ) (I [ B [ L [ V ). The set of variables (resp. values: IRIs, blank nodes, literals and variables) occurring in a BGP P is denoted by Var(P) (resp. Val(P )). Note that a variable may occur in any position of a triple pattern. In particular, we say that a variable x occurs in property position for a triple of the form ( ; x; ) and in class position for a triple of the form ( ; ; x).
De nition 1 (BGPQ). A BGPQ q is of the form q(x) P , where P is a
BGP (also denoted body(q)) and x Var(P) are the answer variables of q.
For simplicity, below, we will assume that BGPQs have no blank nodes, as
it is well-known that these can be replaced by non-answer variables [
We distinguish query evaluation, whose result is just based on the explicit graph triples, from query answering that also accounts for its implicit triples. De nition 3 (Evaluation and answering). Let q be a (partially instantiated) BGPQ. The answer set to q on a graph G w.r.t. rule set R is: q(G; R) = fh'(x)i j ' homomorphism from body(q) to GRg. If x = ;, i.e., q is a Boolean query, q is true i q(G; R) = fhig. The evaluation of q on G, denoted q(G; ;), or q(G) in short, is obtained through homomorphisms from body(q) to G only. These notions and notations naturally extend to unions of (partially instantiated) BGPQs, or UBGPQs in short.
Example 3 (Example query). Consider the BGPQ asking who is writing which
kind of articles: q(x; y) (z; :author; x); (z; ; y); (y; sc; :Article). Its evaluation
on Gex is empty. However, the answer set of q on Gex w.r.t. R is q(Gex; R) =
fh:Alice; :GOpenArti, h:Alice; :OpenArti; h:Bob; :GOpenArti; h:Bob; :OpenArtig.
Many RDF data management systems use saturation-based query answering,
i.e., query evaluation on the previously saturated graph; clearly, from the above
de nition, q(G; R) = q(GR) holds. An alternative technique is
reformulationbased query answering, e.g., [
T (q) = q(./jcond ( T (t1); : : : ; T (tn)) where T , the query triple translation for the T layout, translates the i-th query triple ti(si; pi; oi) into an algebraic expression of the form scond(t), where t is the triple table, and scond is a (possibly empty) set of selections over the attributes of t; speci cally, if si (respectively, pi, oi) is an IRI or a literal, scond contains a predicate of the form S = si (and similarly for pi; oi); jcond is a conjunction of join predicates containing, for every variable appearing in several positions (in one or several triples) in q, an equality between the respective attributes in the T (ti) triple translations; nally q is a projection on the attributes from the (ti)'s corresponding to the answer variables of q, or the values to which such variables are bound in case of a partially instantiated query.
t1:O;t2:O(./t1:S=t2:S;t2:O=t3:S ( P =:author(t); P = (t); P = sc^O=:Article(t))) In the above, the selection P =:author(t) restricts the triples from the t table to those having the attribute P equal to :author. Similarly, P = (t) corresponds to the selection P = . On the atom t3, T applies a double selection P = sc^O=:Article(t), since t3 has only one variable in position S. Further, ./jcond=./t1:S=t2:S;t2:O=t3:S joins the three previous selections, where t1:S = t2:S and t2:O = t3:S respectively re ect the co-occurrences of variables z and y. The nal projection t1:O;t2:O returns the pairs of values obtained for (x; y). Reformulation-based query answering. Here, the graph G is stored in t (but not its saturation), and every incoming BGPQ q is reformulated into a (partially instantiated) UBGPQ QR = Sn
i=1 qi, whose algebraic translation on the T layout is the union of the algebraic translations of its (partially instantiated) BGPQs:
T (QR) = Sin=1 T (qi) Example 6. Consider again the example query q and its reformulation QR shown in Example 4. The algebraic translation T (QR) is:
t1:O;:OpenArt(./t1:S=t2:S ( P =:author(t); P = ^O=:OpenArt(t))
[ t1:O;:OpenArt(./t1:S=t2:S ( P =: rstAuth(t); P = ^O=:OpenArt(t))
[ t1:O;:OpenArt(./t1:S=t2:S ( P =:author(t); P = ^O=:GOpenArt(t))
[ t1:O;:OpenArt(./t1:S=t2:S ( P =: rstAuth(t); P = ^O=:GOpenArt(t))
[ t1:O;:GOpenArt(./t1:S=t2:S ( P =:author(t)); P = ^O=:GOpenArt(t))
[ t1:O;:GOpenArt(./t1:S=t2:S ( P =: rstAuth(t); P = ^O=:GOpenArt(t))
3.2 BGPQ answering on the CP layout
With the CP layout, an RDF graph is stored as a set of tables corresponding
to classes and properties: for each class c, there is a table tc(S) that stores all
subjects s of triples (s; ; c), and for each data or schema property p 6= , there is
a table tp(S; O) that stores all subject-object pairs (s; o) for triples (s; p; o). We
call any such tc a class table, and tp a property table. The CP layout speeds up
data access for queries which specify the class in every triple whose property is
and specify the property in every triple. However, as noted in [
CP (q) = q(./jcond ( CP (t1); ; CP (tn))) where q and jcond are de ned as for the T layout, and translation for the CP layout, is:
8> S; ;c( scond(tc)) if t = (s; ; c) with c 62 V (1) CP (t) = ><>:>SSCc;2Pp;C(O((sC;sPc;o(on()sd);([tp;)Sc))p)i2fiPft t==C(Ps(;(s(p;s;;o;p)x;)wo)wi)tihtifhpt x62=2V(sV[;xf; og) with x 2 V (((342))) CP , the query triple where C and P are, respectively, the set of classes and of properties other than in the queried graph, and scond is a (possibly empty) conjunction of selections, just as we de ned it for T , but over the class and property tables instead of the triple table t.
Example 7. The naive translation of the example query q on the CP layout is: t1:O;t2:O(./t1:S=t2:S;t2:O=t3:S ( S;:author;O(t:author);
s; ;:GOpenArt(t:GOpenArt) [ s; ;:OpenArt(t:OpenArt) [ s; ;:Article(t:Article)
[ s; ;:Prof (t:Prof ) [ s; ;:Person(t:Person) [ S; sc;O( O=:Article(t sc )))
Note that in cases (3) and (4) above, CP introduces unions under joins, as
illustrated by the previous example. This leads to suboptimal evaluation
performance in many data management engines, which may optimize and execute
e ciently a join over several data collections, but do not attempt to reorder
(commute) joins with unions. For instance, the query (x; :a; :a1), (x; y; z), (z; ; u),
(z; :b; :b1) translates into a plan that joins (among others) the union of all the
tables (for (x; y; z)) with the union of all class tables (for (z; ; u)). Most
systems execute this \literally", i.e., they build and materialize these two very large
unions, which is very costly, before joining them with the rst and last triple6.
To avoid such unions under joins, we rely on the notion of instantiation, which
has been used in various query answering techniques e.g., [
Example 8. The class instantiation qc;Gex of the example query q, where the only instantiated variable is y, is: q(x; :GOpenArt) [ q(x; :OpenArt) [ q(x; :Article) [ q(x; :Prof) [ q(x; :Person) (z; :author; x); (z; ; :GOpenArt); (:GOpenArt; sc; :Article) (z; :author; x); (z; ; :OpenArt); (:OpenArt; sc; :Article) (z; :author; x); (z; ; :Article); (:Article; sc; :Article) (z; :author; x); (z; ; :Prof); (:Prof; sc; :Article)
(z; :author; x); (z; ; :Person); (:Person; sc; :Article) Class and property instantiations extend from BGPQs to UBGPQs in the natural way. Given a UBGPQ of the form Q = q1 [ q2 [ qn, we set:
Qp;G = q1p;G [ q2p;G [ qnp;G and Qc;G = q1c;G [ q2c;G [ qnc;G
QG = (Qc;G)p;G [ (Qp;G)c;G 6We checked this on systems that disclose their query execution strategy; experiments with others who do not, con rm the same hypothesis (see Section 5). We need both terms of the above union, exactly in the case when some variable of Q appears both in a property and in a class position. These cases are rare and easy to detect, thus in practice we only use one of the unions as soon as we detect both are not needed. Crucially, (U)BGPQ instantiation is correct for saturation- and reformulation-based query answering. Intuitively, this is because instantiation enumerates all possible combinations of classes and properties that query reformulation or evaluation may nd in G.
We can now de ne the instantiation-based query translation. A BGPQ q is rst instantiated into qG = Sin=1 qi, then translated on the CP layout as: n CP (qG) = [ CP (qi)
i=1 [ Importantly, because qG does not contain any variable in class or property position, every nave translation CP (qi) within CP (qG) avoids both (3) or (4) in the CP triple transformation function. Hence, the translation avoids the introduction of unions under joins, with their potential bad impact on performance. Example 9. Consider the query q and its instantiation qGex = qc;Gex in Example 8. The instantiation-based translation of q corresponds to the nave translation of qGex :
t1:O;u(./t1:S=t2:S;t2:O=t3:S ( S;:author;O(t:author); u2f:GOpenArt;:OpenArt;:Article;:Prof;:Persong S; ;u(tu); S; sc;O( S=u;O=:Article(t sc )) Reformulation-based query answering. The graph G is again stored using the CP layout (but not saturated). In this case, answering a BGPQ q starts by computing its reformulation QR w.r.t. the ontology of G. Then, we obtain the answers q(G; R) either through CP (QR), the nave translation of QR, or through CP (QGR), the instantiation-based translation of QR, i.e., the nave translation
G ; as in the previous section, the algebraic translation of of its instantiation QR a UBGPQ is de ned as the union of the algebraic translations of its BGPQs. Instantiating QR generally increases its size, but, by removing variables in class and property positions, it avoids the unions under joins introduced in cases (3) and (4) by the CP triple translation function.
Example 10. Consider the query q and its reformulation QR from Example 4. Here, since no variable of QR occurs in class or property position, CP (QR) and
G ) lead to the same algebraic expression: CP (QR
t1:O;:OpenArt(./t1:S=t2:S ( S;:author;O(t:author); S; ;:OpenArt(t:OpenArt)) [ t1:O;:OpenArt(./t1:S=t2:S ( S;: rstAuth;O(t: rstAuth); S; ;:OpenArt(t:OpenArt)) [ t1:O;:OpenArt(./t1:S=t2:S ( S;:author;O(t:author); S; ;:GOpenArt(t:GOpenArt)) [ t1:O;:OpenArt(./t1:S=t2:S ( S;: rstAuth;O(t: rstAuth); S; ;:GOpenArt(t:GOpenArt)) [ t1:O;:GOpenArt(./t1:S=t2:S ( S;:author;O(t:author); S; ;:GOpenArt(t:GOpenArt)) [ t1:O;:GOpenArt(./t1:S=t2:S ( S;: rstAuth;O(t: rstAuth); S; ;:GOpenArt(t:GOpenArt)) 4
Below, we present our technical contributions: the TCP layout and its algebraic translation (Section 4.1), and summary-based pruning (Section 4.2).
BGPQ answering based on the TCP layout The TCP layout combines T and CP with the aim of getting the best of both, while avoiding the performance problems they respectively entail (Sections 3.1 and 3.2). Here, an RDF graph is stored both in the triple table t of the T layout and in the tc class and tp property tables of the CP layout. The rationale behind this is that CP is e cient to access triples when the data structures holding the triples we need to access are immediately clear from the query, and small ; this is the case with query triples of the form (s; ; c) or (s; p; o) for a known class c or property p. However, with query triples of the form (s; ; x) and (s; x; o), the CP translation introduces unions, typically executed before joins, degrading performance. Interestingly, direct access to a potentially large share of a graph's triples is exactly what the T layout supports well - thus our idea to combine them. As we show in the next section, this allows to signi cantly improve performance, at expense of some extra storage space, typically inexpensive since it is on disk. Saturation-based query answering. Let us assume that the saturation GR of a graph G is stored in the TCP layout. The answers to a BGPQ q t1; : : : ; tn are obtained through its algebraic transformation for the TCP layout: T CP (q) = q(./jcond ( T CP (t1); ; T CP (tn))) where q and jcond are de ned as for the T and CP layouts, and T CP , the query triple translation for the TCP layout, is:
CP (t) if t = (s; ; c) or t = (s; p; o) with c 62 V ; p 62 V [ f g
T CP (t) = T (t) otherwise, i.e., if t = (s; ; x) or t = (s; x; o) with x 2 V Importantly, T CP translates the triples that penalize the CP layout into t atoms, and never into a union: hence, T CP avoids the cases (3) and (4) of CP . Example 11. The translation of the example query for the TCP layout combines the T layout for the second triple and the CP layout for the others: t1:O;t2:O(./t1:S=t2:S;t2:O=t3:S ( S;:author;O(t:author); P = (t); S; sc;O( O=:Article(t sc )))) Reformulation-based query answering. Again, the answers to a query q are computed by evaluating the algebraic translation of its reformulation QR = Sin=1 qi, but now for the TCP layout:
T CP (QR) = Sin=1 T CP (qi) Example 12. Consider the query q(x; y; z) ! (x; ; z); (x; : rstAuth; y) asking for all resources with their type and rst author. Its reformulation w.r.t. Gex's ontology is shown below (the last four union terms are omitted for space reasons): q(x; y; z) (x; ; z); (x; : rstAuth; y) [ q(x; y; :Article) (x; ; :OpenArt); (x; : rstAuth; y) QR = [ q(x; y; :Article) (x; ; :GOpenArt); (x; : rstAuth; y) [ q(x; y; :OpenArt) (x; ; :GOpenArt); (x; : rstAuth; y) [ q(x; y; :Person) (x; ; :Prof); (x; : rstAuth; y) : : : Its algebraic translation on the TCP layout (similarly abridged) is: t1:S;t2:O;t1:O(./t1:S=t2:S ( P = (t); S;: rstAuth;O(t: rstAuth))) [ t1:S;t2:O;:Article(./t1:S=t2:S ( S; ;:OpenArt(t:OpenArt); S;: rstAuth;O(t: rstAuth))) [ t1:S;t2:O;:Article(./t1:S=t2:S ( S; ;:GOpenArt(t:GOpenArt); S;: rstAuth;O(t: rstAuth))) [ t1:S;t2:O;:OpenArt(./t1:S=t2:S ( S; ;:GOpenArt(t:GOpenArt); S;: rstAuth;O(t: rstAuth))) [ t1:S;t2:O;:Person(./t1:S=t2:S ( S; ;:Prof (t:Prof ); S;: rstAuth;O(t: rstAuth))) : : : Above, the rst union term refers to the triple table t, while the others do not. We now introduce an optimization technique, which can be applied on any storage layout to reduce (U)BGPQ answering time. It allows detecting some BGPQs with an empty answer set on a graph, without evaluating them, by using a (typically much smaller) structural summary of this graph.
Given an RDF graph G and an equivalence relation among the nodes in G, i.e.,
the subjects and objects of triples, an RDF quotient summary [
Q(G) = Qpruned(G) where Qpruned is the result of pruning Q. As our experiments will show, this generally leads to a signi cant reduction of query answering time. 5
We now describe experiments comparing the query answering methods presented
in the previous sections, on the T, CP and TCP layouts.
5.1 Experimental settings
We implemented the T, CP and TCP layouts in OntoSQL (https://ontosql.
inria.fr), a Java platform providing e cient RDF storage and saturation- and
reformulation-based query answering on top of an RDBMS [
For summary-based pruning, we used the RDFQuotient (https://rdfquotient.
inria.fr) tool to build the \typed strong" summary [
Hardware We used a server with 2,7 GHz Intel Core i7 processors and 160 GB of RAM, running CentOs Linux 7.5.
Graph jGj jG=TSj jGRj j(GR)=TSj jGjT jGjCP jGjTCP jGRjT jGRjCP jGRjTCP LUBM 100M 340 131M 439 28:95 11:95 37:89 32:52 13:52 39:31 DBLP 88M 290 147M 708 26:07 16:35 35:89 38:39 22:91 52:72 Table 3. Graph and summary sizes (number of triples), OntoSQL database sizes (in GB), including all indexes, for the T, CP and TCP layouts.
RDF graphs We used two benchmark graphs: a LUBM [
Queries We used two diverse sets of queries, having from 1 to 11 triples (4 on average) on LUBM, and from 2 to 9 triples (5.9 on average) on DBLP. Each query has 1 or 2 triple(s) of the form (s; ; x) and/or (s; x; o), except Q11 and Q15 on DBLP which do not contain any. Table 4 shows their number of answers, and the number of BGPQs in: their instantiation (qG), reformulation (QR), and instantiation of their reformulation (QGR), before and after summary-based Query Q01 Q02 Q03 Q04 Q05 Q06 Q07 Q08 Q09 Q10 Q11 Q12 Q13 Q14 jq(G; R)j 2.78M 0.59M 2.15M 1.72M 0.47M 2.77M 25K 3696 2003 17.35M 187 518K 857 9.85M jqGj 45 45 45 82 2025 45 45 82 3690 82 82 37 1369 82 j(qG)prunedj 45 45 45 67 1806 44 44 3 88 68 59 23 43 51 jj(QQGRRj )prunedj 134214087 11045696 12425669 664888 221110668 1283104 431417783 997 33662 1687988 997 622371 17932791 11118858829 jj(QQRGRj )prunedj 206 99 135 48 108 73 299 7 2 144 7 42 50 892 Query Q01 Q02 Q03 Q04 Q05 Q06 Q07 Q08 Q09 Q10 Q11 Q12 Q13 Q14 Q15 jq(G; R)j 72K 24K 96.3M 361K 4K 10 138 42K 1.52M 3.09M 957K 414K 409K 16.3K 460K jqGj 18 18 18 18 50 900 900 18 900 900 1 18 324 50 1 j(qG)prunedj 18 18 18 18 3 136 136 17 85 85 1 18 324 3 1 jj(QQGRRj )prunedj 12155726 224094570 124560158 12155726 1586271936 543920258779 332311466536 733262 115180041 32663522204 243363 328944 2310878148 112217940 2244333 jj(QQRGRj )prunedj 161 331 277 161 1224 3275 2189 37 1 64 3 69 1497 117 3 Table 4. Statistics of our queries on LUBM (top) and DBLP (bottom); M stands for millions and K for thousands.
T SAT T (q)(GR)
CP SAT NAIVE CP SAT INS CP SAT INS PRUN TCP SAT
CP (q)(GR) CP (qG)(GR) CP ((qG)pruned)(GR) T CP (q)(GR) VIRTUOSO SAT
T (q)(GR) 5.2 Experiment results: query answering times For each query, we report the average of the last ve (\hot") runs out of six. Through saturation Figure 2 shows the query answering times through saturation, for LUBM (top) and DBLP (bottom), with a timeout of 10 minutes; in all our graphs, executions that reached the timeout have been interrupted. Below the graphs, we show the label used in the plot for each query answering strategy, e.g., T SAT stands for T (q)(GR). For readability, some very fast queries are repeated in a \zoom" plot (the LUBM one has a logarithmic y axis). On LUBM (top), we notice some very high running times for VIRTUOSO SAT, e.g., on Q03, Q06, and a time-out on Q14. Among the SQL-based strategies, the nave translation on CP (green bars) is slowest in 10 out of 14 queries, with large performance penalties for Q04, Q07, Q08, Q11-13. Instantiation (CP SAT INS, red bars) is generally faster than nave CP. It strongly speeds up Q04, Q07, Q08, Q10-Q14; it brings a modest improvement to Q01 and Q05, but also a modest overhead for Q02, Q03, Q06. However, on the complex Q09, which has the largest qG size, namely 3690, instantiating each of these more than doubles the answering time w.r.t. nave CP translation (and ran until the timeout); pruning (yellow bars) brings it back below the timeout. T SAT is generally faster than all executions on the CP layout, because all queries contain triples of the form (s; ; x) and/or (s; x; o), which, as explained in Section 3.2, challenge CP execution. TCP SAT avoids the (sometimes drastic) performance problems of all CP variants, and is the fastest (by up to several orders of magnitude) on all queries but Q14, where the CP variant with pruning is a bit faster. Virtuoso is also always slower than TCP (by up to 95 , almost two orders of magnitude). On DBLP (bottom), poor performance is exhibited by Virtuoso (Q03, Q07, Q09, Q10), and on even more queries by the nave CP strategy (green bars, Q05Q07, Q09-Q10, Q14). T SAT performs very badly on Q09, Q10, Q14 and Q15. These are rather large (6 to 9-triples) queries; an analysis of their plans shows signi cant errors in the RDBMS' estimation of join cardinality. As is well-known, join cardinality estimation errors multiply along subsequent joins; when all joins carry over a single, very large table, the negative impact of such cumulated errors can be quite strong. Historically, this observation actually motivated the introduction of the CP layout, on which join estimation errors still multiply, but usually much smaller tables are involved. Indeed, as expected, for the queries Q11 and Q15, exactly those where no triple has a variable in class and property position, nave CP largely outperforms T SAT (by very far for Q15). Again, we observe the robust behavior of TCP SAT. We conclude that through saturation, T and CP execution each underperform on some queries, but TCP avoids all these pitfalls and is consistently very e cient.
Through reformulation Figure 3 shows reformulation-based query answering times (note the logarithmic y axis in the zoom), again with the correspondences between the bar labels and the strategy names previously used in the paper. On LUBM, among the evaluation strategies without pruning, TCP REF is generally the fastest (or very close to it), with the exception of Q14, where CP REF INS is 1:4 faster. This query with the most results (9.85M) and a large reformulation (Table 4) has two atoms of the form (x; p; z); (y; p; z). On CP, this leads to a large number of self-joins of the form tp ./o tp, executed very fast because loading tp in memory once ensures the join runs completely in-memory. While the rather unusual Q14 shows a case when CP may still out
T REF T REF PRUN CP REF INS CP REF INS PRUN T (QR)(G) T ((QR)pruned)(G) CP (QGR)(G) CP ((QGR)pruned)(G)
TCP REF TCP REF PRUN VIRTUOSO REF VIRTUOSO REF INS
T CP (QR)(G) T CP ((QR)pruned)(G) T (QR)(G) T (QGR)(G) Fig. 3. LUBM (top) and DBLP (bottom) query answering times (ms) through reformulation. perform TCP, the di erence is not dramatic. On the three layouts, pruning generally helps: it saves, e.g., more than half of the CP answering time for Q01, Q02. In the zoomed view (shortest-running queries), pruning brings an overhead (takes more time that the query evaluation time it saves) of a few milliseconds. Among the strategies with pruning, TCP REF PRUN is the fastest, except for Q14 discussed above. As Virtuoso did not support reasoning with our rule set R (details online5), we gave it reformulations expressed in SPARQL; for Q07 and Q14, they failed to run, with the error \union nesting is too deep". The impact of instantiation for Virtuoso is unclear; it helped for Q04, Q08 but not for Q02, Q06 etc. All missing Virtuoso bars in Figure 3 are execution failures, mostly due to large unions.
On DBLP, VIRTUOSO REF failed for Q06, Q07, Q09, Q10, Q13; VIRTUOSO REF INS was consistently worse, and we omitted it from the plot. The rest of the analysis is similar to the one above, except that T REF performs very badly in a few cases (Q07, Q11). Overall, in Figure 3, TCP query answering with pruning is the fastest, or very close to it, on all queries, while all other strategies's weaknesses are exposed by one or more queries. 5.3 Experiment conclusion We studied the performance of query answering in RDF databases through saturation and reformulation, on challenging queries that remain poorly supported: those with variables in class or property position. We have exhibited queries that lead to poor to catastrophic performance of query answering on the T layout (mainly due to many self-joins on a large table) and/or on the CP layout (mainly due to large unions, brought by variables in class and property positions, and/or by reformulation). Query answering on the TCP layout is extremely robust; it avoids all these pitfalls by taking the best of both T and CP, at the expense of more storage space. As disks are getting ever cheaper7, TCP appears to be a robust, practical layout, compatible with well-established large-scale RDF storage and query engines. For the challenging queries we study, summary-based pruning helps improve performance, in particular for the TCP layout.
Our work studies the impact of RDF graph storage on query answering in
the presence of RDFS ontologies, both through graph saturation (SatQA) and
query reformulation (RefQA). Prior works such as [