# Revisiting RDF storage layouts for efficient query answering

Maxime Buron, François Goasdoué, Ioana Manolescu, Tayeb Merabti,
Marie-Laure Mugnier

► To cite this version:

Maxime Buron, François Goasdoué, Ioana Manolescu, Tayeb Merabti, Marie-Laure Mugnier. Revisiting RDF storage layouts for efficient query answering. SSWS 2020 - 13th International Workshop on Scalable Semantic Web Knowledge Base Systems, Nov 2020, Athène, Greece. pp.17-32. hal-02921457

HAL Id: hal-02921457

https://inria.hal.science/hal-02921457

Submitted on 25 Aug 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Revisiting RDF storage layouts for efficient
query answering

M. Buron¹,², F. Goasdoué³, I. Manolescu¹,², T. Merabti¹,², and M.-L. Mugnier⁴

¹ Inria firstname.lastname@inria.fr

² Institut Polytechnique de Paris, France

³ Univ Rennes, CNRS, IRISA, France fg@irisa.fr

⁴ Univ Montpellier, LIRMM, Inria, France mugnier@lirmm.fr

**Abstract.** 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 inefficient 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.

# 1 Introduction

We consider the problem of efficiently 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) \leftarrow (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. Specifically, 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., filtering, 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., [7,15,20]. Lacking a known query set, a workload-unaware layout is used, with the two most popular being: **T (triple)**, e.g., [8,25,19], which stores all triples together as a single (*s*,*p*,*o*) (subject, predicate, object) collection; and **CP (class and property)** [4], which separates the data for each property and class, i.e., as (i) a collection of (*s*,*o*) pairs for every property *p*, and (ii) a collection of all the resources *s* that have a given type *c* in the graph. Indexes can be added to both the T and CP layouts.

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 benefits of system-specific 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 benefits* of the TCP layout and translation, and of summary-based pruning, on a relational and a native RDF database. Our experiments are detailed online<fnref n="5" /> 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 naïve algebraic translation on CP leads to *poor performance*, not only for *general BGPQs* (as noted since [21]), but also for *reformulated ones* (whether general or not). This is due to *interleaved joins and unions*, which limit the optimization opportunities in the RDF database. At the same time, the T layout entails repeated self-joins of the whole triple set, degrading performance on large graphs and complex queries (this motivated

<footnote n="5">⁵https://gitlab.inria.fr/mburon/graph-layout-experiments</footnote>
<table><thead><tr><th>RDFS constraint</th><th>Schema triple notation</th><th>RDFS constraint</th><th>Schema triple notation</th></tr></thead><tbody><tr><td>Subclass</td><td>(s, &lt;sc, o)</td><td>Subproperty</td><td>(s, &lt;sp, o)</td></tr><tr><td>Domain typing</td><td>(s, &larr;d, o)</td><td>Range typing</td><td>(s, &larr;r, o)</td></tr></tbody></table>

<table><caption>**Table 1.** RDF statements.</caption><thead><tr><th>RDF assertion</th><th>Data triple notation</th></tr></thead><tbody><tr><td>Class assertion</td><td>(s, τ, o)</td></tr><tr><td>Property assertion</td><td>(s, p, o) with p &notin; {τ, &lt;sc, &lt;sp, &larr;d, &larr;r}</td></tr></tbody></table>

<table><caption>**Fig. 1.** Sample RDF graph $G_{ex}$ (schema triples on top and data triples below).</caption><tr><td>G<sub>ex</sub> =</td><td>(:OpenArt, &lt;sc, :Article), (:GOpenArt, &lt;sc, :OpenArt), (:Prof, &lt;sc, :Person), (:teaches, &larr;d, :Prof), (:author, &larr;r, :Person), (:firstAuth, &lt;sp, :author), (:art1, :title, "RDF storage"), (:Alice, :name, "Alice") (:art1, :firstAuth, :Alice), (:Alice, :teaches, :algo101), (:art1, :author, :Bob), (:Bob, :name, "Bob"), (:art1, rdf:type, :GOpenArt)</td></tr></table>

introducing the CP layout [4]). Section 4 presents our technical contributions and Section 5 our experiments. We then discuss related works and conclude.

## 2 Preliminaries

We rely on three pairwise disjoint sets of values: the sets $\mathcal{I}$ of IRIs (resource identifiers), $\mathcal{L}$ of literals (constants) and $\mathcal{B}$ of blank nodes modeling unknown IRIs or literals. A triple $(s, p, o) \in (\mathcal{I} \cup \mathcal{B}) \times \mathcal{I} \times (\mathcal{L} \cup \mathcal{I} \cup \mathcal{B})$ states that its subject $s$ has the property $p$ with the object value $o$ [1]. We denote by $Val(G)$ the set of all values (IRIs, blank nodes and literals) occurring in an RDF graph $G$. In triples, we use $:b$ (possibly with indices) to denote blank nodes, and strings between quotes to denote literals.

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), **do-main** (typing of the first 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 $G_{ex}$, 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) \rightarrow 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** $\mathcal{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
<table><caption>**Table 2.** Sample set $\mathcal{R}$ of RDFS entailment rules.</caption><thead><tr><th>Name [2]</th><th>Entailment rule</th><th>Name</th><th>Entailment rule</th></tr></thead><tbody><tr><td>rdfs5</td><td>(p<sub>1</sub>, &lt;sp, p<sub>2</sub>), (p<sub>2</sub>, &lt;sp, p<sub>3</sub>) → (p<sub>1</sub>, &lt;sp, p<sub>3</sub>)</td><td>ext4</td><td>(p, &lt;sp, p<sub>1</sub>), (p<sub>1</sub>, ↪<sub>r</sub>, o) → (p, ↪<sub>r</sub>, o)</td></tr><tr><td>rdfs11</td><td>(s, &lt;sc, o), (o, &lt;sc, o<sub>1</sub>) → (s, &lt;sc, o<sub>1</sub>)</td><td>rdfs2</td><td>(p, ↪<sub>d</sub>, o), (s<sub>1</sub>, p, o<sub>1</sub>) → (s<sub>1</sub>, τ, o)</td></tr><tr><td>ext1</td><td>(p, ↪<sub>d</sub>, o), (o, &lt;sc, o<sub>1</sub>) → (p, ↪<sub>d</sub>, o<sub>1</sub>)</td><td>rdfs3</td><td>(p, ↪<sub>r</sub>, o), (s<sub>1</sub>, p, o<sub>1</sub>) → (o<sub>1</sub>, τ, o)</td></tr><tr><td>ext2</td><td>(p, ↪<sub>r</sub>, o), (o, &lt;sc, o<sub>1</sub>) → (p, ↪<sub>r</sub>, o<sub>1</sub>)</td><td>rdfs7</td><td>(p<sub>1</sub>, &lt;sp, p<sub>2</sub>), (s<sub>1</sub>, p<sub>1</sub>, o) → (s<sub>1</sub>, p<sub>2</sub>, o)</td></tr><tr><td>ext3</td><td>(p, &lt;sp, p<sub>1</sub>), (p<sub>1</sub>, ↪<sub>d</sub>, o) → (p, ↪<sub>d</sub>, o)</td><td>rdfs9</td><td>(s, &lt;sc, o), (s<sub>1</sub>, τ, s) → (s<sub>1</sub>, τ, o)</td></tr></tbody></table>

rdfs9). The saturation of a graph $G$ with the rule set $\mathcal{R}$, denoted $G^{\mathcal{R}}$, allows materializing its semantics, by iteratively augmenting it with the triples it entails using $\mathcal{R}$, until reaching a fixpoint; this process is finite [2].

