Introduction
In the field of Natural Language Interfaces to Databases (NLIDB), a persistent challenge is the "Compositional Gap." This gap exists between the high-level, compositional semantics of natural language and the specific, often idiosyncratic structure of a target database. When a user asks a question, a natural language system typically generates a formal logical expression. However, mapping this expression to the actual fields and tables of a database is rarely straightforward.
This paper presents a "Recursive Terminological Simplification" algorithm designed to bridge this gap. By utilizing a taxonomic knowledge representation system (NIKL), the proposed method transforms complex logical forms into simplified versions that align more closely with database predicates, thereby making the mapping process more robust and maintainable.
The Problem: The Compositional Gap
Traditional approaches to mapping natural language to databases generally fall into two categories: local mapping rules and global pattern-matching rules.
- Local Rules: These map individual predicates in a logical form directly to database entities. While simple, they fail when a single database field represents a complex combination of concepts. For example, a database might store information about a patient's mother having diabetes in a single boolean field called
DIAMOTHER. A local rule cannot easily map the multi-word phrase "patient's mother is a diabetic" to this single field. - Global Rules: These use large-scale patterns to match entire sub-expressions. While more powerful, they suffer from a combinatorial explosion. Because natural language is highly flexible—allowing users to say "female parent" instead of "mother" or use different types of quantification—a global pattern matcher would require a unique rule for every possible linguistic variation of the same underlying concept.
Methodology: Recursive Terminological Simplification
The author, David Stallard, proposes an intermediate processing level that uses the NIKL (New Information KL-ONE) system. NIKL is a taxonomic knowledge representation tool that includes a "classifier"—an inference engine capable of determining the relationship between different concepts based on their definitions.
The simplification process occurs in two primary phases:
1. The Contraction Phase
The contraction algorithm recursively traverses the logical expression generated from the user's query. It uses the NIKL classifier to identify when a complex set of nested quantifiers and predicates is equivalent to a more specific, pre-defined concept in the taxonomy. For instance, if the system encounters a definition for "a person whose mother is a diabetic," the classifier can collapse that entire logical structure into a single taxonomic node (e.g., DIABETIC-MOTHER-PATIENT). If the database has a direct mapping for this specific node, the translation becomes trivial.
2. The Role-Tightening Phase
Following contraction, the system performs "role-tightening." This involves examining the "sorts" or types of variables within the expression. If a query uses a generic relation (such as SEX) but the variable involved is known to be of a specific type (such as DOCTOR), the system specializes the relation to a more specific one (e.g., DOCTOR-SEX). This specific relation often maps directly to a particular column in a database table, such as a SEX column within a DOCTORS table, rather than a general PERSONNEL table.
Conceptual Framework: "Sinking" the Expression
The paper introduces a compelling metaphor for this process: "sinking" the logical expression. The goal is to push the high-level logical form deeper into the "logical space" of the domain model until it reaches the level of the database predicates. By using inference rather than literal string matching, the system ensures that different linguistic expressions of the same concept (e.g., "female parent" vs. "mother") eventually "sink" to the same taxonomic node.
From a model-theoretic perspective, this transformation allows the database to be viewed as a partially specified model of the world. The simplification algorithm essentially translates the user's query into the specific vocabulary of that model.
Implementation and Results
The algorithm was implemented and tested within IRUS, a natural language question-answering system developed for the Navy battle-management domain as part of DARPA’s Strategic Computing Program. While the paper does not provide modern quantitative benchmarks, it offers a qualitative proof of concept through its integration into this complex, real-world domain.
Key results include:
- Restoration of Local Rules: By simplifying the logic before mapping, developers can return to using simple, maintainable local rules for individual predicates rather than maintaining an unmanageable library of global patterns.
- Robustness to Variation: The system successfully handles variations in phrasing and quantification by resolving them to the same underlying taxonomic concepts through NIKL inference.
- Handling "Overshoot": In cases where the simplifier creates a concept that the database does not directly support, the paper describes a "back-conversion" process. The system can look at the definition of the new concept and recursively generate the necessary database query logic.
Limitations and Future Work
The author identifies two primary limitations to this approach:
- Undecidability: Finding the absolute simplest form of a logical expression is a mathematically undecidable problem. However, the algorithm is designed to be practically effective, reaching a "close enough" simplification for database mapping purposes.
- Modeling Overhead: The effectiveness of the system is entirely dependent on the quality of the NIKL domain model. Constructing a comprehensive taxonomy that accurately reflects both the domain and the database schema requires significant expert effort.
Future research directions include applying terminological simplification to other areas of automated reasoning beyond database interfaces, such as general deductive operations and theorem proving.
Summary updated