Cheikh-Brahim El Vaigh
email: cheikh-brahim.el-vaigh@irisa.fr

François Goasdoué

A Well-founded Graph-based Summarization Framework for Description Logics

Keywords: Data summaries, quotient graph, most specific concept

The quotient operation from graph theory offers an elegant graph summarization framework that has been widely investigated in the literature, notably for the exploration and efficient management of large graphs; it consists in fusing equivalent vertices according to an equivalence relation.

In this paper, we study whether a similar operation may be used to summarize ABoxes. Towards this goal, we define and examine the quotient operation on an ABox: we establish that a quotient ABox is more specific than the ABox it summarizes, and characterize to which extent it is more specific. This preliminary investigation validates the interest of a quotient-based ABox summarization framework, and paves the way for further studies on it in the description logic setting, e.g., to devise equivalence relations suited to the optimization of typical data management and reasoning tasks on large ABoxes or to the visualization of large ABoxes, and on its utilization in related settings, e.g., Semantic Web.

Introduction

Graph summarization has received considerable attention in the literature [START_REF] Liu | Graph summarization methods and applications: A survey[END_REF][START_REF] Cebiric | Summarizing semantic graphs: a survey[END_REF], in particular for the exploration and visualization of large graphs, as well as for the optimization of graph management systems (cardinality estimation, indexing, etc). A well-established tool used to summarize graphs into compact ones is the quotient operation from graph theory [START_REF]Handbook of Graph Theory[END_REF]; other kinds of summaries have also been considered like collections of graph statistics or of frequent graph patterns, or a mix of both as in [START_REF] Palmonari | ABSTAT: linked data summaries with abstraction and statistics[END_REF].

The quotient operation offers an elegant graph summarization framework by decoupling the summarization method, which basically fuses equivalent vertices, from the high-level specification of equivalent vertices, defined by an equivalence relation, e.g., bisimilarity [START_REF] Abriola | Bisimulations on data graphs[END_REF]. Applying the quotient operation to a graph results in a (typically small) homomorphic approximation of it, called quotient graph; the equivalence relation to choose depends on the target summary usage.

In this paper, we study whether a similar operation may be used to summarize ABoxes. Towards this goal, we first transfer the quotient operation from graphs to description logics (DLs) [START_REF]The Description Logic Handbook[END_REF] in order to summarize ABoxes as if they were merely graphs. Then, because ABoxes are not just graphs but are essentially first-order theories (or slight extensions of them), we examine the semantics of the quotient operation on an ABox. We establish that a quotient ABox is more specific than the ABox it summarizes, by showing that its structure entails the structure of the ABox, and we characterize to which extent this quotient ABox is more specific than the ABox it summarizes, by determining the precise nature of the approximation between the quotient ABox contents and the ABox contents. This latter characterization is the main result of this paper. It provides an in-depth understanding of the quotient operation itself as a tool for ABox summarization; the essence of quotient ABoxes is independent of the DL under consideration and of the chosen equivalence relation (that depends on the target summary usage).

The paper is organized as follows. We recall the basics of DLs in Sec. 2. Then, we transfer the quotient operation from graphs to ABoxes in Sec. [START_REF] Bienvenu | Ontology-mediated query answering: Harnessing knowledge to get more from data[END_REF] and we examine its semantics w.r.t. DLs in Sec. [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]. Finally, we discuss related works in Sec. 5 and we conclude with salient perspectives in Sec. [START_REF] Dolby | Scalable semantic retrieval through summarization and refinement[END_REF].

The proofs of our technical results can be found in the appendix of this paper.

Preliminaries

We recall the important aspects of DLs that are used in this paper [START_REF]The Description Logic Handbook[END_REF], with a focus on the lightweight DL-lite R DL [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] that we (just) use to illustrate our discussions throughout this paper; our results hold for (standard) DLs.

DL syntax and semantics Given a set N C of concept names (unary predicates), a set N R of role names (binary predicates), and a set N I of individuals (constants), a DL allows expressing unary and binary formulae respectively called concepts and roles. They are used to build TBoxes (ontologies) made of concept inclusions of the form C 1 ⊑ C 2 and role inclusions of the form R 1 ⊑ R 2 , as well as to build ABoxes (databases) storing concept assertions of the form C(a) and role assertions of the form R(a 1 , a 2 ), where a, a 1 , a 2 ∈ N I . In DL-lite R , concepts and roles are built according to the following rules, where A ∈ N C and R ∈ N R :

B := A | ∃Q, C := B | ¬B, Q := R | R -, S := Q | ¬Q.
Also, TBox inclusions are of the forms B ⊑ C and Q ⊑ S, while ABox assertions are of the forms A(a) and R(a 1 , a 2 ).

First-order interpretations are used to define the semantics of DLs. They are of the form I = (∆ I , • I ), where ∆ I is a non-empty domain and • I is a function that maps every a ∈ N I to a I ∈ ∆ I , every A ∈ N C to A I ⊆ ∆ I , and every R ∈ N R to R I ⊆ ∆ I × ∆ I . Further, the interpretation function • I is extended to the concept and role formulae allowed in the DL under consideration. In DLlite R , • I is extended as follows: (R -)

I = {(o 1 , o 2 ) | (o 2 , o 1 ) ∈ R I }, (∃Q) I = {o 1 | ∃o 2 (o 1 , o 2 ) ∈ Q I }, (¬B) I = ∆ I \ B I and (¬Q) I = (∆ I × ∆ I ) \ Q I . Let I be an interpretation. I satisfies a DL concept C (resp. role R) iff it has a non-empty interpretation, i.e., C I ̸ = ∅ (resp. R I ̸ = ∅). I satisfies an inclusion C 1 ⊑ C 2 (resp. R 1 ⊑ R 2 ) iff C I 1 ⊆ C I 2 (resp. R I 1 ⊆ R I 2
) holds, and it satisfies a TBox iff it satisfies all the TBox inclusions. I satisfies an assertion C(a

) (resp. R(a 1 , a 2 )) iff a I ∈ C I (resp. (a I 1 , a I 2 ) ∈ R I )

Data management

The main data management tasks are consistency checking and query answering. They involve an ABox A and may rely on the knowledge of a TBox T . A is consistent w.r.t. T iff A has a model that is also a model of T . To query ABoxes, we consider the first-order language of unions of conjunctive queries that is widely-considered for ontology-mediated query answering [START_REF] Bienvenu | Ontology-mediated query answering: Harnessing knowledge to get more from data[END_REF] and ontology-based data access [START_REF] Xiao | Ontology-based data access: A survey[END_REF]. A conjunctive query (CQ) is of the form ∃ ⃗ Y ϕ, where ϕ is a conjunction of the forms A(t) or R(t, t ′ ) where t, t ′ are variables or constants, and ⃗ Y is a tuple of variable from ϕ. A CQ is Boolean if all its variables are existentially quantified. The answer to a Boolean CQ q is true if it is entailed by A and T , denoted A |= T q, i.e., q is true in all the models of A and T ; otherwise q is false. The answer to a non-Boolean CQ q with free variables X 1 , . . . , X n , i.e., of arity n, is the set of all the tuples of constants of the form ⃗ a = ⟨a 1 , . . . , a n ⟩ such that A |= T q[⃗ a], where q[⃗ a] is the Boolean CQ obtained by replacing each X k by a k for 1 ≤ k ≤ n. We note q A,T the answer set of q on A w.r.t. T , with the convention that for Boolean queries q A,T = ∅ if q is f alse, and q A,T = {⟨⟩} if q is true where ⟨⟩ is the empty tuple. A union of CQs (UCQ) is a disjunction of CQs with same arity. The answer to a UCQ is the union of the answers to its individual CQs.

