Concerning Referring Expressions in Query Answers

Alexander Borgida, David Toman, Grant E. WeddellIJCAI 2017 · DOI

TL;DR

This paper introduces "singular referring expressions" as a more human-friendly way to present query answers from knowledge bases. Instead of just returning opaque identifiers, it proposes using descriptive formulas that uniquely identify individuals, making answers more interpretable and useful.

What Problem Does This Paper Address?

Traditional query answering systems in databases and knowledge bases typically return answers as constant symbols or identifiers. These identifiers are often system-generated and lack semantic meaning, making it difficult for users to understand what real-world object they refer to. For instance, an identifier like "/guid/9202a8c04000641f8000000002f9e349" for an album is uninformative. This problem is exacerbated in large knowledge bases, when merging databases, or when dealing with complex data models. Furthermore, some individuals might not have explicit identifiers but can be described through their relationships to other known entities (e.g., "Fred's mother"). The paper aims to bridge this gap by allowing query answers to be more descriptive, natural language-like expressions that still guarantee unique identification of the intended individual.

Methods

The core of the paper's contribution lies in defining and formalizing "singular referring expressions" (REs) and "referring expression types" (RETs).

  • Referring Expressions (REs): These are defined as formulas with a single free variable that identify individuals. The paper proposes a framework where query answers can be RE-substitutions, mapping query variables to these REs.
  • Singularity: A crucial property is that these REs must be "singular," meaning they uniquely identify one individual within the knowledge base. This is formally defined by checking if, for a given query and knowledge base, any two individuals satisfying the RE are necessarily the same.
  • Referring Expression Types (RETs): To manage the potentially infinite space of REs and to control their complexity, the authors introduce RETs. These are syntactic patterns that specify the allowed structure and properties of REs. RETs can involve paths, unary predicates (guards), conjunctions, and preferences.
  • Typed Queries: Queries can be "typed" by associating RETs with their free variables. This allows for compile-time analysis to ensure that the REs generated for answers will be singular, regardless of the specific data in the knowledge base.
  • Query Answering Algorithm: A procedure is outlined that uses an oracle for standard query answering and then leverages the typed queries and RETs to reconstruct singular referring expressions. This involves normalizing preferences, creating auxiliary queries, evaluating them, resolving preferences, and finally constructing the RE from retrieved constant symbols.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Semantic Gap: The most significant insight is the formalization of descriptive, yet uniquely identifying, expressions as query answers. This moves beyond opaque IDs to more human-understandable representations.
  • The Importance of "Singularity": The paper rigorously defines and emphasizes the need for REs to be singular. This is key to ensuring that the descriptive answer actually points to a single, unambiguous individual, which is the fundamental goal of query answering.
  • Controlling Complexity with Types: The introduction of RETs is a clever way to make the problem tractable. By defining types, the system can reason about the potential for singularity at compile time, before specific data is even considered. This allows for a separation of concerns between ontology design and data instance handling.
  • Separation of Concerns: The authors advocate for separating the task of identifying which objects to return from how to describe them. RETs facilitate this by allowing users to specify preferences for identification strategies.
  • Generalization of Answers: The framework naturally extends from simple constant symbols to more complex, yet still singular, formulas, accommodating cases where individuals are identified by relationships or properties.

Key Results

The paper provides a formal framework for defining and computing singular referring expressions as query answers. It introduces the concept of referring expression types and demonstrates how they can be used to ensure that answers are not only descriptive but also uniquely identifying. The authors present an algorithm for query answering that leverages these concepts and prove its correctness under certain conditions (Theorem 5). They also discuss how this framework can be applied to Description Logics (DLs) and ontology-based data access (OBDA).

Limitations and Future Work

  • Completeness of REs: The paper acknowledges that the proposed language for REs is just one possibility and that other languages could be explored.
  • Tractability of Singularity Testing: While the framework aims for compile-time analysis, the actual testing of singularity (weak identification) can still be a logical implication problem, which might be computationally challenging depending on the underlying logic.
  • Application to Specific DLs: The paper outlines how the framework applies to DLs and OBDA, but further details and specific implementations for various DL dialects are left for future work or are referenced in other publications by the authors.
  • User Preference Modeling: While preferences are mentioned, the paper could explore more sophisticated ways of modeling and learning user preferences for referring expressions.
  • Real-world System Integration: The practical implementation and performance of such a system in real-world knowledge management platforms would be a significant area for future exploration.

Summary updated

BibTeX
@inproceedings{borgida2017concerning,
  author = {Alexander Borgida and David Toman and Grant E. Weddell},
  title = {{Concerning Referring Expressions in Query Answers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/668},
}
Figure