# SHARP: A Hybrid Approach for SPARQL Query Relaxation

Ginwa Fakih, Patricia Serrano-Alvarado, Matthieu Perrin

► To cite this version:

Ginwa Fakih, Patricia Serrano-Alvarado, Matthieu Perrin. SHARP: A Hybrid Approach for SPARQL Query Relaxation. 21st International Conference on Semantic Systems (SEMANTiCS), Aug 2025, Vienna, Austria. pp.194 - 216, 10.3233/SSW250020. http://05228252

HAL Id: hal-05228252

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

Submitted on 28 Aug 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>
SHARP : A Hybrid Approach for
SPARQL Query Relaxation

Ginwa FAKIH a,<fnref n="1" />, Patricia SERRANO-ALVARADO a and Matthieu PERRIN a

a LS2N, UMR 6004, Nantes Université, 44300 Nantes, France

ORCiD ID: Ginwa Fakih https://orcid.org/0009-0009-8510-0724, Patricia

Serrano-Alvarado https://orcid.org/0000-0003-2367-5361, Matthieu Perrin

https://orcid.org/0000-0002-8019-0830

**Abstract.**

**Purpose:** Existing relaxation works either focus on ontology-based or entity-based elements, leaving a gap in handling queries that combine both. The purpose of this paper is to fill this gap and relax real-world SPARQL queries combining ontology-based and entity-based techniques to retrieve top-*k* relevant results.

**Methodology:** We propose a hybrid query relaxation solution with a ranking system based on information content, integrating ontology-based and entity-based strategies by extending similarity measures beyond classes to entities and literals.

**Findings:** The model retrieves relevant top-*k* results and better aligns with user expectations across diverse query types. It effectively ranks relaxed queries involving ontology-based and instance-based relaxations.

**Value:** This work introduces a unified relaxation framework and an evaluation benchmark grounded in human-judgment-based relevance. It advances the literature by providing a relaxation system that aligns closely with user-validated relevance, especially for queries involving annotations.

**Keywords.** Query relaxation, Ontology, Information Content, Metadata, Reification.

# 1. Introduction and motivation

In recent years, semantic knowledge graphs (KGs) have become powerful tools for representing complex, interconnected information. They contain rich semantic links between entities, enabling advanced data retrieval across domains. However, querying KGs is challenging, especially with complex queries involving classes, properties, entities, and literals. Often, queries return empty or insufficient results due to being too restrictive, misaligned with the ontology, or incompatible with the data representation. One solution to this problem is query relaxation, the process of adjusting the constraints of a query to make it more flexible in order to retrieve approximate results. When a user query returns too few results, relaxation techniques aim to return the *top-*k *similar results* to the original target. A significant body of work has been dedicated to query relaxation, which can be categorized into two main groups of approaches.

*Ontology-based approaches* use the structured relationship between classes and properties within the ontology to broaden the search scope. Each triple pattern has mul-

<footnote n="1">¹Corresponding Author: Author Name, contact details.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1. Example of SPARQL query Q and some relaxed queries Q'.</figcaption></figure>

triple relaxation possibilities, forming a relaxation lattice. The overall lattice is the Cartesian product of the relaxation lattices of triple patterns of the initial query. The relaxation lattice generated by this approach can grow exponentially due to deep class and property hierarchies. Since exploring the entire lattice of relaxed queries is infeasible, most approaches aim to selectively identify those queries that return the top-k results. Although the lattice defines a partial order among queries, queries at the same level are not directly comparable, requiring a similarity measure to rank them. Most approaches rely on statistics on classes and properties to guide this ranking. Some, rank queries by relaxation distance [1,2,3], while others use information content (IC) [4,5,6,7,8]. Such approaches address domain-specific queries, where the interest lies in types of things. These queries are common where domain-specific ontologies are available.

Entity-based approaches replace entities and literals with similar alternatives using precomputed ranking orders among entities and literals through mapping functions. They rank relaxed queries based on different solutions, such as word embeddings [9], symbolic similarity [10], numeric distance functions [11], and JS-divergence between statistical models [12]. They are well suited for entity-centric queries, where users seek information about specific individuals, places, organizations, objects, etc.

However, real-world queries frequently involve a combination of both approaches including classes, properties, entities, and literals. For example, query *Q*, shown in gray in Figure 1, searches for 2 students who are friends with Maya, and who are enrolled in a "very easy" course. Suppose this query yields no results but there exist Maria and John which are the 2-most similar results for the original query. Figure 1 proposes several relaxed queries *Q'* generated using existing relaxation strategies. The similarity measures for *Q'*_1, *Q'*_2, and *Q'*_3 are computed using information content-based similarity measures, as proposed by Huang et al. [5]. In contrast, the similarity measures for *Q'*_4 and *Q'*_5 are calculated using the Jaccard similarity and the cosine similarity of embeddings, respectively. For ontology-based techniques, three relaxed queries can be generated:

* Q'1 (Class Relaxation) Generalizing *Student* to *Person* (no results).

* Q'2 (Property Relaxation) Relaxing the property *enrolledIn* to *attends* (1 result: Maria). This retrieves students who attend a very easy course.
* Q'3 (Simple Relaxation) Replacing the constraint difficulty "very easy" with a variable(2 results: Sam, John). This retrieves students in courses of any difficulty, but loses the focus on difficulty.

Concerning instance-based relaxation, two relaxed queries can be considered:

* Q'4 (Literal Relaxation) Replacing the difficulty level "very easy" with "easy" suppose produces one result: John.

* Q'5 (Entity Relaxation) Replacing an instance (Maya) with the most similar instance (suppose it is Patricia) does not return results.

<table><caption>**Table 1.** Similarity between different students (computed using RDF-star2Vec).</caption><thead><tr><th>Person 1</th><th>Person 2</th><th>Similarity</th></tr></thead><tbody><tr><td>ex:Alice</td><td>ex:Maya</td><td>0.80</td></tr><tr><td>ex:Maya</td><td>ex:John</td><td>0.75</td></tr><tr><td>ex:Maria</td><td>ex:Maya</td><td>0.67</td></tr><tr><td>ex:Maria</td><td>ex:John</td><td>0.60</td></tr><tr><td>ex:Alice</td><td>ex:John</td><td>0.50</td></tr><tr><td>ex:Alice</td><td>ex:Maria</td><td>0.30</td></tr></tbody></table>

<table><caption>**Table 2.** Similarity between difficulty levels (computed using Jaccard measure).</caption><thead><tr><th>Level 1</th><th>Level 2</th><th>Similarity</th></tr></thead><tbody><tr><td>very easy</td><td>easy</td><td>0.80</td></tr><tr><td>easy</td><td>hard</td><td>0.40</td></tr><tr><td>very easy</td><td>hard</td><td>0.20</td></tr></tbody></table>

Tables 1 and 2 show the similarity scores between students and between difficulty levels, respectively (Figure 3 in the Appendix A.5 shows the ontology and the dataset used for this motivating example). These scores can be used in instance-based relaxation to substitute entities or literals with their most similar alternatives, as illustrated in the relaxed queries Q'4 and Q'5. Although the closest results to those expected in the original query are Maria (from Q'2) and John (from Q'4), no existing approach retrieves both together. This limitation highlights the need for a strategy that combines ontology-based and instance-based relaxations. To the best of our knowledge, no such approach exists, thus our goal is to develop a hybrid approach to improve the quality and completeness of SPARQL query relaxation.

Leveraging both types of relaxation introduces three main challenges:

* *Designing a unified hybrid similarity ranking.* A unified ranking function is needed to consistently order relaxed queries from both ontology- and instance-based strategies. This requires extending the Information Content framework to entities and literals, and aligning query elements in a common semantic space while preserving their original ranking order from precomputed mapping functions.

* *Establishing a reliable evaluation benchmark.* Evaluating the effectiveness of relaxed queries demands a benchmark that reflects human judgment. Designing such a benchmark involves selecting representative queries, generating meaningful relaxations, and collecting user-validated relevance assessments—all while ensuring scalability, fairness, and reproducibility.

The research problem addressed in this paper is as follows: *given a knowledge graph and a failing query, how can we define an efficient hybrid system that combines ontology-based and instance-based relaxations, while extending IC-based similarity from the entity level to the class level?*

Our contributions are twofold. We propose SHARP, a SPARQL Hybrid Query Relaxation Approach, with a new ranking system that combines both ontology-based and instance-based relaxations. This system ensures a total order over relaxed queries. We also introduce a benchmark that measures how well results match user expectations, rather than execution time or query count.
The rest of the paper is structured as follows. Section 2 introduces related works. Section 3 introduces the necessary background and definitions. Section 4 elaborates on our contributions, detailing the novel similarity functions introduced in this work to address the identified challenges. Section 5 describes the proposed benchmark, which serves as a framework to evaluate the quality and relevance of query relaxation results. Section 6 presents the experimental evaluation. Section 7 presents our concluding remarks and perspectives.

## 2. Related works