Quotient operation for ABoxes

An ABox A can be represented, and is frequently drawn, as a multigraph with typed vertices and typed edges: the vertices are the constants in A, there is a vertex type C on the vertex a iff the concept assertion C(a) is in A, and there is an R-typed edge a R → a ′ iff the role assertion R(a, a ′ ) is in A. Based on this analogy, we transfer the quotient operation from graphs to ABoxes to define quotient ABoxes.

Definition 1 (Quotient ABox). Let A be an ABox, ≡ be some equivalence relation between constants, and let a 1 ≡ , . . . , a n ≡ denote by a slight abuse of notation both the equivalence classes of the constants in A w.r.t. ≡ and the names of these equivalence classes. The quotient ABox of A w.r.t. ≡ is the ABox A ≡ such that:

-C(a i ≡ ) ∈ A ≡ iff there exists a ∈ a i ≡ such that C(a) ∈ A, for 1 ≤ i ≤ n, -R(a i ≡ , a j ≡ ) ∈ A ≡ iff there exist a ∈ a i ≡ and a ′ ∈ a j ≡ such that R(a, a ′ ) ∈ A, for 1 ≤ i, j ≤ n.
In this paper, we do not focus on particular equivalence relations between constants (i.e., binary relations that are reflexive, symmetric and transitive), though in the description logic setting we consider they should be defined w.r.t. an ABox and a TBox. Discussing DL-specific equivalence relations between constants is delegated to future work.

Example 1 (Running example). Let us consider the ABox

A ex = {PhDS(s), sB(s, r 1 ), sB(s, r 2 ), R(r 1 ), R(r 2 ), wW(r 2 , r 1 ), wF(r 1 , l 1 ), wF(r 2 , l 2 ),
ULab(l 1 ), CLab(l 2 )} which states that s is a PhD student (PhDS), who is jointly supervized by (sB) the researchers (R) r 1 , who works for (wF) the university lab (ULab) l 1 , and r 2 , who works for the company lab (CLab) l 2 and who also works with (wW) r 1 .

The graph representations of A ex and of three of quotient ABoxes obtained from it are depicted in Fig. 1. The equivalence relations used in this figure somehow reflect that equivalent constants are instances of the same concept for Fig. 1(b), or instances of non-disjoint concepts with a common generalizing concept if we assume that company labs and university labs are not necessarily disjoint kinds of labs for Fig. 1(c), i.e., CLab ⊑ Lab ∈ T ex and ULab ⊑ Lab ∈ T ex , and if we further assume that PhD student and researcher are not necessarily disjoint kinds of employees for Fig. 1(d), i.e., PhDS ⊑ Emp ∈ T ex and R ⊑ Emp ∈ T ex .

In the sequel, we term summary of an ABox A a quotient ABox of A.

Characterization of ABox summaries

Although Definition 1 does enable the quotient-based summarization of an ABox, an ABox is not just a graph because it also has a first-order semantics. An important question that therefore arises is: does there exist a semantic relationship between an ABox and a summary of it? To answer this question we first point out that, in Definition 1, the implicit function that maps the constants in A to the constants in A ≡ defines a homomorphism from A to A ≡ ; from now, we name this function h and we say that an ABox constant a is represented by a summary

b ≡ , A c ≡ , A d ≡ .
constant a ≡ iff h(a) = a ≡ holds. Based on this ABox-to-summary homomorphism, we answer the above question by relating an ABox and a summary of it through entailment between ABoxes w.r.t. a TBox. The property below states that if we compare an ABox and a summary of it through entailment regardless of the constants they use (they are incomparable otherwise because they use different sets of constants), by just considering how the ABox (resp. summary) atoms join according to these constants, then the ABox is more general than its summary.

Property 1. Let T be a TBox, a 1 , . . . , a m be the constants in an ABox A and a 1 ≡ , . . . , a n ≡ be the constants in some summary A ≡ of A. If we consider these constants as existential variables, then

∃a 1 ≡ • • • ∃a n ≡ A ≡ |= T ∃a 1 • • • ∃a m A holds.
Besides, it is also worth noting that, due to the existence of the ABox-tosummary homomorphism, an ABox and a summary of it are related through the essential data management tasks of consistency checking and query answering. Property 2. Let T be a TBox, A be an ABox and A ≡ be some summary of A.

If A ≡ is consistent w.r.t. T , then A is consistent w.r.t. T .
Property 3. Let T be a TBox, A be an ABox, A ≡ be some summary of A, and let q be a UCQ. If q A,T ̸ = ∅ holds then q A≡,T h ̸ = ∅ holds, with q h the query q in which every constant a is replaced by its image h(a) through the A-to-A ≡ homomorphism h.

We remark that Property 2 and the contraposition of Property 3 (i.e., if q A≡,T h = ∅ holds then q A,T = ∅ holds) are of practical interest to check rapidly if, for sure, an ABox is consistent and if a query has no answer, by using the typically (much) smaller ABox summary.

Example 2 (Cont.). From now, let us assume that T ex just consists of the inclusions mentioned in Example 1.

To illustrate Property 1, it is easy to see on Fig. 1 that A i ≡ |= ∅ A ex holds for i ∈ {b, c, d}, hence holds with |= Tex .

As for Property 2, it is also easy to see that A i ≡ is consistent w.r.t. T ex , for i ∈ {b, c, d}, as well as A ex . We remark that if PhD students and researchers would be disjoint, i.e., PhDS ⊑ ¬R ∈ T ex , then A d ≡ would be inconsistent w.r.t. T ex while A ex would be consistent w.r.t. T ex . This observation indicates that DL-specific equivalence relations should avoid to the extent possible building inconsistent summaries out of consistent ABoxes.

Finally, let us illustrate Property 3 on Fig. 1. Consider the UCQ q = R(X) ∧ wF(X, l 1 )∪R(X)∧wF(X, l 2 ) asking for the researchers who work for the lab l 1 or l 2 .

q has some answer on A ex w.r.t. T ex (q Aex,Tex = {⟨r 1 ⟩, ⟨r 2 ⟩}), thus its translation q h has some answer w.r.t. T ex on the summary A i ≡ , i ∈ {b, c, d}. For the CQ q = PhDS(X 1 ) ∧ wW(X 1 , X 2 ) asking for the PhD students and people with whom they work, we note that because the q h translation does not have answers on A i ≡ w.r.t. T ex , i ∈ {b, c}, i.e., q