*Example 2.* The saturation of $G_{ex}$ with $\mathcal{R}$ (Table 2) is: $(G_{ex})^{\mathcal{R}} = G_{ex} \cup \{((:GOpenArt, \prec_{sc}, :Article), (:teaches, \leftrightarrow_d, :Person), (:firstAuth, \leftrightarrow_r, :Person), (:Alice, \tau, :Prof), (:Bob, \tau, :Person), (:art1, :author, :Alice), (:art1, \tau, :OpenArt), (:Alice, \tau, :Person), (:art1, \tau, :Article)\}$

Given a set of variables $\mathcal{V}$ disjoint from $\mathcal{I} \cup \mathcal{B} \cup \mathcal{L}$, a basic graph pattern (BGP in short) is a set of triple patterns (or triples in short, when non-ambiguous) belonging to $(\mathcal{I} \cup \mathcal{B} \cup \mathcal{V}) \times (\mathcal{I} \cup \mathcal{V}) \times (\mathcal{I} \cup \mathcal{B} \cup \mathcal{L} \cup \mathcal{V})$. The set of variables (resp. values: IRIs, blank nodes, literals and variables) occurring in a BGP $P$ is denoted by $\text{Var}(P)$ (resp. $\text{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 $(-, \tau, x)$.

**Definition 1 (BGPQ).** A BGPQ $q$ is of the form $q(\bar{x}) \leftarrow P$, where $P$ is a BGP (also denoted body($q$)) and $\bar{x} \subseteq \text{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 [3]. We also consider a slight generalization of BGPQs, namely **partially instantiated** BGPQs: such queries are obtained from BGPQs by substituting some variables with values from $\mathcal{I} \cup \mathcal{L} \cup \mathcal{B}$. For simplicity again, we will not distinguish between a standard and a partially instantiated BGPQ. The semantics of a BGPQ on a graph is defined through homomorphisms from the query body to the graph:

**Definition 2 (BGP-to-RDF homomorphism).** A homomorphism from a BGP $P$ to an RDF graph $G$ is a function $\varphi$ from $\text{Val}(P)$ to $\text{Val}(G)$ such that for any triple $(s, p, o) \in P$, the triple $(\varphi(s), \varphi(p), \varphi(o))$ is in $G$, with $\varphi$ the identity on IRIs and literals.

We distinguish **query evaluation**, whose result is just based on the explicit graph triples, from **query answering** that also accounts for its implicit triples.

**Definition 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 $\mathcal{R}$ is: $q(G, \mathcal{R}) = \{\langle\varphi(\bar{x})\rangle | \varphi \text{ homomorphism from body}(q) \text{ to } G^{\mathcal{R}}\}$. If $\bar{x} = \emptyset$, i.e., $q$ is a Boolean query, $q$ is true iff $q(G, \mathcal{R}) = \{\langle\rangle\}$. The evaluation of $q$ on $G$, denoted $q(G, \emptyset)$, 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) \leftarrow (z, :author, x), (z, \tau, y), (y, \prec_{sc}, :Article)$. Its evaluation on $G_{ex}$ is empty. However, the answer set of $q$ on $G_{ex}$ w.r.t. $\mathcal{R}$ is $q(G_{ex}, \mathcal{R}) = \{\langle :Alice, :GOpenArt \rangle, \langle :Alice, :OpenArt \rangle, \langle :Bob, :GOpenArt \rangle, \langle :Bob, :OpenArt \rangle \}.$

Many RDF data management systems use **saturation-based** query answering, i.e., query evaluation on the previously saturated graph; clearly, from the above definition, $q(G, \mathcal{R}) = q(G^{\mathcal{R}})$ holds. An alternative technique is **reformulation-based** query answering, e.g., [6,18,9], which injects the ontological knowledge into a reformulated query, whose simple evaluation on $G$ yields the complete answer set of the original query. More precisely, given a BGPQ $q$ asked on a graph $G$, the reformulation of $q$ w.r.t. $\mathcal{R}$ and the ontology of $G$, denoted $Q_{\mathcal{R}}$, is such that $q(G, \mathcal{R}) = Q_{\mathcal{R}}(G)$. A property of the technique proposed in [9], on which we rely in this paper, is that the reformulated query does not contain schema triples anymore; intuitively, such triples are evaluated on the ontology of the queried graph during the query reformulation. Further, from now on, we assume that (U)BGPQs, in particular those produced through reformulation, are *minimal*: non-minimality incurs redundancy of triples in BGPQs, or of BGPQs within UBGPQs. Well-known query minimization techniques exist for this purpose.

*Example 4.* The reformulation of the example query $q$ (Example 3) is:

$$ 
\begin{aligned}
q(x, :OpenArt) & \leftarrow (z, :author, x), (z, \tau, :OpenArt) \\
\cup q(x, :OpenArt) & \leftarrow (z, :firstAuth, x), (z, \tau, :OpenArt) \\
Q_{\mathcal{R}} = & \cup q(x, :OpenArt) \leftarrow (z, :author, x), (z, \tau, :GOpenArt) \\
& \cup q(x, :OpenArt) \leftarrow (z, :firstAuth, x), (z, \tau, :GOpenArt) \\
& \cup q(x, :GOpenArt) \leftarrow (z, :author, x), (z, \tau, :GOpenArt) \\
& \cup q(x, :GOpenArt) \leftarrow (z, :firstAuth, x), (z, \tau, :GOpenArt)
\end{aligned}
$$

It can be checked that $Q_{\mathcal{R}}(G_{ex}) = q(G_{ex}, \mathcal{R})$.

# 3 BGPQ answering through translation on T and CP

We now detail how (saturation- or reformulation-based) query answering can be performed on the T and the CP storage layouts (Sections 3.1 and 3.2).

## 3.1 BGPQ answering on the T layout

Let $t(S, P, O)$ be the table storing the triples of a graph $G$ for the T layout.

*Saturation-based query answering.* The saturation $G^{\mathcal{R}}$ of $G$ is stored in the table $t$. The algebraic translation of a BGPQ $q(\bar{x}) \leftarrow t_1, \dots, t_n$ on the T layout is:

$$ T(q) = \pi_q(\bowtie_{jcond} (\alpha_T(t_1), \dots, \alpha_T(t_n))) $$

where $\alpha_T$, the query triple translation for the T layout, translates the $i$-th query triple $t_i(s_i, p_i, o_i)$ into an algebraic expression of the form $\sigma_{scond}(t)$, where $t$ is the triple table, and $scond$ is a (possibly empty) set of selections over the attributes of $t$; specifically, if $s_i$ (respectively, $p_i, o_i$) is an IRI or a literal, $scond$ contains a predicate of the form $S = s_i$ (and similarly for $p_i, o_i$); $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
$\alpha_T(t_i)$ triple translations; finally $\pi_q$ is a projection on the attributes from the $\alpha(t_i)$'s corresponding to the answer variables of $q$, or the values to which such variables are bound in case of a partially instantiated query.

*Example 5.* The example query translates on the T layout as:

$$ \pi_{t_1.O,t_2.O}(\bowtie_{t_1.S=t_2.S,t_2.O=t_3.S} (\sigma_{P=:\text{author}}(t), \sigma_{P=\tau}(t), \sigma_{P=\prec_{sc}\wedge O=:\text{Article}}(t))) $$

In the above, the selection $\sigma_{P=:\text{author}}(t)$ restricts the triples from the t table to those having the attribute P equal to :author. Similarly, $\sigma_{P=\tau}(t)$ corresponds to the selection $P = \tau$. On the atom $t_3$, $\alpha_T$ applies a double selection $\sigma_{P=\prec_{sc}\wedge O=:\text{Article}}(t)$, since $t_3$ has only one variable in position S. Further, $\bowtie_{jcond}=\bowtie_{t_1.S=t_2.S,t_2.O=t_3.S}$ joins the three previous selections, where $t_1.S = t_2.S$ and $t_2.O = t_3.S$ respectively reflect the co-occurrences of variables z and y. The final projection $\pi_{t_1.O,t_2.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 $Q_R = \bigcup_{i=1}^n q_i$, whose algebraic translation on the T layout is the union of the algebraic translations of its (partially instantiated) BGPQs:

$$ T(Q_R) = \bigcup_{i=1}^{n} T(q_i) $$

*Example 6.* Consider again the example query q and its reformulation $Q_R$ shown in Example 4. The algebraic translation $T(Q_R)$ is:

$$ \begin{aligned} & \pi_{t_1.O;\text{OpenArt}}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=:\text{author}}(t), \sigma_{P=\tau\wedge O=:\text{OpenArt}}(t))) \\ \cup & \pi_{t_1.O;\text{OpenArt}}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=:\text{firstAuth}}(t), \sigma_{P=\tau\wedge O=:\text{OpenArt}}(t))) \\ \cup & \pi_{t_1.O;\text{OpenArt}}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=:\text{author}}(t), \sigma_{P=\tau\wedge O=:\text{GOpenArt}}(t))) \\ \cup & \pi_{t_1.O;\text{OpenArt}}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=:\text{firstAuth}}(t), \sigma_{P=\tau\wedge O=:\text{GOpenArt}}(t))) \\ \cup & \pi_{t_1.O;\text{GOpenArt}}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=:\text{author}}(t)), \sigma_{P=\tau\wedge O=:\text{GOpenArt}}(t))) \\ \cup & \pi_{t_1.O;\text{GOpenArt}}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=:\text{firstAuth}}(t), \sigma_{P=\tau\wedge O=:\text{GOpenArt}}(t))) \end{aligned} $$

