How individuals are identified when cooperating agents need to communicate is an inherent issue faced by the designers of information systems. Solutions to this problem range from insisting on global often opaque identifiers, such as URIs, to application specific ways of externally identifying individuals, such as primary keys in relational systems. The goal of this tutorial is to introduce a flexible framework based on referring expressions that unifies approaches that address these issues.
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 a knowledge base K, commonly captured using a first order theory, constant symbols occurring in K are the artifacts usually used to identify a subset of the objects for which K captures knowledge.
In this tutorial, we explore how the class of objects that can be usefully identified
can be extended by allowing a variety of more general formulas in the language of K,
called singular referring expressions, to replace constants as syntactic identifiers of such
objects. In particular, we lay a foundation for admitting singular referring expressions in
certain answer computation for queries over K. An integral part of this foundation are
characterization theorems for identification properties of singular referring expressions
for queries annotated with a domain specific language for referring expression types [
We then apply the work on referring expression types to the issue of identification
in conceptual modelling. In particular, we consider how such types yield a separation
of concerns in a setting where an information system based on an ontology or
conceptual schema is to be mapped to a relational schema that is then queried using relational
queries. We start from a simple object-centered representation common in ontologies and
in virtually all semantic data models where, since objects are self identified, naming is
not an issue. We then allow the analyst to attach referring expression types to classes,
and to specify appropriate uniqueness constraints to satisfy the requirements on referring
expressions. Finally, we show: (a) how a number of well-formedness conditions
concerning an assignment of referring expressions can be efficiently diagnosed, and (b) how
the above types attached to classes allow an automatic synthesis of a concrete relational
schema, and relational queries over that schema, from a combination of the conceptual
schema, a choice of referring expression types, and abstract “logical” queries over the
conceptual schema [
We conclude by considering variations on referring expressions in situations in which singularity can be relaxed, and therefore extend the applicability of the framework to weaker knowledge representation languages.
The tutorial focuses on foundational issues relating to object identification in ontologies and information systems based on ontologies, and on how such issues can be comprehensively addressed. The approach to object identification discussed in the tutorial naturally and seamlessly complements standard approaches in ontology design.
What is a referring expression? We start with an introduction and overview of how well formed formulae that satisfy certain properties, in particular singularity—the property stating that the expression describes a single individual in every model of a knowledge base—can serve as referring expressions in information systems whose underlying ontologies correspond to first order knowledge bases. Background. We introduce formal properties of referring expressions and show how they can be determined. We then discuss how referring expressions can be computed, in particular when K conforms to a decidable fragment of first order logic, and more generic characterizations of varieties of referring expressions in the conceptual modelling of information systems. We also review past work on determining referring expressions in the context of knowledge bases and position these approaches among other approaches designed to indirectly and/or symbolically capture identities of (sets of) objects.
Referring expressions and query answering. We show how referring expressions can be used to enrich query answers over knowledge bases by allowing to refer to answer objects that may not have an explicit name within the knowledge base K, or for which a more preferred way of communicating its identity is available. To control the form of the answers, we define a type language that describes varieties of referring expressions desired in query answers. How these types are used to adorn free variables in queries over K is presented. This includes an overview of cases in which K conforms to a description logic and how computation issues are then resolved by off-the-shelf technology for the logic.
Referring expressions in conceptual modelling. Next, we explore the benefits of adopting referring expression types for use in information systems derived from conceptual modelling. In particular, we show how this approach can separate the purely conceptual ontology design from issues connected with how objects are identified within an eventual information system based on the design. Results on how this enables a more wide spectrum use of SQL in defining information retrieval requirements is also presented.
Referring expressions for light knowledge representation formalisms. Finally, we discuss variations on the singularity requirement for referring expressions: we show that in certain situations, such as in the case of certain answers, the singularity condition can be weakened to require singularity of individual certain answers rather than singularity in every model of the knowledge base K. This allows us to extend our results to knowledge bases formulated in weaker formalisms, such as the various light-weight Description Logics, e.g., those that lack the capability of enforcing functionality of binary predicates/roles.
Open problems. We conclude the tutorial with an outline of directions for further research, and with a list of open issues related to the use of referring expressions in ontology-based information systems.
The tutorial also links the proposed framework to existing approaches to managing
identities of objects in information systems, in particular of those based on knowledge bases
or other logic-backed systems, e.g., [