# RDF Query Answering in the Presence of Access Restrictions

Maxime Buron, Hritika Kathuria, Ioana Manolescu, George Siachamis

► To cite this version:

Maxime Buron, Hritika Kathuria, Ioana Manolescu, George Siachamis. RDF Query Answering in the Presence of Access Restrictions. CoopIS 2025 - 31st International Conference on Cooperative Information Systems, INSTICC, Oct 2025, Marbella, Spain. hal-05252157

HAL Id: hal-05252157

https://hal.science/hal-05252157v1

Submitted on 12 Sep 2025

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
RDF Query Answering in the Presence of Access
Restrictions

Maxime Buron¹[0000-0002-8227-4771], Hritika Kathuria²[0009-0002-3375-9673],
Ioana Manolescu²[0000-0002-0425-2462], and George
Siachamis²[0000-0002-4618-2028]

¹ Université de Clermont Auvergne, Clermont-Ferrand, France maxime.buron@uca.fr

² Inria & Institut Polytechnique de Paris
{first.last}@inria.fr

**Abstract.** In this work, we explore algorithms for answering conjunctive RDF queries in the presence of RDFS ontologies and access control. We consider an access control setting where by default all users have access to the complete graph, and a *restriction* can forbid user a user's access to specific IRIs. Here, restricting for user *u* the access to an IRI *i* entails that: no answer to a query by *u* may contain the IRI *i*; no triple containing *i* can be used to compute an answer for a query by *i*, nor to entail such a triple via reasoning with the ontology. We present a set of query answering algorithms for this novel context, and prove that five among them are correct, i.e., sound and complete, with respect to both the ontology and the access restrictions in place. We have implemented all our algorithms and present experiments comparing their performance.

**Keywords:** Semantic Web · Access Control · Query Answering.

# 1 Introduction

Knowledge graphs, especially RDF graphs standardized by the World Wide Web Consortium, are a simple, flexible and powerful format for heterogeneous data. In RDF (Resource Description Framework), *resources*, identified by *International Resource Identifiers* (IRIs) are described by their *properties*, which have *values*. A (subject, property, value) combination is called a *triple*. A value can itself be a resource, e.g., a company as a person's employer; both can be described further. A value can also be a *literal* (constants with optional types). A literal has no further properties. RDF also supports *blank nodes*, anonymous resources, modeling partial knowledge. For instance, an RDF graph may state that the group to which employee Alice belongs is `:_g`, where `:_g` is a blank node; we know that the group exists, even if we do not know a full IRI for it. RDF resources and blank nodes can be assigned *types* (or classes), e.g., Alice may be described in a graph as being of type Employee. We denote the *special RDF property* used to attach types to resources by `[τ]`.

A key RDF feature is support for *ontologies*, which enrich data understanding and exploitation. Ontologies can be specified in languages of varying expressive power. Among these, RDF Schema (RDFS, in short) [28] provides properties allowing to state relationships between classes and/or properties. For instance,
<figure><img src="image_2.png" /><figcaption>Fig. 1: Sample RDF graph.</figcaption></figure>

we can specify that Clerk is a subclass of Employee, or that anyone having a
paysheet is an Employee. In the presence of an ontology, inference (also called
entailment) may lead to some triples being implicitly part of an RDF graph, even
if not explicitly stated. For instance, if an RDF graph contains the triples (Alice,
$\tau$, Clerk) and (Clerk, subclassOf, Employee), the triple (Alice, $\tau$, Employee) is
also implicitly part of the graph. The presence of implicit triples requires special
care when answering queries over a graph, in order for the answer to correctly
reflect all the triples. For RDFS, polynomial-time algorithms for query answering
in the presence of ontologies exist [15,9], while OWL dialects have significantly
higher complexity [4]. For this reason, in this work, we consider RDFS ontologies.

In a multi-user setting, a user's access to an RDF graph may be limited (restricted). Accordingly, many RDF data access control proposals have been made in the literature (see Section 9). They may differ on the scope of an access right, e.g., a node, a triple, or a set of triples; they consider positive privileges, in the sense of SQL's GRANT, and/or negative ones, which restrict (or hide) parts of the graph to a user. However, most methods do not account for ontologies. Some works partially support RDFS [17,22] without full query answering; others use OWL [20,14] but with high reasoning costs.

To our knowledge, this is the first work thoroughly exploring algorithms for
answering conjunctive RDF queries in the presence of RDFS ontologies and
access control. We consider that by default all users have access to the complete
graph, and a restriction can forbid user *u*'s access to specific IRIs. Restricting
the access of user *u* to IRI *i* entails that: no answer for *u* may contain *i*; no
triple containing *i* can be used to compute an answer for a query, nor to entail
such a triple via reasoning with the ontology. We present a set of novel query
answering algorithms for this context, with respect to both the ontology and the
access restrictions.

Below, we recall RDF preliminaries in Section 2 and state our problem in
Section 3. Section 4, 5, 6 and 7 describe our algorithms, leveraging multiple
techniques: materialization of entailed triples, query reformulation, and triple
provenance. Section 8 covers experiments, followed by related work and conclusion.
The extended version [2] contains all formal proofs and the set of experimental
queries.

## 2 Preliminaries

We recall the core concepts and terminology describing RDF graphs in (Section 2.1),
RDF queries and query answering (Section 2.2).
## 2.1 RDF graphs, entailment and saturation

We consider given a set $\mathcal{I}$ of International Resource Identifiers (IRIs, in short), a set $\mathcal{L}$ of literals and a set of blank nodes $\mathcal{B}$ that are pairwise disjoint. A triple is an element in $(\mathcal{I} \cup \mathcal{B}) \times \mathcal{I} \times (\mathcal{I} \cup \mathcal{B} \cup \mathcal{L})$; its elements are called the subject, property, and object (or value). Among the IRIs $\mathcal{I}$, the special IRI rdf:type, denoted $\tau$, in short, is part of the RDF standard itself; it characterizes subjects by associating them various *classes*, or *types*. For instance, the triple (Alice, $\tau$, Clerk) states that the resource identified by the IRI Alice is of the type having for IRI Clerk.

An RDF graph $\mathcal{G}$ is a set of triples. In particular, $\mathcal{G}$ may contain RDF Schema [28] (RDFS, in short) ontology triples, whose property is one among the four RDFS properties: subclassOf, subpropertyOf, domain and range. Intuitively, $(c_1, subclassOf, c_2)$ states that the type (or class) $c_1$ is a specialization (subclass) of $c_2$, e.g., Clerk subclassOf Employee; $(p_1, subpropertyOf, p_2)$ specifies that $p_1$ is a more specific property than $p_2$, e.g., isDirectorOf is a subproperty of worksFor; $(p, domain, c)$ means that any subject having property $p$ is of type $c$, e.g., anyone having a studentCardNumber is a Student, and, symmetrically, $(p, range, c)$ means that any value of property $p$ is of class $c$, e.g., the value of a birthPlace is a GeographicLocation. We denote by $\text{Val}(\mathcal{G})$ the set of IRIs, blank nodes and literals used in $\mathcal{G}$ and by $\mathcal{O}_{\mathcal{G}}$ (or simply $\mathcal{O}$ when this does not cause any confusion) the set of ontology triples in $\mathcal{G}$. We define:

**Definition 1 (Class and property positions).** *Given an (s, p, o) triple, we say the object position is a class position if p is τ. Further, if p is subclassOf, we say the subject and object positions of the triple are class position. Finally, if p is domain, respectively, range, then the object position is also called class position. In a triple (s, p, o), we say p is a data property position if p is neither τ, nor subclassOf, subpropertyOf, domain or range.*

Note that we define data property positions slightly differently from class positions, based on their actual use in the graph. That is: if a property appears only in an ontology triple, but its value is not defined for any subject IRI, we do not consider it a data property.