## 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 $t_c(S)$ that stores all subjects s of triples $(s, \tau, c)$, and for each data or schema property $p \neq \tau$, there is a table $t_p(S, O)$ that stores all subject-object pairs $(s, o)$ for triples $(s, p, o)$. We call any such $t_c$ a class table, and $t_p$ a property table. The CP layout speeds up data access for queries which specify the class in every triple whose property is $\tau$ and specify the property in every triple. However, as noted e.g., in [21], it may render the evaluation of general queries, with variables in class or property position, inefficient, as the triples they refer to may be in any $t_c$ or $t_p$ tables, respectively.

*Saturation-based query answering.* Assume that $G^R$ is stored using the CP layout. To obtain the answers to a BGPQ $q(\bar{x}) \leftarrow t_1, \dots, t_n$, a first simple naïve translation, which can be traced back to [4,21], is:

$$ CP(q) = \pi_q(\bowtie_{jcond} (\alpha_{CP}(t_1), \dots, \alpha_{CP}(t_n))) $$
where $\pi_q$ and $jcond$ are defined as for the T layout, and $\alpha_{CP}$, the query triple translation for the CP layout, is:

$$ \alpha_{CP}(t) = \begin{cases} \pi_{S,\tau,c}(\sigma_{scond}(t_c)) & \text{if } t = (s, \tau, c) \text{ with } c \notin \mathcal{V} \quad (1) \\ \pi_{S,p,O}(\sigma_{scond}(t_p)) & \text{if } t = (s, p, o) \text{ with } p \notin \mathcal{V} \cup \{\tau\} \quad (2) \\ \bigcup_{c \in C} \alpha_{CP}((s, \tau, c)) & \text{if } t = (s, \tau, x) \text{ with } x \in \mathcal{V} \quad (3) \\ \alpha_{CP}((s, \tau, o)) \cup \bigcup_{p \in P} \alpha_{CP}((s, p, o)) & \text{if } t = (s, x, o) \text{ with } x \in \mathcal{V} \quad (4) \end{cases} $$