When a user query returns insufficient results, several relaxation methods aim to retrieve the closest top-k results to the original target. Most existing works [1,2,3,4,13,5,6,14,8,7] rely on ontology-based relaxation, relaxing classes and properties based on entailment rules. In contrast, entity-based relaxation [12,11] replaces specific entities with similar ones without relying on ontological hierarchies. This is especially useful when the RDF graph lacks a complete domain-specific ontology.

### 2.1. Ontology-based relaxation

Ontology-based relaxation uses class and property hierarchies to relax queries. Hurtado et al. [1] introduced this concept using OPTIONAL clauses and RDFS entailment. Subsequent works [2,3] extended it to full queries and property paths, while [4] proposed similarity-based ranking. Query ranking techniques are widely used to better match user expectations. In the relaxation lattice, queries are partially ordered by relaxation distance, but queries at the same level remain incomparable. Several works [4,5,6,7,8] apply information content-based similarity to achieve a total order, complementing earlier distance-based methods [1,2,3]. These works also generate relaxed queries by replacing an entity or literal with a constant having zero similarity score.

To improve scalability, several pruning strategies have been proposed, such as MBS, O-MBS, and F-MBS in [6], and OBFSR and BR in [5]. Among these, O-MBS [6] stands out by heuristically detecting failure causes without exhaustively computing all minimal failing subqueries. It significantly reduces the number of relaxed queries and execution time, as shown in experiments on LUBM datasets. Therefore, we adopt O-MBS as the relaxation strategy in our hybrid model due to its efficiency.

### 2.2. Entity-based relaxation

Entity-based relaxation on SPARQL queries relies on entity-level techniques that rewrite queries based on entity similarities. Hogan et al. [11] proposes an approach that ranks entities and literals by computing distance scores, such as Levenshtein and Euclidean distance, but it lacks robustness due to imbalanced scores of distance and the lack of reference standard. Similarly, Elbassuoni et al. [12] evaluates the closeness of relaxed queries and answers through human judgment, offering a language-model-based framework focused on entity-centric relaxation. However, it does not compare its approach with other techniques, nor does it handle class or property relaxation.

Among entity-based techniques, the partitioning-based approach by Ferré [10] stands out for its suitability to queries with many joins, common in RDF graphs. It uses Formal Concept Analysis (FCA) to group entities into a concept lattice based on shared
properties. Query relaxation is achieved by navigating this lattice, allowing generaliza-
tion or specialization of entities in a structured, explainable way. This captures semantic
proximity without requiring a precomputed similarity function—unlike most instance-
based approaches that rely on mapping functions to rank alternatives. Ferré's method was
not developed for a specific project or dataset, unlike the EADS industrial use case [11],
enhancing its generalizability. It is also the only entity-based technique with publicly
available source code, which enabled us to use the Java version (CONNOR) in our ex-
periments, providing a solid basis for comparison.

2.3. *Analysis of the existing benchmarks*

Although some datasets have been used in query relaxation research [15], they dif-
fer in focus. Datasets like MONDIAL, LUBM, and its reification-based extension
LUBM4OBDA support ontology-driven relaxations involving class hierarchies, property
generalization, and metadata. Others, such as DBpedia and LibraryThing, emphasize
queries over entities and literals, with limited reliance on ontology. Some are domain-
specific, like the Vehicles dataset from the EADS project [11], targeting security applica-
tions. Dataset sizes range from 5k to 13M triples (e.g., LUBM in the partitioning-based
approach).

The number of queries used for evaluation ranges from 5 to 40, typically with 3 to 21 triple patterns. Some approaches, like the partitioning-based one, test larger queries up to 1.5k triple patterns. However, most benchmarks fail to capture the diversity of elements found in realistic relaxation scenarios. They often focus either on class/property hierarchies or entity/literal values, but rarely both. In particular, queries combining classes, properties, entities, and literals—especially with metadata—are lacking. To address this, we extend LUBM4OBDA, leveraging its rich ontology and reification, by adding diverse literals and entities. We define 7 queries of 2–4 triple patterns, each designed to trigger and evaluate specific types of term relaxation.

Among existing works, Elbassuoni et al. [12] used human judgment to evaluate
the quality of relaxed query results. They pooled the top-10 answers from multiple ap-
proaches and asked six evaluators to rate them on a 4-point scale. To assess query quality,
they generated the top-5 relaxed queries per evaluation query, ranked them by score, and
asked the evaluators to rate their closeness to the original, also using a 4-point scale.

In this work, we propose a hybrid model that combines both categories of query re-
laxation. Each relies on distinct similarity measures and ranking criteria, making integra-
tion non-trivial. Ontology-based relaxations are typically ranked using information con-
tent, while entity-based ones use statistical, symbolic, or embedding-based similarities.
We address this by introducing a unified ranking system that harmonizes these measures,
enabling a total order over the combined set of relaxed queries. We generalize similarity
to a set-based approach, allowing all types of relaxations, i.e., over classes, properties,
entities, or literals, to be viewed within a unified framework, enabling consistent and
comparable ranking. We also introduce a benchmark as a gold standard for evaluating
relaxation approaches.

3. Preliminaries

The following definitions establish the foundation of our model by formalizing the
two types of relaxations that can be applied to SPARQL queries: ontology-based and
instance-based relaxation. These preliminaries are important to show how relaxed queries
are generated by our model and how the relaxation lattice is constructed.

3.1. Terminology in SPARQL query relaxation

The simplest graph pattern is a *triple pattern*, composed of a subject, predicate, and object, denoted as $(s, p, o) \in (I \cup V \cup B) \times (I \cup V) \times (I \cup V \cup L \cup B)$, where *I* is the set of IRIs, *V* is the set of variables, *L* is the set of literals, and *B* is the set of blank nodes. A SPARQL query *Q* is composed of a set of triple patterns, typically written as: $Q\{tp_1, tp_2, ..., tp_n\}$. These triple patterns together form a *basic graph pattern*, and the evaluation of such a query over a knowledge graph returns all the bindings of variables that satisfy all the triple patterns simultaneously.

Given two queries *Q* and *Q'*, we say that *Q'* is a *relaxed query* of *Q* if and only if the answers of *Q* are a subset of the answers of *Q'*, that is: answers(*Q*) ⊆ answers(*Q'*). A relaxed query *Q'* is obtained from *Q* by applying one or more relaxations to the triple patterns of *Q*. We denote this relationship by *Q* ≺ *Q'*, meaning that *Q'* is more general (or relaxed) than *Q*. The relation ≺ defines a partial order over the set of all possible relaxed queries of *Q*. This order can be represented as a lattice, called a relaxation lattice of a query that is the product of the relaxation lattices of all triple patterns of the query.

*Triple pattern relaxation* Relaxing a query includes relaxing one or more of its triple patterns. Given two triple patterns *tp* and *tp'*, *tp'* is a relaxed triple pattern obtained from *tp*, denoted *tp* ≺ *tp'*, by applying one or more triple pattern relaxations to *tp* in order to produce *tp'*. The state of the art distinguish between the following types of relaxations:

**Ontology-based relaxations.** They are based on the RDFS entailment rules [16].

* *Property relaxation* (*<sub>sp</sub>*<sub>) replaces a property *p* in the predicate of a triple pattern with its superproperty *p'*.

* *Type relaxation* (*<sub>sc</sub>*<sub>) replaces a class *c* in the subject or object of a triple pattern with its superclass *c'*.

• *Simple relaxation* (*<sub>s</sub>*<sub>) replaces a constant of a triple pattern with a variable.

**Instance-based relaxations.** They are based on precomputed mapping functions.

* *Entity relaxation* (*<sub>e</sub>*<sub>) replaces an entity (IRI) in the subject or object of a triple pattern with a similar entity from the knowledge graph.

* *Literal relaxation* (*<sub>l</sub>*<sub>) replaces a literal in the subject or object of a triple pattern with a similar literal from the knowledge graph.

3.2. *Information content measures*

Following the principles of information theory [17], the information content (IC) of a
concept *c* is defined as the negative log-likelihood of its occurrence: *IC(c) = -log Pr(c)*.
This reflects the idea that more general, frequent concepts are less informative, resulting
in lower IC. Specific and rare concepts are more informative. The IC of a concept can
be used to measure semantic similarity: the more information two concepts share, the
more similar they are. This shared information is captured by the IC of their common
subsumers in the ontology. Building on this, [5] defines similarity measures based on IC
for ranking relaxed queries, often used in ontology-based query relaxation.
For classes c and c', assuming $c \subseteq c'$, the similarity is:

$$Sim(c, c') = \frac{IC(c')}{IC(c)} \quad \text{with} \quad IC(c) = -\log Pr(c), \quad Pr(c) = \frac{|Instances(c)|}{|Instances|} \quad (1)$$

It holds that $IC(c') \le IC(c)$ for subclasses c' and c, because the probability of finding instances in a more specific class c is lower than or equal to that in a more general class c'. As the similarity of classes is defined as the ratio of their IC values, similarity values always remain between 0 and 1. The similarity reaches 1 when c and c' have equal IC values, which occurs when the number of instances of c and c' are the same. When the inclusion relationship $c' \subseteq c$ does not hold, [18] generalizes the similarity to consider partial overlaps between classes. They computed the similarity between two classes using this formula where $msca(c, c')$ is the most specific common ancestor of c and c':

$$Sim(c, c') = \frac{IC(msca(c, c'))}{IC(c) + IC(c') - IC(msca(c, c'))} \quad (2)$$

