We make a step towards the interactive exploration of data in the ontology-mediated setting, presenting a technique to construct an ofline compilation that allows us to answer eficiently diferent related queries in online phase, without the need to access again the original data. We also propose algorithms to construct relevant variations of a given query that, for example, reduce or increase the number of answers, while modifying the query in a minimal way, or make explicit the common properties of all objects that are in the answers to a given query.
structure such that, without accessing the data again, we can eficiently get the answers to any query that asks for objects of the desired type, with diferent combinations of properties. We also use this compilation to obtain (minimal) modifications of a query that retrieve strictly more or strictly less answers, as well as to obtain the most specialized query that retrieves exactly the same answers but makes explicit all their shared properties. A prototype implementation of our algorithms shows promising results, pointing to adequate functionality to support users in their attempts to understand datasets in the presence of ontologies. 2
set of roles is NR = NR ∪ {P − | P ∈ NR}, and R− denotes the inverse of the role R. Basic concepts are concept names A, and expressions of the form ∃R with R a role. A TBox is a set of axioms of the forms R1 ⊑ R2, R1 ⊑ ¬R2, C1 ⊑ C2, and C1 ⊑ ¬C2, where R1, R2 are roles and the C1, C2 basic concepts. An ABox is a finite set of assertions of the form A(b), ¬A(b) and P (b, c), ¬P (b, c), where A ∈ NC , P ∈ NR and b, c ∈ NI . We denote by Ind(A) the set of individuals appearing in A. A knowledge base (KB) has the form K = ⟨A, T ⟩ for A an ABox and T a TBox. The semantics of DL KBs is defined in terms of interpretations I = (∆ I , ·I ) with ∆ I the domain and ·I the usual interpretation function. We use the usual definitions and notations for satisfaction of axioms, assertions, TBoxes and ABoxes, models of a KB, and entailment.
We also recall the syntax and semantics of conjunctive queries (CQs) over
DL KBs. A CQ has the form q(x) :- ∃y.ϕ, where ϕ is a conjunction of atoms
of the form A(t) and R(t, t′), where each term t, t′ is either an individual or a
variable from x ∪ y. The variables in x are called answer variables, and term(q)
denotes the set of terms occurring in q. Given a CQ q and an interpretation I,
we call a partial match any function π mapping terms of q to objects in ∆ I , and
we write I π A(t) for a concept atom A(t) if π(t) ∈ AI , and I π R(t1, t2) for
role atom R(t1, t2) ∈ q if (π(t1), π(t2)) ∈ RI . A match for q in I is a partial
match with domain term(q) such that I π α for every atom α in q. A tuple of
individuals t is a certain answer to q(x) over KB K if for each I model of K
there exists a match π for q in I s.t. (t)I = π(x). We use cert(q, K) to denote
the set of certain answers of q over K. It is well known that if a DL-LiteR KB
K = ⟨T , A⟩ is consistent, it possesses a canonical model IT ,A such that for any
CQ q(x), cert(q, K) = {t | IT ,A π q, π(x) = t} [
AIT ,A = {a | T , A
A(a)} ∪ {aR1 . . . Rn | n ≥ 1, ∃Rn− ⊑T A} P IT ,A ={(a, b) | R(a, b) ∈ A and R ⊑T P } ∪ {(b, a) | R(a, b) ∈ A and R ⊑T P −} ∪ {(w1, w2) | w2 = w1S, S ⊑T P } ∪ {(w2, w1) | w2 = w1S, S ⊑T P −} We can rely on IT ,A for query answering, since we can assume that KB consistency has been tested in advance, and queries trivialize over inconsistent KBs. 3
In this paper we only consider CQs of a restricted form, which we call 1treeCQs. A 1treeCQs is tree-shaped (i.e., its primal graph is a tree), and has exactly one answer variable, which is its root. We denote this variable x. We use a special subquery relation between 1treeCQs: Definition 1 (Subquery). Given a DL-LiteR TBox T and two 1treeCQs q1 and q2, we call q1 subquery of q2 (w.r.t. T ), written q1 FT q2, if term(q1) ⊆ term(q2) and (i) for each atom R1(t1, t2) ∈ q1 there exists R2(t1, t2) or R2−(t2, t1) ∈ q2 such that R2 ⊑T R1; and (ii) for each atom C1(t) ∈ q1 there exists C2(t) ∈ q2 such that C2 ⊑T C1. In this case, we also call q2 a superquery of q1 (w.r.t. T ).
The following claim is straightforward: Proposition 1. Let K be a DL-LiteR KB. For any two given 1treeCQs q1, q2 such that q1 FT q2, we have that cert(q2, K) ⊆ cert(q1, K). 3.1
Compiling the Answers of Related Queries For a given DL-LiteR KB K := ⟨T , A⟩, let qL, qU be two 1treeCQs such that qL FT qU holds. We call them the lower bound query and the the upper bound query, respectively. Any 1treeCQ q such that qL FT q FT qU is called in-between query. We use the term 1treeCQs family to refer to the set of 1treeCQs containing a pair of qL and qU, together with all the in-between queries. Intuitively, the lower bound is a general query that retrieves all objects the user could be interested in, while the upper bound is a query (which may have no answers) that gathers properties that those objects could potentially have; the family of 1treeCQs contains queries that ask for combinations of those objects.
Example 1. Our examples are based on the well-known LUBM ontology and
describe the domain of universities [
In what follows, we assume a given pair of qL and qU, and a KB K = ⟨T , A⟩. The goal of this section is to build a structure that stores all information needed for answering any query in the 1treeCQ family, without having to look up A.
To this aim, we introduce the notion of matching witness. Intuitively, it stores all objects in the canonical model that may be relevant to a match of an in-between query. We start from the answers to qL (since any answer to an inbetween query must also be an answer to qL), and from there, we consider partial matches for pairs of terms t1, t2 that occur together in an atom R(t1, t2) ∈ qU. For each object in the range of a partial match, we store some labels that store the concept and roles the object satisfies that may be relevant to the matches.
We introduce some notation. For a ∈ ∆ IT ,A , MSconc(a, K) denotes the set of most specialized concepts satisfied by a in IT ,A, containing each concept name A such that IT ,A A(a) and there is no A′ ̸= A with A′ ⊑T A and IT ,A A′(a). Similarly, for a pair a, b ∈ ∆ IT ,A , the set of all most specialized roles satisfied by (a, b) in IT ,A is denoted MSrole(a, b, K) and contains each role R such that IT ,A R(a, b) and there is no R′ ̸= R with R′ ⊑T R and IT ,A R′(a, b). Given a partial match π := [t1 7→ o1, t2 7→ o2], a role label R is relevant w.r.t. π if there exists R′(t1, t2) ∈ qU with R ⊑T R′ or R′ ⊑T R. Similarly, a concept label C is relevant (w.r.t π) if there exists C′(t2) ∈ qU with C ⊑T C′ or C′ ⊑T C. For each pair t1, t2 of query terms that occur together in some atom R(t1, t2) ∈ qU, and each o1 ∈ ∆ IT ,A , we define a set of matching candidates that contains each o2 such that if o1 is a match for t1 in IT ,A, then o2 may be a match for t2. Definition 2 (Matching candidates). Let {t1, t2} ⊆ term(qU) be such that there is some R(t1, t2) in qU, and let o1 ∈ Ind(A) ∪ AnonObj. The set of matching candidates for t2 relative to t1 7→ o1, denoted MCt17→o1 (t2), is: I. if t2 ∈ Ind(A), then 1. if there is some R ∈ MSrole(o1, t2, K) that is relevant w.r.t. [t1 7→ o1, t2 7→ t2], then MCt17→o1 (t2) := {t2}, 2. otherwise, MCt17→o1 (t2) := ∅.
II. if t2 ∈ vars(qU), then 1. if o1 ∈ Ind(A), then MCt17→o1 (t2) := candA ∪ cando1R where: candA ={o2 | T , A cando1R ={o1R | T , A
R(o1, o2), R′ ⊑T R, R′(t1, t2) ∈ qU}
∃R(o1), R is relevant w.r.t [t1 7→ o1, t2 7→ o1R]} 2. if o1 := wR ∈ AnonObj, then MCt17→o1 (t2) := candwRS ∪ candw where: candwRS ={wRS | T
∃R− ⊑ ∃S, S relevant w.r.t [t1 7→ wR, t2 7→ wRS]} candw ={w | T
R− ⊑ S, R′ ⊑T S, R′(t1, t2) ∈ qU} We also define label strings that store the concepts and roles for partial matches: Definition 3 (Label String). For a partial match π, we define labels(π) as: I. if π is of the form [t 7→ o], where t ∈ term(qU) and o ∈ Ind(A) ∪ AnonObj, then labels(π) = ⟨{C | C relevant w.r.t. π}⟩ II. if π is of the form [t1 7→ o1, t2 7→ o2] with o2 ∈ MCt17→o1 (t2), then labels(π) = ⟨Rlbl, Clbl⟩, where Clbl = {C | C ∈ MSconc(o2, K) relevant w.r.t. π}, and Rlbl is defined as follows: A. if o1, o2 ∈ Ind(A) or o1 is of the form o2R, then Rlbl = {R | R ∈ MSrole(o1, o2, K) and R is relevant w.r.t π} B. if o2 = o1R, then Rlbl = {R}
Now we are ready to build matching witnesses by iteratively constructing relevant partial matches and storing them together with their label strings: Definition 4 (Matching Witness). Let a1, . . . , an be an arbitrary enumeration of the individuals that are a certain answer to qL. We define the root matching witness as wroot = ⟨[labels(x 7→ a1)a1, . . . labels(x 7→ an)an]⟩.
For a given term t ∈ term(qU) and an object o ∈ Ind(A) ∪ AnonObj, the matching witness for t and o is defined as follows: wot = ⟨valuest1 , . . . , valuestk ⟩, where {t1, . . . , tk} = {t′ | there exists R(t, t′) ∈ qU}, and valuesti , 1 ≤ i ≤ k, is constructed as follows: if MCt7→o(ti) = {o1 . . . om}, then valuesti = [φ1o1, . . . , φmom], where φj = labels(t 7→ o, ti 7→ oj ), 1 ≤ j ≤ m.
In particular, if MCt7→o(ti) = ∅, then valuesti = [ε] (ε is the empty string). We denote by W the set obtained by starting from x and wroot, and then recursively, for each child t′ of the current term t and each object o in IT ,A that occurs in the range of a witness, adding the witness wot′ to W. 3.2
Compilation-based Query Answering
In fact, to decide whether an individual is an answer to an arbitrary in-between query, it sufices to recursively check the following satisfaction conditions. Below, for t ∈ term(q), we denote by q t the query obtained by restricting q to atoms that involve only terms that are descendants of t in q.
Definition 5 (Satisfaction). Let t ∈ term(qU) and q FT qU t. An object o ∈ Ind(A) ∪ AnonObj satisfies q (w.r.t. W) if: if t = x, then o is an answer to qL, and for each C′(x) ∈ q there exists C ∈ labels(x 7→ o) s. t. C ⊑T C′ if t is a leaf in (the tree-structure of) q, then wot = ⟨⟩ ∈ W Additionally, the following condition must hold: for each t′ child of t in q there exists o′ ∈ MCt7→o(t′) such that labels(t 7→ o, t′ 7→ o′) = ⟨Rlbl , Clbl ⟩ satisfies: for each R′(t, t′) ∈ q there exists R ∈ Rlbl such that R ⊑T R′ and for each C′(t′) ∈ q there exists C ∈ Clbl such that C ⊑T C′; and o′ satisfies q t′ (w.r.t. W).
This correctly captures the answers of any query in the 1treeCQ family: Theorem 1 (Correctness of compilation-based QA). For each in-between 1treeCQ q, we have: cert(q, K) = {a ∈ Ind(A) | a satisfies q (w.r.t.W)}.
Given a query, we identify interesting variations of it that could be relevant to a user. For example, we identify the minimal ways to modify the current query so that it provides more or less answers. We are also interested in identifying all the common properties that our set of answers has, that is, the possible additions to our query that, while making it syntactically more restrictive, would still retrieve the same set of answers. In the experiments in the next section, we will illustrate the usefulness of these query modifications on several examples.
Algorithm 1.1: neutralSpecialization
Input: W the set of matching witnesses, q in-between query
Output: Q the set of neutral specializations of q 1 S := {}; 2 foreach a ∈ ans(q, W) do 3 S := S ∪ {q | q x-maximal for a}; 4 Q := ∅;
/* compute intersection of each tuple in the n-fold Cartesian product over S */ 5 intersect(S,Q,q,∅,0); 6 return Q; Algorithm 1.2: intersect
Input: S = {Q1, . . . , Qn} set of sets of queries, Qneutral collects the neutral specializations, q in-between query, qinter intersection query, k the index of current set in S 1 if k == n then 2 Qneutral := Qneutral ∪ {qinter} ; 3 else 4 foreach query q′ ∈ Qk do 5 if q FT q′ then 6 if qinter == ∅ then 7 qinter := q′; 8 else 9 qinter := qinter ∩T q′ ; 10 intersect(S,Qneutral,q,qinter,k + 1)
Algorithm 1.3: strictSpecialization
Input: W the set of matching witnesses, q in-between query
Output: Q set of strict specializations of q 1 Q := ∅ ; 2 foreach a ∈ ans(q, W) do 3 foreach q1 x-maximal for a do 4 foreach q2 max. neutral spec. of q do 5 if q2 FT q1 then 6 qdiff := q1 \ q2; 7 foreach query atom A ∈ qdiff do 8 if q2 ∪ {A} is 1treeCQ then 9 Q := Q ∪ {q2 ∪ {A}} ; 10 return Q; Algorithm 1.4: minGeneralization Intuitively, the set of constructed matching witnesses contains information regarding how much of the upper-bound query we have matched in the canonical model, for each a ∈ Ind(A) - possible answer. Hence we can read from the witnesses, for each possible answer a, the set of maximal queries in the family for which a is a match. We will see that these maximal queries provide the key information to suggest the user the desired query modifications. We remark that there can be multiple such maximal queries for the same individual a.
Definition 6 (t-Maximal Query). Let q t be a 1treeCQ rooted in t, where t ∈ term(qU), s.t. q tFT qU t. A query q is said to be t-maximal for a ∈ Ind(A) ∪ AnonObj if: (a) a satisfies q t w.r.t. W, and (b) for each q′ t, q t ̸= q′ t, s.t. q t FT q′ t FT qU t, a does not satisfy q′ t w.r.t. W.
4.2
Specializations and Generalizations We use the term query specialization to refer to any superquery of a given q in a 1treeCQ family. Indeed, superqueries ‘specialize’ the query by requiring additional or more specific properties to hold. We further distinguish between two kinds of specializations: the ones that retrieve the same answers as the given q, and the ones that retrieve strictly less answers.
Definition 7 (Neutral Specialization). We call q2 a neutral specialization of q1 if q1 FT q2 and ans(q2, W) = ans(q1, W).
Trivially, any in-between 1treeCQ is a neutral specialization of itself. Definition 8 (Strict Specialization). We call q2 a strict specialization of q1 if q1 FT q2 and ans(q2, W) ( ans(q1, W), with ans(q2, W) ̸= ∅.
Conversely, any subquery of a given 1treeCQ q is less constrained than q, and retrieves at least the same answers. We are interested in those subqueries that retrieve strictly more answers, which we call query generalizations.
The first query modification problem we consider is to construct the maximal neutral specializations of a query. Intuitively, the maximal neutral specialization includes all most specialized additional constraints that we can add to the query without modifying its answers, and hence it makes explicit all the properties that are common to all the answer individuals.
Definition 9 (Maximal Neutral Specialization). A maximal neutral specialization for q w.r.t. ans(q, W) is a neutral specialization q′ such that, for each q′′ s.t. q′′ ̸= q′ and q′ FT q′′, we have ans(q′′, W) ̸= ans(q, W).
Algorithm 1.1 computes neutral specializations for a given in-between query q, by intersecting maximal queries for each a ∈ ans(q, W). Binary operation ∩T on 1treeCQs keeps only those query atoms that are subsumed in both 1treeCQs. One can show that by dropping all subqueries from the neutral specializations we obtain the maximal neutral specializations.
The second query modification problem we consider is to find the minimal strict specializations of a given query, that is, which are the minimal modifications to the query that will result in a smaller set of answers.
Definition 10 (Minimal Strict Specialization). A minimal strict specialization for q is a strict specialization q′ such that, for each q′′ with q FT q′′ FT q′, q′′ is a neutral specialization of q.
It can be the case that q cannot be strictly specialized without loosing all answers. In this case we say that q’s only strict specialization is qU. One can obtain the minimal strict specializations for a given in-between query by discarding all superqueries from the set of strict specializations, constructed by Algorithm 1.3.
Conversely a query generalization refers to any subquery of a given q in a 1treeCQ family that has strictly more answers. Finally, we consider the problem of finding the minimal generalizations of given query, that is, how to minimally relax the query to retrieve more answers.
Definition 11 (Minimal Generalization). Let q be an in-between 1treeCQ. A minimal generalization or relaxation for q is a generalization q′ such that for each q′′, that is q′ FT q′′ FT q, it holds that: ans(q′′, W) = ans(q, W)
It might be the case that an in-between 1treeCQ q cannot be generalized if ans(q, W) = ans(qL, W). Hence, whenever q is a neutral specialization of qL it doesn’t have any generalizations. Algorithm 1.4 constructs all the minimal generalizations for a given in-between query. 5
The matching witness solution is implemented in Java (jdk1.8), using additional libraries. For ontology loading we used the OWLAPI java library1. For ABox 1 http://owlapi.sourceforge.net/ lirsssseeonbwA#112,,,500000000 P 5000.5 0.5 1#Matching W1.i5tnesses 2 ·104
(b) Batch2 Figure 1: Performance of QA 1.5 Max. Neutral 1.25 MMinin..SGtreinct ] 1 [scond se 0.75 e iTm 0.5 0.25 0
Seconds
reasoning we used the Ontop [
autPub Employee
x y1 y3
Employee x
Employee
x y1 y3 we used HermiT2 for TBox reasoning, which captures more expressive DLs but is not as eficient over DL-LiteR. To boost the performance we used multi-threading for computing the matching witnesses as well as for query answering. Specifications. The entire evaluation was done on a server using 7 CPUs (each core running at 2.3GHz), 10 GB RAM, operating system Ubuntu Server amd64, java version Java SE Runtime Environment 7.
Ontology. As ontology we used LUBM [
size vary between ≈ 3.5 MB and ≈ 19 MB.
Evaluation measurements. We evaluated 3 batches of 1treeCQs families deifned by 3 pairs of bound queries that can be accessed online 4. With this simple prototype implementation, the time for constructing the compilation varies from minutes (for small-sized data sets) up to few hours (for largest data set). We hope to decrease this time dramatically in an improved version that, among others optimizations, does not rely on expensive calls to external reasoners. We measured the number of possible answers for the 1treeCQs family, the number of matching witnesses, the average time for answering an in-between query, and for each query modification, the average time per in-between query. 2 http://www.hermit-reasoner.com/ 3 http://swat.cse.lehigh.edu/projects/lubm/ 4 https://github.com/medinaAnd/MatchingWitnesses ResearchGroup ⊑T Institute
headOf ⊑T worksFor worksFor ⊑T memberOf
Faculty ⊑T Employee
Prof ⊑T Faculty
AssProf ⊑T Prof FullProf ⊑T Prof
Note that query modifications depend also on the data, not only on the ontology. E.g., for the maximal neutral specialization 5c, no axiom in the ontology states that each employee that is a head of something is also a full professor. 6
Works that aim at assisting users formulate queries include Quelo [
In this paper we contributed to the theoretical foundations for compilationbased query answering and construction of useful query modifications in support of data exploration. Our prototype shows overall good performance, however implementation can be further improved. Many questions remain open for future work. A natural next step is to explore how one can extend the solution to other DLs. It seems that this can be done at least for Horn-DLs, since a canonical model can be constructed. Another interesting but challenging question is how to extend the solution in such way that it considers queries that are not tree-shaped. This would be indeed very valuable, and we believe it may be possible.