Earlier work has proposed a notion of referring expressions and types in rst order knowledge bases as a way of more e ectively answering conjunctive queries in ontology based data access (OBDA). We consider how PTIME description logics can be combined with referring expressions to provide a more e ective virtual front-end to relational data sources via OBDA. In particular, we consider replacing the standard notion of an assertion box, or ABox, with a more general notion of a concept box, or CBox.
In a query answer (a1; : : : ; an) over a rst order knowledge base K, the common
assumption is that each ai will correspond to some constant symbol occurring
in K. A more general option has been proposed in [
In this paper, we consider query answering in which the ontological component of K consists of a TBox T expressed in terms of a DL, and in which the remaining part of K consists of a CBox C instead of an ABox, where C consists of a nite set of referring expressions in the form of concept descriptions in the DL, and for which each is presumed non-empty and singular in all models of K. 8
The DL we consider is partial CF DInc [
A core problem in deriving the ABox relates to identity issues when introducing new constants. Of particular signi cance is that x-point computations are necessary when such constants are introduced. Indeed, this can be necessary when a TBox derives from relational data sources with tables that have uniqueness constraints as well as primary keys, or for which primary keys themselves are not minimal. In database parlance, one would say in this case that primary keys are superkeys but not candidate keys. Such \key conversion" tables can serve to map between alternative primary keys and thereby lead to additional query answers.
While several approaches to integrating information in settings in which the
same individual can be identi ed in several (even syntactically incomparable)
ways have been considered in the past [
The remainder of the paper is organized as follows. We begin with the necessary background material in Section 2 in which we introduce partial CF DI8nc concepts, and \standard" knowledge bases consisting of a TBox of inclusion dependencies over such concepts and an ABox of assertions. Our main results then 8 follow in Section 3 in which an ABox is replaced with a CBox of partial CF DInc concepts called referring expressions. We then de ne a mapping of CBoxes to ABoxes and show how each of the following can be resolved with the use of this mapping: (1) diagnosing an admissibility condition for a CBox, (2) satis ability of knowledge bases with a CBox, and (3) query answering over knowledge bases with a CBox. The admissibility condition requires that the TBox ensures each referring expression occurring in the CBox is singular in the sense outlined above. Throughout, we introduce examples to illustrate why CBoxes are useful and how identi cation issues become far more complicated as a consequence. We conclude with summary comments in Section 4. 2
8 The description logic partial CF DInc is a member of the CF D family of DLs which 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 features. Note that features deviate from the normal practice of admitting roles denoting binary predicate symbols. However, features make it easier to incorporate concept constructors that are better suited to the capture of relational data sources, particularly so when they include dependencies such as primary keys, uniqueness constraints, functional dependencies and foreign keys. This is achieved by a straightforward rei cation of n-ary predicates and by using a concept constructor peculiar to the CF D family called a path functional dependency. Consider the case of a role R. It can be rei ed as a primitive concept RC , two features domR and ranR and an inclusion dependency of the form
RC v RC : domR; ranR ! id in partial CF DI8nc . The latter e ectively ensures any combination of domR and ranR values uniquely determine an R 2-tuple. Note that an ALC inclusion dependency mentioning R of the form \A v 8R:B", can also be captured in 8 partial CF DInc as the inclusion dependency
8domR:A v 8ranR:B: 8 Concepts in partial CF DInc are de ned as follows:
Let F and PC be sets of feature names and primitive concept names, respectively. A partial path expression is de ned by the grammar \ Pf ::= f: Pf j id " for f 2 F. We de ne derived concept descriptions by the grammar on the left-hand-side of Fig. 1. A path functional dependency concept, or PFD, is obtained by using the nal production of this grammar.
An inclusion dependency C is an expression of the form C1 v C2. A terminology (TBox) T consists of a nite set of inclusion dependencies. A posed question Q is a single inclusion dependency.
Syntax
Semantics: Defn of \ I " C ::= A j C1 u C2 j :C j 8 Pf :C j 9Pf j 9f 1:C j fag j C : Pf1; :::; Pfk ! Pf0
AI 4 (primitive concept; A 2 PC) C1I \ C2I (conjunction) 4 n CI (negation) fx : PfI (x) 2 CI g (value restriction) fx : PfI (x) existsg (existential restriction) ff I (x) : x 2 CI g (inverse feature) faI g (nominal) (see text ) (PFD)
The semantics of expressions is de ned with respect to a structure I = (4; I ), where 4 is a domain of \objects" and I an interpretation function that xes the interpretations of primitive concepts A to be subsets of 4 and primitive features 8 f to be partial functions f I : 4 ! 4. Note that partial CF DInc adopts the strict interpretation of unde ned values, which means that arguments terms must be de ned whenever equality and set membership do hold. The interpretation is extended to partial path expressions, id I = x:x, (f: Pf)I = PfI f I , in the natural way, and derived concept descriptions C not including PFDs as de ned in the centre column of Fig. 1. For concept descriptions that are PFDs, the interpretation is de ned as follows:1 (C : Pf1; : : : ; Pfk ! Pf0)I = fx j 8y:y 2 CI ^ x 2 (9Pf0)I ^ y 2 (9Pf0)I ^
Vik=1(x 2 (9Pfi)I ^ y 2 (9Pfi)I ^ PfiI (x) = PfiI (y)) ! Pf0I (x) = Pf0I (y) g: An interpretation I satis es an inclusion dependency C1 v C2 if C1I C2I and is a model of T (I j= T ) if it satis es all inclusion dependencies in T . The logical implication problem asks if T j= Q holds, that is, if Q is satis ed in all models of T . 2 Observe that features are still functional, and that there is therefore no need for a quali ed existential restriction of the form 9f:C, since such restrictions can be equivalently written as 8f:C u 9f . Hence the use of quali ed existential restrictions in the rest of the paper should be considered to be syntactic sugar.
To ensure PTIME reasoning in partial CF DI8nc we require all subsumptions
in the TBox to adhere to the following restrictions (for more general TBoxes and
normalization see [
D ::= A j ? j :A j 8f:A j 9f 1 j 9f j A : Pf1; : : : ; Pfk ! Pf
In addition, PFDs must adhere to one of the following two forms to avoid
undecidability [
8 The second component of a partial CF DInc knowledge base is an ABox A that contains assertions of the form \A(a)", \a = b", \a 6= b", and \f (a) = b", with the usual interpretation mapping constant symbols to domain elements, and interpreting the assertions as set membership and an equality/inequality between a constant and another constant or a function application to a constant, respectively. 2 8
8 Satis ability of partial CF DInc knowledge bases is complete for PTIME. 1 This constitutes the minimum necessary conditions needed for recognizing when one violates an inclusion dependency of the form \ C1 v C2 : Pf1; : : : ; Pfk ! Pf0 " : Conjunctive queries are, as usual, formed from atomic queries (or atoms), corresponding to concept descriptions, and equalities between variables and application of function to variables, using conjunction and existential quanti cation. To simplify notation, we con ate conjunctive queries with the set of its constituent atoms and a set of answer variables :
Let ' be a set of atoms (representing a conjunction) A(xi) and f (xi1 ) = xi2 , where A is a primitive concept description, f a feature (including id ), and x a tuple of variables. We call the expression fx j 'g a conjunctive query (CQ). 2 A conjunctive query fx j 'g is therefore a notational variant of the formula 9y: V 2' in which y contains all variables appearing in ' but not in x. The usual de nition of certain answers is given by the following:
Let K be a partial CF DI8nc KB and Q = fx j 'g a CQ. A certain answer to Q over K is a substitution of constant symbols a, [x 7! a], such that K j= Q[x 7! a]. 2
8 Query answering over partial CF DInc knowledge bases is complete for PTIME (data complexity).
The query answering algorithm presented in [
In this section we introduce referring expressions, concept descriptions that will serve as external identi ers of objects in partial CF DI8nc knowledge bases.
We will require that these concept descriptions behave the same way constant symbols behave in the traditional setting: we expect their interpretations to be singular in every model of a given knowledge base.
8 Let C be a partial CF DInc concept description conforming to the grammar
C ::= A j C1 u C2 j 9f:C j 9f 1:C j fag; where a is a constant symbol, and T a TBox. We say that C is a (singular) referring expression (w.r.t. T ) if jCI j 1 for all interpretations I that are models of T . 2 We use referring expressions to de ne the counterpart of assertions in traditional knowledge bases.
Consider a situation in which objects are identi ed by their f value, such as an employee number, within a class A. Two A objects can then be captured by the following pair of concepts:
A u 9f:f123g and A u 9f:f345g: The singularity requirement, in this example, can be enforced by ensuring f values can indeed serve as the key for A objects, e.g., by adding the inclusion dependency
A v A : f ! id to the TBox. The two concepts now replace the usual ABox assertions of the form A(c1) and A(c2), which need an invention of additional constant symbols for the two abstract objects. Moreover, ABox assertions of the form g(c1) = c2 can also be captured by concepts, in our example:
A u 9f:f123g u 9g:(A u 9f:f345g): Note that such descriptions naturally arise when the assertion part of a knowledge base is captured in various database back-ends, e.g., in relational databases (via keys and foreign keys) or in document databases, such as MongoDB2, in which the structure of the referring expressions correspond to JSON3.
To illustrate the exibility of our approach based on CBoxes, consider the following JSON fragment describing persons, hypothetically occurring in a MongoDB document source: {"fname" : "John", "lname" : "Smith", "age" : 25, "phoneNum" : [ {"loc" : "home", "dialnum" : "212 555-1234"}, {"loc" : "work", "dialnum" : "212 555-4567"} ]} In our setting, this document can be naturally and directly represented as a CBox assertion of the form
PERSON u (9fname:f\John"g) u (9lname:f\Smith"g) u 9age:f25g u 9phoneNumFor 1:((9loc:f\home"g) u (9dialnum:f\212 555-1234"g)) u 9phoneNumFor 1:((9loc:f\work"g) u (9dialnum:f\212 555-4567"g)) One way in which this assertion satis es an admissibility condition, de ned below, happens whenever the combination of an fname and an lname can serve to identify a PERSON. 2 https://www.mongodb.com/. 3 https://www.json.org/. Identities of documents (and sub-documents) are now captured using referring expressions; this potentially allows for join operations on document databases (not typically supported by such systems). Queries navigating JSON documents 8 can be now expressed as conjunctive queries over the partial CF DInc representation.
This development leads to a revision of the de nition of partial CF DI8nc knowledge bases in which the traditional notion of an ABox is replaced by a CBox: a set of concept descriptions that are referring expressions for individuals the knowledge base knows about.
Let T be a partial CF DI8nc TBox and Q a conjunctive query with answer 8 variables x1; : : : ; xk. We de ne a CBox C to be a set of partial CF DInc concept descriptions.
8 A partial CF DInc knowledge base K is a pair (T ; C).
We say that the CBox C is admissible for T if jCI j models I of T .
We say that K is consistent if there is an interpretation I such that 1 for all C 2 C and all 1. I j= T , and 2. jCI j = 1 for every C 2 C.
We say that (C1; : : : ; Ck) is a certain answer to Q in K if
K j= Q ^ C1(x1) ^ : : : ^ Ck(xk) CBoxes inherently represent information about how objects in a knowledge base are identi ed. Note there is no restriction on how such identi cation must be captured. In particular, there are no uniformity conditions on identi cation of objects that must hold, such as requiring each object to have a single global identi er in all assertions in the knowledge base.
However, CBoxes allow one to capture various resolutions of the heterogeneity
of identi cation, e.g., through translation tables or cross-links [
Consider the TBox f A v B; C v B;
A v A : f ! id ; B v B : f; g ! id; C v C : g ! id A v B : f ! id ; C v B : g ! id g; for fC1; : : : ; Ckg
2 and the CBox f A u 9f:f3g;
B u 9f:f3g u 9g:f5g;
C u 9g:f5g g: Note that the referring expression \A u 9f:f3g" identi es the same object as \B u 9f:f3g u 9g:f5g", due to the second-last TBox subsumption, and in turn as \C u 9g:f5g", due to the last TBox assertion. Thus, the object described by \Au9f:f3g" should be a certain answer to a conjunctive query fx j A(x)^C(x)g. The same happens for all pairs of referring expressions in the CBox subsumed by A and C, respectively, for which there is a B cross-link. 3.2
In relational databases the notion of candidate key, a key that has a minimal set of attributes of a relation, is typically used as an external identi er of objects stored in the database.
Our development of a referring expression strictly generalizes the notion of a superkey in the relational setting: sets of attributes, not necessarily minimal, that identi es an object or entity. We now present a procedure that (syntactically) minimizes a referring expression to obtain minimal co-referring referring expressions that are counterparts to relational candidate keys.
8 Let T be a partial CF DInc TBox and C a referring expression w.r.t. T . We say that subconcepts of C of the form A, fag, 9f:>, 9f 1:>, and > u > are leaves of C and write C[L 7! >] for a description C in which a leaf L was replaced by >. Assuming \ rst-leaf" and \next-leaf" denote functions that successively enumerate all leaves of C, the procedure 1. L := rst-leaf(C); 2. while C[L 7! >] is singular w.r.t. T do 3. C := C[L 7! >]; L := next-leaf(C);
computes a syntactically-minimal co-referring expression for C. (Note that replacing a leaf by > may create additional leaves.) Proof (sketch): Since the C[L 7! >] operation weakens the concept description C, it preserves satis ability. The algorithm tests for singularity at every step. Hence the result is a minimal referring expression equivalent to C since no additional leaves can be removed. 2 The algorithm nds a minimal referring expression in time linear in jCj. Analogous to the relational setting, backtracking this algorithm facilitates the discovery of alternative minimal referring expressions, and, also analogous to the relational setting, there can be exponentially many of these. 3.3
Our technique crucially depends on mapping CBoxes to (standard) ABoxes as follows. We begin by de ning how individual concepts corresponding to referring expressions are transformed:
ToAbox(a : C1 u C2) 7!
ToAbox(a : 9f:C) 7! ToAbox(a : 9f 1:C) 7!
ToAbox(a : fbg) 7!
ToAbox(a : A) 7!
ToAbox(a : C1) [ ToAbox(a : C2) ff (a) = bg [ ToAbox(b : C); b fresh ff (b) = ag [ ToAbox(b : C); b fresh fa = bg fA(a)g; A primitive The ToAbox function converts a CBox assertion C to a set of ABox assertions by introducing constant names for all necessary individuals, in particular a constant aC for the (witness of satis ability of) C itself. The mapping is then lifted to CBoxes by applying it on all referring expressions in the CBox as follows: ToAbox(C) = [ ToAbox(aC : C) [ fai 6= aj j ai; aj individuals in C; i 6= jg
C2C Note that we make nominals distinct since they correspond to values from a relational backend that typically assumes UNA. Also, one could reuse the textual representation of the concepts to serve as the invented constant names.
Let T be a partial CF DI8nc TBox and C a concept description. Then C is a singular referring expression w.r.t. T if and only if the knowledge base (T [ fA v :Bg; ToAbox(a : C) [ ToAbox(b : C) [ fa : A; b : Bg) is inconsistent, where A and B are primitive concepts not occurring in T and C and a and b are distinct constant symbols.
Proof (sketch): The ToAbox mapping expands complex concepts in a CBox to sets of assertions in a corresponding ABox. By case analysis we can show that a model of (T [ fA v :Bg; ToAbox(a : C) [ ToAbox(b : C) [ fa : A; b : Bg) provides an counterexample to C's singularity (w.r.t. T ). Moreover, whenever C is not singular, such a model can be constructed by appropriately naming additional individuals in a counterexample to C's singularity. 2 It is easy to verify that the CBox in Example 11 is admissible w.r.t. the given TBox since `f ', `f; g' and `g' are keys on A, B, and C, respectively.
Let K = (T ; C) be a knowledge base with an admissible CBox C. Then K is consistent if (T ; ToAbox(C)) is consistent.
Proof (sketch): Similar to the argument in the proof sketch in Theorem 13. 2 3.4
We now show how query answering over CBox-based knowledge bases can be reduced to the standard case of ABoxes. We also show an example of the utility of CBoxes in capturing distinct co-references to a particular object, and how partial CF DI8nc based TBoxes can account for such co-references.
Let K = (T ; C) be a consistent knowledge base and Q = f(x1; : : : ; xk) : 'g a
conjunctive query over K. Then (C1; : : : ; Ck) is a certain answer to Q in K if
and only if (aC1 ; : : : ; aCk ) is a certain answer to Q over (T ; ToAbox(C)).
Proof (sketch): Since C1; : : : ; Ck are singular referring expressions, there must
be individuals o1; : : : ; ok witnessing nonemptiness of C1; : : : ; Ck, respectively,
that make the query true in every model of K; case analysis shows that, in the
corresponding models of (T ; ToAbox(C)), these individuals will be the
interpretations of the constant symbols (aC1 ; : : : ; aCk ) (and vice versa). 2
Note that ABox completion [
Reconsider the TBox and CBox in Example 11. The ABox constructed from the CBox is as follows: f A(aAu9f:f3g); f (aAu9f:f3g) = 3;
B(aBu9f:f3gu9g:f5g); f (aAu9f:f3gu9g:f5g) = 3; g(aAu9f:f3gu9g:f5g) = 5;
C(aCu9g:f5g); f (aCu9g:f5g) = 5;
g
Note that the referring expressions A u 9f:f3g and C u 9g:f5g, despite being
syntactically distinct, co-refer to the same object in the knowledge base due to
the existence of the B referring expression and the TBox subsumptions. The
standard ABox completion [
faAu9f:f3g = aCu9g:f5gg using the last two constraints in the TBox and the fact that both A and C are subsumed by B, that serves as a translation concept generated from a translation table. This yields the referring expression A u 9f:f3g to be a certain answer to the query.
On Query Answers. The de nition of certain answers asks for all tuples of constants|in our setting proxied by referring expressions|for which the query is entailed by the knowledge base. Thus the selection of referring expressions in the CBox determines components of query answers presented to the user. There are two considerations: 1. Additional answers may be needed; these can be obtained by considering additional referring expressions describing, e.g., sub-documents, to the CBox (as long as the CBox remains admissible); 2. Simpler answers may be desired, i.e., simpler referring expressions denoting the answers; these can be obtained by appropriate selection of minimal referring expressions (and removing all the more complex referring expressions from answers).
Both of these goals can be achieved by a simple housekeeping that determines which referring expressions are eligible to appear in query answers. This step can be easily combined with the CBox-to-ABox mapping by appropriately marking the generated constant symbols. Indeed, similar marking is commonly used, e.g., when ABoxes are normalized in most OBDA settings. 4
We have considered how referring expressions corresponding to concepts in a description logic can serve the role of constant symbols in both assertion boxes and in query answering, and how doing so leads to a more e ective and direct way of achieving an integration of backend data sources via OBDA, as well as more descriptive and meaningful answers to queries.
Admitting referring expressions leads naturally to a notion of a concept box or CBox in place of an ABox in a knowledge base. This in turn raises a number of technical issues: how to ensure referring expressions in a CBox refer to a single individual, how to check for knowledge base consistency, and how to evaluate conjunctive queries over the knowledge base. We have shown how all these issues can be resolved by a mapping of CBoxes to ABoxes. The mapping enables o -theshelf procedures for ABox completion, for consistency checking, and for ABox completion and query rewriting over standard knowledge bases consisting of a TBox and ABox.
In [