A i ≡ ,T h
= ∅, hence by contraposition of Property 3, q does not have answer on A ex w.r.t. T ex either, i.e., q Aex,Tex = ∅. However, we observe that q h has some answer on A d ≡ w.r.t. T ex , while q has no answer on A ex w.r.t. T ex , i.e., this particular summary fails in detecting that q has no answer on A ex w.r.t. T ex . This observation suggests that DL-specific equivalence relations should be carefully chosen depending on the target summary usage.

Resuming our initial discussion, though Property 1 states that a summary is more specific than the ABox it summarizes up to the set of constants they use, it immediately raises a second crucial question: to which extent a summary is more specific than the original ABox it summarizes? We answer this second question by characterizing to which extent the knowledge a summary has about a constant is more specific than the knowledge the ABox has about the equivalence class this summary constant represents, and similarly for a pair of summary constants and the pair of equivalence classes these summary constants represent in the ABox.

For an ABox A and a TBox T , the most precise knowledge about a set of constants a 1 , . . . , a n corresponds to one or more concepts known as the most specific concepts (MSCs) a 1 , . . . , a n are all instances of [START_REF]The Description Logic Handbook[END_REF]. A concept C is a MSC of a 1 , . . . , a n w.r.t. A and T iff (i) A |= T C(a i ) holds for all i ∈ [1, n], and (ii) for any concept D such that A |= T D(a i ) holds for all i ∈ [1, n], either C ⪯ T D holds or C ̸ ⪯ T D and D ̸ ⪯ T C hold. We remark that though a MSC may be of infinite size in some DLs, this is not an issue here as we just want a semantic characterization of it. In the sequel, we designate by msc A,T (a 1 , . . . , a n ) the conjunction (⊓) of the MSCs of a 1 , . . . , a n w.r.t. A and T 1 and we refer to it as the MSC of a 1 , . . . , a n w.r.t. A and T , because it always exists (the empty conjunction is the universal concept ⊤) and it is obviously unique up to equivalence.

A first step towards answering our second question is Lemma 1, which provides an upper approximation through subsumption of the MSC of some summary constant w.r.t. the individual MSCs of the equivalent ABox constants it represents; Lemma 1 follows from the existence of the ABox-to-summary homomorphism.

Lemma 1. Let T be a TBox, A be an ABox and A ≡ be the summary of A w.r.t. the ≡ equivalence relation. If a 1 , . . . , a n are all the constants in A that belong to the equivalence class a ≡ according to ≡, then the following holds:

msc A≡,T (a ≡ ) ⪯ T n i=1 msc A,T (a i ).

Example 3 (Cont.). Let us consider the summary A d

≡ of A ex in Fig. 1 and illustrate Lemma 1 with the summary constant l 1 |l 2 and the ABox constants l 1 , l 2 it represents:

msc A d ≡ ,Tex (l 1 |l 2 ) = Clab ⊓ ULab ⊓ ∃wF -, msc Aex,Tex (l 1 ) = ULab ⊓ ∃wF -, msc Aex,Tex (l 2 ) = CLab ⊓ ∃wF -, and msc A d ≡ ,Tex (l 1 |l 2 ) ⪯ Tex ⊓ x∈{l1,l2} msc Aex,Tex (x), i.e., Clab ⊓ ULab ⊓ ∃wF -⪯ Tex (ULab ⊓ ∃wF -) ⊓ (CLab ⊓ ∃wF -), clearly holds.
At the same time, in the above Lemma 1, to the set of (equivalent) constants a 1 , . . . , a n corresponds its most specific concept msc A,T (a 1 , . . . , a n ), as recalled above. As the next step towards answering our second question, Lemma 2 provides a lower approximation through subsumption of the MSC of a 1 , . . . , a n w.r.t. the individual MSCs of these constants; it follows from the definition of MSC.

Lemma 2. Let T be a TBox and A be an ABox. If a 1 , . . . , a n are constants in A, then the following holds:

n i=1 msc A,T (a i ) ⪯ T msc A,T (a 1 , . . . , a n ).

Example 4 (Cont.). Let us consider again the summary A d

≡ of A ex in Fig. 1 and illustrate Lemma 2 with the summary constant l 1 |l 2 and the ABox constants l 1 , l 2 it represents like in the preceding example: msc Aex,Tex (l 1 , l 2 ) = Lab ⊓ ∃wF -, and ⊔ x∈{l1,l2} msc Aex,Tex (x) ⪯ T msc Aex,Tex (l 1 , l 2 ), i.e., (ULab ⊓ ∃wF -) ⊔ (CLab ⊓ ∃wF -) ⪯ Tex Lab ⊓ ∃wF -, clearly holds.

We are now ready to answer our second question with Theorem 1, which is a direct corollary of Lemma 1 and Lemma 2. It relates msc A,T (a ≡ ) and msc A,T (a 1 , . . . , a n ) through their respective upper and lower approximations.

Theorem 1. Let T be a TBox, A be an ABox and A ≡ be the summary of A w.r.t. the ≡ equivalence relation. If a 1 , . . . , a n are all the constants in A that belong to the equivalence class a ≡ according to ≡, then the following holds:

msc A≡,T (a ≡ ) ⪯ T n i=1 msc A,T (a i ) ⪯ T n i=1 msc A,T (a i ) ⪯ T msc A,T (a 1 , . . . , a n ).
From Theorem 1, it is now clear that the semantic distance through subsumption between the knowledge about each constant a ≡ in the summary, i.e., msc(a ≡ ), and the knowledge about the set of equivalent constants that a ≡ represents in the ABox, i.e., msc A,T (a 1 , . . . , a n ), corresponds at least to approximate the union of individual knowledge about a 1 , . . . , a n in the ABox by a conjunction, i.e., approximating n i=1 msc A,T (a i ) by n i=1 msc A,T (a i ). We establish similar results (omitted due to space limitations) by adapting the notion of MSC to roles.

Finally, we stress that all the above results just follow from the definition of quotient ABox (Definition 1). In particular, they are independent of the equivalence relation (≡) and of the DL under consideration.

Related work

We present below the works from the DL literature that are closely related to ABox summarization.

