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 usefulto 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 whichK captures knowledge.
In this tutorial, we explore how the class of objects that can be usefully identified can be extended byallowing a class of more general formulas in the language of K, called singular referring expressions, toreplace constants as syntactic identifiers of such objects. In particular, we lay a foundation for admittingsingular referring expressions in certain answer computation for queries over K. An integral part of thisfoundation are characterization theorems for identification properties of singular referring expressionsfor queries annotated with a domain specific language for referring expression types [1]. We apply thisframework in the context of tractable knowledge representation languages (often based on descriptionlogics, 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 thesedialects, such as perfect rewriting, can be used in query evaluation [1]. We also show that the extensiondoes not negatively impact the computational properties of the underlying logic.
We then apply the work on referring expression types to the issue of identification inconceptual modelling. In particular, we consider how such types yield a separation of concerns in a settingwhere an Information System based on an ontology (or a conceptual schema) is to be mapped to a relationalschema that is then queried using relational queries. We start from a simple object-centered representationcommon 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 tospecify appropriate uniqueness constraints to satisfy the requirements on referring expressions. We thenshow 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 aconcrete 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 informationsystems based on ontologies, and on how such issues can be comprehensively addressed. The approach toobject identification discussed in the tutorial naturally and seamlessly complements standard approachesin 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 descriptionlogics) and formalisms is assumed.
Outline of the Tutorial
What is a referring expression?We start with an introduction and overview of how well formedformulae that satisfy certain properties can serve as referring expressions in information systemswhose 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 conformsto 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 approachesdesigned to indirectly and/or symbolically capture identities of (sets of) objects.
Referring expression types and query answering.We show how referring expressions can be usedto enrich query answers over knowledge bases by allowing to refer to answer objects that may nothave an explicit name within the KB, or for which a more preferred way of communicating itsidentity is available. To control the form of the answers, we define a type language that describesvarieties of referring expressions desired in query answers.
Referring expression types in conceptual modelling.Finally, we explore the benefits of adoptingreferring expression types for use in information systems derived from conceptual modelling. Inparticular, we show how this approach can separate the purely conceptual ontology design fromissues connected with how objects are identified within an eventual information system based onthe design.
Open problems
We conclude the tutorial with an outline of directions for further research, and with alist 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 thearea of Ontology-based data access (OBDA) [1] and received the Ray Reiter Best Paper prize at KR2016 for this work. They subsequently extended this work to the area of conceptual modelling [2] andother areas connected with ontological reasoning and knowledge representation. They have published andpresented 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 temporalrepresentation and reasoning that led to an invited chapter in the Handbook of Temporal Reasoning inArtificial Intelligence.
References
[1] Alexander Borgida, David Toman, and Grant Weddell. On referring expressions in query answeringover first order knowledge bases. In Principles of Knowledge Representation and Reasoning, CapeTown, SA, pages 319-328, 2016.
[2] Alexander Borgida, David Toman, and Grant E. Weddell. On referring expressions in informationsystems derived from conceptual modelling. In Conceptual Modeling – 35th International Conference,ER 2016, Gifu, Japan, pages 183-197, 2016.