A referring expression in linguistics is any noun phrase identifying an object in a way that will be useful to interlocutors. In the context of conjunctive queries over a description logic knowledge base (DL KB), typically constant symbols (usually treated as rigid designators) are used as referring expressions in a certain answer to the query. In this paper, we begin to explore how this can be usefully generalized by allowing more general DL concept descriptions, called singular referring expressions, to replace constants in this role. In particular, we lay the foundation for singular referring expressions in conjunctive query answers over a DL KB using a member of the CFD family of DL dialects. In the process, we introduce a speci c language for referring concept types, and present initial results on how conjunctive queries with referring concept types can be e ciently supported.
Query answering in logic-based approaches to data and knowledge bases has traditionally been viewed as nding constant names, appearing in the knowledgebase, which can be substituted for the variables of the query. More formally, a query q(x1; : : : ; xn) is viewed as a formula with free variables x1; : : : ; xn and, if the knowledge-base K contains individual constant names IN, query answering consists of computing the set f (a1; : : : ; an) j ai 2 IN; K j= q(a1=x1; : : : ; ak=xk) g. We believe that in a number of circumstances this is less than ideal.
(1) In object-based KBMSs (including Object-Relational, XML and
ObjectOriented DBMSs, as well as DLs with UNA), all known individual objects must
have unique (internal) distinguishing identi ers. However, these identi ers are
often insu cient to allow users to gure out what real-world object they refer
to, especially for large KBs. For example, system generated ref expressions in
object-oriented databases [
We note that even in databases, universally unique keys are hard to nd (e.g., newly arrived foreign students do not have ssn#), though they may work for subsets of individuals, such as those returned by queries.
(3) Additional problems for nding identifying attributes for classes of
objects arise in conceptual modeling. For example, consider all cases where
Extended Entity-Relationship modeling creates a new heterogeneous entity set by
\generalization" [
(4) The next example illustrates a subtler version of the above: consider the following hierarchy of concepts relating to publications:
Journal v EditedCollection ; EditedCollection v Publication And suppose edited collections are identi ed by isbn#, while journals are identi ed by title and publisher. When we retrieve a set of objects in Publication, we would like to describe them in di erent ways, depending on the subclass they belong to; but in this case, there would be an additional preference for textittitle; publisher) over isbn# for elements of Journal.
(5) Many kinds of KBMSs, including those based on DLs and FOL, allow us to describe situations where objects can be inferred to exist, without having an explicit (internal) identi er. For example, if Michelle is a person, then she has a mother, and if she is married then she has a spouse. Normally, such objects cannot be returned in the list of answers. This is all the more unpleasant if we can capture information about this unknown person, such as the phone number of Michelle's mother: fMichelleg v 9hasMother:9hasPhone:f1234567g. Yet it is common in human communication to identify objects by their relationship to other known objects. For example, \Michelle's mother" is a perfectly reasonable intensional description of someone who has phone 1234567.
The standard response to some of the above problems would be to have the user modify the query by nding the appropriate values for identifying attributes (external keys). For example, instead of the query q1(x) :- Journal(x), the programmer would be expected to write
q2(t; p) : Journal(x); hasTitle(x; t); hasPublisher(x; p):
1 OBDA systems such as Mastro [
q5(isb) : EditedCollection(x); :Journal(x); hasIsbn(x; isbn) which is not a conjunctive query, since it includes a negation. (iii) From the point of view of software engineering, the task of choosing these identifying references is mentally distinct from the task of selecting the objects of interest to begin with. Both SQL's select clause, and XQuery's return clause are examples of separating these two aspects in existing query languages.
This paper is then dedicated to the task of proposing a rst solution to (some of) the issues raised by providing \singular referring expressions" in the place of individuals returned by conjunctive queries, in the context of DL KBs.
Our plan and contributions are as follows: We will start by proposing a language for referring concept expressions and types. This language will generalize the usual case of presenting answers to queries as individual names to situations that: (i) allow object identi cation by key (paths), possibly within the limited context of some concept instances; (ii) deal with heterogeneous answer sets, such as LegalEntity; and (iii) allow preferential choice of referring expressions, as for EditedCollection. We will use this language to de ne answers for conjunctive queries over DL KBs. More generally, the proposed approach introduces a new separation of concerns for knowledge bases (identi cation vs. quali cation). In our case, the query head will annotate each variable returned with an answer concept type; this will be instantiated to an answer concept (a subset of our DL concepts) for each answer; such concepts will eventually bottom out to individual constants, rather than atomic concepts.
Because we wish to generalize the usual case of constant names in answers,
we desire referring concept types to be singular expressions { i.e., to identify
one individual.2 Unfortunately, without knowing anything else, it is impossible,
for example, to tell whether an expression such as \object with p-value 3" will be
singular or not: if p is a key, then yes, but not otherwise. Therefore, we need to use
information from the ontology to verify the singularity of referring concept type.
This can be extended by examining the body of the query (and hence learning
more about what possible values variables may take). We will concentrate in
this paper on: (i) the (compile-time) analysis of conjunctive query bodies in the
context of the TBox to determine whether a referring concept type will return
a reference to at most one individual; (ii) the reformulation of the query to
2 Researchers interested in so-called co-operative query answering have considered
returning predicates/concepts describing sets of individuals (e.g., [
Preliminaries: the Description Logic CF Dn8c The knowledge bases that we consider are based on the logic CF Dn8c, a recent member of the CF D family of DL dialects. All members of this family are fragments of FOL with underlying signatures based on disjoint sets of unary predicate symbols called primitive concepts, constant symbols called individuals and unary function symbols called attributes. Although attributes deviate from the normal practice of using binary predicate symbols called roles, they make it easier to incorporate concept constructors suited to the capture of relational data sources that include various dependencies, e.g., by a straightforward rei cation of arbitrary n-ary predicates, and also make it easier to explore varieties of concepts that can serve as referring expressions.
De nition 1 (CF Dnc Concepts) Let F, PC and IN be disjoint sets of (names 8 of) attributes, primitive concepts and individuals, respectively. A path function Pf is a word in F with the usual convention that the empty word is denoted by id and concatenation by \:". The set of CF Dnc concepts C is given by the 8 following grammar, where a 2 IN, A 2 PC, Pf and Pfi are path functions, k > 0 and fi 2 F.
C ::= fag j A j 8Pf:C j C1 u C2 j :A j Pf1 = Pf2 j (1)
A : Pf1:Pf; Pf2; : : : ; Pfk ! Pf1 j A : Pf1:Pf; Pf2; : : : ; Pfk ! Pf1:f Semantics is de ned in the standard way with respect to an interpretation I = (4; ( )I ), where 4 is a domain of \objects" and ( )I an interpretation function that xes the interpretation of attributes f to be total functions on 4, primitive concepts A to be subsets of 4, and individuals a, b to be elements of 4. The (fag)I (8Pf:C)I (C1 u C2)I
(:A)I (Pf1 = Pf2)I (A : Pf1; : : : ; Pfk ! Pf)I = = f(a)I g; fx 2 4 j (Pf )I (x) 2 (C)I g; = (C1)I \ (C2)I ; = = = 4 n (A)I ; fx 2 4 j (Pf1)I (x) = (Pf2)I (x)g and fx 2 4 j 8 y 2 (A)I :
Vi(Pfi)I (x) = (Pfi)I (y) ! (Pf)I (x) = (Pf)I (y)g
Fig. 1. Semantics of CF Dn8c Concepts. interpretation function is extended to path expressions by interpreting id as the identity function and concatenation as function composition. The semantics of the remaining CF Dn8c concepts are then de ned in Figure 1. 2 Concepts having the last two forms in (1) are called a (path) key and a path functional dependency (PFD), respectively. Informally, such concepts each denote a set of objects, each of which, whenever agreeing with any A-object on all left-hand-side path functions, also agrees with that object on the right-hand-side path function. Thus, the axiom EditedCollection v EditedCollection : isbn# ! id, expresses that isbn# is a key for edited collections, while P erson v P erson : home:phone# ! home:address, says that if two persons have the same home phone then they have the same home address.
De nition 2 (CF Dn8c Knowledge Bases) Generic knowledge/metadata and 8 speci c facts/data in a CF Dnc knowledge base K are respectively de ned by a TBox TK and an ABox AK.
A TBox TK consists of a nite set of general concept inclusion axioms, which adhere to one of the following six forms, where A and Ai are primitive concepts, f is an attribute in F, B is a primitive concept or a negation of a primitive concept, and where Pf and Pfi are path functions: A v B ; A v 8f:B ; 8f:A v B ; A v (Pf1 = Pf2); A1 v A2 : Pf1; : : : ; Pfk ! Pf: TK must also satisfy the following condition: strati cation of path function equalities: If A v (Pf1 = Pf2) 2 TK then A is a primitive concept that does not occur on the right-hand-side of any inclusion axiom in TK.
An ABox AK consists of a nite set of axioms that express facts, each of which has one of the following two forms, respectively called individual membership assertions and individual relationship assertions,
A(a) and Pf1(a) = Pf2(b);
for individuals a; b 2 IN, primitive concept A 2 PC, and path functions Pfi 2 F .
Note that (fag)I = f(a)Ig and thus we can use nominal concepts as proxies
for individuals. An interpretation I satis es an inclusion axiom C1 v C2 if
(C1)I (C2)I. It satis es ABox axioms A(a) and Pf1(a) = Pf2(b) if (a)I 2 (A)I
and (Pf1)I((a)I) = (Pf2)I((b)I), respectively. I satis es a knowledge base K if
it satis es each axiom in K. 2
The need for the additional restriction on a TBox to avoid undecidability of
TBox reasoning due to equational constraints derives in a straightforward way
from the undecidability of the word problem for monoids [
Proposition 3 (Consistency and Logical Implication in CF Dn8c [
In this section we re-evaluate the way answers to conjunctive queries are understood and presented.
De nition 4 (Conjunctive Queries) A conjunctive query (CQ) Q, with free variables fx1; : : : ; xkg, has the form 9xk+1; : : : ; 9xm : Body(Q) where Body(Q), the query body of Q, is a rst order formula over the signature C [ F of the form ^ C(xi) ^
^ f (xj ) = xk) ; Recall that our objective in this paper is to study how CF Dn8c concepts can help serve the role of a singular referring expression in certain answers to conjunctive queries. To review current practice, assume K is a knowledge base over some DL dialect, and consider one of the purposes served by an ABox in de ning the certain answers over K to a CQ Q: the nite collection of individual names fa1; : : : ; ang in the ABox de nes a space of nk potential answers to Q: k-tuples i that map query variables xj to individual names aij ,
fx1 7! ai1 ; : : : ; xk 7! aik g: Viewed as a substitution, recall that each i is a certain answer to Q over K exactly when K j= Q i: Note that the occurrence of an individual aij in a certain answer is a simple example of a referring expression, i.e., a syntactic artifact that identi es elements of an underlying domain.
This notion of a potential answer is easily modi ed to accommodate a much larger variety of referring expressions. To start, one can view a potential answer i as a set of size k that maps query variables to nominal concepts instead of individuals, as in
fx1 7! fai1 g; : : : ; xk 7! faik gg; where each xi; xj and xk occurs in fx1; : : : ; xmg.3 (2)
2 (3) and then extend this idea by allowing arbitrary CF Dn8c concepts in potential answers to queries, i.e., potentially by allowing answers to have the form fx1 7! C1; : : : ; xk 7! Ckg: In this alternative setting \certain answers" are de ned as follows: De nition 5 (Referring Concepts and Certain Answers) 8 Let K be a CF Dnc knowledge base, Q a conjunctive query with free variables 8 x1; : : : ; xk and C1; : : : ; Ck CF Dnc concept descriptions. We say that C1; : : : ; Ck are referring concepts in a certain answer fx1 7! C1; : : : ; xk 7! Ckg to Q if the following two conditions hold: 1. K j= 8x1; : : : ; xk:C1(x1) ^ : : : ^ Ck(xk) ! Q, and 2. jfo 2 4 j I; [xi 7! o] j= Ci(xi) ^ (9x1; : : : ; xi 1; xi+1; : : : xk:Q)gj = 1 for every I j= K and 0 < i where C (x) is the rst-order formula derived from the concept description C . 2 The rst condition states that Ci objects (as values of xis) satisfy Q and the second one that we are interested in singular referring expressions Ci, as generalizations of simple individual names. In the rest of the paper we call fx1 7! C1; : : : ; xk 7! Ckg a candidate answer to Q if condition (1) in the above de nition 3 To improve readability in the rest of the paper we allow constants to appear in CQs.
However, conjuncts of the form x = a are just syntactic sugar for a conjunct fag(x) formed using a concept fag. Similarly, f (x) = a is 9y(f (x) = y ^ fag(y)), etc. is satis ed,and call it a weakly identifying answer to Q if only an upper bound (of one) is guaranteed to hold in condition (2) We call concepts Ci that are used in this way singular referring concepts since they replace the role of individual names as referring expressions in certain answers to conjunctive queries.
To illustrate, assume K captures information about persons, and consider a query with body Person(x). In the rest of the paper, we will use Pf = a as an alternative syntax for 8Pf:f a g (to improve readability). Possibilities for certain answers to the query now include one or more of the following:
fx 7! (ssn# = 1234)g or fx 7! F emale u (hasSpouse.name = 'Enya') u (hasSpouse.phone# = 1234567)g: Note that De nition 5(2) disallows answers of the form fx 7! Femaleg or more generally, rules out any C for x in which j(C)I j 6= 1 when I j= K. Thus, the earlier examples of certain answers would be contingent on TK ensuring that persons have unique ssn#, as well as unique spouses, who can be identi ed by a (name; phone#) pair. 4
Allowing referring concepts beyond nominals in certain answers to a query Q may lead to in nitely many syntactically distinct certain answers. In this section, we develop a framework that ensures the set of certain answers to any conjunctive query is nite by introducing a speci c language for referring concept types, which bottom out at individual nominals.
Important note: while De nition 5 allows general CF Dn8c concepts to serve as referring concepts, in the rest of the paper we restrict our attention to the subset of referring concepts adhering to the more limited grammar
C ::= fag j A j 8Pf:C j C u C where fag is a nominal, A is a primitive concept name, and Pf 2 F . These C are intuitively instances of the following referring types.
De nition 6 (Referring Concept Types) A referring concept type Rt is given by the following grammar, where T denotes a nite conjunction of primitive concepts (or > standing for empty conjunction), to be called henceforth a simple type.
Rt ::= f?g j Pf = f?g j Rt1 u Rt2 j T ! Rt j Rt1; Rt2 The referring concept set RC(Rt; K) is the \extension" of a referring concept type Rt with respect to KB K, and is de ned inductively as follows, where Si is short for RC(Rti; K): 1. RC(f?g; K) = ffag j a occurs in AKg; 2. RC(Pf = f?g; K) = f(Pf = fag) j a occurs in ABox AKg; 4. RC(T ! Rt1; K) = fT u C j C 2 S1g; and 5. RC(Rt1; Rt2; K) = S1 [ fC2 2 S2 j :9C1 2 S1 s.t. K j= C1
A referring concept type is homogeneous if it is free of any occurrence of the construct in 5. 2 Examples of their use will follow immediately after the next de nition. Note that, as desired, the set of referring concepts associated with a single referring concept type is nite if AK is nite.
De nition 7 (Certain Answers and Singular Referring Concepts) Let Q be a conjunctive query with free variables fx1; : : : ; xkg. A query head H for Q is a set of pairs fx1 : Rt1; : : : ; xk : Rtkg that associates a referring concept type Rti with each xi.
The set of certain answers to Q with respect to a head H and a knowledge base K, denoted Ans(Q; H; K), is the set of all certain answers fxi 7! Ci j 0 < i kg to Q over K for which Ci 2 RC(Rti; K), for 0 < i k. 2 After the examples below, the objective in this section is to show that computing Ans(Q; H; K) can be achieved in PTIME for CF Dn8c, provided that referring concept types satisfy a \weak identi cation condition".
The following examples illustrate the use of referring concepts with conjunctive queries to extend the current situation with the more expressive cases motivated in the Introduction (a conjunctive query Q with a head H will be written in the following SQL-like style: select H where Body(Q)): We now make concrete our requirement that referring concepts occurring in query answers do indeed satisfy the ability to identify objects.
De nition 8 (Weak Identi cation in Certain Answers) Let Q be a con8 junctive query, H a head for Q, and T a CF Dnc TBox. Q is weakly identifying for H with respect to T if j(C)I j 1 for every ABox A, model I of T [ A, and candidate answer to Q with respect to H and T [ A in which x 7! C 2 . 2 Lemma 9 (Normal Form of Referring Concept Types) For every referring concept type Rt, there is an equivalent normal form
Rt1; : : : ; Rtn; denoted Norm(Rt), consisting of tagged record types Rti that are, in turn, homogeneous referring concept types of the form
T [ fAQ v ((8x:T ) u M(Body(Q))) j= AQ v AQ : x:Pfi;1; : : : ; x:Pfi;mi ! x for all (x : Rt) 2 H, and all T ! (Pf1 = f?g) u : : : u (Pfm = f?g) 2 Norm(Rt). Proof (sketch): The if direction is straightforward. For the only-if direction, consider the earliest tagged record type Rt 0 2 Norm(Rt) for some x : Rt 2 H for which the check for the logical consequence of the key PFD fails. Then one can construct an ABox A where there exists C 2 RC(Rt 0; T [ A) that occurs in some candidate answer for Q for which one can also construct an interpretation I for T [ A for which j(C)I j > 1. 2 De nition 11 Let Q be a CQ with free variables fx1; : : : ; xkg. We say that H is a homogeneous head for Q if it is of the form
H = fxi : Ti ! (Pfi;1 = f?g) u : : : u (Pfi;`i = f?g) j 0 < i kg: For every CQ Q and a homogeneous head H for Q we de ne a conjunctive query k QH = Q ^ ^(Ti(xi) ^ (Pfi;1(xi) = xi;1 ^ : : : ^ (Pfi;`i = xi;`i )
i=1 with additional free variables fxi;j j 0 < i k; 0 < j `ig. 2 To handle preferences, i.e., non-homogeneous heads H of queries of the form fxi : Rpi;1; : : : ; Rpi;ni j 0 < i kg we rst de ne a sequence of homogeneous heads
Hj1;:::;jk = fxi : Rpi;ji j 0 < i kg over all 0 < ji < ni. In addition, we de ne a normalized ABox A0 for an ABox A to contain only individual relationship assertions of the form f (a) = b obtained from A by introducing additional individuals for the intermediate individuals participating in A's individual relationship assertions.4 Theorem 12 Let K = (T ; A) be a knowledge base, Q a CQ, and H a head for Q, such that Q is weakly identifying for H in T . Then
fxi 7! Ti u (Pfi;1 = fai;1g) u : : : u (Pfi;`i = fai;`i g)g 2 Ans(Q; H; K) if and only if
fxi 7! fbig; xi;j 7! fai;jg j 0 < i and there is no fxi 7! fbig; xi;j 7! fa0i;jg j 0 < i k; 0 < j k; 0 < j `ig 2 Ans(QHj1;:::;jk ; H0; K0) `ig 2 Ans(QHj10;:::;jk0 ; H0; K0) for Hj10;:::;jk0 dominates Hj1;:::;jk , where H0 = fxi : f?g j 0 < i kg [ fxi;j : f?g j 0 < i k; 0 < j `ig, K0 = (T ; A0) where A0 is a normalized A, and ai;j and a0i;j are constants in A.
Proof (sketch): Consider rst the case where H is homogeneous. Then we can reconstruct an answer to Q and H from an answer to QH and H0 (which consists of nominal concepts only. Conversely, from answer to Q and H we can extract nominal concepts that are an answer to 9x1; : : : ; xk:QH and H0 (restricted to free variables of 9x1; : : : ; xk:QH ). This answer is then extended to QH and (full) H0 by using individual names introduced in the normalized ABox A0, this extension is unique since Q is weakly identifying for H in T .
For the non-homogeneous case we simply consider all possible homogeneous
subcases and then lter the answers by the valuations of the variables x1; : : : ; xk
(since those describe the possibly anonymous individuals in A using their
systemassigned names A0). 2
Note that the queries QHj10;:::;jk0 are answered in K with respect to H0, a
trivial and homogeneous head: this reduces the answering to standard CQ query
8
answering in CF Dnc knowledge base K as introduced in [
Corollary 13 Computing certain answers to conjunctive queries with respect
to referring concepts and CF Dn8c knowledge bases is complete for PTIME.
4 Such a transformation is already part of the CQ answering algorithm [
The paper's contributions are as follows.
First and foremost, on the non-technical side, it recognized and motivated the utility of \singular referring expressions" for query answers, which are more complex than just nominals, and it argued for the need for a new separation of concerns in query writing: quali cation (what the query body does) vs. identi cation (how results are presented).
On the speci cation side, the paper de ned formally the notion of \query answering using referring expressions" for certain answers in conjunctive queries over DLs. In the context of CF Dn8c, it introduced a speci c language for referring 8 expressions, which are a subset of CF Dnc concepts, and which allows us to handle all the motivating problems (except intensional descriptions in this paper. This language generalizes the notion of nominal, currently used in OBDA, to handle keys (as found in both the database and DL KB literature), and supports heterogeneous sets (as in the case of LegalEntity), as well as preferential choice of referring expressions (as in the EditedCollection example).
On the algorithmic and complexity side, it rst considered, in the context of CF Dn8c, the problem of determining (in polynomial time) whether a referring concept type was \weakly" identifying in the context of a query and TBox, in the sense that its instances necessarily referred to at most one object. It also showed how one can transform a query and knowledge base so that the answers had cardinality one. This led to the result that computing certain answers to 8 conjunctive queries with respect to referring concepts and CF Dnc KBs was complete for PTIME.
There are many avenues left to explore in this work. We have already mentioned that lack of space prevented us from considering referring concepts types for \Michelle's mother", which use inverse functions. Another direction to consider are additional forms or desirable properties of referring expressions. For example, the variety of references raises a problem: the same object may be returned in an answer with di erent references to it, even if the knowledge base works with the UNA. As a simplest example, a journal has multiple candidate keys. We are currently investigating ways to reason about and avoid such duplication.
The reader may also have observed that so far it was up to the programmer to select the referring expression(s) to consider for each variable. A form of type inference on the query variables would be useful, as the basis of a tool which would suggest to the user a (bounded) list of possible referring expressions that are guaranteed to have the singular reference property with respect to a particular TBox.
Of course, all the technical questions considered in this paper will have different answers for di erent DLs. Therefore, an orthogonal avenue of research is to re-consider these issues in the context of other DLs, especially DL-Lite. Acknowledgments: We wish to thank those reviewers who have made excellent suggestions for improving the paper, and nancial support from NSERC Canada.