**Definition 3.1 (Classes similarity).** Given two properties c and c', where c' is a super-property of c, the similarity between c and c' is defined as: $Sim(c, c') = \frac{IC(c \cup c')}{IC(c \cap c')}$.

**Definition 3.2 (Properties similarity).** Given two properties p and p', where p' is a superproperty of p, the similarity between p and p' is defined as: $Sim(p, p') = \frac{IC(p')}{IC(p)}$ where $IC(p)$ is the information content of p: $-\log Pr(p)$, and $Pr(p) = \frac{|Triples(p)|}{|Triples|}$ is the probability of finding a property of p in triples of the RDF dataset.

The similarity between triple patterns $tp$ and $tp'$ is normally computed as:

$$Sim.tp.tp' = \frac{1}{3} \cdot Sim(s, s') + \frac{1}{3} \cdot Sim(p, p') + \frac{1}{3} \cdot Sim(o, o') \quad (3)$$

**Definition 3.3 (Similarity between queries).** Given two queries $Q$ and $Q'$ such that where $Q'$ is a relaxation of $Q$, the similarity of the relaxed query $Q'$ to the original query $Q$, denoted $Sim(Q, Q')$, is defined as the weighted product of the similarities between the triple patterns of the queries: $Sim(Q, Q') = \prod_{i=1}^{n} w_i \cdot Sim.tp_i.tp_i'$

Where $tp_i$ is a triple pattern of $Q$, $tp_i'$ is a triple pattern of $Q'$, $tp_i \prec tp_i'$, and $w_i \in [0, 1]$ is the weight of triple pattern $tp_i$. Weight can be specified by the user to take into account the importance of a triple pattern $tp_i$ in query $Q$. A higher weight means the user considers the triple pattern more important and prefers it to stay unchanged or be relaxed only after less important ones.

By definition, $Sim(Q, Q') \in [0, 1]$. Furthermore, given queries $Q$, $Q'$, and $Q''$, if $Q'$ and $Q''$ are both relaxed queries of $Q$ such that $answers(Q') \subseteq answers(Q'')$, then: $Sim(Q, Q') > Sim(Q, Q'')$. That is, the more relaxed a query is (i.e., the more general its answer set), the lower its similarity to the original query.

## 4. SHARP: SPARQL Hybrid Query Relaxation Approach

This section presents our hybrid relaxation model, which integrates ontology-based and entity-based methods to relax query terms, i.e., classes, properties, entities, and literals.
In Section 4.1 we abstract all terms in a triple pattern to set level. We begin by abstracting classes and properties to sets to create a unified representation. And we extend this abstraction to entities and literals by treating them as elements within these sets. Section 4.2 builds upon this abstraction and introduces key hypotheses. In Section 4.3, we derive similarity of queries relying on information content, with the particularity that these similarities consider also entities and literals where we take care of preserving the semantic ordering given by predefined mapping functions.

### 4.1. Abstracting terms of a triple pattern to set level

**Shifting classes and properties to sets** At an abstract level, relaxing classes and properties can be treated similarly: classes denote sets of instances, while properties correspond to sets of triples where they occur. Therefore, we extend the notion of concept similarity to sets of elements $S$ and $S'$. When the sets represent classes $c$ and $c'$, Equation 2 relies on the taxonomy through the closest class that subsumes both $c$ and $c'$. To handle cases where such hierarchies are less relevant, such as for properties or entities, we generalize the measure to work directly on sets. This shift from hierarchical to set-based level enables a unified approach across different query terms. The more informative (i.e., specific) the intersection is relative to the union, the more similar the sets.

$$ \mathrm{Sim}(S, S') = \frac{\mathrm{IC}(S \cup S')}{\mathrm{IC}(S \cap S')} \qquad (4) $$

If $S \subseteq S'$, then the equation simplifies to: $\mathrm{Sim}(S, S') = \frac{\mathrm{IC}(S')}{\mathrm{IC}(S)}$.

**Shifting entities and literals to elements of a set** To achieve a unified ranking of all relaxed queries, we build on the observation that an entity is, by definition, an instance of a class, and thus an element of the set of instances defined by that class. Similarly, a literal value belongs to the set of possible values defined by a datatype range. From this perspective, entities and literals can be seen as elements within sets (classes or ranges). So, we treat an element $e$ as a singleton set $\{e\}$ since both give same results. This abstraction allows us to lift the relaxation of individual entities and literals to the level of sets, aligning them conceptually with the relaxation of classes and properties, which are already set-based. Hence, we can view all types of query relaxations whether over classes, properties, entities, or literals within a unified, set-based similarity framework, enabling a consistent and comparable ranking of relaxed queries.

$$ \mathrm{Sim}(\{e\}, S) = \frac{\mathrm{IC}(S \cup \{e\})}{\mathrm{IC}(S \cap \{e\})} = \frac{\mathrm{IC}(S)}{\mathrm{IC}(e)}. \qquad (5) $$

By considering an entity $e_i$ as an instance of a class $c$, and a literal value $l_i$ as an element of a set of range values $R$, this formulation specializes to:

$$ \mathrm{Sim}(e_i, c) = \frac{-\log \mathrm{Pr}(c)}{-\log \mathrm{Pr}(e_i)} \quad \text{and} \quad \mathrm{Sim}(l_i, R) = \frac{-\log \mathrm{Pr}(R)}{-\log \mathrm{Pr}(l_i)}, \qquad (6) $$

where the probabilities are defined as:

$$ \mathrm{Pr}(c) = \frac{|\mathrm{Instances}(c)|}{|\mathrm{Instances}|}, \quad \mathrm{Pr}(e_i) = \frac{|\mathrm{Triples}(e_i)|}{|\mathrm{Triples}|}, \quad \mathrm{Pr}(R) = \frac{|\mathrm{Triples}(R)|}{|\mathrm{Triples}|}, \quad \mathrm{Pr}(l_i) = \frac{|\mathrm{Triples}(l_i)|}{|\mathrm{Triples}|} $$
## 4.2. Hypothesis to extend the similarity of entities and literals to sets level

In order to decide whether to relax an entity by another entity or by a class (respectively a literal by an other literal or by the range values of a predicate), we have to define the similarity $Sim(e, e')$ between two elements, as well as the similarity $Sim(e, S)$ between an element and a set. To this end, we suppose there exists a mapping function $MF$ that maps pairs of elements (entities or literals) to non negative real numbers. Let us suppose that we want to relax an element $e_1$ belonging to a set $S = \{e_1, ..., e_n\}$ ordered by mapping function $MF(e_1, e_1) \le MF(e_1, e_2) \le ... \le MF(e_1, e_n)$. There are several possibilities: either we relax $e_1$ to another element $e'_1$, or we relax $e_1$ to $S$.

Our strategy is based on the following hypothesis:

* The similarity between two elements can be considered as a probability.

$$ \forall j: 0 \le Sim(e_1, e_j) \le 1 \qquad (7) $$

* The order of relaxation between elements follows the output of the mapping function. Ideally, similarity should decrease linearly with the mapping function. However, enforcing linearity directly fails to satisfy the below conditions. Instead, we assume an affine dependency (i.e., a linear relationship with a constant offset) to preserve the ranking order given by the mapping function $MF$:

$$ \exists a, b: \forall j: Sim(e_1, e_j) = a \cdot MF(e_1, e_j) + b \qquad (8) $$

* Suppose that the initial query gives some answers but not enough. In such case, relaxing $e_1$ with $e_2$ can keep the answers provided by the initial query and the result of the relaxation, i.e., $Sim(e_1, e_2) = Sim(e_1, \{e_1, e_2\})$. In general,

$$ Sim(e_1, e_j) = Sim(e_1, \{e_1, e_2, ... e_j\}) \qquad (9) $$

By applying equations 7, 8, and 9, we derive the following definitions:

**Definition 4.1 (Similarity between entities).** Given two entities $e_i$ and $e_j$ that belong to a class $c$, and a mapping function $MF$ as defined previously, the similarity between $e_i$ and $e_j$ is given by: $Sim(e_i, e_j) = \frac{MF(e_i, e_j) - Sim(e_i, e_j)}{1 - Sim(e_i, e_j)} + Sim(e_i, c) \cdot \frac{1 - MF(e_i, e_j)}{1 - Sim(e_i, e_j)}$ where $e_n$ is the least similar entity to $e_i$ among the elements of class $c$, and $Sim(e_i, c)$ denotes the similarity between the entity and its class.

**Definition 4.2 (Similarity between literals).** Given two literal values $l_i$ and $l_j$ that belong to a range $R$, and a mapping function $MF$, the similarity between $l_i$ and $l_j$ is defined as: $Sim(l_i, l_j) = \frac{MF(l_i, l_j) - Sim(l_i, l_j)}{1 - Sim(l_i, l_j)} + Sim(l_i, R) \cdot \frac{1 - MF(l_i, l_j)}{1 - Sim(l_i, l_j)}$ where $l_n$ is the least similar literal to $l_i$ among the elements in $R$, and $Sim(l_i, R)$ represents the similarity between the literal and its range.

## 4.3. Similarity between queries with a set-based approach

*Similarity between entities/literals and variables.* This similarity captures how much information is lost when a constant object $o$ in a triple pattern $(?s, p, o)$ is replaced by a variable $o$. Traditionally, the similarity between an entity or a literal and a variable is assigned a score of zero. However, in our measure we take into account the predicate $p$: if $p$ is rare in the dataset, then the constant $o$ provides more specific information.
**Definition 4.3 (Simple relaxation similarity).** Given a triple pattern $tp = (s, p, o)$ that is relaxed into a new triple pattern $tp' = (\?s, p, \?o)$ by replacing the constant object $o$ with a variable $\?o$, the similarity between $o$ and $\?o$, under predicate $p$, is defined as: $\text{Sim}(o, \?o) = \left[ -\log\left(\frac{|\text{Triples}(p)|}{|\text{Triples}|}\right) \right]^{-1}$ where $|\text{Triples}(p)|$ denotes the number of triples in the dataset that use predicate $p$, and $|\text{Triples}|$ is the total number of triples in the dataset.

*Similarity between triple patterns.* Given two triple patterns $tp_i$ and $tp'_i$, such that $tp_i \prec tp'_i$, the similarity of the triple pattern $tp'_i$ to the original triple pattern $tp_i$, denoted $\text{Sim}(tp_i, tp'_i)$, is usually calculated as the arithmetic mean of the similarities between the terms of the triple patterns, but in this work we take the cubic root of the product. This aims to ensure that the similarity score reflects the overall similarity across the three terms in a triple pattern, rather than being influenced by any individual term.

**Definition 4.4 (Triple pattern similarity).** Given two triple patterns $tp = (s, p, o)$ and $tp' = (s', p', o')$, where $tp'$ is derived from $tp$ by applying one or more relaxations, the similarity between $tp$ and $tp'$ is defined as: $\text{Sim}(tp, tp') = \sqrt[3]{\text{Sim}(s, s') \cdot \text{Sim}(p, p') \cdot \text{Sim}(o, o')}$. If $tp'_i$ and $tp'_j$ are two relaxations obtained from $tp_i$ where $i \neq j$ and $tp'_i \prec tp'_j$ then $\text{Sim}(tp_i, tp'_i) \geq \text{Sim}(tp_j, tp'_j)$.

*Similarity between queries.* (as in the state of the art, cf Definition 3.3) Given two queries $Q$ and $Q'$ such that $Q'$ is a relaxation of $Q$), the similarity of the relaxed query $Q'$ to the original query $Q$, denoted $\text{Sim}(Q, Q')$), is defined as the weighted product of the similarities between the triple patterns of the queries (as in the state of the art): $\text{Sim}(Q, Q') = \prod_{i=1}^{n} w_i \cdot \text{Sim}(tp_i, tp'_i)$

