# RDF Query Answering in the Presence of Access Restrictions

Maxime Buron, Hritika Kathuria, Ioana Manolescu, George Siachamis

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

## To cite this version:

Maxime Buron, Hritika Kathuria, Ioana Manolescu, George Siachamis. RDF Query Answering in the Presence of Access Restrictions. INRIA; Ecole polytechnique. 2025. [hal-05250941](https://hal.science/hal-05250941v1)

HAL Id: hal-05250941

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

Submitted on 12 Sep 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>
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 *u* 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) [29] provides properties
allowing to state relationships between classes and/or properties. For instance,
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,23] without full query answering; others use OWL [21,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
<figure><img src="image_3.png" /><figcaption>Fig. 1: Sample RDF graph.</figcaption></figure>

them various *classes*, or types. For instance, the triple (Alice, τ, 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 [29] (**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}, \text{SecurityOfficer}), (\text{Alice}, \text{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 \in \mathcal{U}$ is a user and $r$ is an IRI, different from subclassOf, subpropertyOf, domain, range and $\tau$.

We exclude the $\tau$ 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 \in \mathcal{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 $\mathcal{G}$ i.e. $A \subseteq Val(\mathcal{G})$.

**Definition 5 (Restricted graph).** We define the restriction of a graph $\mathcal{G}$ based on $A$, denoted $\mathcal{G}_A$, as follows:

$$ \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, SecurityOfficer), (u, 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}, \subset\subset\subset\subset\subset\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.

*Proof.* Each RDF inference rule is of the form $t_1, t_2 \Rightarrow t_3$, where triple $t_3$ is entailed from $t_1$ and $t_2$. It follows from the set of possible RDFS entailment rules [15] that $t_3$ may contain IRIs:

- That appear in $t_1$ and/or $t_2$;

- Or, the IRI $\tau$, even if it was not present in $t_1$ nor in $t_2$. For instance, from (Bob, securityPermit, "SO24"), (securityPermit, domain, SecurityOfficer), the entailed triple (Bob, $\tau$, securityOfficer) introduces $\tau$.
As per Definition 4, $\tau$ cannot be restricted. Thus, the entailed triple cannot introduce a restricted IRI.

**Property 2 (Inclusion).** The following inclusion holds :

$$ (\mathcal{G}_A)^+ \subseteq (\mathcal{G}^+)_A $$

In general, the opposite inclusion does not hold.

*Proof.* Let $t \in (\mathcal{G}_A)^+$, $t$ also belongs to $G^+$, since $G_A \subseteq G$ and the saturation is monotonic, so $(\mathcal{G}_A)^+ \subseteq \mathcal{G}^+$. Moreover according to Property 1 does not contain any restricted IRI, it implies that $(\mathcal{G}_A)^+ \subseteq (\mathcal{G}^+)_A$.

For our sample graph, we obtain:

$$ (\mathcal{G}_A)^+ = \{ (\text{Alice}, \tau, \text{Clerk}), (\text{Clerk}, \text{subclassOf}, \text{Employee}), (\text{Alice}, \text{worksFor}, \text{ACME}), (\text{Bob}, \text{worksFor}, \text{ACME}), (\text{Alice}, \tau, \text{Employee}) \} $$

One additional triple is introduced in $(\mathcal{G}^+)_A : (\text{Bob}, \tau, \text{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 $\phi$ can map a triple pattern in the body of $q$, into a restricted $\mathcal{G}^+$ 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
<figure><img src="image_4.png" /><figcaption>Fig. 2: Overview of our algorithms.</figcaption></figure>

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) :-(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$.

**Soundness** We show that every answer $a$ returned by evaluating the reformulated query $q^{\text{ref } A}$ over $\mathcal{G}_A$ does not contain a restricted IRI.

1. By definition, $\mathcal{G}_A$ has no triple featuring a restricted IRI.
2. The reformulation process uses only the ontology triples in $\mathcal{G}_A$. Thus, the reformulated query does not contain any restricted IRI, either.

3. When the reformulated query is evaluated over $\mathcal{G}_A$, all answers are derived solely from permitted triples.

Thus, algorithm RTR is sound.

**Completeness** We show that every query answer as per Definition 6 is returned by the algorithm.

As per [9], the query reformulation step in RTR is complete, which means that: evaluating $q^{\text{ref } A}$ over $\mathcal{G}_A$ yields all the answers to $q(\mathcal{G}_A)$. In turn, by definition of query answers (Section 2.2), each such answer corresponds to a homomorphism from $q$ into $(\mathcal{G}_A)^+$, concluding the proof. RTR is thus correct.

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. Unlike MAT, PROV does not require store $(\mathcal{G}_A)^+$ for each set of access restrictions $A$; instead, it relies on the saturated graph $\mathcal{G}^+$. As shown in Property 2, a query answering algorithm that evaluates the query over the restriction of the saturated graph may 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) :- (x, \tau, y)$, $(x, \text{worksFor}, \text{ACME})$ (Section 2.2), the extension is $\tilde{q}_1(x, y) :- (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}(\mathcal{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., [27]; 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>AτC</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
<figure><img src="image_5.png" /><figcaption>Fig. 3: Entailment graph for the sample graph in Figure 1.</figcaption></figure>

entailment for $n_{ArE}$; this is shown by blue nodes and edges in Figure 3. Similarly, $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.

**Soundness** We show that the algorithm is sound, that is, every returned answer $a$ belongs to $q(\mathcal{G}, A)$.

1. By Definition 10, the first step builds all the entailments of each triple $t$ in $\mathcal{G}^+$.

2. Evaluating $\tilde{q}$ (and not the given query $q$) guarantees that all the triples enabling an homomorphism from $q$ into $\mathcal{G}^+$ (and not just the IRIs matching variables in the query head) are retrieved in $T_r$ for each result $r$ of $\tilde{q}^0(\mathcal{G}^+)$.
3. A result $r$ leads to an answer iff each triple in $T_r$ has a permitted provenance.

**Completeness:** We show that every expected answer $a$ is returned by the algorithm.

1. First, due to the relationship between $q$ and $\tilde{q}$, for each result $r_q \in q^0(\mathcal{G}^+)$, there exists at least one result $r_{\tilde{q}} \in \tilde{q}^0(\mathcal{G}^+)$, such that a projection of $r_{\tilde{q}}$ yields exactly $r_q$. Thus, for each expected answer, our algorithm produces at least one result of $q^0(\mathcal{G}^+)$ from which the desired answer can be projected.

2. Definition 8 ensures we obtain from each $r \in q^0(\mathcal{G}^+)$ all the triples from which it has been computed. Next, the completeness of $\mathcal{G}_e$ (which holds all the entailments for each triple) ensures our checks guarantee that an answer is returned as soon as all these triples have one permitted provenance.

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

*Proof.* Building on the correctness proof of Algorithm PROV, we only need to show that the test at step (3(b)i) correctly decides whether every triple $t$ leading to a result $r$ has a permitted entailment provenance. There are two cases:

- $t$ is not explicit, but only implicit. Then, $\mathcal{G}_e$ stores all its entailment provenances, and the correctness proof of PROV applies directly.

- $t$ is explicit, in which case we can further distinguish two possibilities:

* $t$ contains a restricted IRI; in this case, $t$ is not permitted (whether or not it had been entailed);

* $t$ does not contain a restricted IRI; then, $t$ has at least one permitted provenance: the explicit one. Thus, we do not need to store the possible entailments it may have had.

# 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}$.

**Completeness** We show that algorithm RAR produces every answer that should be returned. As established in [9], the reformulation process is complete with respect to the ontology given in its input. In RAR, that ontology is $\mathcal{O}_A$. Therefore, any answer entailed from $\mathcal{G}$ (which Algorithm RAR does not restrict) and the permitted ontology is actually produced by RAR.

However, it turns out that algorithm RAR 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 provide an algorithmic variant, and establish limited correctness results. Algorithm **RARE** (Restriction-Aware Reformulation and Extension) proceeds as follows:

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 $\tilde{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(\mathcal{G})$: if all the triples in $T_r$ are permitted, then the projection $\pi_{\tilde{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.

- For relational BGPs (Definition 3), Algorithm RAR is sound.

- Algorithm RARE is sound for general BGPs.

*Proof.* We start by noting that each reformulation step uses only permitted O triples, and adds only triple patterns using permitted IRIs. Hence, if the initial restriction check did not remove the original query q, we know that $q^{\text{ref A}}$ only contains permitted IRIs.

**RAR soundness for relational BGPs** We show that any G triple t matching a triple $t_q$ in the body of one conjunctive query in $q^{\text{ref A}}$ is permitted. One of the following must hold for t:

- t is a τ triple; therefore, $t_q$ is also an τ triple; $t_q$ has no variable in the object (class) position (because q is relational), thus $t_q$ has a (permitted) IRI as object. Because t matches $t_q$, t has the same permitted IRI as object; the subject of t is not restricted, because AR are CP restrictions.

- t is a data triple; then, $t_q$ has the same IRI in the property position (since it cannot have a variable); this property URI is permitted, otherwise the query is removed by the initial restriction check. The subject and object of t are not restricted.

Note that t cannot be an ontology triple, because q is relational, thus it is not allowed to query the ontology; q has no variable in a property position, either, thus no ontology triple can match it. Thus, all the triples that may lead to a result computed by RAR are permitted, concluding our proof.

**RARE soundness for general BGPs** Algorithm RARE makes the extra effort of evaluating extended queries, and checking the triples in each result, in order to remove possible erroneous bindings that it may introduce at step (3a). This ensures its soundness.

# 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 [22], 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.

$$(q^f)^0(G) = \{r \mid r \in q^0(G) \wedge (\bigwedge_i (v_i \neq a_i))\}$$
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 (QFilter, and accordingly, the query it builds, do not take the ontology into account):

1. Let $I$ be a set of inequality predicates, initially empty, and $\mathcal{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$.

Note that algorithm QFilter can be seen as a generalization of the restriction test we have presented early on; it returns an empty query exactly for those queries on which the restriction check (Section 3.2) returns an empty result.

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

1. Saturate $\mathcal{G}$.

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

3. Evaluate $q^f$ over $\mathcal{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) :- (x, \tau, Employee)$, the filtered query $q_6^f$ is: $q_6^f(x) :- (x, \tau, Employee) \land (x \neq SecurityOfficer)$. Evaluating this over $\mathcal{G}^+$ returns Bob, even though the correct answer is empty. The problem is that filtering acts on the consequences of inference and can no longer discern that some results are due to restricted IRIs.

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 f}}$.

3. Evaluate $q^{\text{ref f}}$ 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 f}}(x) :- (x, \tau, \text{Employee}) \land (x \neq \text{SecurityOfficer})$, which has no results evaluated over $\mathcal{G}$.

**Soundness** We avoid the use of restricted triples in reasoning by pruning the reformulation in step (1). The inequality predicates added by query filtering on *all variables* ensure no homomorphism leading to an answer can rely on restricted IRIs.

**Completeness** Because the reformulation algorithm is complete, and because filtering $q^{\text{ref}}$ only removes answers from bindings that contradict the restrictions, all answers are found.
<table><caption>Table 2: Query metadata.</caption><thead><tr><th>Query q</th><th>q<sub>1</sub>(x, y, z)</th><th>q<sub>2</sub>(x)</th><th>q<sub>3</sub>(x, y)</th><th>q<sub>4</sub>(x)</th><th>q<sub>5</sub>(o, u, p, d, v)</th><th>q<sub>6</sub>(x, y, z)</th><th>q<sub>7</sub>(l, p, pr)</th><th>q<sub>8</sub>(x, y, z)</th><th>q<sub>9</sub>(x, y)</th><th>q<sub>10</sub>(r, p, l, n, t)</th><th>q<sub>11</sub>(l, o)</th><th>q<sub>12</sub>(s, p)</th></tr></thead><tbody><tr><th>|q|</th><td>1</td><td>1</td><td>1</td><td>1</td><td>7</td><td>3</td><td>4</td><td>3</td><td>2</td><td>6</td><td>4</td><td>2</td></tr><tr><th>Relational?</th><td>No</td><td>Yes</td><td>No</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td></tr></tbody></table>

# 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 $G$ and a set $A$ of access restrictions, we restrict $G$'s triples directly upon loading, thus, we load only $G_A$ and we can saturate it leading to $(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 $G_e$. We serialize it JSON and bring it in memory when needed by an algorithm. We extended OntoSQL's BGPs to support BGPQs with filters, translating them into SQL by adding $v <> IRI$ predicates for each restricted IRI in $A$, to the WHERE clause.

**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 $A_3$ only 0.07%. Clearly, $A_2$ restricts the graph the most. For comparison, we use $A_0$, the empty restriction set.

## 8.2 Results

**Loading data with(out) restrictions** Table 4 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^{ref}A_k|$, the number of reformulation (BGPQs in the union) in case of restriction set $A_k$,
<figure><img src="image_6.png" /><figcaption>Fig. 4: Per-query answering times.</figcaption></figure>

and **semantically** via $ARR_{A_k}$ the *Answer Retention Ratio*: the fraction of query answers without restrictions that are returned under $A_k$. Table ?? 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. The extended versions $\tilde{q}_1, \tilde{q}_2$ closely track the originals. 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., [26], middleware architectures [24], 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 [25] 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 [20], 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 [22] 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 [23], *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.

Other methods **either accept or reject the incoming query**. In [18], authorizations can be granted to a user to perform an operation (read or write) on the triples matching the body of a query *q*. They can also be propagated to another user, via hand-written rules. Exact matching is required between an authorization and a data access requests; thus, an authorization to a triple set would fail to give access to a subset of this set, which is counterintuitive. To evaluate a user query *q*, their method checks for an authorization covering the *exact body* of *q*; if none exists, the query is rejected. The authors do not discuss correctness, completeness, or reasoning. **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 [21,14], where *access restrictions define*
classes such that determining whether an IRI is accessible reduces to an OWL inference task. In [21], 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 [19] 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 explore *transforming* RDF graphs, i.e., anonymizing nodes, or modifying sensitive graph portions. In [7], this is achieved by a formal set of graph transformation operators, which can be combined to achieve all the desired information. In [28], differential privacy mechanisms for exchanging information between a relational and an RDF database are discussed. 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://drive.google.com/file/d/1Z0FbUiz60kkjHfaMM3kwa5Nw13s2iEMT/view?usp=sharing

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., Abdelrahman, A., Mileo, A., Decker, S.: Secure manipulation of linked data. In: ISWC (2013)

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

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

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

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

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

24. 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)

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

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

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

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

29. RDF Schema. https://www.w3.org/TR/rdf12-schema/
<table><caption>Table 3: Queries used in our experiments.</caption><thead><tr><td>QueryName</td><td>Query</td></tr></thead><tbody><tr><td>q1</td><td>&lt;x, y, z&gt; :- triple(x, y, z);</td></tr><tr><td>q2</td><td>&lt;x&gt; :- triple(x, rdf:type, foaf:Agent);</td></tr><tr><td>q3</td><td>&lt;x, y&gt; :- triple(x, bsbm:rating, y);</td></tr><tr><td>q4</td><td>&lt;x&gt; :- triple(x, rdf:type, bsbm:ProductType);</td></tr><tr><td>q5</td><td>&lt;offer, offerURL, price, deliveryDays, value&gt; :- triple(offer, bsbm:offerWebpage, offerURL), triple(offer, bsbm:price, price), triple(offer, bsbm:deliveryDays, deliveryDays), triple(offer, bsbm:product, product), triple(product, rdf:type, bsbm:ProductType4), triple(product, bsbm:productFeature, value), triple(product, bsbm:producer, producer);</td></tr><tr><td>q6</td><td>&lt;product, feature, type&gt; :- triple(product, bsbm:productFeature, feature), triple(product, rdf:type, type);</td></tr><tr><td>q7</td><td>&lt;productLabel, productProperty, price&gt; :- triple(product, rdfs:label, productLabel), triple(product, property, productProperty), triple(offer, bsbm:product, product), triple(offer, bsbm:price, price);</td></tr><tr><td>q8</td><td>&lt;offer, vendor, vendorHomepage&gt; :- triple(offer, bsbm:vendor, vendor), triple(vendor, rdfs:label, vendorLabel), triple(vendor, foaf:homepage, vendorHomepage);</td></tr><tr><td>q9</td><td>&lt;review, rating&gt; :- triple(review, bsbm:reviewFor, product), triple(review, bsbm:rating2, rating);</td></tr><tr><td>q10</td><td>&lt;review, product, label, personName, title&gt; :- triple(review, bsbm:reviewFor, product), triple(review, dc:title, title), triple(review, rev:reviewer, person), triple(person, foaf:name, personName), triple(product, rdfs:label, label), triple(review, rdf:type, x);</td></tr><tr><td>q11</td><td>&lt;productLabel, organization&gt; :- triple(product, rdfs:label, productLabel), triple(offer, bsbm:product, product), triple(offer, offerProperty, organization), triple(organization, rdf:type, foaf:Organization);</td></tr><tr><td>q12</td><td>&lt;pointingToProduct, product&gt; :- triple(pointingToProduct, property, product), triple(product, rdf:type, bsbm:Product);</td></tr></tbody></table>
<table><caption>Table 4: 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>