Tutorial: Referring Expressions in Ontologies and Query Answering

David Toman and Grant Weddell

Cheriton School of Computer Science, University of Waterloo, Canada

{david, gweddell}@cs.uwaterloo.ca

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 class 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 [1]. We apply this framework in the context of tractable knowledge representation languages (often based on description logics, fragments of first order logic), showing how identification properties can be determined at compile-time for conjunctive queries, and how off-the-shelf conjunctive query answering approaches for these dialects, such as perfect rewriting, can be used in query evaluation [1]. We also show that the extension does not negatively impact the computational properties of the underlying logic.

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 a 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. We then show how a number of well-formedness conditions concerning an assignment of referring expressions can be efficiently diagnosed, and how the above types attached to classes allow an automatic synthesis of a concrete relational schema (and relational queries over that schema) from the conceptual schema (and
abstract “logical” queries over the conceptual schema) [2].

Relevance to FOIS

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.

Audience and Background

Familiarity with first order logic and conceptual modelling formalisms (such as ER or UML) at introductory university course level. No knowledge of particular ontology/KR languages (such as description logics) and formalisms is assumed.

Outline of the Tutorial

What is a referring expression? We start with an introduction and overview of how well formed formulae that satisfy certain properties can serve as referring expressions in information systems whose underlying ontologies correspond to first order knowledge bases.


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. 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 expression types 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 KB, 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.

Referring expression types in conceptual modelling. Finally, 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.

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.

About the Tutorial Authors

Dr. David Toman and Dr. Grant Weddell are professors of Computer Science at the University of Waterloo. Together with Alexander Borgida (Rutgers), they have introduced referring expressions in the area of Ontology-based data access (OBDA) [1] and received the Ray Reiter Best Paper prize at KR 2016 for this work. They subsequently extended this work to the area of conceptual modelling [2] and other areas connected with ontological reasoning and knowledge representation. They have published and presented results in the area of knowledge representation over the last 20 years at premier AI conferences (including another Reiter prize in 2010); Dr. Toman has also given tutorials in the area of temporal representation and reasoning that led to an invited chapter in the Handbook of Temporal Reasoning in Artificial Intelligence.


[1] Alexander Borgida, David Toman, and Grant Weddell. On referring expressions in query answering over first order knowledge bases. In Principles of Knowledge Representation and Reasoning, Cape Town, SA, pages 319-328, 2016.

[2] Alexander Borgida, David Toman, and Grant E. Weddell. On referring expressions in information systems derived from conceptual modelling. In Conceptual Modeling – 35th International Conference, ER 2016, Gifu, Japan, pages 183-197, 2016.