Earlier work has shown how Russell's notion of proper definite descriptions can be captured as referring expressions: concept descriptions that are known to be singular. Concept descriptions are a more general and transparent way of communicating answers to queries. In general, how long such answers can be relied on will depend on how long facts about entities are not altered via data update, that is, on revisions to the underlying ABox of a KB. In this paper, we show how a simple variety of dynamic constraints can be added to a KB to ensure user specified durations on how long query answers must be able to be relied on.
(
ROOM ⊓ ∃.⟨?⟩ ⊓ ∃..⟨?⟩
Note that occurrences of “⟨?⟩” serve as placeholders for nominals, and that an is therefore a pattern language for concepts.
One might expect that relying on the second referring expression in (
EMP ⊓ ∃.{77}.
We will see that referring expressions (ii) and (iii) are in the language generated by an defined as the
following pattern:
(STUDENT ⊓ ∃.⟨?⟩) ; (PERSON ⊓ ∃.⟨?⟩)
(
It is this kind of efect that sensible data update can have on referring expressions that is our primary concern. In particular, we introduce a form of dynamic constraint that can be added to to ensure the eficacy of a referring expression.
To illustrate, if the facts that rob is a student and that his student number is 321 are implied by , consider where should also ensure that any data update on the ABox in which he continues to be a student must also preserve knowledge of this number. We augment the above mentioned FunDL dialect for capturing to incorporate a form of dynamic constraint to ensure this, in particular, a dynamic constraint of the form
(STUDENT, ).
The constraint is dynamic in the sense that it fails to hold when also considering any data update to the ABox in which rob remains a student but in which knowledge of this student number is either removed or updated.
Our main result introduces the procedure ChooseRE(, , ) where is an individual name, a concept expressing a “duration requirement” and a knowledge base that now includes dynamic constraints, such as the above, and an . The procedure attempts to compute the most preferred referring expression in the language generated by for referring to that can be relied on for as long as is known to be a .
For example, assume the TBox and ABox of are as given in Figure 1, where it has additional dynamic
constraints such as the above, and where it has the given by (
To summarize, our contributions revolve around the ChooseRE procedure. In particular, we introduce a variety of dynamic constraints relating to individuals and their feature values and incorporate such constraints in the computation of referring expressions for individuals that (a) are more general and transparent ways of communicating references to individuals, for example, in answers to queries, and (b) can be trusted to reliably refer for a specified duration.
The remainder of the paper is organized as follows. Section 2 provides the needed background relating to our FunDL dialect, to referring expressions, and to our new dynamic constraints. Procedure ChooseRE is then introduced in Section 3. In Section 4, we consider a number of additional issues relating to “unique name” possibilities, to counting, and to incremental ways to guarantee the existence of referring expressions. Summary comments are given in a final subsection.
TBox = { ROOM ⊑ (∃.⊤) ⊓ (∃.BLD) ⊓ ROOM : , . → id ,
BLD ⊑ (∃.⊤) ⊓ BLD : → id , PERSON ⊑ (∃.⊤) ⊓ (∃.⊤) ⊓ PERSON : → id , STUDENT ⊑ PERSON ⊓ (∃.⊤) ⊓ STUDENT : → id ,
EMP ⊑ PERSON ⊓ (∃.⊤) ⊓ (∃.ROOM) ⊓ EMP : → id } ABox = { ROOM(room1), (room1) = 5678, (room1) = bld1,
BLD(bld1), (bld1) = "Davis Center", PERSON(rob), (rob) = 1234, (rob) = "Smith", STUDENT(rob), (rob) = 321, PERSON(robin), (robin) = 1234, (robin) = "Smith",
EMP(robin), (robin) = 77, (robin) = room1 } ∅ { | ∀.(( ∈ ℐ ∧ (⋀︀=0{, } ⊆ (∃Pf.⊤)ℐ )
(⋀︀=1 Pfℐ () = Pfℐ ())) → (Pf0ℐ () = Pf0ℐ ()))} | ⊤ | A | ∃Pf. | 1 ⊓ 2 | {} | ∃ − 1. △ℐ Aℐ ⊆ △ ℐ { | ∃.( ∈ ℐ ∧ Pfℐ () = )} 1ℐ ∩ 2ℐ {ℐ } { ℐ () | ∈ ℐ }
We now formally define the artifacts introduced in our introductory comments, beginning with the definition of concepts and TBoxes for a member of the FunDL family of DLs with decidable complexity of logical consequence for subsumptions and for assertions. Recall that members of this family replace roles with partial functions, and that concepts also serve the role of referring expressions. Also note that we distinguish a countably infinite subset of individual names that are literal values such as strings or integers and for which we adopt the unique name assumption.
Definition 1 (FunDL Concepts, Referring Expressions, and TBoxes). Let F, PC, IN, and D be respective countably infinite sets of feature names {1, 2, . . .}, primitive concept names {A1, A2, . . .}, individual names {1, 2, . . .}, and a countably infinite subset of IN that are literal values. A path expression is defined by the grammar “ Pf ::= . Pf | id ” for ∈ F and a concept by the grammar on the left-hand-side of Figure 2. Concepts generated by the second production are called path functional dependencies (PFDs).2
A referring expression () is a concept description parsed by the last six productions in Figure 2; these are intended to assert the existence of individuals with complex properties.
A subsumption is an expression of the form 1 ⊑ 2, where the are FunDL concepts parsed by the ifrst six productions in Fig. 2. A terminology (TBox) consists of a finite set of subsumptions.
The semantics of concepts and path expressions is defined with respect to a structure ℐ = (△ℐ , · ℐ ), where △ℐ is a domain of “individuals” including “literal values”, and where · ℐ is an interpretation function that 2Recall that such concepts are the above-mentioned means of capturing equality generating dependencies. . ifxes the interpretations of primitive concepts to be subsets of △ℐ and primitive features to be partial functions ℐ : △ℐ → △ℐ . The interpretation function also satisfies the unique name assumption (UNA) for literal values, that is, that (1)ℐ ̸= (2)ℐ for any pair of distinct 1 and 2 in D. The interpretation is extended in the natural way to path expressions: id ℐ = . , (. Pf)ℐ = Pfℐ ∘ ℐ ; and to concept descriptions as indicated on the right-hand-side of Figure 2.
A structure ℐ satisfies a subsumption 1 ⊑ 2 if 1ℐ ⊆ 2ℐ , and is a model of a TBox if it satisfies all subsumptions in . A subsumption is a logical consequence of a TBox, written |= (1 ⊑ 2), when every model of also satisfies 1 ⊑ 2.
Given a TBox , a referring expression is singular with respect to if |ℐ | ≤ 1 for any model ℐ of □
Unfortunately, an unrestricted use of the first six concept constructors in Fig. 2 in TBox subsumptions still leads to undecidability of KB consistency and logical implication questions [5]. To regain decidability, all PFDs in the TBox must appear on right-hand sides of subsumptions and must conform to the following forms: 1. 2.
C : Pf1, . . . , Pf . Pf, . . . , Pf → Pf or
C : Pf1, . . . , Pf .1, . . . , Pf → Pf .2 With these restrictions, reasoning tasks become complete for EXPTIME. Further restrictions are needed to obtain PTIME reasoning algorithms for the above tasks. The most general form of such restrictions (to date) has been developed in [6].
Referring expression types are now defined. Recall from our introductory comments that these were first introduced in [ 2], and that the version presented here is from later work in [4] which adapts earlier syntax to conform with referring expressions expressed as concepts. In this version, we have made a minor revision to enable such types to distinguish the case in which “feature paths” lead more specifically to literal values. The discussion that follows on how a referring expression type can be diagnosed at “compile time” to determine if all generated referring expressions are singular w.r.t. a given TBox is also from [4]. This entails the introduction of a couple of useful auxiliary functions that is used in later sections.
Definition 2 (FunDL Referring Expression Types). A referring expression type () is defined by the following grammar:3
::= A | {?} | ⟨?⟩ | ∃Pf. | ⊓ | ; We define the language of referring expressions inhabiting , ℒ(), as follows:
ℒ(A) = {A} ℒ({?}) = {{} | ∈ IN} ℒ(⟨?⟩) = {{} | ∈ D} ℒ(∃Pf.) = {∃Pf. | ∈ ℒ()} ℒ(1 ⊓ 2) = {1 ⊓ 2 | 1 ∈ ℒ(1) and 2 ∈ ℒ(2)} ℒ(1; 2)) = ℒ(1) ∪ ℒ(2) Also, we write Norm() to refer to an exhaustive application of the following rewrite rules to : ⊓ (1; 2) ↦→ ⊓ 1; ⊓ 2 (1; 2) ⊓ ↦→ 1 ⊓ ; 2 ⊓ ∃Pf.(1; 2) ↦→ ∃Pf.1; ∃Pf.2 □ 3This is a pattern language obtained by abstracting nominals in referring expressions, and by admitting a final production to express preference among referring expressions [2]. Also note that such a preference only becomes an issue when more than one referring expression for an individual is possible in an ABox, in particular, in defining our ChooseRE procedure in the next section.
The definition of Norm() is a simple variant of referring expression type normalization defined
in [2], and the following are consequences: (
Given a TBox and a referring expression type , the following auxiliary functions will enable a static test for singularity of referring expressions in ℒ():
Con(A) = A Con({?}) = ⊤
Con(⟨?⟩) = ⊤
Con(∃Pf′.) = ∃Pf′.Con() Con(1 ⊓ 1) = Con(1) ⊓ Con(2)
Pfs(A) = { } Pfs({?}) = {id }
Pfs(⟨?⟩) = {id }
Pfs(∃Pf′.) = {Pf′ . Pf | Pf ∈ Pfs()} Pfs(1 ⊓ 1) = Pfs(1) ∪ Pfs(2) The functions extract a FunDL concept and a set of path expressions leading to nominals from a preference-free referring expression type. A straightforward variation of the ideas presented in [2], Theorem 20, yields the following formulation of the static test: Theorem 1 (from [4]). Let be a TBox and a referring expression type. Then all referring expressions in ℒ() are singular if and only if for every preference-free component ′ of Norm(): |= Con(′) ⊑ Con(′) : Pfs(′) → id .
The definition of our dynamic constraints now follows and includes a definition of ABoxes and of data update. Note that a finite set of dynamic constraints and a (single) referring expression type are now included as part of the definition of a knowledge base and that we have taken a very general view of what constitutes data update: replacing an ABox with an entirely new ABox. More discussion will follow.
Definition 3 (FunDL ABoxes, Dynamic Constraints and Data Update). An assertion box (ABox) consists of a finite set of assertions of the form (1), 1 = 2, or (1) = 2, where is a concept and the are individual names.
A dynamic constraint has the form (, Pf), and we write to refer to a WBox, a finite set of dynamic constraints.
A knowledge base is a four-tuple ( , , , ).
A structure ℐ satisfies when it satisfies each assertion in , that is, when (1)ℐ ∈ ℐ , (1)ℐ = (2)ℐ and ℐ ((1)ℐ ) = (2)ℐ . = ( , , , ) is consistent if there exists a structure over , that is, that satisfies and .
A data update is an ABox , and qualifies as an update on = ( , ′, , ) if is consistent, ′ = ( , , , ), also written /, is also consistent, and if and also satisfy each dynamic constraint (, Pf) in , written (, ) |= (, Pf). This holds when: for any ℐ1 over , ℐ2 over / and individuals 1 and 2, if (1)ℐ1 ∈ ℐ1 , (1)ℐ2 ∈ ℐ2 and Pfℐ1 ((1)ℐ1 ) = (2)ℐ1 then Pfℐ2 ((1)ℐ2 ) = (2)ℐ2 .
More generally, we write |= (, Pf) when (, ) |= (, Pf) for any data update on .
Our notion of a data update is based on the notion of a transaction on a relational database that
updates only the contents of tables and is consistency preserving, that is consists of inserts, updates
and deletes on a given collection of tables for which all integrity constraints continue to hold. Also,
in earlier work, we have considered where an was attached to each free variable of a query [2]
and, more recently, where an is attached instead to primitive concepts in the context of a DL-based
knowledge base [4]. It turns out in the latter case that a single obtained by using “;” to “catenate”
□
(
Observe that dynamic constraints cannot disqualify the ABox of a consistent knowledge base from also qualifying as a data update on , nor can revising such constraints of a consistent knowledge base lead to its inconsistency. This leads immediately to the following: Theorem 2. Let = ( , , , ) be a consistent knowledge base and a subsumption or assertion. Then |= if ( , , { }, ) |= , that is, admitting dynamic constraints in a knowledge base are a conservative extension w.r.t. logical consequence of subsumptions or assertions. □
We now define procedure ChooseRE(, , ) for computing more transparent and readable referring expressions for an individual in knowledge base that can be relied on for duration , that is, for as long as is known to be an instance of concept . The procedure uses the definition of ToRE given in [4] for computing a referring expression that works “in the here and now” for a given “;”-free ′. In particular, ToRE is called in an iterative fashion on the sequence of such ′ in Norm() until finding a referring expression that also satisfies a subsumption relating to and ′. In addition, durability requires that itself satisfies a durability condition.
Note that, unlike the case in [4], it is now possible that diferent referring expressions are obtained for the same individual name due to alternative choices for , that is, for durations. Again, more discussion will follow.
Definition 4 (Choosing a Referring Expression). Let be an individual name, a concept and =
( , , , ) a consistent knowledge base, and assume Norm() = 1; . . . ; . is durable when
the following holds:
|= (Con(), Pf), for 1 ≤ ≤ and all Pf ∈ Pfs().
(
ToRE(, A, Pf, ) = A if |= : ∃Pf.A, undefined otherwise; ToRE(, {?}, Pf, ) = {′} if |= : ∃Pf.{′} for some ′ ∈ IN, undefined otherwise; ToRE(, ⟨?⟩, Pf, ) = {′} if |= : ∃Pf.{′} for some ′ ∈ D, undefined otherwise; ToRE(, ∃Pf′., Pf, ) = ∃Pf′.ToRE(, , Pf . Pf′, ); and ToRE(, 1 ⊓ 2, Pf, ) = ToRE(, 1, Pf, ) ⊓ ToRE(, 2, Pf, ) if both are defined, undefined otherwise.
We write ChooseRE(, , ) to return a concept ′ for the least ≤ for which the following hold, and to be undefined otherwise: 1. |= ⊑ Con(), 2. ToRE(, , id , ) is defined and returns ′. □
See earlier work [7, 8] for more efective ways of computing the second and third cases of ToRE by appealing to logical consequence in FunDL knowledge bases based on a binary search that assumes access to a total ordering of individual names IN. This earlier work also shows how standard classification can be employed to compute the first case of ToRE.
Building on our university domain, consider where the TBox and ABox for are as given in Figure 1. Also assume the dynamic constraints and referring expression type for are as given in Figure 3. Observe that the of a person and the ation of an employee ofice are really the only kinds WBox = { (ROOM, ), (ROOM, ), (BLD, ),
(PERSON, ), (STUDENT, ), (EMP, ) } =
ROOM ⊓ ∃.⟨?⟩ ⊓ ∃..⟨?⟩ ; BLD ⊓ ∃.⟨?⟩ ;
STUDENT ⊓ ∃.⟨?⟩ ; EMP ⊓ ∃.⟨?⟩ ; PERSON ⊓ ∃.⟨?⟩ of facts that can updated. Then the following lists examples of calls to ChooseRE and the referring expression returned as a consequence:
ChooseRE(rob, STUDENT, ) → STUDENT ⊓ ∃.{321} ChooseRE(rob, PERSON, ) → PERSON ⊓ ∃.{1234} ChooseRE(room1, ROOM, ) → ROOM ⊓ ∃.{5678} ⊓ ∃..{"Davis Center"} ChooseRE(rob, EMP ⊓ ∃...{"David Center"}, ) → EMP ⊓ ∃.{77} Note that the first three are as reported in our introductory comments. The fourth shows another referring expression for rob that is requested to last for as long as he is an employee with an ofice located in the David Center building.
Theorem 3. Let be an individual name, 1 a concept and = ( , , , ) a consistent knowledge base that is durable and for which all referring expressions in ℒ() are singular w.r.t. . If ChooseRE(, 1, ) is defined and returns concept 2, then 2ℐ1 = 2ℐ2 = {()ℐ1 } for any ℐ1 over , any data update ′ on and any ℐ2 over /′.
Proof. (sketch) By induction on the structure of the concept 2 generated by ToRE(, , id , ) for
some . The invariant of the structural induction is {Pf . Pf′ | Pf′ ∈ Pfs()} ⊆ Pfs() where
and Pf are the second and third arguments of the recursive calls to ToRE in Definition 4. Then in
the first base case |= : ∃Pf.A holds as Con() ⊑ ∃Pf.A and in the second and third case we
have Pf ∈ Pfs() and thus, due to the requirement |= (Con(), Pf) for all Pf ∈ Pfs() and
condition (
Recall that logical consequence for subsumptions is decidable. Thus, by Theorem 2, the only outstanding computational issue with ChooseRE(, 1, ) concerns logical consequence for dynamic constraints, that is, to determine if |= (, Pf) for some , and Pf. To this end, we define two inference axioms: |= (1, Pf), |= 2 ⊑ 1
|= (2, Pf)
|= (1, Pf1), |= 1 ⊑ ∃Pf1.2, |= (2, Pf2)
|= (1, Pf1 . Pf2)
(
As with individual names that are not literal values for which the UNA applies, referring expressions
can in principle co-refer to the same object in a structure for a given . This was indeed the case in our
introductory example (
PERSON ⊓ ∃.{1234}
STUDENT ⊓ ∃.{321}
EMP ⊓ ∃.{77} On the other hand, literal values (elements of D) will be distinct since we have assumed the UNA for literal values. Hence, referring expressions in ℒ(⟨?⟩) will inherit this property. In the following we show how the UNA can be lifted to more complex referring expression types. In this way we ensure that referring expressions that inhabit these types also obey this lifted variant of UNA: syntactically distinct referring expressions must always refer to distinct domain elements. The following condition on referring expression types lifts UNA to more complex referring expression types: • Let Norm() = 1; . . . ; be “{?}”-free referring expression type such that |= Con()⊓
Con( ) ⊑ ⊥ for all < ≤ . Then ℒ() obeys lifted UNA.
Note that, e.g., stronger lower bounds for counting are enabled by detecting lifted UNA.
The procedure for choosing a referring expression in Definition 4 may fail to return an appropriate referring expression. We focus on the situation in which the reason for failure is entirely due to where ToRE(, , ) is not defined, i.e., where does not entail suficiently many facts about the individual in question.
One can strengthen definition (
|= (Con(), Pf), for 1 ≤ ≤ and all Pf ∈ Pfs(),
and that these now satisfy both conditions (
LitPfs(A) = { } LitPfs({?}) = { }
LitPfs(⟨?⟩) = {id }
LitPfs(∃Pf′.) = {Pf′ . Pf | Pf ∈ LitPfs()}
LitPfs(1 ⊓ 1) = LitPfs(1) ∪ LitPfs(2) With this stronger requirement, ToRE(, , ) always returns an appropriate referring expression for any that will persist as long as () holds. Hence, evolving via data updates starting from an empty ABox guarantees the existence of referring expressions for any individual for which such an expression can exist. We have developed dynamic constraints—constraints on allowed ABox changes—that make referring expressions durable relative to concept membership of the objects they identify. This way we can guarantee that, e.g., the value of the feature snum can be used to identify PERSONs as long as they are STUDENTs, but ceases to be reliable when a PERSON ceases to be a STUDENT (and we have to revert to other ways of identifying such objects). This durability of referring expressions relative to concept membership has many applications, for example, when one considers physical representation of such objects in multi-level storage systems (such as caches). We also introduced conditions under which the existence of appropriate referring expressions is guaranteed for all objects belonging to a given concept description. Last, we studied how UNA for constant symbols can be lifted to complex referring expressions.
The author(s) have not employed any Generative AI tools.