An ABox summarization approach for the SHIN DL has been studied to optimize consistency checking [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF] and instance retrieval in the subsequent work [START_REF] Dolby | Scalable semantic retrieval through summarization and refinement[END_REF], i.e., finding the instances of a given SHIN concept; these two summary-based optimizations are implemented in the SHER system [START_REF] Dolby | Scalable highly expressive reasoner (SHER)[END_REF]. This approach can be seen as a particular instantiation for the SHIN DL of our general ABox summarization framework, in which equivalent constants are non-distinct constants2 stored in the ABox as instances of the same SHIN concepts; our framework allows using this definition of equivalent constants for the equivalence relation ≡ or any other relevant to the target summary usage. We therefore provide a better understanding of the SHIN summaries of [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF][START_REF] Dolby | Scalable semantic retrieval through summarization and refinement[END_REF][START_REF] Dolby | Scalable highly expressive reasoner (SHER)[END_REF] by establishing that they are more specific than the SHIN ABoxes they summarize, and notably to which extent they are more specific. Further, we remark that our ABox summarization approach, because it is based on the quotient operation, is more declarative than that of [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF][START_REF] Dolby | Scalable semantic retrieval through summarization and refinement[END_REF][START_REF] Dolby | Scalable highly expressive reasoner (SHER)[END_REF], by elegantly decoupling the summarization means (i.e., fusing equivalent constants) from the high-level specification of equivalent constants, i.e., the equivalence relation ≡ to use. By contrast, SHIN summaries are defined by an explicit canonical function that maps ABox constants to summary one; our function h has similar goal but is implicit because derived from the ABox and equivalence relation at hand.

Another form of ABox summarization is ABox abstraction, which has been studied for materialization in the Horn-ALCHOI and Horn-SHOIF DLs [START_REF] Glimm | Abstraction refinement for ontology materialization[END_REF][START_REF] Glimm | Ontology materialization by abstraction refinement in horn SHOIF[END_REF],

i.e., for pre-computing and storing entailed assertions. The idea is to represent several assertions of an ABox by a single one in the ABox abstraction. To this aim, an ABox B is defined as an abstraction of an ABox A if there exists a mapping from the constants in B to the constants in A that defines a homomorphism from B to A. Hence, by contrast with our summaries that are more specific than original ABoxes, abstractions are more general than original ABoxes, thus capture a subset of their contents.

Also related to ABox summarization is ABox modularization, which has been studied for instance retrieval in the SHIF [START_REF] Guo | A scalable approach for partitioning owl knowledge bases[END_REF] and SHI [START_REF] Möller | Advances in accessing big data with expressive ontologies[END_REF] DLs. It consists in extracting a subset of an ABox that entails all the assertions in which a given constant is involved.

Finally, less related works on ABox summarization do not summarize an ABox by another, e.g., [START_REF] Palmonari | ABSTAT: linked data summaries with abstraction and statistics[END_REF] which computes statistics about the concept and roles instances, and Abstract Knowledge Patterns of the form (C 1 , r, C 2 ) indicating that the role r relates instances of the concept C 1 to instances of the concept C 2 .

Conclusion and perspectives

We devised a well-founded ABox summarization framework for DLs, by applying the quotient operation from graph theory to ABoxes and examining the quotient ABoxes, i.e., summaries, it produces.

With this now well-understood ABox summarization framework in place, the next necessary step is to study DL-specific equivalence relations between constants, to explore, visualize or optimize reasoning on and the management of ABoxes. These equivalence relations might be sought either from scratch or derived from the ones used for graph summarization if meaningful w.r.t. the DL semantics, e.g., the well-established and widely adopted ones based on bisimilation [START_REF] Liu | Graph summarization methods and applications: A survey[END_REF] or the recent ones based on the cooccurrence of types and edges [START_REF] Goasdoué | RDF graph summarization for firstsight structure discovery[END_REF]. Also, ideally, such relations should be devised to avoid to the extent possible building inconsistent summaries out of consistent ABoxes (recall Example 2).

C(a i

≡ ) ∈ A ≡ and 1 ≤ i ≤ n, and such that (ψ(a i ≡ ), ψ(a j ≡ )) ∈ R I for every R(a i ≡ , a j ≡ ) ∈ A ≡ and 1 ≤ i, j ≤ n. Let us consider the composite function ψ • h, where ψ is the above function and h is the implicit function that defines our ABox-to-summary homomorphism. This function thus maps a 1 , . . . , a m to the interpretation domain of I and clearly ψ(h(a i )) ∈ C I for every C(a i ) ∈ A and 1 ≤ i ≤ m, because by construction of A ≡ C(h(a i )) ∈ A ≡ , and such that (ψ(h(a i )), ψ(h(a j ))) ∈ R I for every R(a i , a j ) ∈ A and 1 ≤ i, j ≤ m, because by construction of A ≡ R(h(a i ), h(a j )) ∈ A ≡ . Therefore, I is also a model of ∃a Consider the model J = (∆ J , • J ) defined as follows: ∆ J = ∆ I , A J = A I for every concept name A ∈ N C , R J = R I for every role name R ∈ N R , and for every constant a in A, a J = h(a) I .

For every concept assertion C(a) ∈ A, C(h(a)) ∈ A ≡ by definition of a quotient ABox, where h is the implicit function defining the ABox-to-summary homomorphism. Since I is a model of A ≡ , I is a model of C(h(a)), i.e., h(a) I ∈ C I . By definition of J , C J = C I and a J = h(a) I , thus a J ∈ C J , i.e., J is a model of C(a). J is therefore a model of all the concept assertions in A.

Similarly, for every role assertion R(a k , a l ) ∈ A, R(h(a k ), h(a l )) ∈ A ≡ by definition of a quotient ABox, where h is the implicit function defining the ABox-to-summary homomorphism. Since I is a model of A ≡ , I is a model of R(h(a k ), h(a l )), i.e., (h(a k ) I , h(a l ) I ) ∈ R I . By definition of J , R J = R I , a J k = h(a k ) I and a J l = h(a l ) I , thus (a J k , a J l ) ∈ R J , i.e., J is a model of R(a k , a l ). J is therefore a model of all the role assertions in A.

It therefore follows that J is a model of all the assertions in A, hence a model of A. ⊓ ⊔ Proof (Proof of Property 3). We remark that if a query is asked on an ABox that is inconsistent w.r.t. its associated TBox, then both true and f alse if the query is Boolean, and all the tuples of the arity of the query otherwise, are answers. If A is not consistent w.r.t. T , then q A,T ̸ = ∅, and by the contraposition of Property 2, A ≡ is not consistent w.r.t. T too, therefore q A≡,T h ̸ = ∅ and Property 3 holds in this first case.

If A is consistent w.r.t. T , while A ≡ is not consistent w.r.t. T (see Example 2), then Property 3 holds in this second case: q A≡,T h ̸ = ∅ holds whenever q A,T ̸ = ∅ or q A,T = ∅ holds.

