In the ontology-based data access paradigm, ontologies act as an interface to data sources, facilitating query formulation by providing a vocabulary closer to the users' understanding. However, accessing data in large and unfamiliar sources can still be hard. In practice, users may find that the formulated queries have too many answers to be informative, or at the other extreme, they have very few or no answers at all. Refining queries can be difficult for users who may not know how to formulate their information needs according to the data. Moreover, changes in the query may have no effect on the answers, or dramatically affect them in unexpected ways. Manual exploration via iterative query evaluation can be computationally very costly if each minor query variation is evaluated independently and from scratch. Towards addressing this problem, we propose a framework for exploring datasets using ontology-mediated queries (OMQs). Rather than formulating a precise conjunctive query (CQ), the user writes a template CQ where parts may be marked to indicate that they may be relaxed or constrained during the exploration. From such a template we build what we call a query space: a set of OMQs that are ordered according to their specificity (or generality). The OMQs in the space are obtained from the template using a fixed set of reformulation rules that modify CQs to be more general or more specific w.r.t. O and a given dataset A. Navigating the query space from one query to a more general (or specific one) allows then users to explore the dataset. The reformulation rules were proposed in our previous work [1], but here their application is restricted by the template and yields a finite space of queries that enables data exploration by choosing among the automatically generated reformulations those which modify the answers in a minimal way. Our framework can be realized in Datalog. We describe how a query space can be generated using Datalog rules. The Datalog program is evaluated over the data and produces a structure (i.e., compilation) that contains all OMQs in the space and their answers, and which can be used to navigate between
reformulations and compute answers to individual queries on-the-fly. As a
proofof-concept, we implement the approach and test its potential for exploring data
in DBpedia, using the VLog Datalog reasoner [
extensions of DL-LiteR [
respectively concept, role, and individual names. Further, we assume the set of role names is the union of two disjoint sets of simple and non-simple role names. A DL-LiteH;R TBox T is a finite set of axioms taking the following forms: A v A0;
A v 9p; 9p v A
A v 9p:A0 p v s; p v s r s v p; where A; A0 2 C and p; r; s 2 R, and such that: (i) for every r s v p 2 T , s is simple and p is non-simple; (ii) if p v s 2 T or p v s 2 T , and s is a simple role, then p is also simple. Axioms of the form r s v p are called complex role inclusions (CRI). A DL-LiterHecR-safe TBox is a DL-LiteH;R TBox where all the
form B v 9s. A DL-LiteR TBox is a DL-LiteH;R TBox without CRIs. We use
A(a), and p(a; b), with a; b 2 I, A 2 C, and p 2 R.
I = ( I ; I ) consists of a nonempty domain I , and interpretation function I ; I is a model of O (I j= O), if I satisfies every axiom in O. An interpretation
p(a; b) 2 A. Given a DL ontology O and an ABox A, we denote by IO;A the
canonical model of (O; A), which models (O; A) and can be homomorphically
maped to any other model of (O; A). For DL-LiteR ontologies, if (O; A) has a
model, then it has a canonical model [
Ontology-mediated Querying. A conjunctive query q is a first order formula with free variables x that takes the form 9y:'(x; y), with ' a conjunction of atoms of the form A(x), r(x; y), and x = a, where A 2 C, r 2 R, x; y variables from x [ y and a is an individual. A term is either an individual from I or a variable. The free variables in a query are called the answer variables. We will write q(x) to make explicit reference to the answer variables of q, and '(x; y) to denote the set of atoms in q. The arity of q(x) is defined as the length of x, denoted jxj.
1 Implementation, evaluation and proofs at https://github.com/medinaandresel/DL2020 in q, and (iv) (t) = (t0) for each t = t0 in q. We use ans(q; I) to denote the set of all answers to q in I.
An ontology mediated query (OMQ) is a pair (q(x); O) with O an ontology and q(x) a CQ. Given A, a tuple of individuals a from A with jaj = jxj is a certain answer of (q(x); O) over A if a 2 ans(q; I) for each model I of O satisfying A, and we use ans(q; O; A) to denote all such tuples. The OMQ answering problem is: Given (O; q(x)), a dataset A, and a a tuple of individuals of length equal to jxj, is a a certain answers of (q(x); O) over A. For (q1; O) and (q2; O) of the same arity, we write q1 O;A q2 if ans(q1; O; A) ans(q2; O; A). In this case, we say that q1 is a specialization of q2 w.r.t. O; A and, conversely, q2 a generalization of q1 w.r.t. (O; A). 3
Definition 1. An exploratory query space for a given ABox A is a preordered set Q = hQ; i of queries mediated by an ontology O, such that (q1; O) (q2; O) implies q1 (O;A) q2. We will write q1 q2, whenever O is clear from the context.
ploratory query spaces. Syntactically, they are CQs whose atoms may be marked if we want to consider more specialized( s) or generalized( g) versions of them. Definition 2 (Query Templates). A query template 9y: 1 ^ ^ n, where each i is an atom of the form: [x] is an expression
A(x) j r(x; y) j x = a j As(x) j Ag(x) j rs(x; y) j rg(x; y) j x = as j x = ag; where x; y 2 x [ y, x are the answer variables, A 2 C or >, r 2 R and a 2 I.
[x] =9z Events(x) ^ hasLocg(x; z) ^ z = Rhodesg:
Given some as starting point, we will use reformulation rules to build a set of
related CQs. To guarantee that these queries can be ordered according to their
specificity (or generality), these rules will be guided by a set of reformulation
axioms. In general, O can be used to guide the rules application. However, to
take also the data into account, we allow other sets R of reformulation axioms
as well. For example, R can be a subset of O that the user considers relevant. It
may contain assertions from A, or other axioms implied by O and A, enabling
data-driven query reformulations in the style of [
R (R7) If A(a) 2 R (R8) If r(a; b) 2 R (R9) If fs(a; b); r s v rg then: 0 ^ As(x) s 0 ^ Bs(x) then: 0 ^ rs(x; y~) s 0 ^ As(x) then: 0 ^ As(x) s 0 ^ rs(x; _) then: 0 ^ ps(x; y) s 0 ^ rs(x; y) then: 0 ^ ps(x; y) s 0 ^ ss(y; x) 0 ^ rx(x; y^) ^ As(y^) s 0 ^ rx(x; y^) ^ Bg(y^) g then: then: then: then: 0 ^ As(x) s
0 ^ x = as 0 ^ rs(x; y~) s 0 ^ x = as 0 ^ rs(x~; y) s 0 ^ y = bs 0 ^ Bg(x) g 0 ^ Ag(x) g 0 ^ rg(x; y~) g 0 ^ rg(x; y) g 0 ^ sg(x; y) g 0 ^ Ag(x) 0 ^ rg(x; _) 0 ^ Ag(x) 0 ^ pg(x; y) 0 ^ pg(y; x) 0 ^ rx(x; y) ^ Bs(y) 0 ^ rx(x; y) ^ Ag(y) 0 ^ x = ag g 0 ^ Ag(x) 0 ^ x = ag g 0 ^ x = bg g 0 ^ rg(x; _) 0 ^ rg(_; x)
0 ^ rs(x; y^) ^ y^ = b s 0 ^ rs(x; y) ^ y = as 0 ^ rg(x; y^) ^ y^ = ag g 0 ^ rg(x; y) ^ y = bg
.
Definition 3. A reformulation axiom is either an ABox assertion or a TBox axiom in DL-LiterHecR-safe. Given a template and a set of reformulation axioms R, we say that 0 is derivable from using R if there is a sequence of reformulations 1 : : : n = 0, with n 1 and 2 fs; gg, using the rules in Table 1. We will use R 0, to indicate that 0 is derivable from w.r.t. R, and we will write cq( ) to denote the CQ obtained from by removing all the s and g labels. Then we define: – QR is the set of all CQs fq(x) j [x] R 0[x]; cq( 0[x]) = q(x)g. – For each pair q1; q2 2 QR, we set q1 R q2 if q1 = q2, or there are templates 1 and 2 such that cq( i) = qi and either 2 sR 1, or 1 gR 2.
Note that, following [
Rules in Table 1 specialize As(x) as either B(x) using (R1) or r(x; _) using (R3), which are more specific than A, or as A(a), with a a known instance of concept A using (R7). Atoms ps(x; y) are specialized as r(x; y) with r a role more specific than r using (R4) or (R5), or B(x) (or B(y)), with B a concept that is more specific than 9r (or 9r ) with rule (R2). The rules work similary for the generalizing counterparts.
of reformulation axioms: R1 = fhasLoc partOf v hasLoc; partOf(Rhodes; Greece)g:
and R1 (since z is not an answer variable): Events(x) ^ hasLocg(x; z) ^ z = Rhodesg g Events(x) ^ hasLocg(x; z) ^ z = Greeceg
q1(x) : 9z Event(x) ^ hasLoc(x; z) ^ z = Greece: Thus, cq( ) R1 q1. The semantics of change if we consider, for example, the set of reformulation axioms R2 = fConference v Eventg. Using rule (R1) we can capture the query q2(x) : 9z Conference(x) ^ hasLoc(x; z) ^ z = Rhodes:
we call a set R of reformulation axioms compatible with (O, A) if IO;A R.
Lemma 1. Let be a template, R a set of reformulation axioms, and O an ontology in a language that enjoys the canonical model. If A is such that R is compatible with (O; A), then hQR; Ri is exploratory for A.
Example 3. Let O = fWorkshop v Conference, Conference v Eventg and A = fWorkshop(DL2020); hasLoc(DL2020; Rhodes); hasLoc(DL2020; Greece); partOf(Rhodes; Greece)g: fhasLoc partOf v hasLocg is compatible with (O; A) and the rest of R1 and R2 are in (O; A), so both (QR1 ; R1 ) and (QR2 ; R2 ) are exploratory for (O; A).
DL-LiterHecR-safe, such test can be done in PTime [
Exploring Query Spaces
ing from one query to a more general (or specific one) on demand. However, obtaining all reformulations may not be satisfactory if there are too many of them, and we may need to identify the most relevant ones. For example, assuming that a dataset contains in addition to the assertions in Example 3: Conference(KR2020), hasLoc(KR2020; Rhodes), a natural way to filter out the answers to q(x): Event(x) ^ hasLoc(x; z) ^ z = Rhodes is to navigate to qn(x) : Conference(x) ^ hasLoc(x; z) ^ z = Rhodes. This reformulation however does not change the set of answers – fKR2020; DL2020g, and it may be more interesting to directly specialize to qs(x) : Workshop ^ hasLoc(x; z) ^ z = Rhodes, which drops KR2020 as answer. By identifying such queries in the space, the data can be explored in a more effective step-by-step fashion.
Definition 4. For queries q1 6= q2 in Q = (Q; ) such that q1 q2, we say
that q1 is a neutral specialization of q2, written q1 ' q2, if ans(q1; O; A) =
ans(q2; O; A); it is a strict specialization of q2, written q1 q2, if ans(q1; O; A) (
ans(q2; O; A). Conversely, q2 is a neutral, respectively strict, generalization of
q1. Further,
– If q1 ' q2, we say that q1 is a maximal neutral specialization of q2 if for each
q0 2 Q such that q0 q1, it holds that q0 q2. Conversely, q2 is a maximal
neutral generalization of q1 if for each q0 2 Q such that q2 q0, we have
q1 q0.
– q1 is a minimal strict specialization of q2, if q1 q2 and for each q0 2 Q
such that q1 q0 q2 we have q0 ' q2. Conversely, q2 is a minimal strict
generalization of q1 if for each q0 2 Q such that q1 q0 q2 we have q1 ' q0.
We denote by maxNeusA(q; Q) and minStrAs(q; Q) the set of all maximal neutral
and of all minimal strict specializations, respectively, and similarly for
generalizations. Maximal neutral reformulations are useful, since they allow us to easily
identify the minimal strict reformulations desirable for navigating the space.
Observation 1 Let Q = hQ; i be an exploratory query space for A mediated
by O, and let c extend so that q1 c q2 whenever q1 ' q2. For q 2 Q, we
have:
– q1 2 minStrAs(q; Q) iff q1 6 c q, and q1 c q2 for some q2 2 maxNeusA(q; Q).
– q1 2 minStrAg(q; Q) iff q1 6 c q, and q2 c q1 for some q2 2 maxNeugA(q; Q).
Not surprisingly, identifying minimal strict reformulations is not feasible in
polynomial time in general. It is at least as hard as the following following decision
problem: given q and q0 in Q, verify if q0 is a maximal neutral specialization (or
generalization) of q in Q. Specifically, coNP-hardness for maximal neutral
specializations can be proved even for monadic tree-shaped CQs mediated by the
empty ontology, by reducing the problem of verifying if a given E L concept is the
most specific concept for individuals a1; : : : ; an, given ABox A [
grams with stratified negation [
Datalog with Equality and Stratified Negation. Let P, V and K be countable infinite sets of predicates, variables and constants. Variables and constants are terms. An atom is either (i) p(v) with v a tuple of terms of the same arity as p, or (ii) v = v0 for terms v; v0. A Datalog rule has the form: p(v)
1; : : : ; k; : k+1; : : : ; : m where m k, p(v) is called the head of and denoted by head ( ), while the set of atoms f 1; : : : ; mg is the body of ; body+( ) denotes the positive atoms and body ( ) the negative ones. As usual, all variables in head( ) and in body ( ) must also occur in body+( ). A rule with empty body is called fact and maybe written p(v):
partitioned as 1; : : : ; n such that for each p, all rules with p in the head are in the same partition i, and for all atoms in the bodies of those rules, the definitions of such predicates are in some j , with j i if the atom is positive, or j < i for negative atoms.
A set of facts I satisfies a rule if there exists a mapping h : vars( ) 7! term(I) such that whenever h(body+( )) I and h(body ( )) 6 I, then h (head ( )) I. A model of is any set of facts that satisfies each 2 . For a stratified program and finite set of facts D, (D) denotes the minimal model of (which is unique and always exists) consisting of Sin=0 Ii, where I0 = D and for 1 i n, each Ii minimally extends Ii 1 such that Ii is a model of i. 4.1
Datalog Encoding of Template-generated Query Spaces
a space. In this section we fix a template = 9y: 1 ^ ^ n with answer variables x = (x1; : : : ; x`), as well as a set of reformulation axioms R. Further, we assume that all non-answer variables occuring only once in have been substituted by ‘_’, and for convenience, assume x [ y V (these are the only Datalog variables written in lower-case). Since we denote concepts, roles and individuals by constants, we assume for simplicity C [ R [ I K. We also assume a constant vx 2 K for every variable x and a constant c for each atom in . A special constant null acts as placeholder for ‘_’ and as a ‘filler’ for irrelevant predicate positions. For each atom i, we use xi to denote (x; null) if i is either P x(x), P x(x; _) or x = ax; (null; x) if i = P x(_; x); and (x; y) if i = P x(x; y). By convention, U = (U1; : : : ; Un) and V = (V1; : : : ; Vn) are n-ary tuples of variables, and X is an `-ary tuple of variables.
(7!) to a fact in D , and axioms in R to facts in DR. A fixed program rules simulates the reformulation rules from Table 1. These rules derive a atms atom for each reformulation of a specializing atom, and a atmg atom for each reformulation of a generalizing atom in . The final group of rules Q build up the set of
tr(q) the translation of a given CQ q(x) into the signature of our Datalog program, obtained by applying to each atom in q the function tr with tr(x = a) = uAtm(a; t(x)), tr(A(x)) = uAtm(A; t(x)), and tr(r(x; y)) = bAtm(r; t(x); t(y)), where for each xi, t(xi) = null if x = _ and t(xi) = Xi otherwise. Definition 5. We let = rules [ Q and D ;R = D pair h ; D ;Ri the Datalog encoding of ( ; R). [ DR, and call the
atmg(V ; U; X; Y ): strs(U[Ui 7! V ]; c i; V 0) refAx(V; V 0); refAt(c i; V; X; Y ); refAt(c i; V 0; X0; Y 0);
query (U[Ui 7! V ]; X); : query (U[Ui 7! V 0]; X): strg(U[Ui 7! V 0]; c i; V ) refAx(V; V 0); refAt(c i; V; X; Y ); refAt(c i; V 0; X0; Y 0);
query (U[Ui 7! V ]; X); : query (U[Ui 7! V 0]; X): nrts(U[Ui 7! V ]; c i; V 0) refAx(V; V 0); refAtms(U[Ui 7! V ]); : strs(U[Ui 7! V ]; c i; V 0): ntrg(U[Ui 7! V ]; c i; V 0) refAx(V 0; V ); refAtms(U[Ui 7! V ]); : strg(U[Ui 7! V ]; c i; V 0):
nrtx(U[Ui 7! V ]; c i; V 00) nrtx(U[Ui 7! V ]; c i; V 0); nrtx(U[Ui 7! V 0]; c i; V 00): maxNtrx(U[Ui 7! V ]; c i; V 0) nrtx(U; c i; V 0); : nrtx(U; c i[Ui 7! V ]; V 00); V 0 6= V 00: maxx(U; V ) refAtms(U); maxNtrx(U1; c 1; V1); : : : ; maxNtrx(Un; c n; Vn):
with x 2 s; g mins(U; V1; : : : ; Vi 1; V 0; Vi+1; : : : ; Vn) maxs(U; V ); strict(U; c i; Vi; V 0): ming(U; V1; : : : ; Vi 1; V 0; Vi+1; : : : ; Vn) maxg(U; V ); strict(U; c i; V 0; Vi):
Table 3. Datalog program to compute query reformulations Let c = (c1; : : : ; cn) be a tuple of constants from C [ R [ I. The unfolding of for c is the rule obtained from
query (c; x) refAtms(c); qAtm 1 (c1; x1); : : : ; qAtm n (cn; xn) by choosing some 2 Q for each qAtm i (ci; xi), and a substitution such that – head( ) = qAtm i (ci; xi), and – each atom conc(ci), role(ci) and const(ci) is contained in D ;R and then: (i) replacing qAtm i (ci; xi) with body( ) , and (ii) removing each atom from body(query (c; x)) that is contained in (D ;R). If the body of the unfolding for c is tr(q) for some CQ q, we call c the -encoding of q. Example 4. Let c = (Conference; hasLoc; Rhodes). The unfolding of query (c; x) uAtm(Conference; x); bAtm(hasLoc; x; z); z = Rhodes: The body matches tr(q2), so c is a -encoding for q2. for c is
Lemma 2. A CQ q is derivable from of q.
w.r.t R. Conversely, for each using R iff there exists a -encoding 4.2
Evaluation of the Datalog Translation for DL-LiteR OMQs
We now fix an ABox A and a DL-LiteR ontology O, and consider the evaluation
of the queries (q; O) in QR over A. The relevant q are encoded in h ; D ;Ri,
but we still need an OMQ answering algorithm for the DL of O. In the case
of DL-LiteR, one could call an external query rewriting engine for the encoded
queries. However, we chose to partially complete the data w.r.t. O, and then
evaluate the Datalog encoding over the extended dataset.2
2 Such a procedure is very easy to realize if an existential rule engine [
We say that a CQ template is rooted if each variable is either an answer variable or occurs in a join sequence of the form r1(x0; x1); : : : ; rk(xk 1; xk), where x1 is an answer variable and for 1 < i k, xi occurs existentially in . We define the join length of a CQ template as the length of its longest join sequence, and let k be the join length of . In the following, B denotes either a concept name or 9r. Then, we apply the following procedure:
AO;k of A w.r.t. O constructed by taking for each A 2 and each r 2 : If T B v A and A j= B(a), then A(a) 2 AO;k.
If T B v 9r1 v : : : v 9rn, T 9rn v A and A B(a), then A(ar1:::rn ) 2 AO;k, where ar1:::rn is a fresh individual not in A and n k.
If T s v r (with s possibly inverse) and A s(a; b), then r(a; b) 2 AO;k.
If T B v 9r1 v : : : v 9rn v 9r and A B(a) then r(ar1:::rn ; ar1:::rnr) 2 AO;k, where k n 0 and ar1:::rn and ar1:::rnr are fresh individuals. 2. Lastly, we translate AO;k into the signature of , similarly as before. For that, we assume that each individual in AO;k is a constant in K. We define DA = tr(AO;k), where tr translates each assertion in AO;k as above.
Lemma 3. Let (q; O) be a rooted DL-LiteR OMQ over the signature ans(q; O; A) = ans(q; ;; AO;k). . Then,
be rooted. Let q 2 QR, and let cq be the -encoding of q.
Theorem 1. Let Then a 2 ans(q; O; A) iff query (cq; a) 2 (D ;R [ DA) 4.3
Datalog Program to Compute Query Reformulations Finally, we also define a set ref of Datalog rules that compute the minimal strict reformulations of each query in the space, which are the most relevant for exploration. The program ref is presented in Table 3. In a nutshell, it derives atoms ming(cq; cq0 ) for tuples of -encodings of queries q; q0 such that q0 2 minStrg (q; Q), and analogously for the specializations. For this, it relies on finding pairAs cq and cq0 of -encodings that are the result of applying one reformulation axiom such that query (cq; a) and :query (cq0 ; a). Using pairs of strict reformulations and stratified negation, we can identify the reformuations that are neutral, and again use negation to find the maximal neutral ones.
Relying on Observation 1, it is not hard to prove that ref computes the relevant reformulations that we use to explore the dataset: Template i [ # atoms in i]
Size of i = (Di) (MB) # Queries in QRi with answers Sum of answers over all queries
s( i) / g( i)
Computation of i(Di) (s) Avg. retrieval of answers q 2 QRi (ms) Avg. retrieval q0 2 minStrG=S(q) (ms) ((ba)) qq00 22 mmianxSNtreAxuxA(q(;qQ;Q))iffiffmminaxx(cx(qc;qc;qc0)q02) 2
Theorem 2. Let Q = (QR; R) and let Dall = D ;R [ DA. For q; q0 2 Q, let cq be -encoding of q and cq0 the -encoding of q0. Then, for x 2 fs; gg: 5
a translator of the template and rules of the encoding into Rulewerk syntax. All experiments have been performed on a MacBook Pro (2.7 GHz i5 8GB) using JavaSE 14.0.1 and Rulewerk version 0.5.03. We used the DBpedia ontology and dataset, accessed via the endpoint4. We used one set R of reformulation axioms with 336 axioms and assertions extracted from DBpedia. With its signature and the DBpedia ontology, we computed the k-bounded -extension DA using existential rules in VLog. The resulting dataset was computed relatively fast, given that the data was remotely accessed, and it took in total about 3 minutes to materialize. The size of the extended dataset is around 700 MB. We have designed templates of various sizes and shapes over the ontology vocabulary containing classes such as: Events, Museums, ArtWorks, Organizations etc., properties startDateg; museums, hasLocations, headquarterg etc., and resources e.g., Parisg. The main goals of our evaluation were (a) to test the feasibility of our framework in practice, in particular the tradeoff between the time to evaluate the
the pre-computed model, and (b) to test if the template-generated query spaces ensure a gradual navigation of the answers. For each input i we have measured: jQRi j - number of generated queries with answers, total number of answers captured by the query space, and as well as the computational time: to evaluate the
3 https://github.com/knowsys/rulewerk 4 SPARQL endpoint: https://dbpedia.org/sparql measure s(q) – the average number of answers that are droped by minStrAs(q), respectively g(q) the average number of answers that minStrAg(q) ensures. Then, for the entire query space, s( i) = (Pq2Q i s(q))=jQ i j measures the average discarded answers when navigating the query space and similarly for g( i). Table 4 summarizes our evaluation. Evaluating the Datalog program over the materialized data is done within seconds for all the query spaces and depends on the number of answers captured by the query space (i.e., the larger the number of answers the longer it took to compile). Reading the answers to queries and navigating the query space is done in less than 1 ms in all cases. The selectivity and inclusivity of the minimal strict reformulations leads to a reasonably gradual exploration of the data, relative to the number of answers captured by each space. 6
In recent years, several exploratory search engines have been proposed to
support data access for different exploratory purposes. The basic idea at the core
of many of them is to guide the query formulation process, in a step-by-step
fashion. The many proposed techniques for exploring ontology-mediated data
include similarity-based methods such as [
Query generalizations have been proposed as a technique for interpreting
null answers (i.e., empty answers) in cooperative database systems [
proach seems feasible in practice, however an extended evaluation is part of future work. It would also be interesting to exploit the compilation for analytical purposes and to extend the reformulation rules to relate queries that have a different structure.