**Definition 2 (Classes and data properties).** *A class present in $\mathcal{G}$ is an IRI appearing in a class position in some triple of $\mathcal{G}$. A data property in $\mathcal{G}$ is an IRI appearing in a property position in a triple of $\mathcal{G}$.*

Figure 1 illustrates a sample graph. Labels such as Alice, Bob, etc. designate IRIs, and quoted strings such as "SO24" denote literals. Properties are shown as labels on edges; RDFS properties are shown in blue. The classes present in this graph are: Employee, SecurityOfficer, and Clerk, whereas the data properties are worksFor and securityPermit.

If $\mathcal{G}$ contains ontology triples, this may lead to the presence of *entailed* triples, that hold in $\mathcal{G}$ even though they are not explicitly part of it. The RDFS entailment process is defined by a set of entailment rules [1]. In this work, we only consider the four rules that infer type and data triples. We leave out rules that also infer schema triples mainly to simplify the presentation of our algorithms,
and also because they do not entail data or type triples, that is the reason why
they are rarely considered in the literature.

We say that there is an *entailment step* $(t_1, t_2) \xrightarrow{r} t$ from $\mathcal{G}$, when two triples $t_1$ and $t_2$ in $\mathcal{G}$ trigger a rule $r$ to entail a triple $t$. For instance, in our sample graph, the triples (Alice, $\tau$, Clerk) and (Clerk, subclassOf, Employee) lead to the implicit triple (Alice, $\tau$, Employee). Further, the triple (hasSecurityPermit, domain, SecurityOfficer) means that any resource that is the subject of the property securityPermit, is of type SecurityOfficer. This triple, together with (Bob, securityPermit, "SO24"), entail that (Bob, $\tau$, SecurityOfficer). As this example illustrates, an *entailed triple* may also be *explicitly present* in $\mathcal{G}$.

As shown above, a given graph may entail different triples. In turn, any
entailed triple, together with an ontology triple, may lead to more entailed
triples. The **saturation** of $\mathcal{G}$, denoted $\mathcal{G}^+$, is the graph to which we add all
the triples it entails directly or indirectly. It is known that the saturation of an
RDF graph w.r.t. an RDFS ontology can be computed in polynomial time, is
finite, and its size is polynomial in the size of the original graph $\mathcal{G}$ [15]. In our
example, $\mathcal{G}^+ = \mathcal{G} \cup \{(\text{Alice, } \tau, \text{Employee}), (\text{Bob, } \tau, \text{Employee})\}$.

## 2.2 RDF queries and query answering

We consider available a set $\mathcal{V}$ of variables. A *triple pattern* is of the form $(s, p, o)$ that belongs to $(\mathcal{I} \cup \mathcal{V}) \times (\mathcal{I} \cup \mathcal{V}) \times (\mathcal{I} \cup \mathcal{L} \cup \mathcal{V})$. A **Basic Graph Pattern (BGP)**, in short) query $q$ is of the form: $q(\bar{x}):-t_1, t_2, \dots, t_k$, where the $t_i$, $1 \le i \le k$, are triple patterns, the right-hand part is called the body of the query, while the head $\bar{x}$ denotes a list of variables, all of which must appear in the body. We denote by $\text{Var}(q)$ the set of variables that appear in the body of $q$. For instance, the query $q_1(x, y):-(x, \tau, y)$, $(x, \text{worksFor}, \text{ACME})$ asks for all the employees of ACME, together with their types.

The **evaluation of a BGP query** $q$ **over an RDF graph** $\mathcal{G}$, denoted $q^0(\mathcal{G})$, is defined as follows:

- An *homomorphism* from $q$ to $\mathcal{G}$ is a function $\phi$ from $\text{Var}(q)$ to $\text{Val}(\mathcal{G})$ such that for each triple pattern $t_i$ in the body of $q$, the triple $\phi(t_i)$ (obtained from the substitution of the variables in $t_i$ by their image by $\phi$) belongs to $\mathcal{G}$.

- For each homomorphism $\phi$ from $q$ to $\mathcal{G}$ as above, we denote by $\phi(\bar{x})$ the tuple of IRIs, blank nodes and literals to which the variables $\bar{x}$ are mapped by $\phi$.

- The evaluation $q^0(\mathcal{G})$ is defined as: $\{\phi(\bar{x}) | \phi$ is an homomorphism from $q$ to $\mathcal{G}\}$. In our example, $q_1^0(\mathcal{G}) = \{\phi_1(\bar{x}), \phi_2(\bar{x})\} = \{(\text{Bob, SecurityOfficer}), (\text{Alice, Clerk})\}$.

The **answer of a BGP query** $q$ **over a graph** $\mathcal{G}$ is defined as the evaluation of $q$ over the saturated graph $\mathcal{G}^+$: $q(\mathcal{G}) = q^0(\mathcal{G}^+)$.

As a consequence, computing the query answer $q(\mathcal{G})$ requires to follow one
of the following two strategies:

- *Materialize* $\mathcal{G}^+$, i.e., compute all the triples it entails and add them explicitly to the graph. Then, evaluating $q$ on $\mathcal{G}^+$ produces all the desired results.

- *Reformulate* the query using the ontology triples $\mathcal{O}$, into an expanded query $q^{\text{ref}}$, so that evaluating $q^{\text{ref}}$ over $\mathcal{G}$ produces the full answer to $q$ over $\mathcal{G}$.
On the graph $\mathcal{G}$ in Figure 1, consider the query $q_2(x) :- (x, \tau, \text{Employee})$. To answer it via materialization, it suffices to evaluate it on the saturation $\mathcal{G}^+$ (Section 2.1). Thanks to the two extra triples in $\mathcal{G}^+$, this leads to the answer $q_2(\mathcal{G}) = \{(\text{Alice}), (\text{Bob})\}$. Observe that simply *evaluating* $q_2$ against $\mathcal{G}$ lead to the empty answer, because in $\mathcal{G}$, no resource is declared to be of type Employee.

Polynomial-time algorithms for query reformulation have been described e.g. in [15,9]; the latter extends the former to RDF reasoning that also produces new ontology triples, and queries that carry also over the ontology. Because of its generality, we rely on [9] for this work. We illustrate it via **two reformulation examples**, while delegating the algorithmic details to [9].

First, the reformulation of query $q_2$ above: $q_2^{\text{ref}} = q_2 \cup q_2^1 \cup q_2^2 \cup q_2^3$, where $q_2^1(x) :- (x, \tau, \text{Clerk})$, $q_2^2(x) :- (x, \tau, \text{SecurityOfficer})$, $q_2^3(x) :- (x, \text{securityPermit}, y)$. An answer to $q_2^1$ is an answer to $q_2$, because any Clerk is an Employee, and similarly any answer to $q_2^2$ is also an Employee. Finally, the domain constraint on the securityPermit property ensures that an answer to $q_2^3$ is also an employee. Our sample graph does not support any other answers for $q_2$. As this example demonstrates, reformulation may lead to a *union* of BGP queries.

To see a more elaborate example, consider the query: $q_3(y, z) :- (x, y, \text{ACME})$, $(x, \tau, z)$, $(z, \text{subclassOf}, u)$, asking for all the relationships that a subject $x$ may have with ACME, and the type $z$ attached to $x$, such that $z$ has a known supertype. The reformulated $q^3$ is: $q_3^{\text{ref}} = q_3^1 \cup q_3^2$, where $q_3^1(y, \text{Clerk}) :- (x, y, \text{ACME})$, $(x, \tau, \text{Clerk})$ and $q_3^2(y, \text{SecurityOfficer}) :- (x, y, \text{ACME})$, $(x, \tau, \text{SecurityOfficer})$. Note that $q_3^1$ and $q_3^2$ only have two triples, whereas $q_3$ had three. The last $q_3$ triple carries over the ontology; it is *evaluated* by the reformulation algorithm, and its results injected into the remaining triples during the reformulation. Also note that because $q_3$ requires returning types, the type IRIs are present in the heads of $q_3^1$ and $q_3^2$, which are thus not BGPs as defined (but are a small generalization thereof).