Otherwise, A is consistent w.r.t. T and A ≡ is consistent w.r.t. T . Let us show that Property 3 holds in this third and last case. If the UCQ q has a non-empty answer set, then at least one of its CQs has a non-empty answer set. Let q ′ be such a CQ in q. Let us assume, without loss of generality, that q ′ is Boolean as the definition of non-Boolean query answers reduces to the Boolean case. Let us consider some model J of A ≡ and T . Let I be the interpretation such that ∆ I = ∆ J , A I = A J for every concept name A ∈ N C , R I = R J for every role name R ∈ N R , and a I = h(a) J for every constant a in A. Clearly, by construction, I is homomorphic to J and is a model of A and T . Thus, I is also a model of q ′ . Further, J is obviously a model of q ′ just in case q ′ does not contain contants, because the constants in A do not have interpretations in J : ∆ I = ∆ J , A I = A J for every concept name A ∈ N C , R I = R J for every role name R ∈ N R . Otherwise, J is a model of q ′ h , in which constants from A are replaced by the constants in A ≡ they are represented by: a I = h(a) J for every constant a in A. Therefore, every model of A ≡ and T is a model of q ′ h , i.e., q ′ h is entailed by A ≡ and T , thus has a non-empty answer set, hence q h has a non-empty answer set too. ⊓ ⊔ Proof (Proof of Lemma 1 Otherwise, both A and A ≡ are consistent w.r.t. T , and let us consider some model J of A ≡ and T . Let I be the interpretation such that ∆ I = ∆ J , A I = A J for every concept name A ∈ N C , R I = R J for every role name R ∈ N R , and a I = h(a) J for every constant a in A. Clearly, by construction, I is homomorphic to J and is a model of A and T . Because I is a model of A and T , I is a model of the concept assertion (msc A,T (a i ))(a i ) for 1 ≤ i ≤ n. By construction of I, J is a model of (msc A,T (a i ))(h(a i )) for 1 ≤ i ≤ n, where h is the ABox-to-summary homomorphism, i.e., J is a model of (msc A,T (a i ))(a ≡ ) for 1 ≤ i ≤ n.

It follows that all the models of A ≡ and T are models of (msc A,T (a i ))(a ≡ ) for 1 ≤ i ≤ n, and of (msc A≡,T (a ≡ ))(a ≡ ) ( * ). By definition of the MSC of a ≡ , either (i) msc A≡,T (a ≡ ) ⪯ T n i=1 msc A,T (a i ) holds or (ii) msc A≡,T (a ≡ ) ̸ ⪯ T n i=1 msc A,T (a i ) and n i=1 msc A,T (a i ) ̸ ⪯ T msc A≡,T (a ≡ ) hold. In the latter case (ii), msc A≡,T (a ≡ )⊓ n i=1 msc A,T (a i ) would be strictly subsumed by msc A≡,T (a ≡ ) w.r.t. T , and because of ( * ) above, msc A≡,T (a ≡ ) ⊓ n i=1 msc A,T (a i ) would be the MSC of a ≡ , a contradiction. Therefore, we must be in case (i) and msc A≡,T (a ≡ ) ⪯ T In particular, it is well-known that msc A,T (a 1 , . . . , a n ) and lcs T (msc A,T (a 1 ), . . . , msc A,T (a n )) are equivalent [START_REF]The Description Logic Handbook[END_REF]. Further, it is also known that lcs T (msc A,T (a 1 ), . . . , msc A,T (a n )) cannot be more specific than n i=1 msc A,T (a i ), notably they are equivalent in DLs allowing disjunction (⊔). Thus, n i=1 msc A,T (a i ) ⪯ T msc A,T (a 1 , . . . , a n ) holds. ⊓ ⊔

Fig. 1 :

 1 Fig. 1: The ABox Aex and three quotient ABoxes of it: A b ≡ , A c ≡ , A d ≡ .

  n i=1 msc A,T (a i ) holds. ⊓ ⊔ Proof (Proof of Lemma 2). Lemma 2 follows the well-known relationship between the MSC of constants and the notion of least common subsumer (LCS) of concepts [2], i.e., a most specific concept generalizing all of them. A concept C is a LCS of the concepts C 1 , . . . , C n w.r.t. a TBox T iff (i) C i ⪯ T C holds for all i ∈ [1, n], and (ii) for any concept D such that C i ⪯ T D holds for all i ∈ [1, n], either C ⪯ T D holds or C ̸ ⪯ T D and D ̸ ⪯ T C hold. We denote by lcs T (C 1 , . . . , C n ) the conjunction of the LCSs of C 1 , . . . , C n w.r.t. T and we refer to it as the LCS of C 1 , . . . , C n w.r.t. T .

  holds, and it satisfies an ABox iff it satisfies all the ABox assertions. Finally, I is a model of a concept, role, inclusion, TBox, assertion or ABox iff I satisfies it.Generalization/specialization relations Concepts and roles are compared through subsumption, which may rely on the knowledge of a TBox T . C 1 is subsumed byC 2 or C 2 subsumes C 1 w.r.t. T , denoted C 1 ⪯ T C 2 , iff every model I of T is a model of the inclusion C 1 ⊑ C 2 ;subsumption for roles is defined similarly.ABoxes are compared through entailment, which may also rely on a TBoxT . A 1 entails A 2 or A 2 is entailed by A 1 w.r.t. T , denoted A 1 |= T A 2 ,iff every model I of A 1 and T is also a model of A 2 . As special case, an ABox A entails a concept assertion C(a) w.r.t. T , denoted A |= T C(a), if A entails w.r.t. T the ABox {C(a)}; entailment of a role assertion is defined similarly.

  1 , . . . , a m A. ⊓ ⊔ Proof (Proof of Property 2). If A ≡ is consistent w.r.t. T , there must exist some model I = (∆ I , • I ) of A ≡ . Let us show that we can build a model of A out of I, hence that A is consistent w.r.t. T .

  ). If A is inconsistent w.r.t. T , then A ≡ is also inconsistent w.r.t. T (by contraposition of Property 2), and the Lemma clearly holds. If A is consistent w.r.t. T while A ≡ is inconsistent w.r.t. T , then the Lemma also clearly holds.

a1, . . . , an obviously have a single MSC in DLs equipped with conjunction (⊓).

In SHIN , constants are stated distinct by using assertions of the built-in role ̸ =.

Acknowledgments

This work was partially supported by the ANR project CQFD (ANR-18-CE23-0003).

Appendix

Proof (Proof of Property 1). In case ∃a


Maxime Buron
email: maxime.buron@cs.ox.ac.uk

Cheikh-Brahim El
email: cheikh-brahim.el-vaigh@irisa.fr

François Goasdoué

Towards Faster Reformulation-based Query Answering on RDF Graphs with RDFS Ontologies

Keywords: RDF/S, query answering, reformulation, optimization

Answering queries on RDF knowledge bases is a crucial data management task, usually performed through either graph saturation or query reformulation. In this short paper, we optimize our recent stateof-the-art query reformulation technique for RDF graphs with RDFS ontologies [2], and we report on preliminary encouraging experiments showing performance improvement by up to two orders of magnitudes!

Introduction

The RDF graph data model and its associated SPARQL query language are the two well-established W3C standards for sharing data and knowledge, especially on the Semantic Web through DBpedia, Wikidata, or more generally the Linked Open Data cloud. Their rapid adoption over the last decade has made the study of dedicated query answering techniques a hot topic in the data management community at large, to design database management or data integration systems, e.g., [START_REF] Nenov | RDFox: A highly-scalable RDF store[END_REF][START_REF] Buron | Ontology-based RDF integration of heterogeneous data[END_REF].