Finally, our model is based on a combination of definitions and equations, some adopted from the state of the art and others introduced as original contributions. In this model, similarity between queries is computed as defined in Definition 3.3. Similarity between triple patterns follows Definition 4.4, while similarity between terms is derived from Definitions 3.1, 3.2, 4.1, 4.2, and 4.3.

*Limitation* Our approach compares queries with the same number of triple patterns and does not support adding new ones. Relaxation is thus limited to modifying existing patterns. Deletion is implicitly supported: replacing all components of a triple pattern with variables renders it unrestricted, effectively removing it. The similarity is then computed using the equation for simple relaxation.

**5. A benchmark to evaluate a user-based quality of results**

Our main objective is to evaluate the quality of results obtained by SHARP, i.e. how close the results it produces are close to the initial user expectations. Previous works have largely focused on evaluating the execution performance and algorithmic complexity of their approaches, without explicitly addressing the users point of view. Since ranking relaxed queries can be subjective and depending on the target KG, and available ontologies, a benchmark is necessary for a more objective evaluation.

In this section, we introduce our benchmark composed of a dataset generated from LUBM4OBDA (Section 5.1) and a set of seven queries, each one with four relaxed queries (Section 5.2). A user survey helped us to assess the relevance of each relaxed query towards the original query.
## 5.1. The used dataset - LUBM4OBDA

Reification is an important aspect of our benchmark design because it provides a way for representing annotations in RDF which frequently include literals such as time, provenance, or certainty. These annotations are typically represented using literals like strings, dates, numbers, or intervals. Several syntaxes exist to express reification like standard reification [19]<fnref n="2" />,<fnref n="3" />, n-ary relations [20]<fnref n="4" />, named graphs [21], and RDF-star [22]<fnref n="5" /> to name a few. The RDF 1.2 Draft is considering Triple Terms, where an RDF triple can be used as the object of another triple<fnref n="6" />. Considering annotations aligns with the objective of our work: evaluating a hybrid query relaxation model that considers all query elements—instances, literals, classes, and properties.

Our generated dataset includes both, the initial triples generated with LUBM4OBDA benchmark, and the implicit triples entailed by the RDFS semantics from saturation. Our dataset is a moderate size dataset (2.5 M triples), where we introduced an important number of literals and class instances with a well-defined ontology which in average has a depth of 3 subclasses (see Table 3).

<table><caption>**Table 3.** Statistics of our LUBM4OBDA RDF-star dataset</caption><thead><tr><th></th><th>Triples</th><th>Literals</th><th>Classes</th><th>Properties</th><th>Class Instances</th></tr></thead><tbody><tr><th>Cardinality</th><td>2,572,481</td><td>262,767</td><td>30</td><td>38</td><td>208,064</td></tr></tbody></table>

## 5.2. Seven new SPARQL-star query templates

We defined seven new SPARQL-star queries over our dataset (Listing 1). These queries were manually designed to reflect the different types of relaxations and use cases we aim to address. They cover a range of structural patterns, including star-shaped, chain-shaped, and reified patterns. They were selected to trigger relaxations on different types of triple-pattern terms (e.g., classes, properties, entities, literals).

To capture a human-centered notion of relevance and create a gold standard for evaluating the effectiveness of query relaxation strategies, we conducted a user survey containing our seven queries and four or five relaxed queries. All queries were expressed in natural language. Participants were asked to rank the relaxed queries from the most to least relevant to the original query, based on their intuition. 32 participants, all affiliated with our research laboratory, took part in the survey. To quantify user perception of relevance, we computed the average human-assigned score for each relaxed query version.

As an illustration of our survey, Q1 was described as follows: "Find professors who are members of Computer Science department at Nantes University. (Context: Consider yourself as a Computer science professor searching for people close to your field)". The relaxed queries were presented as follows (here we present the ranked queries as produced by the survey):

Q1: "Find faculty members (Professor + PostDoc + Lecturer) who are members of Computer Science department at Nantes University."

<footnote n="2">²https://www.w3.org/TR/rdf-primer/#reification</footnote>

<footnote n="3">³https://www.w3.org/TR/rdf11-schema/#ch_reificationvocab</footnote>

<footnote n="4">⁴http://www.w3.org/TR/swbp-n-aryRelations</footnote>

<footnote n="5">⁵https://w3c.github.io/rdf-star/cg-spec/2021-12-17.html</footnote>

<footnote n="6">⁶https://www.w3.org/TR/rdf12-concepts/#section-triple-terms</footnote>
Q12 "Find professors who are members of Software Engineering Department at Nantes University."

Q13 "Find any employee who is a member of Computer Science Department at Nantes University."

Q14 "Find professors who have co-authored papers with members of the Computer Science department at Nantes University."

Q15 "Find professors who are members of Industrial Engineering Department at Nantes University."

When participants submit an ordered ranking, each position receives points calculated as $\frac{100}{\text{rank}}$. For example, the first-ranked option gets 100 points, the second 50 points, the third about 33.33 points, and so on. The overall score for each option is the average of these points across all participants. Table 4 presents the aggregated human scores for each query, reflecting the relative importance of each opinion compared to others in the ranking set. This table also shows the number of unique results obtained by each query, indicating the diversity of returned answers. Figure 5 in the appendix illustrates a sample of these survey results, providing a visual representation of participant rankings.