The trade-offs between materialization and reformulation are as follows. Materialization takes some time to compute and space to store, however, it simplifies query evaluation. When the data and/or ontology triples change, the materialized graph may need to be updated to reflect these changes, which may be costly. Reformulation-based query answering does not require any upfront cost nor maintenance; however, the reformulated query evaluation may be costly.

We will also need to refer to a restriction of the BGP query language, considered in many RDF data management works:

**Definition 3 (Relational BGP).** We call relational BGP a BGP satisfying:

1. *No variable appears in class or property position (Definition 1) in a BGP triple;*

2. *Explicitly querying the ontology is not allowed, i.e., subclassOf, subpropertyOf, domain, range do not appear in a property position in the BGP.*

The term "relational" captures the fact that relational BGPs only carry over the data (the facts) present in RDF graphs, not over the ontology. The BGP $q_2$ above is relational, whereas $q_1$ is not, because $y$ appears in a class position. In
the sequel, unless otherwise specified, our discussion carries over all BGPs (not
just the relational ones).

**3 Problem statement**

We now introduce the problem we consider. Section 3.1 describes our notion of access control in RDF graphs, while Section 3.2 defines the problem of restriction-aware query answering on RDF graphs.

**3.1 Restriction-based access control**

**Users** We consider available a set $\mathcal{U}$ of users.

**Definition 4 (Restriction).** An access restriction is a pair of the form (u, r) where u ∈ U is a user and r is an IRI, different from subclassOf, subpropertyOf, domain, range and τ.

We exclude the τ property, as well as the standard RDFS properties, from
the restrictions, in order to preserve the core features of RDF and RDFS,
respectively. Let us fix a user *u* ∈ *U* and let *AR* be a set of access restrictions
whose user is *u*; let *A* be the set of IRIs appearing in *AR*. Without loss of
generality, we assume that all the IRIs in *A* appear in *G* i.e. *A* ⊆ *Val*(*G*).

**Definition 5 (Restricted graph).** We define the restriction of a graph $\mathcal{G}$ based on $A$ as $\mathcal{G}_A = \mathcal{G} \setminus (\bigcup_{a \in A} \{(s, p, o) | (s, p, o) \in \mathcal{G} \text{ and } s = a \lor p = a \lor o = a\})$

Intuitively, $\mathcal{G}_A$ contains the triples in $\mathcal{G}$ without the ones featuring one of the restricted IRIs. For example, consider the restriction set $AR = \{(u, \text{SecurityOfficer}), (u, \text{securityPermit})\}$ and our sample graph in Figure 1. The restricted graph $\mathcal{G}_A$ consists of the triples: $\mathcal{G}_A = \{(\text{Alice}, \tau, \text{Clerk}), (\text{Clerk}, subclassOf, \text{Employee}), (\text{Alice}, \text{worksFor}, \text{ACME}), (\text{Bob}, \text{worksFor}, \text{ACME})\}$ Four $\mathcal{G}$ triples are absent from $\mathcal{G}_A$ (two ontology, and two data triples): the three in which SecurityOfficer appears, as well as (Bob, securityPermit, "SO24").

A set of properties hold concerning $\mathcal{G}_A$. First:

**Property 1.** Applying entailment on an RDF graph $\mathcal{G}_A$ which does not contain a specific set of IRIs cannot to lead to triples that contain a restricted IRI.

**Property 2 (Inclusion).** This inclusion holds : ($\mathcal{G}_A$)$^+ \subseteq (\mathcal{G}^+)_A$. In general, the opposite inclusion does not hold.

For our sample graph, we obtain: ($\mathcal{G}_A$)$^+ =$ {($\text{Alice}$, $\tau$, $\text{Clerk}$), ($\text{Clerk}$, subclassOf, Employee), ($\text{Alice}$, worksFor, ACME), ($\text{Bob}$, worksFor, ACME), ($\text{Alice}$, $\tau$, Employee)} One additional triple is introduced in ($\mathcal{G}^+$)$_A$ : ($\text{Bob}$, $\tau$, Employee). This exemplifies that in general, the opposite inclusion in Property 2 does not hold.

**3.2 Answering RDF queries in the presence of access restrictions**

The problem we consider in this work is: answering queries over RDF graphs in
the presence of access restrictions (Definition 4).

Intuitively, if the access of a user *u* to some IRIs, and thus to all triples
where these IRIs appear, is restricted, then no homomorphism *φ* can map a
<figure><img src="image_3.png" /><figcaption>Fig. 2: Overview of our algorithms.</figcaption></figure>

triple pattern in the body of *q*, into a restricted *G*<sup>+</sup> triple. This may disable some homomorphisms that exist in the absence of access restrictions, and thus, lead to some answers not being found any more.

Note that a given answer may be due to some homomorphism $\phi'$ invalidated by the restrictions, and simultaneously due to some other homomorphism $\phi''$ that is not impacted by the restrictions. In this case, we consider that the answer is available. This is coherent with the natural query evaluation semantics, stating that each homomorphism leads to an answer. Our choice corresponds to a default “allow” (positive) policy; opting instead for a “deny” default policy would require a different set of algorithms.

**Definition 6 (Query answer in the presence of access restrictions).**
Given a graph $\mathcal{G}$, the set of restricted IRIs $A$ for a user $u \in \mathcal{U}$ as above, and a query $q$, the answer to $q$ based on $\mathcal{G}$ and $A$, denoted $q(\mathcal{G}, A)$, is the answer to $q$ over the restricted $\mathcal{G}: q(\mathcal{G}, A) = q((\mathcal{G}_A)^+)$.

**Roadmap** In the sequel, we discuss multiple algorithms for the above problem. These algorithms rely on a set of individual steps applied to the graph and/or the query; Figure 2 traces the main steps of our *correct* (sound and complete) algorithms. A few alternative methods that may fail to compute the correct results, are not included in the Figure. We assign a different color to each algorithm, and leave in black elements shared by multiple algorithms. Each box labeled with an algorithm name, e.g., [MAT], designates the *query evaluation* step of that algorithm, where results are actually computed from a graph.

**Restriction check** A simple check can be made on a BGP query prior to evaluation: if at least one query triple involves a restricted IRI, the query has empty results (because any result would require an homomorphism, and no such homomorphism exists). Such queries are immediately returned an empty answer. Below, we consider answering queries not determined to have an empty answer.

# 4 Baseline algorithms

We now present algorithms for our problem, obtained with minimal modifications to materialization and reformulation algorithms.
## 4.1 Materialization-based algorithms (MAT)

The algorithm MAT follows directly from Definition 6:

1. Restrict the graph, i.e., compute $\mathcal{G}_A$.

2. Saturate it, i.e., build $(\mathcal{G}_A)^+$.

3. Evaluate $q$ over the resulting graph i.e., $q^0((\mathcal{G}_A)^+)$.

For example, evaluating our query $q_1(x) \coloneqq (x, \tau, y)$, $(x, \text{worksFor}, \text{ACME})$ on the graph $(\mathcal{G}_A)^+$ shown in Section 3.1 only returns (Alice).

Algorithm MAT is clearly correct (it is both sound and complete w.r.t. Definition 6), since it computes the query answers, i.e., $q(\mathcal{G}_A)$.

## 4.2 Restrict-then-reformulate (RTR)

A direct reformulation-based algorithm RTR can also be devised:

1. Restrict $\mathcal{G}$ using $A$, that is, compute $\mathcal{G}_A$.

2. Compute the reformulation of $q$ using the restricted ontology, denoted $q^{\text{ref } A}$.

3. Evaluate $q^{\text{ref } A}$ over $\mathcal{G}_A$.

One major drawback of MAT and RTR algorithm is that on a single input graph, one graph per user need to be build and queried. In the following sections, we investigate more sophisticated algorithms avoiding this drawback.