where $C$ and $P$ are, respectively, the set of classes and of properties other than $\tau$ in the queried graph, and $scond$ is a (possibly empty) conjunction of selections, just as we defined it for $\alpha_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:

$$ \begin{aligned} & \pi_{t_1.O,t_2.O}(\bowtie_{t_1.S=t_2.S,t_2.O=t_3.S}(\pi_{S,:author,O}(t:author), \\ & \quad \pi_{s,\tau,:GOpenArt}(t:GOpenArt) \cup \pi_{s,\tau,:OpenArt}(t:OpenArt) \cup \pi_{s,\tau,:Article}(t:Article) \\ & \quad \cup \pi_{s,\tau,:Prof}(t:Prof) \cup \pi_{s,\tau,:Person}(t:Person) \cup \pi_{S,<sc,O}(\sigma_{O=:Article}(t_{<sc}))) \end{aligned} $$

Note that in cases (3) and (4) above, $\alpha_{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 efficiently a join over several data collections, but do not attempt to reorder (commute) joins with unions. For instance, the query $(x, :a, :a_1)$, $(x, y, z)$, $(z, \tau, u)$, $(z, :b, :b_1)$ 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, \tau, 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 first and last triple<fnref n="6" />. To avoid such unions under joins, we rely on the notion of instantiation, which has been used in various query answering techniques e.g., [15,18]:

**Query instantiation.** The instantiation of a BGPQ $q$ consists in instantiating the variables in $q$ that must be bound to classes and properties of the queried graph, in all possible ways, which yields a (partially instantiated) UBGPQ. Given a BGPQ $q$ and a graph $G$, we denote by $q^{p,G}$ (resp. $q^{c,G}$) its property instantiation (resp. class instantiation), which is the UBGPQ obtained by instantiating all its variables in property position (resp. in class position), by all combinations of properties (resp. classes) of $G$.

**Example 8.** The class instantiation $q^{c,G_{ex}}$ of the example query $q$, where the only instantiated variable is $y$, is:

$$ \begin{aligned} & q(x, :GOpenArt) \leftarrow (z, :author, x), (z, \tau, :GOpenArt), (\text{GOpenArt}, <_{sc}, :Article) \\ & \cup q(x, :OpenArt) \leftarrow (z, :author, x), (z, \tau, :OpenArt), (\text{OpenArt}, <_{sc}, :Article) \\ & \cup q(x, :Article) \leftarrow (z, :author, x), (z, \tau, :Article), (\text{Article}, <_{sc}, :Article) \\ & \cup q(x, :Prof) \leftarrow (z, :author, x), (z, \tau, :Prof), (\text{Prof}, <_{sc}, :Article) \\ & \cup q(x, :Person) \leftarrow (z, :author, x), (z, \tau, :Person), (\text{Person}, <_{sc}, :Article) \end{aligned} $$

<footnote n="6">⁶We checked this on systems that disclose their query execution strategy; experiments with others who do not, confirm the same hypothesis (see Section 5).</footnote>
Class and property instantiations extend from BGPQs to UBGPQs in the natural way. Given a UBGPQ of the form $Q = q^1 \cup q^2 \cdots \cup q^n$, we set:

$$Q^{p,G} = q_1^{p,G} \cup q_2^{p,G} \cdots \cup q_n^{p,G} \quad \text{and} \quad Q^{c,G} = q_1^{c,G} \cup q_2^{c,G} \cdots \cup q_n^{c,G}$$

Then, the *instantiation* of $Q$ w.r.t. a graph $G$ is the following:

$$Q^G = (Q^{c,G})^{p,G} \cup (Q^{p,G})^{c,G}$$

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 find in $G$.

We can now define the *instantiation-based query translation*. A BGPQ $q$ is first instantiated into $q^G = \bigcup_{i=1}^n q^i$, then translated on the CP layout as:

$$CP(q^G) = \bigcup_{i=1}^{n} CP(q^i)$$

Importantly, because $q^G$ does not contain any variable in class or property position, every naïve translation $CP(q^i)$ within $CP(q^G)$ avoids both (3) or (4) in the $\alpha_{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 $q^{G_{ex}} = q^{c,G_{ex}}$ in Example 8. The instantiation-based translation of $q$ corresponds to the naïve translation of $q^{G_{ex}}$:

$$\bigcup_{u \in \{\text{GOpenArt}, \text{OpenArt}, \text{Article}, \text{Prof}, \text{Person}\}} \pi_{t_1.O.u}(\boxplus_{t_1.S=t_2.S,t_2.O=t_3.S} (\pi_{S,:\text{author}}, O(t,:\text{author})), \\ \pi_{S,\tau,u}(t_u), \\ \pi_{S,<_{sc},O}(\sigma_{S=u,O=:\text{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 $Q_R$ w.r.t. the ontology of $G$. Then, we obtain the answers $q(G, \mathcal{R})$ either through $CP(Q_R)$, the naïve translation of $Q_R$, or through $CP(Q_R^G)$, the instantiation-based translation of $Q_R$, i.e., the naïve translation of its instantiation $Q_R^G$; as in the previous section, the algebraic translation of a UBGPQ is defined as the union of the algebraic translations of its BGPQs. Instantiating $Q_R$ 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 $\alpha_{CP}$ triple translation function.

**Example 10.** Consider the query $q$ and its reformulation $Q_R$ from Example 4. Here, since no variable of $Q_R$ occurs in class or property position, $CP(Q_R)$ and $CP(Q_R^G)$ lead to the same algebraic expression:
$$
\begin{align*}
& \pi_{t_1.O;OpenArt}(\boxtimes_{t_1.S=t_2.S} (\pi_{S;author,O}(t;author), \pi_{S,\tau;OpenArt}(t;OpenArt))) \\
\cup & \pi_{t_1.O;OpenArt}(\boxtimes_{t_1.S=t_2.S} (\pi_{S;firstAuth,O}(t;firstAuth), \pi_{S,\tau;OpenArt}(t;OpenArt))) \\
\cup & \pi_{t_1.O;OpenArt}(\boxtimes_{t_1.S=t_2.S} (\pi_{S;author,O}(t;author), \pi_{S,\tau;GOpenArt}(t;GOpenArt))) \\
\cup & \pi_{t_1.O;OpenArt}(\boxtimes_{t_1.S=t_2.S} (\pi_{S;firstAuth,O}(t;firstAuth), \pi_{S,\tau;GOpenArt}(t;GOpenArt))) \\
\cup & \pi_{t_1.O;GOpenArt}(\boxtimes_{t_1.S=t_2.S} (\pi_{S;author,O}(t;author), \pi_{S,\tau;GOpenArt}(t;GOpenArt))) \\
\cup & \pi_{t_1.O;GOpenArt}(\boxtimes_{t_1.S=t_2.S} (\pi_{S;firstAuth,O}(t;firstAuth), \pi_{S,\tau;GOpenArt}(t;GOpenArt)))
\end{align*}
$$

4 Taming general BGP answering performance

Below, we present our technical contributions: the TCP layout and its algebraic
translation (Section 4.1), and summary-based pruning (Section 4.2).

4.1 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 *t*<sub>c</sub> class and *t*<sub>p</sub> property tables of the CP layout. The rationale behind
this is that CP is efficient 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 significantly 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 *G*<sup>*R*</sup> of a
graph *G* is stored in the TCP layout. The answers to a BGPQ *q* ← *t*<sub>1</sub>, ..., *t*<sub>n</sub>
are obtained through its algebraic transformation for the TCP layout:

$$
TCP(q) = \pi_q(\boxtimes_{jcond} (\alpha_{TCP}(t_1), \dots, \alpha_{TCP}(t_n)))
$$

where $\pi_q$ and $jcond$ are defined as for the T and CP layouts, and $\alpha_{TCP}$, the
query triple translation for the TCP layout, is:

$$
\alpha_{TCP}(t) = \begin{cases} \alpha_{CP}(t) & \text{if } t = (s, \tau, c) \text{ or } t = (s, p, o) \text{ with } c \notin \mathcal{Y}, p \notin \mathcal{Y} \cup \{\tau\} \\ \alpha_{T}(t) & \text{otherwise, i.e., if } t = (s, \tau, x) \text{ or } t = (s, x, o) \text{ with } x \in \mathcal{Y} \end{cases}
$$

Importantly, $\alpha_{TCP}$ translates the triples that penalize the CP layout into *t* atoms, and never into a union: hence, $\alpha_{TCP}$ avoids the cases (3) and (4) of $\alpha_{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:

$$
\pi_{t_1.O,t_2.O}(\boxtimes_{t_1.S=t_2.S,t_2.O=t_3.S} (\pi_{S;author,O}(t;author), \sigma_{P=\tau}(t), \pi_{S,<_{sc},O}(\sigma_{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 *Q*<sub>R</sub> = ⋃<sub>i=1</sub><sup>n</sup> *q*<sup>i</sup>, but now for the TCP layout:

$$
TCP(Q_R) = \bigcup_{i=1}^{n} TCP(q^i)
$$
*Example 12.* Consider the query $q(x, y, z) \rightarrow (x, \tau, z)$, $(x, :firstAuth, y)$ asking for all resources with their type and first author. Its reformulation w.r.t. $G_{ex}$'s ontology is shown below (the last four union terms are omitted for space reasons):

$$ 
\begin{align*}
q(x, y, z) &\leftarrow (x, \tau, z), (x, :firstAuth, y) \\
\cup q(x, y, :Article) &\leftarrow (x, \tau, :OpenArt), (x, :firstAuth, y) \\
Q_R &= \cup q(x, y, :Article) \leftarrow (x, \tau, :GOpenArt), (x, :firstAuth, y) \\
&\quad \cup q(x, y, :OpenArt) \leftarrow (x, \tau, :GOpenArt), (x, :firstAuth, y) \\
&\quad \cup q(x, y, :Person) \leftarrow (x, \tau, :Prof), (x, :firstAuth, y) \dots
\end{align*}
$$

Its algebraic translation on the TCP layout (similarly abridged) is:

$$ 
\begin{align*}
\pi_{t_1.S,t_2.O,t_1.O}(\bowtie_{t_1.S=t_2.S} (\sigma_{P=\tau}(t), \pi_{S, :firstAuth, O}(t: :firstAuth))) \\
\cup \pi_{t_1.S,t_2.O, :Article}(\bowtie_{t_1.S=t_2.S} (\pi_{S, \tau, :OpenArt}(t, :OpenArt), \pi_{S, :firstAuth, O}(t: :firstAuth))) \\
\cup \pi_{t_1.S,t_2.O, :Article}(\bowtie_{t_1.S=t_2.S} (\pi_{S, \tau, :GOpenArt}(t, :GOpenArt), \pi_{S, :firstAuth, O}(t: :firstAuth))) \\
\cup \pi_{t_1.S,t_2.O, :OpenArt}(\bowtie_{t_1.S=t_2.S} (\pi_{S, \tau, :GOpenArt}(t, :GOpenArt), \pi_{S, :firstAuth, O}(t: :firstAuth))) \\
\cup \pi_{t_1.S,t_2.O, :Person}(\bowtie_{t_1.S=t_2.S} (\pi_{S, \tau, :Prof}(t, :Prof), \pi_{S, :firstAuth, O}(t: :firstAuth))) \dots
\end{align*}
$$

Above, the first union term refers to the triple table *t*, while the others do not.

## 4.2 Summary-based query pruning

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* [12] is an RDF graph $G_{/≡}$ built as follows. A node is created in $G_{/≡}$ for each equivalence class among *G*'s nodes; further, for any triple $(n_1, p, n_2) \in G$, the triple $(m_1, p, m_2)$ appears in $G_{/≡}$, where $m_1$ and $m_2$ represent the equivalence class of $n_1$ and $n_2$ respectively. If there are large equivalence classes in *G*, summarization is a form of compression. Several types of RDF quotient summaries have been proposed [12]; in our experiments, we used the RDFQuotient summary construction tool [14], due to its online availability and low summary construction cost (linear in the number of triples of *G*). An RDFQuotient summary represents each class and property node *by itself*, and consider they are not equivalent to any other *G* node; thus, *G* and any quotient summary $G_{/≡}$ have the same schema triples.

Crucially, it holds that if $q(G_{/≡}) = \emptyset$ then $q(G) = \emptyset$, for *q* a structural (U)BGPQ, i.e., in which the subjects and objects of query triples are either class and property IRIs, or variables. Intuitively, this result holds because structural queries only allow selecting subject, property and object values that are preserved through summarization (class and property IRIs). Note however that the opposite does not hold in general, i.e., $q(G_{/≡})$ may have results while $q(G)$ does not. We exploit this result by defining the structural version of a BGPQ *q*, denoted $q^{\text{str}}$, which is obtained by replacing in *q* the literals and the IRIs that are not class or property IRIs, by fresh variables. For example, the structural version of the query $q(x) \leftarrow (x, \tau, :OpenArt), (x, :firstAuth, :Alice)$ is: $q^{\text{str}}(x) \leftarrow (x, \tau, :OpenArt), (x, :firstAuth, y)$, with :Alice replaced by *y*. Hence, when a summary $G_{/≡}$ is available, we can use it to *prune* a UBGPQ $Q = \cup_i q_i$ by removing
from the union all the $q_i$ terms for which $q_i^{\text{str}}(G/\equiv) = \emptyset$. As explained above, this
may fail to prune some $q_i$ with no results on $G$, but it preserves query results:

$$Q(G) = Q^{\text{pruned}}(G)$$

where $Q^{\text{pruned}}$ is the result of pruning $Q$. As our experiments will show, this
generally leads to a significant reduction of query answering time.

# 5 Experimental evaluation

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 efficient RDF storage and saturation- and reformulation-based query answering on top of an RDBMS [9,10,16] (Postgres 9.6 in these experiments). OntoSQL encodes IRIs and literals as integers, and a dictionary table allows going from one to the other; each table ($t$, $t_p$ or $t_c$) is indexed on all the subsets of its attributes. To use OntoSQL, we *express our algebraic translations in SQL*. We checked that in Postgres query plans, the relative positions of unions and joins in the query plans chosen by the RDBMS are those from our translations; [10,11] showed that this holds for two other major RDBMSs. However, *the RDBMS takes all optimization decisions*, based on its cost model and statistics. To put this into perspective also with respect to native RDF engines, we ran the same experiments also on **Virtuoso Open Source Edition 7.2**, to whom we provided *SPARQL queries*, which correspond exactly to our algebraic translation on the T layout. Virtuoso also controls its optimization decisions, and has full control over its store.

For summary-based pruning, we used the **RDFQuotient** (https://rdfquotient.inria.fr) tool to build the “typed strong” summary [14] of a graph $G$; this summary is denoted $G_{/TS}$. The summary groups typed nodes according to their types, and untyped nodes by exploiting the similarity of their incoming/outgoing properties (see [14] for details). In general, any quotient summary could be used; a large (more detailed) summary makes pruning more accurate, but also slower since it needs to query the summary.

**Hardware** We used a server with 2,7 GHz Intel Core i7 processors and 160 GB of RAM, running CentOS Linux 7.5.

<table><caption>**Table 3.** Graph and summary sizes (number of triples), OntoSQL database sizes (in GB), including all indexes, for the T, CP and TCP layouts.</caption><thead><tr><th>Graph</th><th>G</th><th>G<sub>/TS</sub></th><th>G<sup>R</sup></th><th>|(G<sup>R</sup>)<sub>/TS</sub>|</th><th>G<sub>T</sub></th><th>G<sub>CP</sub></th><th>G<sub>TCP</sub></th><th>G<sup>R</sup><sub>T</sub></th><th>G<sup>R</sup><sub>CP</sub></th><th>G<sup>R</sup><sub>TCP</sub></th></tr></thead><tbody><tr><td>LUBM</td><td>100M</td><td>340</td><td>131M</td><td>439</td><td>28.95</td><td>11.95</td><td>37.89</td><td>32.52</td><td>13.52</td><td>39.31</td></tr><tr><td>DBLP</td><td>88M</td><td>290</td><td>147M</td><td>708</td><td>26.07</td><td>16.35</td><td>35.89</td><td>38.39</td><td>22.91</td><td>52.72</td></tr></tbody></table>

**RDF graphs** We used two benchmark graphs: a **LUBM** [17] graph of 100M triples, as well as a graph of **DBLP** bibliographic data endowed with an ontology of 14 classes and 44 schema triples. Table 3 shows, for these graphs and their saturation, the graph and summary sizes, and the sizes of the OntoSQL databases
<table><caption>**Table 4.** Statistics of our queries on LUBM (top) and DBLP (bottom); M stands for millions and K for thousands.</caption><thead><tr><th>Query</th><th>Q01</th><th>Q02</th><th>Q03</th><th>Q04</th><th>Q05</th><th>Q06</th><th>Q07</th><th>Q08</th><th>Q09</th><th>Q10</th><th>Q11</th><th>Q12</th><th>Q13</th><th>Q14</th></tr></thead><tbody><tr><td>|q(G, R)|</td><td>2.78M</td><td>0.59M</td><td>2.15M</td><td>1.72M</td><td>0.47M</td><td>2.77M</td><td>25K</td><td>3696</td><td>2003</td><td>17.35M</td><td>187</td><td>518K</td><td>857</td><td>9.85M</td></tr><tr><td>|q<sup>G</sup>|</td><td>45</td><td>45</td><td>45</td><td>82</td><td>2025</td><td>45</td><td>45</td><td>82</td><td>3690</td><td>82</td><td>82</td><td>37</td><td>1369</td><td>82</td></tr><tr><td>|(q<sup>G</sup>)<sup>pruned</sup>|</td><td>45</td><td>45</td><td>45</td><td>67</td><td>1806</td><td>44</td><td>44</td><td>3</td><td>88</td><td>68</td><td>59</td><td>23</td><td>43</td><td>51</td></tr><tr><td>|Q<sub>R</sub>|</td><td>318</td><td>106</td><td>146</td><td>68</td><td>216</td><td>80</td><td>318</td><td>9</td><td>36</td><td>88</td><td>9</td><td>27</td><td>39</td><td>1152</td></tr><tr><td>|(Q<sub>R</sub>)<sup>pruned</sup>|</td><td>120</td><td>56</td><td>59</td><td>48</td><td>108</td><td>34</td><td>173</td><td>7</td><td>2</td><td>78</td><td>7</td><td>21</td><td>21</td><td>889</td></tr><tr><td>|Q<sub>R</sub><sup>G</sup>|</td><td>447</td><td>149</td><td>226</td><td>68</td><td>216</td><td>121</td><td>447</td><td>9</td><td>36</td><td>169</td><td>9</td><td>63</td><td>1797</td><td>1188</td></tr><tr><td>|(Q<sub>R</sub><sup>G</sup>)<sup>pruned</sup>|</td><td>206</td><td>99</td><td>135</td><td>48</td><td>108</td><td>73</td><td>299</td><td>7</td><td>2</td><td>144</td><td>7</td><td>42</td><td>50</td><td>892</td></tr><tr><td>Query</td><td>Q01</td><td>Q02</td><td>Q03</td><td>Q04</td><td>Q05</td><td>Q06</td><td>Q07</td><td>Q08</td><td>Q09</td><td>Q10</td><td>Q11</td><td>Q12</td><td>Q13</td><td>Q14</td><td>Q15</td></tr><tr><td>|q(G, R)|</td><td>72K</td><td>24K</td><td>96.3M</td><td>361K</td><td>4K</td><td>10</td><td>138</td><td>42K</td><td>1.52M</td><td>3.09M</td><td>957K</td><td>414K</td><td>409K</td><td>16.3K</td><td>460K</td></tr><tr><td>|q<sup>G</sup>|</td><td>18</td><td>18</td><td>18</td><td>18</td><td>50</td><td>900</td><td>900</td><td>18</td><td>900</td><td>900</td><td>1</td><td>18</td><td>324</td><td>50</td><td>1</td></tr><tr><td>|(q<sup>G</sup>)<sup>pruned</sup>|</td><td>18</td><td>18</td><td>18</td><td>18</td><td>3</td><td>136</td><td>136</td><td>17</td><td>85</td><td>85</td><td>1</td><td>18</td><td>324</td><td>3</td><td>1</td></tr><tr><td>|Q<sub>R</sub>|</td><td>117</td><td>297</td><td>265</td><td>117</td><td>873</td><td>4257</td><td>3163</td><td>36</td><td>1500</td><td>3652</td><td>243</td><td>39</td><td>381</td><td>129</td><td>243</td></tr><tr><td>|(Q<sub>R</sub>)<sup>pruned</sup>|</td><td>56</td><td>205</td><td>151</td><td>56</td><td>616</td><td>3089</td><td>2166</td><td>32</td><td>1184</td><td>2620</td><td>36</td><td>24</td><td>174</td><td>114</td><td>3</td></tr><tr><td>|Q<sub>R</sub><sup>G</sup>|</td><td>252</td><td>440</td><td>408</td><td>252</td><td>1529</td><td>5927</td><td>3345</td><td>72</td><td>1</td><td>324</td><td>3</td><td>84</td><td>2088</td><td>270</td><td>243</td></tr><tr><td>|(Q<sub>R</sub><sup>G</sup>)<sup>pruned</sup>|</td><td>161</td><td>331</td><td>277</td><td>161</td><td>1224</td><td>3275</td><td>2189</td><td>37</td><td>1</td><td>64</td><td>3</td><td>69</td><td>1497</td><td>117</td><td>3</td></tr></tbody></table>

storing them in the T, CP and TCP layout. As expected, TCP takes most space, approx. 90% of the sum of the T and CP database sizes. However, this is stable storage (e.g., disk) space; the selective data access enabled by the class and property tables, and by indexes, as well as cost-based optimization, ensure that the data loaded in memory to process a query is much smaller.

**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, \tau, 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 $(q^G)$, reformulation $(Q_R)$, and instantiation of their reformulation $(Q_R^G)$, before and after summary-based pruning. The impact of pruning ranges from none (in particular for $q^G$, on LUBM Q01 to Q03 and on 8 DBLP queries) to very significant (97.8% of the $q^G$ BGPs are pruned on LUBM Q09). Details on our experiments, and code which can be used to reproduce them, are online$^5$.

## 5.2 Experiment results: query answering times

For each query, we report the average of the last five ("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)(G^R)$. 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 naïve 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 naïve 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
<figure><img src="image_2.png" /><figcaption>**Fig. 2.** Query answering times (milliseconds) on LUBM (top) and DBLP (bottom), through saturation.</figcaption></figure>

the largest $q^G$ size, namely 3690, instantiating each of these more than doubles the answering time w.r.t. naïve 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, \tau, 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 naïve CP strategy (green bars, Q05-Q07, 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 significant 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, naïve CP largely outperforms T_SAT (by very far for Q15). Again, we observe the robust behavior of TCP_SAT. We conclude that through saturation,
<figure><img src="image_3.png" /><figcaption>Fig. 3. LUBM (top) and DBLP (bottom) query answering times (ms) through reformulation.</figcaption></figure>

# 6 Related work and conclusion

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 [4,7,19,20,21] only considered SatQA. While [4] advocated the CP layout, [21] nuanced the analysis: in a row store, they show that proper indexing (such as we used here) can significantly improve performance using T, while many distinct properties may hurt CP performance. It is not fully clear if [4,21] used the naïve or instantiation-based CP translation; as our experiments show, TCP outperforms both, in particular with summary pruning. The optimized T layout of [24], indexed on all (s, p, o) permutations, has been used for RefQA in [15,16,10]; in our experiments, TCP avoids all its bad-performance scenarios. Storage was optimized based on a known workload by creating materialized views in [15]. Query reformulation has also been used with the CP layout in [9,11]. Both [10] for T and [11] for CP explored how to express a reformulated query as a join of several subqueries, so as to minimize the evaluation cost through the RDBMS. Applying this technique to the TCP layout could presumably also improve its performance. A simplified version of TCP is briefly mentioned in [13], which studies generic SPARQL-to-SQL translation functions, as an example of possible relational layout. However, [13]
does not consider the performance impact of this layout; nor do they consider RDFS entailment. Optimized storage layouts [7,20,25] or indexes [22,5] have been investigated to limit joins by storing e.g., the values of several properties for a given subject together. They allow translating several BGPQ triples into a single table (or index) access; they could also be applied on the TCP layout to further improve it. Finally, in [23], the storage layout based on binary tables is adapted to the graph topology, in order to speed up query evaluation.

TCP is a robust layout, which does not require query workload knowledge, and allows to significantly reduce BGPQ answering times. On queries well supported by the T, respectively, CP layout, TCP matches that performance; but most importantly, it avoids all the performance (or plain unfeasibility) issues they encounter, in saturation- or reformulation-based query answering. Summary-based pruning also importantly improves performance. We believe the TCP layout, and pruning, can be adopted with little effort, and can strongly consolidate and improve query answering performance in many RDF databases.

## References

1. RDF 1.1 Concepts, https://www.w3.org/TR/rdf11-concepts/

2. RDF 1.1 Semantics, https://www.w3.org/TR/rdf11-mt/#rdfs-entailment

3. SPARQL 1.1 Query Language, https://www.w3.org/TR/sparql11-query/

4. Abadi, D.J., Marcus, A., Madden, S.R., Hollenbach, K.: Scalable Semantic Web Data Management Using Vertical Partitioning. PVLDB (2007)

5. Atre, M., Chaoji, V., Zaki, M.J., Hendler, J.A.: Matrix "bit" loaded: a scalable lightweight join query processor for RDF data. In: WWW (2010)

6. Bischof, S., Krötzsch, M., Polleres, A., Rudolph, S.: Schema-agnostic query rewriting in SPARQL 1.1. In: ISWC (2014)

7. Bornea, M.A., Dolby, J., Kementsietsidis, A., Srinivas, K., Dantressangle, P., Udrea, O., Bhattacharjee, B.: Building an efficient RDF store over a relational database. In: SIGMOD (2013)

8. Broekstra, J., Kampman, A., van Harmelen, F.: Sesame: A generic architecture for storing and querying RDF and RDF schema. In: ISWC (2002)

9. Buron, M., Goasdoué, F., Manolescu, I., Mugnier, M.: Reformulation-based query answering for RDF graphs with RDFS ontologies. In: ESWC (2019)

10. Bursztyn, D., Goasdoué, F., Manolescu, I.: Optimizing reformulation-based query answering in RDF. In: EDBT (2015)

11. Bursztyn, D., Goasdoué, F., Manolescu, I.: Teaching an RDBMS about ontological constraints. PVLDB 9(12) (2016)

12. Cebiric, S., Goasdoué, F., Kondylakis, H., Kotzinos, D., Manolescu, I., Troullinou, G., Zneika, M.: Summarizing Semantic Graphs: A Survey. VLDB Journal (2018)

13. Chebotko, A., Lu, S., Fotouhi, F.: Semantics preserving SPARQL-to-SQL translation. Data Knowl. Eng. 68(10) (2009)

14. Goasdoué, F., Guzewicz, P., Manolescu, I.: RDF Graph Summarization for First-sight Structure Discovery. The VLDB Journal (Apr 2020)

15. Goasdoué, F., Karanasos, K., Leblay, J., Manolescu, I.: View selection in semantic web databases. PVLDB 5(2) (2011)

16. Goasdoué, F., Manolescu, I., Roatis, A.: Efficient query answering against dynamic RDF databases. In: EDBT (2013)
17. Guo, Y., Pan, Z., Heflin, J.: LUBM: A benchmark for OWL knowledge base systems. J. Web Sem. 3(2-3) (2005)

18. Kontchakov, R., Rezk, M., Rodriguez-Muro, M., Xiao, G., Zakharyaschev, M.: Answering SPARQL queries over databases under OWL 2 QL entailment regime. In: ISWC (2014)

19. Neumann, T., Weikum, G.: The RDF-3X engine for scalable management of RDF data. VLDB J. (2010)

20. Pham, M., Passing, L., Erling, O., Boncz, P.A.: Deriving an emergent relational schema from RDF data. In: WWW (2015)

21. Sidirourgos, L., Goncalves, R., Kersten, M., Nes, N., Manegold, S.: Column-store support for RDF data management: not all swans are white. PVLDB 1(2) (2008)

22. Udrea, O., Pugliese, A., Subrahmanian, V.S.: GRIN: A graph based RDF index. In: AAAI (2007)

23. Urbani, J., Jacobs, C.J.H.: Adaptive low-level storage of very large knowledge graphs. In: WWW (2020)

24. Weiss, C., Karras, P., Bernstein, A.: Hexastore: Sextuple indexing for Semantic Web data management. PVLDB (2008)

25. Wilkinson, K., Sayers, C., Kuno, H., Reynolds, D.: Efficient RDF storage and retrieval in Jena2. In: SWDB (2003)