<table><caption>**Table 4.** Human evaluation scores and cardinality of results for each relaxed query</caption><thead><tr><th></th><th colspan="4">Q1</th><th colspan="4">Q2</th><th colspan="4">Q3</th><th colspan="4">Q4</th></tr><tr><th></th><th>RQ1<sub>1</sub></th><th>RQ1<sub>2</sub></th><th>RQ1<sub>3</sub></th><th>RQ1<sub>4</sub></th><th>RQ1<sub>5</sub></th><th>RQ2<sub>1</sub></th><th>RQ2<sub>2</sub></th><th>RQ2<sub>3</sub></th><th>RQ2<sub>4</sub></th><th>RQ2<sub>5</sub></th><th>RQ3<sub>1</sub></th><th>RQ3<sub>2</sub></th><th>RQ3<sub>3</sub></th><th>RQ3<sub>4</sub></th><th>RQ4<sub>1</sub></th><th>RQ4<sub>2</sub></th><th>RQ4<sub>3</sub></th></tr></thead><tbody><tr><th>Human score</th><td>82</td><td>50</td><td>37</td><td>31</td><td>23</td><td>71</td><td>58</td><td>38</td><td>33</td><td>20</td><td>72</td><td>65</td><td>39</td><td>21</td><td>19</td><td>76</td><td>58</td></tr><tr><th>Query Results</th><td>20</td><td>20</td><td>10</td><td>15</td><td>25</td><td>4</td><td>1</td><td>0</td><td>50</td><td>1</td><td>0</td><td>7</td><td>3,008</td><td>3,901</td><td>76,509</td><td>16</td><td>0</td><td>12</td></tr></tbody></table><table><thead><tr><th></th><th colspan="4">Q5</th><th colspan="4">Q6</th><th colspan="4">Q7</th></tr><tr><th></th><th>RQ5<sub>1</sub></th><th>RQ5<sub>2</sub></th><th>RQ5<sub>3</sub></th><th>RQ5<sub>4</sub></th><th>RQ5<sub>5</sub></th><th>RQ5<sub>6</sub></th><th>RQ6<sub>1</sub></th><th>RQ6<sub>2</sub></th><th>RQ6<sub>3</sub></th><th>RQ6<sub>4</sub></th><th>RQ6<sub>5</sub></th><th>RQ7<sub>1</sub></th><th>RQ7<sub>2</sub></th><th>RQ7<sub>3</sub></th><th>RQ7<sub>4</sub></th><th>RQ7<sub>5</sub></th></tr></thead><tbody><tr><th>Human score</th><td>78</td><td>54</td><td>38</td><td>27</td><td>22</td><td>17</td><td>88</td><td>48</td><td>44</td><td>23</td><td>19</td><td>80</td><td>60</td><td>38</td><td>26</td><td>19</td></tr><tr><th>Query Results</th><td>2</td><td>3</td><td>1</td><td>4</td><td>3,012</td><td>16</td><td>3</td><td>0</td><td>5</td><td>0</td><td>27</td><td>2</td><td>4</td><td>4</td><td>2</td><td>16</td></tr></tbody></table>

# 6. Experimental Evaluation

We implemented SHARP on top of OMBS in JAVA using Jena. Our implementation and all experimental material is available on GitHub<sup>7</sup>. We compared SHARP, with two relevant state-of-the-art approaches: the entity-based relaxation technique CONNOR [23], and the ontology-based relaxation model OMBS [6]. As for SHARP, these models take as input a failing query and a number of expected answers *k*.

Based on the benchmark introduced in previous section, we conduct two evaluations. First, in Section 6.1, we evaluate how closely the ranking of each of relaxed query matches the ranking derived from human judgments. Second, in Section 6.2, we compare the top-*k* answers produced by each model with a gold standard built from the query results as ranked by the human preferences.

## 6.1. Ranking relaxed queries by similarity

To be able to define similarities based on information content, we calculated the statistics of our dataset. In addition, we calculated mapping functions to map entities and literals to similar ones with similarity scores. For entities, we computed embeddings using RDF-star2vec<sup>8</sup>. For literal, we used several distance functions.

We first focused on comparing the order of relaxed queries generated by each model with the ranking established from users' feedback. We used the recall score to measure to which extent the golden standard queries were generated by each model. The precision

<footnote n="7"><sup>7</sup>https://github.com/GhinwaFAKIH/SHARP-SPARQL-Hybrid-Query-Relaxation-Approach/tree/main</footnote>

<footnote n="8"><sup>8</sup>https://github.com/aistairc/RDF-star2Vec</footnote>
```sql
1 #contains an entity and a class subject to instance/class relaxation
2 SELECT ?prof
3 WHERE { ?prof a ub:Professor;
4 ub:memberOf <http://www department0 university0 edu/graduateCourse0>.
5 } #Initial results = 15
```

(a) Q1 - Instance/Class relaxation.

```sql
1 # triggers sibling class relaxation
2 SELECT ?student
3 WHERE { ?student a ub:GraduateStudent;
4 ub:takesCourse
5 <http://www department0 university0 edu/graduateCourse0>.
6 ub:undergraduateDegreeFrom <http://www university103 edu>.
7 } #Initial results = 1.
```

(b) Q2 - Sibling class relaxation using common instances.

```sql
1 # includes a string literal relaxation
2 SELECT DISTINCT ?publication
3 WHERE { ?publication a ub:Publication ;
4 ub:name ?publication_name ;
5 ub:publicationAuthor ?z .
6 ?z ub:researchInterest "Gene Expression Analysis" .
7 } #Initial results = 10.
```

(c) Q3 - Literal relaxation.

```sql
1 # contains property that triggers property-level relaxation
2 SELECT ?student
3 WHERE { ?student ub:advisor ?Y.
4 ?Y ub:headOf <http://www department3 0 university0 edu>.
5 } #Initial results = 2.
```

(d) Q4 - Property relaxation.

```sql
1 # includes numeric literal within a reified triple
2 SELECT ?student
3 WHERE { ?student a ub:GraduateStudent ;
4 ub:takesCourse <http://www department0 university0 edu/graduateCourse0> .
5 << ?x ub:undergraduateDegreeFrom ?y >> ub:yearOfAward "2010"^^xsd:integer.
6 } #Initial results = 1.
```

(e) Q5 - Literal relaxation of metadata value (numeric).

```sql
1 # uses string metadata in a reified triple
2 SELECT DISTINCT ?student
3 WHERE { ?student ub:name ?student_name.
4 <<?student ub:takesCourse
5 <http://www department0 university0 edu/undergraduateCourse1> >>
6 ub:semester "Autumn";
7 ub:courseYear "2024"^^xsd:integer.
8 } #Initial results = 0.
```

(f) Q6 - Literal relaxation of metadata value (string).

```sql
1 # features a numeric interval filter for range relaxation
2 SELECT ?student
3 WHERE { ?student a ub:GraduateStudent;
4 ub:takesCourse <http://www department0 university0 edu/graduateCourse0> .
5 << ?student ub:undergraduateDegreeFrom ?y >> ub:yearOfAward ?year.
6 FILTER (?year >= "2008"^^xsd:integer && ?year <= "2010"^^xsd:integer ).
7 } #Initial results = 1.
```

(g) Q7 - Interval relaxation.

**Listing 1.** Benchmark query templates.
is not useful here because of the important difference in the number of relaxed queries produced by each evaluated model. We used Rank-Biased Overlap (RBO) to assess how closely the models' rankings are to the gold standard. This measure only considers the gold standard queries produced by the models.

Table 5 shows that SHARP outperforms in both recall and RBO, indicating that the relaxed queries it generates and their ranking align closely with the user-validated benchmark. However, for Q1, SHARP achieves high recall but lower RBO. This query involves both instance-based and ontology-based relaxations, and SHARP combines both, retrieving many relevant results. Yet, the ranking diverges from the human-defined order due to equal weights assigned to all triple patterns. This can be improved by adjusting weights to better reflect user preferences. On the other side, CONNOR and OMBS show limited ranking similarity, with several queries returning RBO scores close to zero. This is mainly due to the fact that they do not relax annotated triples.

<table><caption>Table 5. Recall and RBO scores for models on queries Q1 to Q7</caption><thead><tr><th rowspan="2">Model</th><th colspan="2">Q1</th><th colspan="2">Q2</th><th colspan="2">Q3</th><th colspan="2">Q4</th><th colspan="2">Q5</th><th colspan="2">Q6</th><th colspan="2">Q7</th></tr><tr><th>Recall</th><th>RBO</th><th>Recall</th><th>RBO</th><th>Recall</th><th>RBO</th><th>Recall</th><th>RBO</th><th>Recall</th><th>RBO</th><th>Recall</th><th>RBO</th><th>Recall</th><th>RBO</th></tr></thead><tbody><tr><td>CONNOR</td><td>0.4</td><td><strong>0.75</strong></td><td><strong>0.8</strong></td><td>0.479</td><td>0.2</td><td>0</td><td>0.6</td><td>0.278</td><td>0.167</td><td>0</td><td>0</td><td>0.2</td><td>0</td></tr><tr><td>OMBS</td><td>0.4</td><td><strong>0.75</strong></td><td>0.4</td><td>0.25</td><td>0.2</td><td>0</td><td><strong>0.8</strong></td><td><strong>0.729</strong></td><td>0.167</td><td>0</td><td>0.4</td><td>0.111</td><td>0</td></tr><tr><td>SHARP</td><td><strong>0.8</strong></td><td>0.604</td><td><strong>0.8</strong></td><td><strong>0.875</strong></td><td><strong>0.8</strong></td><td><strong>0.854</strong></td><td><strong>0.8</strong></td><td><strong>0.729</strong></td><td><strong>0.667</strong></td><td><strong>0.479</strong></td><td><strong>0.8</strong></td><td><strong>0.729</strong></td><td><strong>0.8</strong></td><td>1</td></tr></tbody></table>