# 5 Provenance-based result pruning (PROV)

We now present a new materialization-based algorithm PROV. As shown in Property 2, a query answering algorithm that evaluates the query over the restriction of the saturated graph may to lead to unsound results from $(\mathcal{G}^+)_A$. To avoid it, PROV tracks restricted IRIs throughout inference and query evaluation, to output only allowed answers. We start by introducing a few helper notions.

**Definition 7 (Query extension).** Given a BGP query $q$, the extension of $q$, denoted $\tilde{q}$, is a BGP whose head contains all the variables in $q$, and having the same body as $q$.

For our sample BGP query $q_1(x) \coloneqq (x, \tau, y)$, $(x, \text{worksFor}, \text{ACME})$ (Section 2.2), the extension is $\tilde{q}_1(x, y) \coloneqq (x, \tau, y)$, $(x, \text{worksFor}, \text{ACME})$. Observe that each extended query result is due to exactly one homomorphism into $\mathcal{G}^+$ whereas the result of an arbitrary BGPQ could be due to several. Based on this observation, we define:

**Definition 8 (Triples leading to an extended query answer).** For a given result $r \in \tilde{q}(G^+)$, we call triples leading to $r$, denoted $T_r$, the set of triples obtained by replacing, in each triple in the body of $\tilde{q}$, each variable with the IRI, blank nodes or literal to which the variable is bound in $r$.

For instance, recall the query $\tilde{q}_1(x, y)$ and consider the result $r = (\text{Alice}, \text{Clerk})$ to $\tilde{q}_1$. Then, $T_r$ is $\{(\text{Alice}, \tau, \text{Clerk}), (\text{Alice}, \text{worksFor}, \text{ACME})\}$. Extending the query guarantees that we can compute $T_r$ directly from each answer. In contrast, the result of a non-extended query may be due to several (alternative) triple sets; further, retrieving these sets requires a query evaluation engine specifically designed, e.g., [26]; in this work, instead, we rely on standard conjunctive query engines. Note that $\tilde{q}$ has at least as many results as $q$, and its evaluation could be more costly.
<table><caption>Table 1: Triple identifiers for the sample entailment graph.</caption><thead><tr><th>Triple</th><th>ID</th><th>Triple</th><th>ID</th></tr></thead><tbody><tr><td>(Alice, worksFor, ACME)</td><td>n<sub>Aw</sub></td><td>(Clerk, subclassOf, Employee)</td><td>n<sub>subC</sub></td></tr><tr><td>(Bob, worksFor, Acme)</td><td>n<sub>Bw</sub></td><td>(SecurityOfficer, subclassOf, Employee)</td><td>n<sub>subS</sub></td></tr><tr><td>(Alice, τ, Clerk)</td><td>n<sub>ArC</sub></td><td>(Bob, securityPermit, "SO24")</td><td>n<sub>sp</sub></td></tr><tr><td>(Bob, τ, SecurityOfficer)</td><td>n<sub>BτS</sub></td><td>(securityPermit, domain, SecurityOfficer)</td><td>n<sub>sdS</sub></td></tr><tr><td>(Alice, τ, Employee)</td><td>n<sub>AτE</sub></td><td>(Bob, τ, Employee)</td><td>n<sub>BτE</sub></td></tr><tr><td>(worksFor, domain, Employee)</td><td>n<sub>wdE</sub></td><td></td><td></td></tr></tbody></table>

**Definition 9 (Entailment graph).** The entailment graph of an RDF graph $\mathcal{G}$ is a directed graph $\mathcal{G}_e$ obtained as follows. $\mathcal{G}_e$ contains a node for each triple in $\mathcal{G}$. Further, for each possible entailment step (Section 2.1) of the form $(t_1, t_2) \xrightarrow{r} t$ that can apply based on $\mathcal{G}$, and possibly triples previously entailed from $\mathcal{G}$, where $t_1, t_2, t$ are triples and $r$ is an entailment rule, $\mathcal{G}_e$ contains:

- One node for each of the triples $t_1, t_2, t$, such that $\mathcal{G}_e$ contains at most one node for any triple from $\mathcal{G}^+$. For each triple, $\mathcal{G}_e$ also stores whether it was explicitly present in $\mathcal{G}$;

- One node labeled $r$; we denote this node by $n_r$;

- Edges from the nodes corresponding to $t_1$ and $t_2$ to $n_r$;

- An edge from $n_r$ to the node corresponding to $t$. Node $n_r$ only has this outgoing edge, and only has the two incoming edges described above (in other words, there is exactly one node for each rule application).

In our example, assigning to each triple in $\mathcal{G}$ (Figure 1) a node identifier, as shown in Table 1 (ignore for now the last line in blue), the entailment graph appears in Figure 3, with a node name shown in a box, e.g., $n_{Aw}$, $n_{BτS}$, etc. if the node is explicitly present in the graph. Again, ignore for now the blue nodes and edges. We say **a triple is permitted** if it does not contain any restricted IRI. In Table 1 and Figure 3, the non-permitted triples are shown in red; they contain the restricted IRI SecurityOfficer or securityPermit.

**Cycles in entailment graphs** Cycles in the entailment graphs are unlikely: it is not common for a triple to (directly, or transitively) entail itself. This may still happen, only when the ontology implies that a class (resp. a property) is a subclass (resp. subproperty) of itself, i.e., there is a cycle in the class (resp. property) hierarchy. Below, we assume there are no such cycles. If it does exist, it can be eliminated without loss of expressivity by merging all the classes (resp. properties) involved in the cycle into a single one. With the above notions, we can define:

**Definition 10 (Entailment and entailment provenance (EP)).** Let $t$ be a triple represented by a node $n_t$ in the entailment graph $\mathcal{G}_e$. An entailment of $t$ is a subtree of $\mathcal{G}_e$, such that all the tree leaves are explicit triples. The entailment provenance of $t$, denoted $EP(t)$, is the sub-DAG of $\mathcal{G}_e$ containing all the entailments of $t$.

For instance, assume that $\mathcal{G}$ contains also the extra triple in blue in Table 1. This, together with the triple (Alice, worksFor, ACME), would lead to another entailment for $n_{ArE}$; this is shown by blue nodes and edges in Figure 3. Similarly,
<figure><img src="image_4.png" /><figcaption>Fig. 3: Entailment graph for the sample graph in Figure 1.</figcaption></figure>

$EP(n_{BτE})$ contains three entailments: (i) the lowest subtree (in blue); (ii) the subtree consisting of $n_{BτS}$, $n_{subs}$ (these are both explicit triples) and $n_{subclassOf}^2$; (ii) the subtree that starts from $n_{sp}$ and $n_{sds}$ and derives $n_{BτS}$, instead of using the explicit triple. As the examples illustrate, an entailment provenance encodes the set of alternative ways why $t$ may hold.

We say an **entailment is permitted** if it contains no restricted triples. For example, both entailments of $n_{AτE}$ are permitted; only the entailment denoted (i) above for $n_{BτE}$, consisting of blue nodes and edges, is permitted.

**Entailment graphs are complete:** By definition of $\mathcal{G}_e$, for each entailed triple $t$, all the entailments of $t$ are subtrees of $\mathcal{G}_e$.

We can now describe the complete PROV algorithm:

1. **Saturation with provenance:** Saturate $\mathcal{G}$, and, while doing so, build the entailment provenance $\mathcal{G}_e$.

2. **Query extension:** Let $\tilde{q}$ be the extension of $q$.

3. **Query evaluation and result construction:**

(a) Compute $R = \tilde{q}^0(\mathcal{G}^+)$, the evaluation of $\tilde{q}$ over the saturated graph.

(b) For each result $r \in R$:

i. If every triple leading to $r$ (Definition 8) has at least one permitted entailment provenance in $\mathcal{G}_e$, then the projection $\pi_q(r)$, that retains from $r$ only the variables from the head of $q$, is a result of $q(\mathcal{G}_A)$.