Answering queries on an RDF graph (graph in short) is not an easy task as it combines database-style query evaluation with AI-style reasoning, to answer queries from both the explicit and implicit information that the graph models. Saturation-based query answering aims at computing first the saturation of the graph by adding to it all its implicit information obtained through reasoning. Then, the answers to a query on the graph are obtained by simply posing the query to a data management system (DMS) that stores the graph saturation. This technique provides fast query answering in general, but the saturation needs possibly costly maintenance upon updates [START_REF] Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]. By contrast, reformulation-based query answering amounts to transforming the query into a query reformulation, so that the answers to the query are obtained by posing the query reformulation to a DMS that stores only the explicit graph part. This technique does not need maintenance upon updates, as it does not rely on the graph saturation, but query reformulations may be too complex to be efficiently evaluated by a DMS [START_REF] Bursztyn | Optimizing reformulation-based query answering in RDF[END_REF].

In this paper, we consider the optimization of the reformulation-based query answering approach that raises so far unsolved performance issues. In particular, we start with our recent technique [START_REF] Buron | Reformulation-based query answering for RDF graphs with RDFS ontologies[END_REF] that applies to the core SPARQL conjunctive queries, a.k.a. Basic Graph Pattern Queries (BGPQs), and RDF graphs with RDF Schema (RDFS) ontologies; this technique supports the four RDFS ontological constraints (subclass, subproperty, domain, and range) between classes (i.e., node types) and properties (i.e., edge labels), and all the RDF entailment rules [10] that allow reasoning with these constraints. Other techniques only focus on a subset of all these RDF entailment rules [START_REF] Goasdoué | Efficient query answering against dynamic RDF databases[END_REF][START_REF] Bursztyn | Optimizing reformulation-based query answering in RDF[END_REF]. Crucially, query answering performance decreases as the number of supported RDF entailment rules increases (because the complexity of its query reformulation increases), hence efficient reformulation-based query answering in the setting of [START_REF] Buron | Reformulation-based query answering for RDF graphs with RDFS ontologies[END_REF] is particularly challenging.

Our contributions are twofold. First, in Sec. 2, we identify two causes of limited performance for the reformulation-based query answering technique in [START_REF] Buron | Reformulation-based query answering for RDF graphs with RDFS ontologies[END_REF] and those it encompasses (e.g., [START_REF] Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]), and we propose three optimizations to address them. They all consists in identifying and avoiding useless query reformulation evaluation efforts either by reasoning on a query reformulation itself via query containment or by reasoning on a query reformulation based on the queried graph using the cardinalities (number of instances) of its classes and properties, or a summary of it. Second, in Sec. 3, we discuss in which order these optimizations must be applied to provide best performance and we report on experiments we made to assess the effectiveness of our optimization workflow. As we shall see, our workflow makes reformulation-based query answering (i) feasible when it was failing or timing out due to too complex query reformulations, (ii) faster when it was feasible (up to 2 orders of magnitude), and (iii) better than saturation-based query answering in a non-negligible number of occasions.

Optimizing reformulation-based query answering

The reformulation-based query answering technique we devised in [START_REF] Buron | Reformulation-based query answering for RDF graphs with RDFS ontologies[END_REF] computes for a given BGPQ q a reformulation q ′ of it w.r.t. the RDFS ontology O of the queried graph G and the set R of entailment rules. q ′ is expressed as a union of BGPQs (UBGPQ) that enumerates the -worst case exponentially manyspecializations of q w.r.t. O and R. We present next three optimizations to apply to q ′ before it is sent for evaluation to some DMS that stores G; they consist in removing useless BGPQs from q ′ to speed up its evaluation time. Containment-based BGPQ elimination. Because every BGPQ within the UBGPQ reformulation q ′ is computed independently from the others through different reasoning paths, it may happen that q ′ contains redundant BGPQs, i.e., whose answer sets are subsets of those of other BGPQs in q ′ . These can be identified thus pruned away from q ′ by comparing every pair of its BGPQs through containment checking. We name this first optimization UBGPQ minimization (M). We note that such minimization has been used in the literature in other reformulation-based query answering settings, e.g., existential rules [START_REF] König | Sound, complete and minimal ucq-rewriting for existential rules[END_REF].

Cardinality-based and summary-based empty BGPQ elimination. An essential property of reformulation-based query answering, which is common to all reformulation-based techniques and not specific to [START_REF] Buron | Reformulation-based query answering for RDF graphs with RDFS ontologies[END_REF], is that the reformulation q ′ computed from q w.r.t. O and R allows retrieving the answers to q on all the graphs with ontology O. Though theoretically nice, the generality of q ′ needlessly limits its performance: q ′ may contain BGPQs with no answer on the specific queried graph G, while evaluating them may take (significant) time.

BGPQs in q ′ may have no answer just because G has no instance for classes or properties these BGPQs mention. To prune them away from q ′ , we compute and store the cardinalities of the classes and properties in G, which, clearly, can be maintained very fast upon graph updates. We name this second optimization empty relation pruning (ER). Also, BGPQs in q ′ may have no answer because, though every class and property they mention has instances, their selection or join conditions cannot be matched in G. Thus, for each BGPQ in q ′ , we check whether it has no answer on a summary of G, in which case it is pruned away from q ′ . We call this optimization summary pruning (S). To do this, we reuse the notion of RDF graph summary we defined in [START_REF] Goasdoué | RDF graph summarization for firstsight structure discovery[END_REF]: a summary is an RDF graph G ≡ computed as the quotient graph of the graph G to summarize, using an RDF equivalence relation ≡ over the nodes of G (discussed shortly); the particular ≡ to use depends on the target summary usage. We recall that the quotient operation basically fuses every set of equivalent nodes into a single new node representing them all in G ≡ ; we say that this latter node represents the former equivalent ones, in particular it inherits of all their types and edges. We pointed out in [START_REF] Buron | Revisiting RDF storage layouts for efficient query answering[END_REF] an important property of a summary: a BGPQ q has no answer on G if the BGPQ q ≡ has no answer on G ≡ , where q ≡ is obtained from q by replacing each mention of a G's node by the G ≡ 's node it is represented by. We remark here that q may have no answer on G while q ≡ does have some answer on G ≡ . Importantly, the ability of a summary to prune BGPQs depends on the choice of RDF equivalence relation ≡, all of those presented in [START_REF] Goasdoué | RDF graph summarization for firstsight structure discovery[END_REF] have been devised for graph visualization. Therefore, we define a novel RDF equivalence relation for BGPQ pruning that behaves as follows: two nodes a,b in G are equivalent, noted a ≡ b, iff (i) they both have the same class (i.e., node type), or (ii) they are both equivalent to a third node c in G, i.e., a ≡ c and b ≡ c. The rationale for this definition is that w.r.t. data compression we want a single representative for every class/type (item (i) above) and w.r.t. of the evaluation of BGPQs we want to capture joins between different classes/types (item (ii) above).

