Earlier work has considered how concepts can replace individual names as referring expressions in both instance retrieval and in more general query answering over knowledge bases with an underlying description logic. This earlier work, however, relied on this logic being able to express functionality, and also relied on syntactic typing restrictions on referring expressions to ensure that the number of query answers was nite. Here, we introduce a variety of referring expression concepts that extend query answering with respect to Horn-ALC and EL?, description logics that are not able to express functionality, and techniques necessary to nitely describe all entailed answers to queries expressed in terms of such concepts.
Usually, individual names occurring in a knowledge base K expressed in terms
of an underlying DL serve the role of referring expressions in query answering.
However, earlier work has considered how concepts in the DL can replace
individual names as referring expressions in instance retrieval [
In this paper, we introduce a variety of referring expression concepts that extend query answering with respect to Horn-ALC and E L?, description logics that are not able to express functionality, and techniques necessary to nitely describe all entailed answers to queries expressed in terms of such concepts. Fundamentally, this involves weakening the strong notion of singularity, requiring instead, that the denotation of a referring concept is a singleton set for some tree interpretation of K. Also, our preliminary focus on Horn-ALC and E L? enables a more transparent development since a knowledge base over these dialects will have a unique tree interpretation.
The remainder of the paper is organized as follows: Section 2 gives the necessary general de nitions, Section 3 studies the problem of instance retrieval in Horn-ALC and E L?, and Section 3.3 discusses a nite representation of sets of answers. The development for instance retrieval is then extended, in Section 4.2, to conjunctive queries. Section 5 summarizes and outlines directions for further research. 2
We begin by de ning a space of concept descriptions for the function free DL dialects that will concern us, including the concept descriptions that replace individual names in the role of referring expressions in query answering:
Let R, PC and IN be disjoint sets of role names, primitive concept names and individual names respectively. Derived concept descriptions and their semantics are de ned as follows:
C ::= A j C1 u C2 j ? j 8R:C j 9R:C j 9R :C j fag
AI 4 (primitive concept; A 2 PC)
C1I \ C2I (conjunction)
fg (bottom)
fx j 8y : (x; y) 2 RI ! y 2 CI g (value restriction; R 2 R)
fx j 9y : (x; y) 2 RI ^ y 2 CI g (existential restriction; R 2 R)
fx j 9y : (y; x) 2 RI ^ y 2 CI g (inverse existential restriction)
faI g (nominal; a 2 IN)
The semantics is with respect to a structure I = (4; I ) in which 4 is a domain
of \objects" and I an interpretation function seeded by xing the interpretations
of primitive concept names A to be subsets of 4 (as indicated), role names R
to be subsets of 4 4, and individual names a to be elements of 4 (and is
extended to derived concept descriptions C as also indicated). 2
The DL dialects E L? and Horn-ALC are given as follows:
De nition 2 (Horn-ALC and E L? TBoxes and Knowledge Bases)
A Horn-ALC or E L? knowledge base K consists of a TBox T and ABox A,
where T consists of a nite set of subsumptions of the form C v D in which
{ C is a conjunction of primitive concepts A and existential restrictions of the
form 9R:A, and
{ D is one of ?, A, 9R:A, and, in the case of Horn-ALC, 8R:A,
and where A consists of a nite set of assertions of the form a : A and R(a; b).
An interpretation I is called a model of K if CI DI for all C v D 2 T ,
aI 2 CI for all a : C 2 A, and (aI ; bI ) 2 RI for all R(a; b) 2 A.
Consistency, logical implication, and other reasoning problems are de ned in the
standard way. 2
Observe that we require TBoxes to be in a simple normal form. For more general
but expressively equivalent syntax, see [
Tree Models. Hereon, we rely on the fact that DL knowledge bases will usually possess the tree model property : with the exception of the explicit ABox, satis able knowledge bases have a tree-like model in which all anonymous objects form a role-connected forest rooted by ABox individuals. Moreover, in the tree parts of this model, no individuals are made equal unless forced to do so by TBox assertions.
For Horn logics, one can also show that there is a unique tree-like model commonly called the minimal or universal model that captures all the facts implied by the knowledge base. Thus, many reasoning tasks, in particular, instance retrieval, reduce to inspecting this model.
Queries and Referring Expressions. In the classical setting, instance retrieval (resp. query answering) with respect to a knowledge base K and a concept C (resp. query Q) is the task that determines for which individual names appearing in K it holds that K j= a : C (resp. K j= Q(a1; : : : ; ak)). Here, constant names serve the role of referring expressions, and our concern is with replacing such expressions by more general concept descriptions:
Referring expressions are simply concepts in (a subset of) the above concept language. In the following, we use concept descriptions of the form
C1 u 9R1 :(C2 u 9R2 :(: : : 9Rk :fag)) where Ci are (conjunctions) of primitive concepts. 2 The intuition behind this choice of referring expressions lies in the tree model property of our logics: every anonymous object can be reached by a role path from an ABox individual. (Indeed, unreachable objects that may exist in some models of our knowledge bases should not be considered since they fail to qualify as certain answers.)
In order to use referring expressions in place of constant symbols, one should ensure that they describe a single (certain) answer. Also note that, to account for various DL dialects, both knowledge base subsumptions/assertions and referring expressions will be restricted to appropriate subsets of the concept language in De nition 1. The following de nition of a singularity property of concepts serving the role of referring expressions in instance checking, however, is independent of the choice of DL dialect:
Let K be a knowledge base, D an instance query (i.e., a concept expression), and C a referring expression. We say that C is a singular certain answer to D if 1. (certainty) K j= C v D and jCI j > 0 for all models I of K, and 2. (singularity) jCI j = 1 for at least one tree model I of K.
This constitutes a weakening of the singularity property de ned in [
T = fA v 9R:C u 9R:D; A v 8R:Bg and A = fa : Ag. Then C u 9R : a f g and D u 9R : a
f g are singular certain answers for the instance query B(x), but 9R : a
f g is not since it fails the singularity requirement. (The description
contains at least two objects in every tree model of K.)
This seems to be in agreement with the usual entailment style of semantics for
certain answers in the database community that thinks of the results of a query
as an \intersection over all models". The bene t of this weaker de nition is that
results can now apply to logics that are unable to express functionality, such as
Horn-ALC or E L?, which were excluded from consideration in [
Conversely, we require the weaker singularity condition to hold in a tree model of the knowledge base. This avoids models that equate objects without a need to do so. Allowing such models in our de nition of singularity would incorrectly allow for concepts to be considered referring expressions for singular certain answers even though there could be two or more referring expressions that also describe singular answers and imply the expression in question. The following illustrates this case: 2
Consider again the situation in Example 5. Without restricting the singularity requirement to tree models, we could use an interpretation I that maps the R successors of aI to the same anonymous object. That interpretation is a model of K since C and D are not mandated to be disjoint. Hence, 9R : a f g would be incorrectly considered to be a singular certain answer even though two distinct singular certain answers referring to two distinct objects (as in Example 5) are subsumed by this description. Hence, this expression should not be considered singular.
Note that the above example presents a situation in which 9R : a f g refers to two distinct certain answers. However, note that aliases, that is, alternative referring expressions that refer to the same single answer, are still possible. This is natural and similar to standard approaches in which distinct constants may be interpreted as the same individual.
We rst consider the problem of generalized instance retrieval. In the classical setting, this task deals only with ABox individuals. However, in our setting, referring expressions can describe certain answers that can be arbitrarily far from ABox individuals denoted by constant symbols.
The two DLs that we consider, Horn-ALC and E L?, do not possess the capability of expressing the functionality of roles. A slightly surprising result is that Horn-ALC or E L? TBoxes are not able to enforce the existence of objects that are indistinguishable by appropriate referring expressions. Hence, all possible answers can in principle be described by such expressions as singular certain answers.
To simplify the exposition and focus on the issues connected with referring expressions, we rst assume that the ABox in a knowledge base contains a single assertion a : A. (We relax this restriction later.) Initially, we only consider instance retrieval queries of the form B(x) for B a primitive concept; instance queries for more complex concepts can be reduced to this case by introducing appropriate subsumptions in the TBox. In principle, testing whether a concept is an answer to an instance query reduces to a simple logical implication problem (perhaps in an extension of Horn-ALC). The main questions we answer here are what concepts should qualify as referring expressions, and how one guarantees singularity for these expressions.
To answer these questions, we utilize a construction similar to the standard construction of a tree automaton for recognizing tree models of the knowledge base.1 We generate a transition relation from our instance checking problem as follows:
Let K = (T ; fa : Ag) be a Horn-ALC knowledge base (in normal form) and Concepts(K) the set of all concepts and subconcepts appearing in K. We de ne Implied(S) = fC 2 Concepts(K) j T j= dA2S A v Cg, where S is a set of primitive concepts, and de ne SK = fS j S PC \ Concepts(K)g. We say that an existential restriction 9R:C 2 Implied(S) is independent if it is minimal among existential restrictions in Implied(S) with respect to subsumption. For mutually equivalent restrictions, we chose one representative to be independent.
A matching tuple for S 2 SK is a tuple
(S; fC0; D0;0; : : : ; D0;k0 g; : : : ; fCk; Dk;0; : : : ; Dk;kk g) 1 In the standard construction, the Hintikka sets are generated syntactically by analyzing concepts present in a TBox. Here, to simplify the presentation, we rely on logical implication algorithms already developed for the underlying logics. where 9R0:C0; : : : ; 9Rk:Ck are all independent existential restrictions that appear in Implied(S) and 8R0:D0;0; : : : ; 8R0:D0;k0 ; : : : ; 8Rk:Dk;0; : : : ; 8Rk:Dk;kk are all value restrictions that appear in Implied(S). We say that fCi; Di;0; : : : ; Di;ki g belongs to S's matching tuple for the existential restriction 9Ri:Ci. This construction is similar to the looping automaton construction for K with an initial state fAg. However, note that the transitions are deterministic for Horn-ALC. A similar construction also yields an optimal EXPTIME upper bound for satis ability of Horn-ALC knowledge bases since the number of the sets in the construction is at most exponential in jKj (as is the size of the tree automaton), and testing for the emptiness of a looping tree automaton can be done in time polynomial in the number of states as follows:
Set S 2 SK is feasible if 1. ? 62 Implied(S), and 2. for the matching tuple (S; S0; : : : ; Sk) all Si are feasible.
Otherwise, S is infeasible.
It is easy to see that the above de nition of (in)feasible states can be implemented by an algorithm that marks all infeasible states in jSKj rounds. Consequently, K is satis able if and only if the initial state fAg is feasible since the structure nitely encodes the universal (minimal) model of K: the model corresponds to the unfolding of the structure starting from fAg (i.e., a run of the automaton). We use the feasible states and the structure de ned over them by the matching tuples (a.k.a., the transition relation of the looping automaton) to de ne referring expressions that will serve as our singular certain answers:
A certain path for a query B(x) and knowledge base K is a sequence of role and concept pairs R1A1 : : : RkAk such that there are feasible S0; : : : ; Sk 2 SK and 1. S0 = fAg, 2. B 2 Implied(Sk), and 3. Si+1 belongs to Si's matching tuple for the existential restriction 9Ri:Ai. Observe that we consider all such paths in the above (i.e., not just paths that are simple). Also note that, unlike satis ability, we need to make certain that the referring expression concept works in all models of K. Here we again take advantage of the logic being Horn and rely on the (universal) tree model captured by the above construction.
Every certain path R1A1 : : : RkAk for B and K corresponds to a singular certain answer Ak u 9Rk :(: : : A1 u 9R1 :fag). Moreover, every B object common to all models of K will be reached by a certain path and will be returned as an answer. Proof (sketch): The construction guarantees that the referring expressions constructed from certain paths satisfy the certainty condition of our de nition: the end object of every certain path for B(x) and K is in the interpretation of the B concept in the minimal model and thus in all models of K. The objects at the ends of these paths are referred to by the referring expression concept constructed from such paths.
Requiring only independent existential restrictions to be parts of matching tuples guarantees singularity of the certain answers witnessed by the tree model of K. 3.2
The EL? Case We use the same construction. However, in the absence of value restrictions, observe that only the sets Implied(fAg), where A 2 PC, are needed. There are only polynomially many of these, all of which can now be constructed in PTIME.2 3.3
Our focus so far has been on problems of determining if a referring expression is a singular certain answer to an instance query B(x) over a knowledge base K. However, in practical information systems, one is often faced with the task of reporting all certain answers. This is easy in the standard case: we simply consider the available constant symbols one-by-one. The following examples show that this is not so simple for referring expressions.
In the case of acyclic TBoxes (even in E L?), the number of singular certain answers can be easily exponential (and doubly exponential in the case of Horn-ALC):
Consider a knowledge base with unit ABox and an E L? TBox of the form
T = fA v 9R:B0 u 9S:B0; : : : ; Bk 1 v 9R:Bk u 9S:Bkg for k > 0. Our construction gives k matching tuples (fBig; fBi+1g; fBi+1g) (plus a tuple (fBkg)). This, however, leads to exponentially many certain paths that are witnessed by the tree model of this TBox that contains 2k leaves. The situation is even worse in the case of Horn-ALC since one can force paths of exponential length using value restrictions and auxiliary concepts that stand for counters. Hence, one can force 22k certain paths (and in turn singular certain answers).
For cyclic TBoxes, it is easy to construct examples in which the number of singular certain answers is in nite:
Let T = fA v 9R:Ag, and A = fa : Ag. Then fag, 9R :fag, 9R :9R :fag,
9R :9R :9R :fag, etc., are all singular certain answers to A(x).
2 This construction is essentially the same as the construction of the so called canonical
model for EL? [
One can represent all these answers as simple regular expression-based extensions of our language of referring expressions, stating that the singular certain answers can be reached, for example, by R1 : : : Ri 1[Ri : : : Rk] paths. When transformed to the concept language embellished by a Kleene star-like construct, such a referring expression would appear as follows:
[Ck u 9Rk :(: : : Ci u 9Ri :(] Ci 1 u 9Ri 1:(: : : 9R1 :fag))): Note that the regular-like concept description corresponds to the certain path written backward, hence the cycle is syntactically at the beginning of this expression. Such expressions can be extracted from our construction of matching tuples as concatenations of simple paths from A to B followed by B to B cycles. However, while this solves our problems with the niteness of (the presentation of) all answers, issues connected with the number of answers raised in Example 10 remain. Similarly, the number of distinct simple cycles can be bounded by a factorial function from below. The representations consisting of sets of matching tuples (essentially the transition relation of a tree automaton) are vastly more succinct, but may not be appropriate as an end user feedback. Indeed, a succinct and user-friendly representation remains a topic for further research. 4
This section considers relaxing the various restrictions that we have assumed in addressing the problem of exhaustive query answering via referring expressions (restrictions that enabled a simpler exposition of what we believe are the principle issues). 4.1
One can use a standard approach to extend an explicitly given ABox to a tree model (represented again using matching tuples). One issue that needs to be addressed is guaranteeing the singularity of answers. This is not an issue for the ABox individuals, but roles in the ABox can make certain existential restrictions redundant and break our independence requirement, as illustrated in the following:
Consider knowledge base K with an ABox A = fA(a); R(a; b); B(b)g and a TBox T = fA v 9R:Bg. Considering the TBox alone, we generate a matching tuple (fAg; fBg) that is used to generate (anonymous) R successors for As. However, were this tuple used for the a object, it would lead to a certain answer 9R : a f g no longer being singular (in the constructed model). Extending the independence requirement to eliminate redundant existential restrictions by generating additional matching tuples for ABox objects solves this problem. In this particular case, one would generate a tuple (fA; fagg) with no successors.
The above approach can be applied to all ABox objects leading to at most jAj
increase in the number of matching tuples and hence preserving our complexity
bounds.
One simply reduces conjunctive query (CQ) answering to existing approaches
that deal with queries whose answer variables match ABox individuals [
The latter two cases need to make certain allowances for free variables of the queries that can now match anonymous objects referred to by our referring expressions in the answer tuples. This requires simple, but slightly tedious housekeeping to be added to the process to track the variable matches, in particular in case (3). 4.3
When quanti ed role restrictions of the form ( 2 R:C) are present in the language, it may not be possible to describe all answers as singular certain answers since such at-least restrictions can force multiple certain answers that cannot be distinguished by referring expressions (without the loss of singularity). Note, however, that genuine at-least restrictions can be modeled by existential restrictions and auxiliary disjoint primitive concepts. Then, however, those concepts will guarantee singularity in the tree model.
Results are better with only functionality or at-most restrictions, although there remains some dependence on the way such restrictions are realized in the TBox or concept language, for example, as (func R) constraints or as ( 1 R:C) concepts. Indeed, negations in the latter case can lead to at-least restrictions and non-singularity of certain answers. The situation for non-Horn logics is even more complex: we can certainly extend our construction to full ALC, but we face the following issue in the presence of disjunctions, in particular, when such disjunctions are allowed in referring expressions:
According to our de nition of singularity, given a TBox fA v 9R:B t 9S:Bg, an ABox fa : Ag, and a query B(x), a singular certain answer could be 9R :fag t 9S : a
f g since the two (minimal) tree models will contain fR(a; o); B(o)g and fS(a; o); B(o)g.
Even worse, where the TBox given instead as fA v (9R:B u 9S:B) t 9T:Bg, one
could have two certain answers, both singular: 9R :fagt9T : a
f g and 9S :fagt
9T :fag, that seem to reuse the second part of the disjunction. This not only
leads to combinatorial problems but also renders answers that are unintuitive.
Also, observe in the rst case that the anonymous object o, indeed the answer we
are trying to refer to, need not be the same object in the two models. However,
this isn't too di erent from interpreting a constant symbol by varying domain
elements in di erent models of a knowledge base. The downside of this
arrangement is that such a system will be reporting answers that contain (possibly large
numbers of) disjunctions may not be what users of such a system would expect.
Limiting what referring expressions are used in answers has been considered in
[
We have presented an extension to instance retrieval and query answering tasks that, with the help of referring expressions, allows one to return all singular certain answers in Horn-ALC and E L? knowledge bases. We have also shown that this is no longer the case for logics endowed with at-least number restrictions, even though additional answers are still possible when referring expressions can be arbitrary concepts.
There are many directions for further research, in particular: { Issues related to a more compact representation of answers; this direction is related to discovering \small" regular expressions or devising other ways to present all the singular certain answers over a knowledge base. { Extensions to more powerful Horn description logics: what concept constructors can be supported while maintaining the ability to report all answers? What to do with at-least restrictions and (unlike functionality) do we really need them? { Extensions to non-Horn Description Logics: can the techniques be extended to DLs with concept disjunction (see the discussion in Section 4.4)?