Following the evaluation of the extended $\tilde{q}_1$ from the beginning of this section, its result $r' = (\text{Bob}, \text{Employee})$ has $T_{r'} = \{(\text{Bob}, \tau, \text{Employee}), (\text{Bob}, \text{worksFor}, \text{ACME})\}$. The first triple in $T_{r'}$ has a permitted entailment only if the blue triple is part of the graph, in which case (Bob) is returned as an answer for $q_1$ by algorithm PROV. Observe that both triples in $T_{r'}$ are themselves permitted; we need their entailments to judge whether an answer can be returned based on $r'$, or not.

**Reduced provenance** The entailment graph $\mathcal{G}_e$ represents every triple in $\mathcal{G}^+$. The reason why we represent even explicit triples, even if not involved in any entailment, is step (3(b)i) of the PROV algorithm: this checks every $\mathcal{G}^+$ triple that may have served to build an answer, whether it is implicit and/or explicit. A $\mathcal{G}$ triple is by definition explicit in $\mathcal{G}^+$ (being in $\mathcal{G}$ counts as one provenance), and the triple may have others due to entailment. Each of these provenances suffices for a triple to satisfy the check. However, the provenance graph is quite large (at least as large as $\mathcal{G}^+$), which makes its processing cumbersome.
As an optimization, instead of storing $\mathcal{G}_e$, we store a reduced version thereof, obtained by removing from $\mathcal{G}_e$ any entailment chain leading to a triple that is (also) explicit. We do keep the triple itself, but remove the node(s) corresponding to each rule application that entails the triple (denoted $n_r$ in Definition 9), together with their adjacent edges. For example, in Figure 3, the node $n^1_{\text{domain}}$ and its adjacent edges are not present in the reduced $\mathcal{G}_e$.

**Property 3.** Algorithm PROV is also correct on the reduced entailment graph.

# 6 Restriction-aware reformulation (RAR and RARE)

In this section, we seek to avoid expensive computations on the graph, and capturing entailment provenance, and instead, attempt to take in account the access restrictions in the query reformulation process. Algorithm RAR (Restriction-Aware Reformulation) proceeds as follows:

1. Reformulate $q$ into $q^{\text{ref } A}$ taking the set of restricted IRIs into account:

– While reformulating a query triple $t_q$ using a $\mathcal{O}$ rule, if the rule uses a restricted IRI, ignore that reformulation.

Note that this is the same reformulated query as in RTR (Section 4.2).

2. Evaluate $q^{\text{ref } A}$ on $\mathcal{G}$.

For instance, on the query $q_2(x) :- (x, \tau, \text{Employee})$, the restricted reformulation $q_2^{\text{ref } A}$ is: $q_2 \cup q_2^1$, where $q_2^1(x) :- (x, \tau, \text{Clerk})$. Comparing this with the full reformulation of $q_2$ (Section 2.2), we can see that the reformulations $q_2^2$ and $q_2^3$, resulting (also) from non-permitted $\mathcal{G}$ triples, specifically (SecurityOfficer, subclassOf, Employee) and (securityPermit, domain, SecurityOfficer) are omitted in $q_2^{\text{ref } A}$.

While algorithm RAR is complete, it is **unsound** in some cases:

1. For instance, consider that we restrict the IRI Bob, and the simple query $q_4(x) :- (x, \text{worksFor}, \text{ACME})$: reformulation leaves $q_4$ unchanged, and evaluation returns $\{(\text{Alice}), (\text{Bob})\}$. Intuitively, this is because RAR only restricts the ontology, and not the graph $\mathcal{G}$.

2. Now consider that we restrict property $p_1$ in a simple graph $\mathcal{G}_5 = \{(i_1, p_1, i_2), (i_2, p_2, i_3)\}$, and the query $q_5(x, w) :- (x, y, z), (z, u, w)$. Lacking an ontology, reformulation leaves $q_5$ unchanged; evaluation returns $(i_1, i_3)$ which is not a valid answer, because it relies on the restricted $p_1$. Here, the problem is due to the variables in property positions, which (restriction-unaware) evaluation binds to the restricted $p_1$.

Based on these observations, we describe Algorithm RARE (Restriction-Aware Reformulation and Extension):

1. (As in RAR) Reformulate $q$ with the restricted ontology, leading to $q^{\text{ref } A}$.

2. Extend each conjunctive query in $q^{\text{ref } A}$; we denote by $\tilde{q}^{\text{ref } A}$ the union of these extended BGPs (recall Definition 7).

3. For each $\tilde{q}_i$ that is a union term in $q^{\text{ref } A}$:

(a) Evaluate $\tilde{q}_i$ over $\mathcal{G}$. If $\tilde{q}_i$ has variables in class or property positions, evaluation may bind them to restricted IRIs!
(b) For each $r \in \tilde{q}_i^0(G)$: if all the triples in $T_r$ are permitted, then the projection $\pi_{q_i}(r)$ is returned as an answer to $q$. This step is denoted RFilter in Figure 2.

It is easy to see that the completeness of RAR extends also to RARE, because every RAR answer is also returned by RARE. Further, we define:

**Definition 11 (CP restrictions).** We say a set AR of access restrictions are class-property restrictions (CP, in short), if every restricted IRI is a class or a data property in $G$ (recall Definition 1).

**Property 4 (Soundness for CP restrictions only).** Let AR be a set of CP restrictions. (i) For relational BGPs (Definition 3), Algorithm RAR is sound. (ii) Algorithm RARE is sound for general BGPs.

# 7 Algorithms based on filtering (MFIL and RFIL)

So far, the queries which we relied upon were conjunctive (BGPs), or (after reformulation), unions of such queries. In the spirit of [21], we can also slightly extend conjunctive queries with inequality predicates, as follows:

**Definition 12 (BGP query with filters).** A BGP query with filters (**BGPf**, in short) $q^f$ consists of: a conjunctive query $q$, together with a set of inequality predicates, each of the form $v \neq a$, where $v$ is a variable from the body of $q$, and $a \in A$, the restriction set for user $u$. The result of evaluating a BGPf $q^f$ over $G$ is the set of results derived from at least one homomorphism from $q$ to $G$ that satisfies all the inequality predicates.

Given a conjunctive query $q$ and a set of access restrictions AR for user $u$, with the restricted IRI set $A$, Algorithm **QFilter** builds a BGPf $q^f$ based on $q$, if one exists, or returns an empty query :

1. Let $I$ be a set of inequality predicates, initially empty, and $G^+$ is the saturated graph.

2. For each triple $t$ in the body of $q$:

(a) If $t$'s subject, respectively, predicate or object is an URI:

- If the IRI is an $a \in A$, return an empty query.

(b) If $t$'s subject, predicate or object is a variable $v$:

- For each $a \in A$, add to $I$ the predicate $v \neq a$.

Filtered queries can be used in more query answering algorithms. First, we consider a **materialization-based algorithm with filtering**, named **MFIL**:

1. Saturate $G$.

2. Filter $q$ with the restrictions, leading to a filtered $q^f$.

3. Evaluate $q^f$ over $G^+$.