Optimization workflow and experimental results

Optimization workflow. With the above three optimizations in place, the crucial question is now in which order they should be applied to a reformulation q ′ to maximize the performance gain. After experimenting on the possible orders, the best we found is: ER, then M, and finally S. The intuition behind this optimization workflow is that ER is very fast to perform (linear in the size of q ′ ) and may reduce the cost of both M by avoiding containment checks and S by avoiding issuing BGPQs to the DMS while we "statically" know that they have no answer. In practice, we observed that ER does help M but not S, because DMSs are smart enough to efficiently detect queries with an empty relation. Then, we chose to apply M because it is independent of the size of G and, though it consists in a number quadratic in the size of q ′ of NP-Complete BGPQ containment checks, it is performed (i) in-memory and (ii) on BGPQs that are not large in practice (although the UBGPQ q ′ that unions them may be large). By contrast, the difficulty of S augments with the size of q ′ and of G ≡ that grows with the size of G. Applying M before S allows handling larger graphs. In our experiments, the percentage of BGPQs pruned by ER, M and S is respectively in average 32%, 19% and 25%, i.e., 76% in total! Further, while the time spent in applying ER is negligible (always less than 2ms), in average, 3.73% of the query answering time is spent in applying M and 24.97% in applying S (dropping to 14.32%, if we disregard the four queries with no answer for which most of the query answering time is spent in applying S as expected). Experiments. We have implemented our optimizations in OntoSQL3 [1,2,4,6], a Java platform for RDF data management on top of Postgres v12.7, in which we stored a LUBM [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF] graph G of 100M edges with its summary G ≡ of 8.3M edges (7.6% G's size). For our experiments, we used a CentOs 7.5 linux server with a 2.7GHz Intel Core i7 CPU, 160GB of RAM and a fast HDD. Loading G took 2h27min and building G ≡ took 13min. We reused 26 queries from [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF][START_REF] Buron | Revisiting RDF storage layouts for efficient query answering[END_REF][START_REF] Bursztyn | Optimizing reformulation-based query answering in RDF[END_REF]] with 1 to 11 joins and 0 to 20M answers. In Figure 1, we can see their corresponding reformulation size (number of BGPQs in the UBGPQ) before optimization (shown as x-axis labels), and their answering times using the reformulation without and with part of or all our optimization workflow; all are compared to the saturationbased approach. We set a timeout to 10min; it is reached when answering Q22, Q20 and Q17 without optimization. We observe that our optimization workflow yields performance improvement except on very simple queries where its overhead shows; we remark performance gain up to one order of magnitude for Q20, Q04 and two orders for Q15, and quite surprisingly optimized reformulationbased query answering is faster than saturation-based query answering on Q04, Q15 and Q03.

Perspectives

A direct perspective to this work is to support fast summary maintenance upon graph updates. We will investigate this using the union-find-delete data structure, which is suited to model and update equivalence relations.

Fig. 1 .

 1 Fig. 1. Query answering times comparison using different optimization workflows.

https://ontosql.inria.fr

Acknowledgements

This work was partially supported by the ANR project CQFD (ANR-18-CE23-0003).


Wafaa El

Cheikh-Brahim El
email: cheikh-brahim.el-vaigh@irisa.fr

François Goasdoué

Ontology-Mediated Query Answering: Performance Challenges and Advances

Keywords: query answering, knowledge base, summary, optimization

Ontology-mediated query answering (OMQA) is a recent data management trend in the Artificial Intelligence, Database and Semantic Web areas, which aims at answering database queries on knowledge bases. Because it is an intricate combination of automated reasoning and database query evaluation, it raises major performance challenges. In this demonstration, we showcase a decade of OMQA optimization to understand "Where do we stand now and how did we get there?" and we highlight a promising new OMQA optimization that brings further significant performance improvement to discuss "What's next?".

Motivations

Ontology-mediated query answering [START_REF] Bienvenu | Ontology-mediated query answering: Harnessing knowledge to get more from data[END_REF] (OMQA) amounts to answering database queries on a knowledge base (KB), i.e., data described by an ontology modelling the background knowledge of the application domain. It goes beyond database query answering that produces answers just from the data, by identifying additional answers through reasoning about the data with the help of the ontology. OMQA has become recently a hot topic in the Artificial Intelligence, Database and Semantic Web communities, notably for conjunctive queries (a.k.a. the core select-project-join database queries) on KBs expressed with Description Logics, on which builds the W3C's Web Ontology Language (OWL2), as well as with the closely related Datalog± and Existential Rules.

Three OMQA techniques have been devised in the literature. They amount to reducing OMQA to standard relational database query evaluation by compiling the ontology knowledge in the query via reformulation or rewriting (e.g., [START_REF] Chortaras | Optimized query rewriting for OWL2QL[END_REF][START_REF] Thomazo | Compact rewritings for existential rules[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF]), in the data via saturation or materialization (e.g., [START_REF] Leone | Fast query answering over existential rules[END_REF]), or in both via combined or hybrid approaches (e.g., [START_REF] Kontchakov | The combined approach to query answering in dl-lite[END_REF]). The OMQA technique based on query reformulation, on which we focus in this demonstration, is the by far the most studied and utilized one. It was introduced in [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] and consists in reformulating every incoming conjunctive query (CQ) q into a union of conjunctive queries (UCQ) q ′ using the KB's ontology, so that the standard database evaluation of (the SQLized) q ′ on the KB's data stored in a relational database yields the correct answers to q. Crucially, such a reformulated query q ′ enumerates within its union all the (worst case exponentially many) specializations of q w.r.t. the ontology knowledge. In practice, reformulations may be large, in which case relational database management systems (RDBMSs), even modern ones, cannot answer them efficiently (all the CQs in the UCQ are evaluated). To mitigate this performance issue, investigations have focused on alternative reformulation languages that may be easier to evaluate than large UCQs, by limiting redundancies across CQs within UCQs: minimal UCQs [START_REF] Chortaras | Optimized query rewriting for OWL2QL[END_REF] and unions of semi-CQs [START_REF] Thomazo | Compact rewritings for existential rules[END_REF] (USCQs). However, such OMQA approaches produce a single reformulation for every query, thus are doomed to fail or to poor performance if the produced reformulation is too costly to evaluate by the RDBMS at hand. Based on this observation, the language of joins of UCQs (JUCQs) was considered to explore a space of semantically equivalent but syntactically different reformulations, among which one with lowest estimated evaluation cost on the RDBMS is chosen [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Bursztyn | Optimizing FOL reducible query answering: Understanding performance challenges[END_REF].

With this demonstration, our ambition is twofold. First, we want to showcase a decade of OMQA optimization to understand "Where do we stand now and how did we get there?" For that, we compare and analyze the performance improvement that the literature has brought over the years with the state-ofthe-art UCQ, then USCQ and finally JUCQ reformulations. Second, we want to discuss "What's next?" by highlighting a novel advance on OMQA optimization that we propose, and which allows improving significantly the performance of UCQ, USCQ and JUCQ reformulations using a summary of the queried data [START_REF] El Vaigh | A well-founded graph-based summarization framework for description logics[END_REF], up to several orders of magnitude in some cases! To substantiate the discussion, we focus on OMQA for CQs on KBs expressed with the DL-lite R description logic [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]; this setting is particularly relevant from both the technical and practical viewpoints: (i) the UCQ, USCQ and JUCQ reformulations were defined for it and (ii) DL-lite R underpins the QL profile of OWL2, i.e., the well-established W3C standard for OMQA on large data volume.

In Sec. 2, we recall the reformulation-based OMQA technique, point out why the evaluation performance of state-of-the-art query reformulations is intrinsically limited, and discuss our new optimization based on data summaries to circumvent this performance issue. Then, in Sec. 3, we present the demo scenarios we prepared, and sketch the demo experience we planned for the attendees.

Reformulation-based OMQA and optimization thereof

A DL-lite R KB K consists of a database called an ABox, noted A, described by an ontology called a TBox, noted T ; we note such a KB K = (T , A).

Reformulation-based OMQA amounts to reformulating a CQ q using a TBox T into a reformulation q T so that for all ABox A ′ , the relational evaluation of q T on A ′ stored in an RDBMS as a relational database computes the exact answer set of q on the KB K = (T , A ′ ). We argue that the universality of a q T reformulation needlessly limits its evaluation performance: when reformulationbased OMQA is used to answer q on a particular KB K = (T , A), the ABox A at hand is just one of all the possible ABoxes q T accommodates to. Because of that, some sub-queries in q T may be useless when evaluating q T on A: they have no answer on it, hence do not participate in producing q's answers from it. Their evaluation, which may take significant time, should thus be avoided to the extent possible; this is the goal of the new optimization we devise below.

As the names of the state-of-the-art query reformulation languages suggest, reformulations encode semantically equivalent but syntactically different algebraic combinations of sub-CQ queries: UCQ, USCQ and JUCQ. Our optimization aims at pruning rapidly away from query reformulations such sub-CQs with no answer on the queried KB's ABox. It relies on the notion of ABox summary [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF], which was proposed for fast consistency checking and instance retrieval with the SHIN DL [START_REF] Dolby | Scalable highly expressive reasoner (SHER)[END_REF] , and which we straightforwardly adapt to DL-lite R : ABox facts are restricted to instances of atomic concepts and roles, i.e., just concept and role predicates instead of SHIN formulae. A summary S of an ABox A is an ABox homomorphic to A defined by a so-called canonical function f from the constants in A to the constants in S: S = A f , where A f is obtained from A by replacing every constant c by its image f (c) through f . A central property of such a summary, which directly follows from the existence of the A-to-S homomorphism defined by the function f , is that if a CQ q has some answer on A, then its translation q f has some answer on S, where q f is obtained from q by replacing every constant c by its image f (c) through f [START_REF] El Vaigh | A well-founded graph-based summarization framework for description logics[END_REF]. The crux of our optimization is to exploit the contraposition of this property, i.e., if q f has no answer on S, then q has no answer on A. We therefore optimize a UCQ, USCQ or JUCQ reformulation by pruning away from it each of its sub-CQs with no answer on the KB's ABox summary. Finally, and crucially for our summary usage, ABox summaries can be rapidly computed and maintained upon ABox updates [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF].

Demonstration outline

For the demo 1 , we selected a set of well-established DL-lite R benchmarks, notably LUBM ∃ [START_REF] Lutz | The combined approach to OBDA: taming role hierarchies using filters[END_REF] and NPD [START_REF] Lanti | The NPD benchmark: Reality check for OBDA systems[END_REF] that are respectively based on synthetic and real data. For each, we stored ABoxes of increasing sizes, from small-tolarge, in the popular DB2 (v11.5), MySQL (v8.0.25) and PostgreSQL (v12.7) RDBMSs, on top of which we deployed the off-the-shelf Rapid (v0.93) [START_REF] Chortaras | Optimized query rewriting for OWL2QL[END_REF], Compact (v1.0b6) [START_REF] Thomazo | Compact rewritings for existential rules[END_REF] and GDL (v1.0) [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF] query reformulation tools 2 for (minimal) UCQ, USCQ and JUCQ reformulations respectively. We also developed a PHP/JSP/jQuery-based GUI (see Fig. 1 and Fig. 2) that offers a nice visual attendee experience in order to examine the performance challenges and advances in OMQA optimization. Scenario 1"Where do we stand now and how did we get there?": We answer this question by carrying out performance analyses through our GUI. For each, we select: (i) ABoxes and queries from a benchmark based on a collection of statistics (e.g., ABox and query sizes, number of answers per ABox/query pair, etc) but also on the graphical inspection of the queries, (ii) query reformulation languages, and (iii) RDBMS(s). For a given analysis, query answering times are reported by RDBMSs, then by ABoxes, then by queries; they are displayed using stacked bar charts to show, in each case, the time spent in reformulating the query w.r.t. the time spent in evaluating the query reformulation (Fig. 1). Further, query reformulations can be graphically inspected to understand the challenges raised by their evaluation through RDBMSs. Based on such analysis, we first show that the UCQ and USCQ reformulation approaches are not robust OMQA solutions because the single reformulation they explore for a given query may lead to poor performance or just fail in being evaluated on moderateto-large ABoxes, on all RDBMSs. We also point out that the performance of the JUCQ reformulation approach strongly depends on the quality of the cost model used to select the reformulation to send to the RDBMS. Because of that, though in principle the JUCQ reformulation approach should be competitive w.r.t. UCQ and USCQ reformulation ones, this is not always the case. Scenario 2"What's next?": We answer this question by advertising the potential of our summarybased optimization for further significant improvement of OMQA performance (up to several order of magnitude) for the UCQ, USCQ and JUCQ reformulation approaches. When enabled, (i) statistics are also reported for ABox summaries (size and compression ratio, time to be computed, and average update time upon update) when setting up a performance analysis and (ii) stacked bar chars also display for every optimized re-formulation the time spent in pruning its empty sub-CQs based on the ABox summary (Fig. 1). Further, to understand the performance gain, the graphical inspection of an optimized UCQ, USCQ or JUCQ query reformulation also highlights its empty sub-CQs on the ABox, and which of them are pruned out based on the summary.

Fig. 1 .

 1 Fig. 1. Performance analysis

Fig. 2 .

 2 Fig. 2. UCQ reformulation inspection

  Query reformulation time is typically negligible w.r.t. reformation evaluation time, thus the particular choice of tools we made does not affect our conclusions.

	1 A	one-minute	teaser	video	of	our	demo	is	available	at:
	http://people.irisa.fr/Francois.Goasdoue/ISWC21/demo-iswc21-teaser.mp4
	2

Acknowledgements

This work was partially supported by the ANR project CQFD (ANR-18-CE23-0003) and the ARED project Gedeon (Région Bretagne & Lannion Trégor Communauté).