## 6.2. *Comparison of the quality of query results*

In the second evaluation, we compared the top-k answers produced by each relaxation model with the benchmark answers ranked by human judgment. To do this, we varied k from 1 to 60 expected query results. If a query returns more results than expected, we sampled to get k-results. The resulting set was then compared to the top-k results obtained by executing the human-ranked queries in the same order.

Figure 2 shows the variation of the precision scores as k varies in each query. As shown, CONNOR is consistently the first model whose precision begins to decline, highlighting its limited ability to maintain relevant results as more results are retrieved. OMBS shows behavior similar to our model for Q2 and Q4, where ontology effectively guide the relaxation process. However, its performance drops significantly for Q5-Q7, where metadata plays a central role, resulting in near-zero precision.

Overall, SHARP demonstrates superior performance both in retrieving relevant results and in producing human-aligned query rankings, confirming its effectiveness for query relaxation tasks.

## 7. Conclusion and Perspectives

In this paper, we introduced SHARP, a hybrid SPARQL query relaxation model combining ontology-based and instance-based strategies, enhanced by a set-based similarity ranking. SHARP relaxes diverse query types involving classes, properties, entities, and literals. We also proposed a human-judgment-based benchmark of seven queries to evaluate relaxed results. Experiments highlight SHARP's performance across multiple evaluation criteria. Compared to two state-of-the-art approaches, SHARP consistently delivers more relevant top-k results and aligns better with user-validated rankings, especially for queries with annotations.
<figure><img src="image_3.png" /><figcaption>**Figure 2.** Precision of relaxation models for different values of *k* over benchmark queries.</figcaption></figure>

This work opens several perspectives for future research. As our approach supports SPARQL queries with reification, specifically RDF-star, we plan to extend it to transparently handle any reification model. Another direction is support for property path queries, which introduces challenges related to sequences and hierarchical relationships.
## References

[1] Hurtado CA, Poulovassilis A, Wood PT. A relaxed approach to RDF querying. In: International Semantic Web Conference (ISWC). vol. 4273. Springer International Publishing; 2006. p. 314-28.

[2] Hurtado CA, Poulovassilis A, Wood PT; Springer International Publishing. Query relaxation in RDF. Journal on Data Semantics X. 2008;4900:31-61.

[3] Poulovassilis A, Wood PT. Combining approximation and relaxation in semantic web path queries. In: International Semantic Web Conference (ISWC). Springer International Publishing; 2010. p. 631-46.

[4] Huang H, Liu C. Query relaxation for star queries on RDF. In: International Conference on Web Information Systems Engineering (WISE). vol. 6488. Springer International Publishing; 2010. p. 376-389.

[5] Huang H, Liu C, Zhou X. Approximating query answering on RDF databases. World Wide Web (WWW). 2012;15:89-114.

[6] Fokou G, Jean S, Hadjali A, Baron M. RDF query relaxation strategies based on failure causes. In: European Semantic Web Conference (ESWC). vol. 9678. Springer International Publishing; 2016. p. 439-54.

[7] Moreau B, Serrano-Alvarado P. Ensuring license compliance in linked data with query relaxation. In: Transactions on Large-Scale Data-and Knowledge-Centered Systems (TLDKS). vol. 12920. Springer International Publishing; 2021. p. 97-129.

[8] Bennani IL, Prakash AK, Zafiris M, Paul L, Roa CD, Raftery P, et al. Query relaxation for portable brick-based applications. In: International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation (BuildSys). Association for Computing Machinery; 2021. p. 150-9.

[9] Ge Z, Wang Y, Yan H, Xu X. A learning-based semantic approximate query over RDF knowledge graph. In: International Conference on Advanced Cloud and Big Data (CBD). IEEE; 2018. p. 135-41.

[10] Ferré S. Answers partitioning and lazy joins for efficient query relaxation and application to similarity search. In: Extended Semantic Web Conference (ESWC). vol. 10843. Springer International Publishing; 2018. p. 209-24.

[11] Hogan A, Mellotte M, Powell G, Stampouli D. Towards fuzzy query relaxation for RDF. In: Extended Semantic Web Conference (ESWC). vol. 7295. Springer International Publishing; 2012. p. 687-702.

[12] Elbassuoni S, Ramanath M, Weikum G. Query relaxation for entity-relationship search. In: Extended Semantic Web Conference (ESWC). vol. 6644. Springer International Publishing; 2011. p. 62-76.

[13] Huang H, Liu C, Zhou X. Computing relaxed answers on RDF databases. In: International Conference on Web Information Systems Engineering (WISE). vol. 5175. Springer International Publishing; 2008. p. 163-75.

[14] Mebrek W, Raddaoui B, Albilani M. On relaxing failing queries over RDF databases. In: International Conference on Big Data. IEEE; 2019. p. 115-24.

[15] Fakih G, Serrano-Alvarado P. A survey on SPARQL query relaxation under the lens of RDF reification. Semantic Web. 2024;15(6):2507-54.

[16] Ter Horst HJ. Extending the RDFS entailment lemma. In: The Semantic Web-ISWC 2004: Third International Semantic Web Conference, Hiroshima, Japan, November 7-11, 2004. Proceedings 3. Springer; 2004. p. 77-91.

[17] Resnik P. Using information content to evaluate semantic similarity in a taxonomy. In: International Joint Conference on Artificial Intelligence (IJCAI). vol. 1. Morgan Kaufmann Publishers Inc.; 1995. p. 448-453.

[18] Fokou G, Jean S, Hadjali A. Endowing semantic query languages with advanced relaxation capabilities. In: International Symposium on Methodologies for Intelligent Systems. Springer; 2014. p. 512-7.

[19] Manola F, Miller E, McBride B, et al. RDF primer. W3C recommendation. 2004;10(1-107):6.

[20] Noy N, Rector A, Hayes P, Welty C. Defining n-ary relations on the semantic web. W3C working group note. 2006. Available from: https://www.w3.org/TR/swbp-n-aryRelations/.

[21] Carroll JJ, Bizer C, Hayes P, Stickler P. Named graphs. Journal of Web Semantics (JWS). 2005;3(4):247-67. ISSN 1570-8268.

[22] Hartig O. Foundations of RDF* and SPARQL*:(An alternative approach to statement-level metadata in RDF). In: Alberto Mendelzon International Workshop on Foundations of Data Management and the Web (AMW). vol. 1912. CEUR-WS.org; 2017.

[23] Ferré S, Huchard M, Kaytoue M, Kuznetsov SO, Napoli A. Formal concept analysis: from knowledge discovery to knowledge processing. A Guided Tour of Artificial Intelligence Research: Volume II: AI Algorithms. 2020:411-45.
# A. Supplemental material

## A.1. Example dataset