Algorithm **MFIL** is not sound. To see that, assume a graph of two triples: (SecurityOfficer, subclassOf, Employee) and (Bob, $\tau$, SecurityOfficer), and assume as before that SecurityOfficer is restricted. Saturation adds (Bob, $\tau$, Employee). Given the query $q_6(x)$: $\neg (x, \tau, Employee)$, the filtered query $q_6^f$ is: $q_6^f(x) \neg \neg (x, \tau, Employee) \wedge (x \neq SecurityOfficer)$. Evaluating this over $G^+$ returns Bob, even though the correct answer is empty. The problem is that filtering acts
<table><caption>Table 2: Query characteristics on the 1M (top) and 10M (bottom) datasets. on the consequences of inference and can no longer discern that some results are due to restricted IRIs.</caption><thead><tr><th>Metric</th><th>q<sub>1</sub></th><th>q<sub>2</sub></th><th>q<sub>3</sub></th><th>q<sub>4</sub></th><th>q<sub>5</sub></th><th>q<sub>6</sub></th><th>q<sub>7</sub></th><th>q<sub>8</sub></th><th>q<sub>9</sub></th><th>q<sub>10</sub></th><th>q<sub>11</sub></th><th>q<sub>12</sub></th></tr></thead><tbody><tr><td>|q(1M)|</td><td>1 133 860</td><td>1 522</td><td>70 827</td><td>151</td><td>224 573</td><td>288 500</td><td>2 138 212</td><td>56 200</td><td>19 731</td><td>28 100</td><td>37 224</td><td>84 300</td></tr><tr><td>|q<sup>ref</sup>|</td><td>509</td><td>11</td><td>5</td><td>1</td><td>25</td><td>493</td><td>509</td><td>1</td><td>1</td><td>215</td><td>2545</td><td>9671</td></tr><tr><td>|q(1M, A<sub>1</sub>)|</td><td>1 069 047</td><td>1 522</td><td>70 827</td><td>0</td><td>224 558</td><td>218 698</td><td>2 069 328</td><td>56 199</td><td>19 717</td><td>28 084</td><td>0</td><td>84 251</td></tr><tr><td>ARR<sub>A<sub>1</sub></sub></td><td>0.943</td><td>1.000</td><td>1.000</td><td><strong>0.000</strong></td><td>1.000</td><td>0.759</td><td>0.968</td><td>1.000</td><td>1.000</td><td><strong>0.999</strong></td><td><strong>0.000</strong></td><td><strong>0.999</strong></td></tr><tr><td>|q<sup>ref</sup>|</td><td>315</td><td>7</td><td>5</td><td>0</td><td>25</td><td>299</td><td>315</td><td>1</td><td>1</td><td>188</td><td>315</td><td>5985</td></tr><tr><td>|q(1M, A<sub>2</sub>)|</td><td>470 184</td><td>1 521</td><td>0</td><td>108</td><td>0</td><td>0</td><td>777 837</td><td>53 781</td><td>0</td><td>28 100</td><td>35 710</td><td>84 300</td></tr><tr><td>ARR<sub>A<sub>2</sub></sub></td><td><strong>0.415</strong></td><td>0.999</td><td><strong>0.000</strong></td><td>0.715</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.364</strong></td><td>0.957</td><td><strong>0.000</strong></td><td>1.000</td><td>0.959</td><td>1.000</td></tr><tr><td>|q<sup>ref</sup>|</td><td>336</td><td>5</td><td>0</td><td>1</td><td>0</td><td>0</td><td>336</td><td>1</td><td>0</td><td>147</td><td>1008</td><td>6048</td></tr><tr><td>|q(1M, A<sub>3</sub>)|</td><td>1 121 954</td><td>1 522</td><td>70 827</td><td>0</td><td>0</td><td>58 220</td><td>1 913 882</td><td>56 200</td><td>19 731</td><td>28 100</td><td>37 224</td><td>84 300</td></tr><tr><td>ARR<sub>A<sub>3</sub></sub></td><td>0.989</td><td>1.000</td><td>1.000</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.202</strong></td><td>0.895</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td></tr><tr><td>|q<sup>ref</sup>|</td><td>122</td><td>11</td><td>5</td><td>0</td><td>0</td><td>106</td><td>122</td><td>1</td><td>1</td><td>68</td><td>610</td><td>2318</td></tr><tr><td>|q(10M)|</td><td>11 958 511</td><td>16 236</td><td>755 971</td><td>585</td><td>2 145 750</td><td>3 182 610</td><td>23 219 926</td><td>600 000</td><td>210 336</td><td>600 000</td><td>573 483</td><td>900 000</td></tr><tr><td>|q<sup>ref</sup>|</td><td>1791</td><td>11</td><td>5</td><td>1</td><td>73</td><td>1775</td><td>1791</td><td>1</td><td>1</td><td>649</td><td>8955</td><td>34029</td></tr><tr><td>|q(10M, A<sub>1</sub>)|</td><td>11 302 423</td><td>16 236</td><td>755 971</td><td>0</td><td>2 145 729</td><td>2 452 499</td><td>22 528 719</td><td>599 999</td><td>210 334</td><td>299 995</td><td>0</td><td>899 987</td></tr><tr><td>ARR<sub>A<sub>1</sub></sub></td><td>0.945</td><td>1.000</td><td>1.000</td><td><strong>0.000</strong></td><td>1.000</td><td>0.771</td><td>0.970</td><td>1.000</td><td>1.000</td><td><strong>0.500</strong></td><td><strong>0.000</strong></td><td><strong>0.999</strong></td></tr><tr><td>|q<sup>ref</sup>|</td><td>1100</td><td>7</td><td>5</td><td>0</td><td>73</td><td>1084</td><td>1100</td><td>1</td><td>1</td><td>612</td><td>1100</td><td>20900</td></tr><tr><td>|q(10M, A<sub>2</sub>)|</td><td>5 037 030</td><td>16 235</td><td>0</td><td>542</td><td>0</td><td>0</td><td>9 522 562</td><td>597 581</td><td>0</td><td>300 000</td><td>571 189</td><td>900 000</td></tr><tr><td>ARR<sub>A<sub>2</sub></sub></td><td><strong>0.421</strong></td><td>0.999</td><td><strong>0.000</strong></td><td>0.926</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.410</strong></td><td>0.996</td><td><strong>0.000</strong></td><td><strong>0.5000</strong></td><td><strong>0.997</strong></td><td>1.000</td></tr><tr><td>|q<sup>ref</sup>|</td><td>1204</td><td>5</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1204</td><td>1</td><td>0</td><td>437</td><td>3612</td><td>21672</td></tr><tr><td>|q(10M, A<sub>3</sub>)|</td><td>11 879 546</td><td>16 236</td><td>755 971</td><td>0</td><td>0</td><td>1 527 609</td><td>21 665 733</td><td>600 000</td><td>210 336</td><td>300 000</td><td>573 483</td><td>900 000</td></tr><tr><td>ARR<sub>A<sub>3</sub></sub></td><td>0.993</td><td>1.000</td><td>1.000</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.480</strong></td><td>0.933</td><td>1.000</td><td>1.000</td><td><strong>0.500</strong></td><td>1.000</td><td>1.000</td></tr><tr><td>|q<sup>ref</sup>|</td><td>414</td><td>11</td><td>5</td><td>0</td><td>0</td><td>398</td><td>414</td><td>1</td><td>1</td><td>360</td><td>2070</td><td>7866</td></tr></tbody></table>

Next, we present a reformulation-based algorithm with filtering, or RFIL, in short.

1. (As in RAR and RARE) Reformulate $q$ on the restricted ontology, leading to a union of sub-queries $q^{\text{ref}}$.

2. For each sub-query $q_i$ of $q^{\text{ref}}$, apply Algorithm QFilter to filter $q_i$. Gather the resulting non-empty queries into a union, denoted $q^{\text{ref}}$.

3. Evaluate $q^{\text{ref}}$ over $\mathcal{G}$.

Considering the latest example, $q_6^{\text{ref}}(x) = q_6(x) \cup q_6^1(x)$ where $q_6^1(x) := (x, \tau, \text{SecurityOfficer})$. Therefore, $q_6^{\text{ref}}(x) := (x, \tau, \text{Employee}) \wedge (x \neq \text{SecurityOfficer})$, which has no results evaluated over $\mathcal{G}$.

# 8 Experiments

We detail the settings in Section 8.1 and our result analysis in Section 8.2.

## 8.1 Experimental settings

We implemented our algorithms in OntoSQL, a Java-based platform (https://ontosql.inria.fr), providing RDF storage, saturation [15], BGP query answering via evaluation or reformulation as in [9], atop Postgres 12.4. Experiments ran on CentOS Linux 7.5, 2.7 GHz Intel Core i7, 160 GB RAM.

**Implementation** OntoSQL optionally saturates graphs upon loading. Given a graph $\mathcal{G}$ and a set $A$ of access restrictions, we restrict $\mathcal{G}$'s triples directly upon loading, thus, we load only $\mathcal{G}_A$ and we can saturate it leading to $(\mathcal{G}_A)^+$. For entailment provenances (Section 5), we modified OntoSQL's saturation algorithm [15], as described in Section 5; we build directly the reduced entailment graph $\mathcal{G}_e$. We extended OntoSQL's BGPs to support BGPQs with filters, translating them into SQL by adding $v \prec \prec$ IRI predicates for each restricted IRI in $A$, to the WHERE clause.
<figure><img src="image_5.png" /><figcaption>Fig. 4: Per-query answering times.</figcaption></figure>

**Graphs** We used BSBM [6] graphs of 1M and 10M triples, having: 44 properties; 177 (respectively, 611) classes; 215 (respectively, 649) ontology triples using domain, range, subclass, and subproperty in this (decreasing) frequency order.

**Restrictions** Lacking a standard benchmark, we built three access restrictions sets $A_1, A_2, A_3$ to simulate varied scenarios. $A_1$ (10 IRIs) class IRIs such as `vocab:Offer` (56,208 mentions in 1M), `rev:Review` (28,106), `vocab:ProductFeature` (4,746), and `vocab:Product` (2,816). $A_2$ (60 IRIs) mixes classes (`vocab:Offer`, `vocab:Producer`, and `foaf:Person`), and properties (`productFeature`, `rating1-4`, `reviewDate`, and `dc:title`). $A_3$ (100 IRIs) is a narrow, instance-level restriction containing: 3 ProductFeatures, 3 Products, 19 Reviews and 75 Offers. IRIs in $A_1$, $A_2$ span diverse frequencies (11–56k mentions on 1M). Their *impact*: on 1M, $A_2$ removes 58.5% triples, while $A_1$ 6% and $A_3$ only 1%; on 10M, $A_2$ restricts 58% triples, $A_1$ 5.7% and
<table><caption>Table 3: Data loading times (ms) for 10M dataset and restriction set ($A_k$).</caption><thead><tr><th>Dataset (10M)</th><th>MAT</th><th>RTR</th><th>PROV</th><th>RARE</th><th>RFIL</th></tr></thead><tbody><tr><td>A<sub>1</sub></td><td>1 129 007</td><td>689 086</td><td>1 272 307</td><td>731 955</td><td>751 715</td></tr><tr><td>A<sub>2</sub></td><td>564 633</td><td>368 054</td><td>1 257 329</td><td>747 226</td><td>764 277</td></tr><tr><td>A<sub>3</sub></td><td>931 294</td><td>544 101</td><td>1 270 806</td><td>749 371</td><td>750 916</td></tr></tbody></table>

$A_3$ only 0.07%. Clearly, $A_2$ restricts the graph the most. For comparison, we use $A_0$, the empty restriction set.

**Queries** Our queries have 1 to 7 triples, returning from 0 to 22M results. Basic queries like $q_1$ (return all triples) and $q_2$ (find all foaf:Agents) test saturation overhead and filtering. $q_3$ retrieves ratings subjects; $q_4$ instances of ProductType (blocked under $A_1$ and $A_3$). Relational BGPs ($q_5-q_8$) join triples about, respectively: offers, product features, prices, and vendors (impacted by foaf: homepage in $A_2$). $q_9$, $q_{10}$ combine ontological and instance triples. $q_{11}$, $q_{12}$ trigger large reformulations. $q_{12}$ asks for any subject pointing to a Product.

## 8.2 Results

**Loading data with(out) restrictions** Table 3 shows loading and pre-processing times for the 10M dataset across restriction sets. PROV is slowest, followed by MAT. It comes from the fact that MAT saturates $G_A$, while PROV saturates $G$ entirely and builds the entailment graph $G_e$. RARE and RFIL are faster, as they just load $G$. RTR is fastest, filtering triples upon ingestion, so the restricted triples never make it into the database.

We measure **query sensitivity to restrictions** first **syntactically** via $|q^{\text{ref } A_k}|$, the number of reformulation (BGPQs in the union) in case of restriction set $A_k$, and **semantically** via $ARR_{A_k}$ the Answer Retention Ratio: the fraction of query answers without restrictions that are returned under $A_k$. Table 2 show $|q^{\text{ref } A_k}|$ and $ARR_{A_k}$ per query, highlighting strong (**bold**), moderate (**italics**), or no impact (normal). For example, $q_6$, is fully blocked under $A_2$ (ARR 0.00), but retains 75% answers under $A_1$, and 20% under $A_3$.

**Query answering times** appear in Figure 4 for both datasets (logarithmic y-axis). Missing bars indicate runs exceeding a 20-minute timeout. Queries rejected by the simple IRI check (Sec. 3.1) are plotted at 1ms, even when they took less, for distinction from timeout. **Simple queries** $q_1$ and $q_2$ show small runtime differences across restriction sets. $q_1$ consistently takes longer due to its large result set, especially in PROV. RFIL exhibits slight overhead due to high reformulation size. $q_2$ has minimal reformulation overhead. **Mildly restricted queries** $q_3$, $q_4$, $q_8$ and $q_9$ are blocked or moderately impacted under $A_k$. They have small reformulation sizes, therefore, while PROV takes the longest (particularly in $A_2$), the reformulation based algorithms, like RARE, are fast. $q_4$ is rejected outright under $A_1$ and $A_3$. $q_8$ and $q_9$ maintain stable runtimes across algorithms, with PROV slower by at least a factor of 2. **Joins with moderate to large reformulations** ($q_5$, $q_6$, $q_{10}$): $q_5$ and $q_6$ are blocked under $A_2/A_3$, stopping early, but under $A_1$ runtimes mirror unrestricted performance ($A_0$). $q_{10}$ with its many reformulations in all $A_k$, shows PROV's advantage over RFIL/RARE. **Complex reformulations** $q_7$, $q_{11}$ and $q_{12}$ show high cost and
timeouts for reformulation-based methods ($|q^{\text{ref}A_k}|$ reaching 6 000+ for $q_{12}$), while PROV performs better.

**Discussion** In practice, multiple users may operate over a single graph, each with their own restriction set $A_u$. This raises questions about the best query answering strategy when balancing loading time, query time, and disk usage. Baseline algorithms MAT and RTR perform well in query evaluation but require storing a distinct graph for each user. This may lead to large disk consumption and high loading times. MAT further amplifies this by storing fully materialized graphs. In contrast, RFIL, RARE and PROV avoid per-user copies by operating on the original graph or its saturation. However, RARE suffers in complex reformulation cases, while RFIL when restriction sets are big. PROV is a robust solution, but it is frequently 10 times slower, especially with large answer sets.

**Takeaway** The optimal strategy depends on many characteristics: for few users or highly static graphs, MAT and RTR may be acceptable despite storage costs. As user count grows, reformulation or filtering strategies become preferable. Among these, PROV is robust for complex queries; RFIL and RARE handle most workloads efficiently.

# 9 Related Work

The classical *role-based access control (RBAC)* involves *users*, *roles* (operational needs), and *privileges* associating a role to (data object, access mode), e.g., the data object may be a table, or a query over it, and the access mode could be *read* or *write*. Since user-role separation is useful but straightforward, we omit it for clarity and discuss privileges given to users directly. More recent research works on access control in relational databases introduce predicate-level access control [11], leverage encryption, e.g., [25], middleware architectures [23], etc.

Early **policy-based frameworks for RDF stores** treat triples and their insertion/deletion as controlled actions with explicit rules. [16] presents an access control model for OWL ontologies, but do not provide query evaluation or answering methods. Privileges in [17] are triple patterns, positive (permitting) or negative (forbidding); this may cause conflicts. The authors consider a limited form of RDFS reasoning, propagating privileges along subclassOf and subpropertyOf hierarchies and determine whether a triple is permitted or forbidden for a user, but query answering is not studied. RDF access privileges in [24] permit or prohibit users to insert, delete, or read triples matching specific patterns; privileges can be conditioned by predicates over the user and/or the triples, such as “only the creator of class *C* may add (*x*, *τ*, *C*)”). A prototype implementation using Jena checks triple-level actions with RDFS reasoning. However, it requires maintaining per-triple “access labels” which is costly (no experiments are provided). Queries with multi-triple bodies are not supported.