<table><caption>Listing 2: Dataset used as running example.</caption><thead><tr><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>@prefix ex: &lt;http://example.org/&gt; .</td><td></td><td></td></tr><tr><td>2</td><td>@prefix foaf: &lt;http://xmlns.com/foaf/0.1/&gt; .</td><td></td><td></td></tr><tr><td>3</td><td>@prefix rdf: &lt;http://www.w3.org/1999/02/22-rdf-syntax-ns#&gt; .</td><td></td><td></td></tr><tr><td>4</td><td>@prefix xsd: &lt;http://www.w3.org/2001/XMLSchema#&gt; .</td><td></td><td></td></tr><tr><td>5</td><td></td><td></td><td></td></tr><tr><td>6</td><td></td><td></td><td></td></tr><tr><td>7</td><td># Triples about Data</td><td></td><td></td></tr><tr><td>8</td><td>ex:Databases</td><td>rdf:type</td><td>ex:Course;</td></tr><tr><td>9</td><td></td><td>ex:difficulty</td><td>"very easy".</td></tr><tr><td>10</td><td>ex:Semantic_Web</td><td>rdf:type</td><td>ex:Course;</td></tr><tr><td>11</td><td></td><td>ex:difficulty</td><td>"easy".</td></tr><tr><td>12</td><td>ex:Linked_Data</td><td>rdf:type</td><td>ex:Course;</td></tr><tr><td>13</td><td></td><td>ex:difficulty</td><td>"hard".</td></tr><tr><td>14</td><td>ex:John</td><td>rdf:type</td><td>ex:Student;</td></tr><tr><td>15</td><td></td><td>ex:enrolledIn</td><td>ex:Semantic_Web;</td></tr><tr><td>16</td><td></td><td>ex:friendOf</td><td>ex:Sam;</td></tr><tr><td>17</td><td></td><td>foaf:knows</td><td>ex:Patricia.</td></tr><tr><td>18</td><td>ex:Maya</td><td>rdf:type</td><td>ex:Student;</td></tr><tr><td>19</td><td></td><td>ex:enrolledIn</td><td>ex:Semantic_Web;</td></tr><tr><td>20</td><td></td><td>foaf:knows</td><td>ex:Peter;</td></tr><tr><td>21</td><td></td><td>foaf:knows</td><td>ex:Patricia.</td></tr><tr><td>22</td><td>ex:Maria</td><td>rdf:type</td><td>ex:Student;</td></tr><tr><td>23</td><td></td><td>ex:attends</td><td>ex:Databases;</td></tr><tr><td>24</td><td></td><td>ex:friendOf</td><td>ex:Peter;</td></tr><tr><td>25</td><td></td><td>foaf:knows</td><td>ex:Patricia.</td></tr><tr><td>26</td><td>ex:Patricia</td><td>rdf:type</td><td>ex:Teacher;</td></tr><tr><td>27</td><td></td><td>ex:worksIn</td><td>ex:Nantes_University;</td></tr><tr><td>28</td><td></td><td>ex:teaches</td><td>ex:Semantic_Web, ex:Databases.</td></tr><tr><td>29</td><td>ex:Peter</td><td>rdf:type</td><td>ex:Person;</td></tr><tr><td>30</td><td></td><td>foaf:knows</td><td>ex:Maya.</td></tr><tr><td>31</td><td>ex:Sam</td><td>rdf:type</td><td>ex:Student;</td></tr><tr><td>32</td><td></td><td>ex:enrolledIn</td><td>ex:Linked_Data;</td></tr><tr><td>33</td><td></td><td>foaf:knows</td><td>ex:Maya.</td></tr><tr><td>34</td><td>ex:Alice</td><td>rdf:type</td><td>ex:Person.</td></tr><tr><td>35</td><td></td><td></td><td></td></tr><tr><td>36</td><td># Triples about Metadata</td><td></td><td></td></tr><tr><td>37</td><td></td><td></td><td></td></tr><tr><td>38</td><td># Metadata about the triple in line 12</td><td></td><td></td></tr><tr><td>39</td><td>ex:S100</td><td>rdf:type</td><td>rdf:Statement;</td></tr><tr><td>40</td><td></td><td>rdf:subject</td><td>ex:John;</td></tr><tr><td>41</td><td></td><td>rdf:predicate</td><td>ex:enrolledIn;</td></tr><tr><td>42</td><td></td><td>rdf:object</td><td>ex:Semantic_Web;</td></tr><tr><td>43</td><td></td><td>ex:enrolldate</td><td>"2022-09-12"^^xsd:-date;</td></tr><tr><td>44</td><td></td><td>ex:enrollpayment</td><td>"Cash"^^xsd:-string.</td></tr><tr><td>45</td><td></td><td></td><td></td></tr><tr><td>46</td><td># Metadata about the triple in line 16</td><td></td><td></td></tr><tr><td>47</td><td>ex:S300</td><td>rdf:type</td><td>rdf:Statement;</td></tr><tr><td>48</td><td></td><td>rdf:subject</td><td>ex:Maya;</td></tr><tr><td>49</td><td></td><td>rdf:predicate</td><td>ex:enrolledIn;</td></tr></tbody></table>
<table><tr><td>50</td><td>rdf:object</td><td>ex:Semantic_Web;</td></tr><tr><td>51</td><td>ex:enrolldate</td><td>"2023-09-13"^^xsd: date;</td></tr><tr><td>52</td><td>ex:enrollpayment</td><td>"Credit card"^^xsd: string.</td></tr><tr><td>53</td><td></td><td></td></tr><tr><td>54</td><td># Metadata about the triple in line 20</td><td></td></tr><tr><td>55</td><td>ex:S200</td><td>rdf:type</td><td>rdf:Statement;</td></tr><tr><td>56</td><td></td><td>rdf:subject</td><td>ex: Maria;</td></tr><tr><td>57</td><td></td><td>rdf:predicate</td><td>ex: enrolledIn;</td></tr><tr><td>58</td><td></td><td>rdf:object</td><td>ex: Databases;</td></tr><tr><td>59</td><td></td><td>ex:enrolldate</td><td>"2023-09-13"^^xsd: date;</td></tr><tr><td>60</td><td></td><td>ex:enrollpayment</td><td>"Cash"^^xsd: string.</td></tr></table>

## A.2. Example ontology

### Listing 3: Ontology used for running example.

<table><tr><td>1</td><td>@prefix ex: &lt;http://example.org/&gt; .</td></tr><tr><td>2</td><td>@prefix rdf: &lt;http://www.w3.org/1999/02/22-rdf-syntax-ns#&gt; .</td></tr><tr><td>3</td><td>@prefix rdfs: &lt;http://www.w3.org/2000/01/rdf-schema#&gt; .</td></tr><tr><td>4</td><td>@prefix xsd: &lt;http://www.w3.org/2001/XMLSchema#&gt; .</td></tr><tr><td>5</td><td>@prefix owl: &lt;http://www.w3.org/2002/07/owl#&gt; .</td></tr><tr><td>6</td><td>@prefix foaf: &lt;http://xmlns.com/foaf/0.1/&gt; .</td></tr><tr><td>7</td><td></td></tr><tr><td>8</td><td></td></tr><tr><td>9</td><td># Define Classes</td></tr><tr><td>10</td><td>ex:Student</td><td>rdf:type</td><td>rdfs:Class.</td></tr><tr><td>11</td><td></td><td>ex:Person</td><td>rdf:type</td><td>rdfs:Class.</td></tr><tr><td>12</td><td></td><td>ex:Teacher</td><td>rdf:type</td><td>rdfs:Class.</td></tr><tr><td>13</td><td></td><td>ex:Course</td><td>rdf:type</td><td>rdfs:Class.</td></tr><tr><td>14</td><td></td><td>rdf:Statement</td><td>rdf:type</td><td>rdfs:Class.</td></tr><tr><td>15</td><td></td><td></td><td></td><td></td></tr><tr><td>16</td><td># Define Object Properties</td></tr><tr><td>17</td><td>ex:attends</td><td>rdf:type</td><td>owl:ObjectProperty;</td></tr><tr><td>18</td><td></td><td>rdfs:domain</td><td>ex:Person;</td></tr><tr><td>19</td><td></td><td>rdfs:range</td><td>ex:Course.</td></tr><tr><td>20</td><td>ex:enrolledIn</td><td>rdf:type</td><td>owl:ObjectProperty;</td></tr><tr><td>21</td><td></td><td>rdfs:domain</td><td>ex:Student.</td></tr><tr><td>22</td><td>ex:friendOf</td><td>rdf:type</td><td>owl:ObjectProperty.</td></tr><tr><td>23</td><td>ex:knows</td><td>rdf:type</td><td>owl:ObjectProperty;</td></tr><tr><td>24</td><td></td><td>rdfs:domain</td><td>ex:Person;</td></tr><tr><td>25</td><td></td><td>rdfs:range</td><td>ex:Person.</td></tr><tr><td>26</td><td>ex:classmates</td><td>rdf:type</td><td>owl:ObjectProperty;</td></tr><tr><td>27</td><td></td><td>rdfs:domain</td><td>ex:Person;</td></tr><tr><td>28</td><td></td><td>rdfs:range</td><td>ex:Person.</td></tr><tr><td>29</td><td>ex:teaches</td><td>rdf:type</td><td>owl:ObjectProperty;</td></tr><tr><td>30</td><td></td><td>rdfs:domain</td><td>ex:Teacher;</td></tr><tr><td>31</td><td></td><td>rdfs:range</td><td>ex:Course.</td></tr><tr><td>32</td><td></td><td></td><td></td><td></td></tr><tr><td>33</td><td></td><td></td><td></td><td></td></tr><tr><td>34</td><td># Define Data Property</td></tr><tr><td>35</td><td>ex:enrolldate</td><td>rdf:type</td><td>owl:DatatypeProperty;</td></tr><tr><td>36</td><td></td><td>rdfs:domain</td><td>rdf:Statement;</td></tr><tr><td>37</td><td></td><td>rdfs:range</td><td>xsd: date.</td></tr></table>
38 ex:difficulty rdfs:domain ex:Course;
39 rdfs:range xsd:string.
40 ex:enrollpayment rdf:type owl:DatatypeProperty ;
41 rdfs:domain rdf:Statement;
42 rdfs:range xsd:string.
43
44
45 # Define classes hierarchy
46 ex:Student rdfs:subClassOf ex:Person.
47 ex:Teacher rdfs:subClassOf ex:Person.
48 rdf:Statement rdfs:subClassOf rdfs:Resource.
49
50 # Define properties hierarchy
51 ex:friendOf rdfs:subPropertyOf foaf:knows.
52 ex:teaches rdfs:subPropertyOf ex:attends.
53 ex:enrolledIn rdfs:subPropertyOf ex:attends.
54
55
56 # RDFS ontology
57 rdfs:Resource rdf:type rdfs:Class .
58
59 rdfs:Class rdf:type rdfs:Class ;
60 rdfs:subClassOf rdfs:Resource .
### A.3. Closure of the example dataset