Focusing on **query (read)** access control, several works enforce it by **rewriting SPARQL queries** before evaluation. They specify positive and negative access policies as queries and add them to user queries to exclude unauthorized results—some using `MINUS` [3], others using `FILTER`. Reasoning is often not considered. Our MFIL algorithm is very similar (but as we have shown, incomplete in the presence of ontologies). In [19], privileges grant or restrict
access over relational BGP results. User queries are then rewritten over the set of privileges seen as materialized views, for two semantics (considering that data not covered by the policies is permitted, respectively, is restricted). Reasoning is not considered; the method remains unimplemented. The fQuery approach [21] defines an access control policy as a set of positive and negative filters on query results, attached to a user; ontologies or reasoning are not considered. A user's SPARQL query is rewritten by injecting FILTER clauses reflecting the access control policies; this corresponds to our MFIL algorithm. Similarly, [8] rewrites queries to restrict visible graphs. Authorization ontologies (permissive policies) are used to define graph-level visibility, and rewritten queries derive only accessible graphs. Some techniques store accessibility labels for each triple. In [13], triples are annotated with labels ("accessible" / "inaccessible") conditioned by conjunctive RDF queries. This raises efficiency issues when policies change, as labels must be recomputed. This is impractical for multi-user scenarios, reasoning is also not considered. In [22], triple access labels are logical formulas that may involve labels of other triples. Policies restrict some triples, and RDFS reasoning (e.g., via subclassOf relationships) propagates restrictions. Labels are dynamically (re-)evaluated upon access requests. However, only certain policies is studied experimentally, and generalizing to multi-user settings would require RDF store modifications impacting performance.

Efficient provenance capture is the topic of [5]. Our provenance gathering (Section 5) aligns with their semi-naïve one; their more efficient method assumes that the original graph is saturated, an assumption which, for full generality, we do not make.

**RDF access control based on OWL** (not RDFS) ontologies has also been investigated. In [10], OWL is used to specify restrictions and policies, while a query can only request one resource. OWL defines classes by expressive logical formulas (intersection, existential/universal quantifiers, etc.). This is leveraged in [20,14], where access restrictions define classes such that determining whether an IRI is accessible reduces to an OWL inference task. In [20], a dedicated OWL ontology is introduced for access restrictions, including property reification, while [14] defines one class per authorization: restricting *C* denies access to any IRI of type *C* and its subclasses. These flexible approaches incur high OWL inference costs [14]. Unlike our BGPs (Section 2.2), these works support relational BGP triple patterns. A survey [18] focuses on positive and negative privileges (grant/restrict), conflict resolution, and highlights the lack of reasoning support in most prior solutions. Departing from RBAC models, a **cryptography-based** RDF access control approach is presented in [12]. A data owner encrypt each triple (or a part of it) and shares decryption keys tied to query patterns. A user may decrypt data if their keys satisfy the relevant predicate, enabling fine-grained access at the triple level.

**Privacy in graph data sharing.** Beyond access restrictions, recent works [7,27] explore transforming RDF graphs, i.e., anonymizing nodes, or modifying sensitive graph portions. These works ignore ontologies; combining them with ours is an interesting area of future work.
**Acknowledgements.** This work is funded by the France 2030 investment plan, supporting the DXP project as part of the IPCEI-CIS European initiative.

**References**

1. RDF 1.1 Semantics. https://www.w3.org/TR/rdf11-mt/#rdfs-entailment (Feb 2014)

2. Extended version of this work (2025), available at https://hal.science/view/index/docid/5250941

3. Abel, F., Coi, J.L.D., Henze, N., et al.: Enabling advanced and context-dependent access control in RDF stores. In: The Semantic Web (2007)

4. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The dl-lite family and relations. J. Artif. Intell. Res. 36 (2009)

5. Belhajjame, K., Mejri, M.Y.: Online maintenance of evolving graphs with RDFS-based saturation and why-provenance support. J. Web Semant. 78 (2023)

6. Bizer, C., Schultz, A.: The berlin SPARQL benchmark. IJSWIS 5(2) (2009)

7. Boiret, A., Eichler, C., Nguyen, B., Taki, S.: Graph rewriting primitives for semantic graph databases sanitization. Comput. Sci. Inf. Syst. 21(3) (2024)

8. Brunk, C., Sigg, L., Harth, A.: Enforcing scalable authorization on SPARQL queries. In: SEMANTiCS (2016)

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

10. Carminati, B., Ferrari, E., Heatherly, R., et al.: A semantic web based framework for social network access control. In: SACMAT (2009)

11. Chaudhuri, S., Dutta, T., Sudarshan, S.: Fine grained authorization through predicated grants. In: ICDE (2007)

12. Fernández, J.D., Kirrane, S., Polleres, A., Steyskal, S.: Self-enforcing access control for encrypted RDF. In: ESWC (2017)

13. Flouris, G., Fundulaki, I., Michou, M., Antoniou, G.: Controlling access to RDF graphs. In: FIS (2010)

14. Fornara, N., Marfia, F.: Modeling and enforcing access control obligations for SPARQL-DL queries. In: SEMANTiCS (2016)

15. Goasdoué, F., Manolescu, I., Roatis, A.: Efficient query answering against dynamic RDF databases. In: EDBT/ICDT (2013)

16. Ionita, C.M., Osborn, S.L.: Specifying an access control model for ontologies for the semantic web. In: SDM (2005)

17. Jain, A., Farkas, C.: Secure resource description framework: An access control model. In: SACMAT (2006)

18. Kirrane, S., Mileo, A., Decker, S.: Access control and the resource description framework: A survey. Semantic Web 8(2) (2017)

19. Li, J., Cheung, W.K.: Query rewriting for access control on semantic web. In: Secure Data Management (2008)

20. Masoumzadeh, A., Joshi, J.: Osnac: An ontology-based access control model for social networking systems. In: SocialCom (2010)

21. Oulmakhzoune, S., Cuppens-Boulahia, N., Cuppens, F., et al.: fQuery: SPARQL query rewriting to enforce data confidentiality. In: DBSec. vol. 6377 (2010)

22. Papakonstantinou, V., Michou, M., Fundulaki, I., et al.: Access control for RDF graphs using abstract models. In: SACMAT (2012)

23. Pappachan, P., Yus, R., Mehrotra, S., Freytag, J.C.: Sieve: A middleware approach to scalable access control for database management systems. PVLDB 13(11) (2020)

24. Reddivari, P., Finin, T., Joshi, A.: Policy-based access control for an RDF store. In: IJCAI Workshop: Semantic Web for Collaborative Knowledge Acquisition (2007)

25. Sarfraz, M.I., Nabeel, M., Cao, J., Bertino, E.: Dbmask: Fine-grained access control on encrypted relational databases. In: CODASPY (2015)

26. Senellart, P., Jachiet, L., Maniu, S., Ramusat, Y.: ProvSQL: Provenance and probability management in PostgreSQL. PVLDB 11(12) (2018)

27. Taki, S., Boiret, A., Eichler, C., Nguyen, B.: Cohesive database neighborhoods for differential privacy: Mapping relational databases to RDF. In: WISE (2024)

28. RDF Schema. https://www.w3.org/TR/rdf12-schema/