<table><caption>Listing 4: Closure computed for the running example dataset.</caption><tr><td>1</td><td>@prefix ex: &lt;http://example.org/&gt; .</td></tr><tr><td>2</td><td>@prefix foaf: &lt;http://xmlns.com/foaf/0.1/&gt; .</td></tr><tr><td>3</td><td>@prefix owl: &lt;http://www.w3.org/2002/07/owl#&gt; .</td></tr><tr><td>4</td><td>@prefix rdf: &lt;http://www.w3.org/1999/02/22-rdf-syntax-ns#&gt; .</td></tr><tr><td>5</td><td>@prefix rdfs: &lt;http://www.w3.org/2000/01/rdf-schema#&gt; .</td></tr><tr><td>6</td><td>@prefix xsd: &lt;http://www.w3.org/2001/XMLSchema#&gt; .</td></tr><tr><td>7</td><td></td></tr><tr><td>8</td><td>ex:Student rdf:type rdfs:Resource, rdfs:Class;</td></tr><tr><td>9</td><td>rdfs:subClassOf ex:Person.</td></tr><tr><td>10</td><td></td></tr><tr><td>11</td><td>rdfs:Resource rdf:type rdfs:Resource, rdfs:Class.</td></tr><tr><td>12</td><td></td></tr><tr><td>13</td><td>rdfs:Class rdf:type rdfs:Resource, rdfs:Class;</td></tr><tr><td>14</td><td>rdfs:subClassOf rdfs:Resource.</td></tr><tr><td>15</td><td></td></tr><tr><td>16</td><td>ex:Person rdf:type rdfs:Resource, rdfs:Class.</td></tr><tr><td>17</td><td></td></tr><tr><td>18</td><td>ex:Peter rdf:type rdfs:Resource, rdfs:Class, ex:Person;</td></tr><tr><td>19</td><td>foaf:knows ex:Maya.</td></tr><tr><td>20</td><td></td></tr><tr><td>21</td><td>ex:Alice rdf:type rdfs:Resource, rdfs:Class, ex:Person.</td></tr><tr><td>22</td><td></td></tr><tr><td>23</td><td>ex:Semantic_Web rdf:type rdfs:Resource, rdfs:Class, ex:Course;</td></tr><tr><td>24</td><td>ex:difficulty "easy".</td></tr><tr><td>25</td><td></td></tr><tr><td>26</td><td>ex:Course rdf:type rdfs:Resource, rdfs:Class.</td></tr><tr><td>27</td><td></td></tr><tr><td>28</td><td>ex:difficulty rdfs:domain ex:Course;</td></tr><tr><td>29</td><td>rdfs:range xsd:string.</td></tr><tr><td>30</td><td></td></tr><tr><td>31</td><td>ex:S300 rdf:type rdfs:Resource, rdfs:Class, rdf:Statement;</td></tr><tr><td>32</td><td>rdf:object ex:Semantic_Web;</td></tr><tr><td>33</td><td>rdf:predicate ex:enrolledIn;</td></tr><tr><td>34</td><td>rdf:subject ex:Maya;</td></tr><tr><td>35</td><td>ex:enrolldate "2023-09-13"^^xsd:-date;</td></tr><tr><td>36</td><td>ex:enrollpayment "CreditCard".</td></tr><tr><td>37</td><td></td></tr><tr><td>38</td><td>rdf:Statement rdf:type rdfs:Resource, rdfs:Class;</td></tr><tr><td>39</td><td>rdfs:subClassOf rdfs:Resource.</td></tr><tr><td>40</td><td></td></tr><tr><td>41</td><td>ex:enrolledIn rdf:type owl:ObjectProperty;</td></tr><tr><td>42</td><td>rdfs:domain ex:Student;</td></tr><tr><td>43</td><td>rdfs:subPropertyOf ex:attends.</td></tr><tr><td>44</td><td></td></tr><tr><td>45</td><td>ex:Maya rdf:type ex:Student, rdfs:Resource, rdfs:Class, ex:Person;</td></tr><tr><td>46</td><td>ex:attends ex:Semantic_Web;</td></tr><tr><td>47</td><td>ex:enrolledIn ex:Semantic_Web;</td></tr><tr><td>48</td><td>foaf:knows ex:Peter, ex:Patricia.</td></tr><tr><td>49</td><td></td></tr><tr><td>50</td><td>ex:enrolldate rdf:type owl:DatatypeProperty;</td></tr><tr><td>51</td><td>rdfs:domain rdf:Statement;</td></tr></table>
52 rdfs:range xsd date .
53
54 ex:enrollpayment rdf:type owl:DatatypeProperty ;
55 rdfs:domain rdf:Statement ;
56 rdfs:range xsd string .
57
58 ex:attends rdf:type owl:ObjectProperty ;
59 rdfs:domain ex:Person ;
60 rdfs:range ex:Course .
61
62 ex:Patricia rdf:type rdfs:Resource , rdfs:Class , ex:Person , ex:Teacher ;
63 ex:attends ex:Semantic_Web , ex:Databases ;
64 ex:teaches ex:Semantic_Web , ex:Databases ;
65 ex:worksIn ex:Nantes_Universite .
66
67 ex:Maria rdf:type ex:Student , rdfs:Resource , rdfs:Class , ex:Person ;
68 ex:attends ex:Databases ;
69 ex:friendOf ex:Peter ;
70 foaf:knows ex:Peter , ex:Patricia .
71
72 ex:Databases rdf:type rdfs:Resource , rdfs:Class , ex:Course ;
73 ex:difficulty "very easy" .
74
75 ex:friendOf rdf:type owl:ObjectProperty ;
76 rdfs:subPropertyOf foaf:knows .
77
78 ex:S200 rdf:type rdfs:Resource , rdfs:Class , rdf:Statement ;
79 rdf:object ex:Databases ;
80 rdf:predicate ex:enrolledIn ;
81 rdf:subject ex:Maria ;
82 ex:enrolldate "2023-09-13"^^xsd: date ;
83 ex:enrollpayment "Cash" .
84
85 ex:Teacher rdf:type rdfs:Resource , rdfs:Class ;
86 rdfs:subClassOf ex:Person .
87
88 ex:teaches rdf:type owl:ObjectProperty ;
89 rdfs:domain ex:Teacher ;
90 rdfs:range ex:Course ;
91 rdfs:subPropertyOf ex:attends .
92
93 ex:Sam rdf:type ex:Student , rdfs:Resource , rdfs:Class ;
94 ex:attends ex:Linked_Data ;
95 ex:enrolledIn ex:Linked_Data ;
96 ex:friendOf ex:Peter ;
97 foaf:knows ex:Maya .
98
99 ex:S100 rdf:type rdfs:Resource , rdfs:Class , rdf:Statement ;
100 rdf:object ex:Semantic_Web ;
101 rdf:predicate ex:enrolledIn ;
102 rdf:subject ex:John ;
103 ex:enrolldate "2022-09-12"^^xsd: date ;
104 ex:enrollpayment "Cash" .
105
106 ex:John rdf:type ex:Student , rdfs:Resource , rdfs:Class , ex:Person ;
107 ex:attends ex:Semantic_Web ;
108 ex:enrolledIn ex:Semantic_Web ;
109 ex:friendOf ex:Sam ;
110 foaf:knows ex:Patricia , ex:Sam .
111
112 ex:Linked_Data rdf:type rdfs:Resource , rdfs:Class , ex:Course ;
113 ex:difficulty "hard" .
114
115 ex:classmates rdf:type owl:ObjectProperty ;
116 rdfs:domain ex:Person ;
117 rdfs:range ex:Person .
118
119 ex:knows rdf:type owl:ObjectProperty ;
120 rdfs:domain ex:Person ;
121 rdfs:range ex:Person .

A.4. Dataset statistics

<table><caption>Table 6. Statistics of classes.</caption><thead><tr><td>Class</td><td>Number of entities</td></tr></thead><tbody><tr><td>ex:Student</td><td>3</td></tr><tr><td>ex:Teacher</td><td>1</td></tr><tr><td>ex:Course</td><td>2</td></tr><tr><td>ex:Person</td><td>7</td></tr><tr><td>rdf:Statement</td><td>3</td></tr><tr><td>rdfs:Resource</td><td>19</td></tr><tr><td>Total</td><td>54</td></tr></tbody></table>

<table><caption>Table 7. Statistics of properties.</caption><thead><tr><td>Property</td><td>Number of triples</td></tr></thead><tbody><tr><td>ex:enrolledIn</td><td>3</td></tr><tr><td>ex:teaches</td><td>2</td></tr><tr><td>ex:attends</td><td>5</td></tr><tr><td>ex:friendOf</td><td>2</td></tr><tr><td>foaf:knows</td><td>8</td></tr><tr><td>rdf:type</td><td>61</td></tr><tr><td>rdf:subject</td><td>3</td></tr><tr><td>rdf:object</td><td>3</td></tr><tr><td>rdf:predicate</td><td>3</td></tr><tr><td>ex:enrolldate</td><td>3</td></tr><tr><td>ex:difficulty</td><td>2</td></tr><tr><td>Total</td><td>122</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>Figure 3. Motivating example.</figcaption></figure>

A.5. Ontology and dataset of our motivating example

<figure><img src="image_5.png" /><figcaption>Figure 4. LUBM ontology.</figcaption></figure>

B. Survey Results
<figure><img src="image_6.png" /><figcaption>Figure 5. Sample survey results collected from 5 participants.</figcaption></figure>