Interpreting Natural Language Database Updates

S. Jerrold Kaplan, Jim DavidsonACL 1981 · DOI

Abstract

While querying a database in plain English is a significant challenge, updating one is even more complex due to the inherent ambiguity of natural language. A single request can often be interpreted in numerous "literally correct" but semantically nonsensical ways. This paper introduces a system that leverages the logic of "minimal side effects" to automatically identify and execute the most reasonable update, ensuring that database modifications align with the user's actual intent.

Introduction

By 1980, natural language (NL) interfaces for databases were becoming increasingly common, though primarily focused on data retrieval. Extending these interfaces to handle updates introduced a major hurdle: ambiguity. For instance, a request to "Change the teacher of CS345 from Smith to Jones" could be interpreted as updating a relationship, changing a person's name, or even reassigning course numbers. While humans naturally filter out nonsensical interpretations using world knowledge, computers lack this context. The authors propose a method to bridge this gap without requiring an exhaustive "common sense" encyclopedia for every database.

Methodology: Language-Driven Inference

The proposed system employs a two-step process to resolve update ambiguities:

  1. Candidate Generation: To avoid an exhaustive search of all possible database changes, the system generates only those updates that directly correspond to the user's phrasing. By focusing on the specific entities and relationships mentioned (e.g., "teachers" and "courses"), the search space is significantly constrained.
  2. Heuristic Ranking: Drawing on David Lewis’s philosophical work on counterfactuals, the system treats an update as a "what if" scenario. It seeks the "nearest possible world"—the update that results in the fewest unintended "side effects" relative to the user's current view of the data.

The system maintains a record of the user's "view" (the data they have previously queried). Updates are ranked based on how much they disrupt this known view. Changes to data the user has not seen are prioritized over changes to data the user has recently inspected.

Implementation and Evaluation

The approach was tested using a pilot implementation in Interlisp on a DEC KL-10 computer, utilizing the LIFER parser and the SODA relational language. The test environment consisted of a small relational database with tables for Department/Manager (DM) and Employee/Department (ED).

Results: Resolving Ambiguity through Minimal Side Effects

The pilot system demonstrated effective decision-making in ambiguous scenarios. Consider the request: "Change Brown's manager from Jones to Baker." The system identifies two primary candidate translations:

  1. Move Brown to a different department that is already managed by Baker.
  2. Replace Jones with Baker as the manager of Brown's current department.
Initial state of the employee-manager relationship.

The system evaluates these options against the user's previous queries. If the user had recently queried the manager of another employee, Adams (who is also managed by Jones), Option 2 would have the side effect of changing Adams' manager as well. Since Option 1 achieves the user's goal without affecting other known records, it is selected as the intended update.

The resulting state after the system correctly chooses to update Brown's manager without affecting other employees.

Discussion and Future Work

The "nearest world" principle provides a mathematical framework for handling ambiguity and allows for domain independence, as the system does not need specific semantic knowledge of "Managers" or "Employees" to function. However, the authors note limitations:

  • Simplicity vs. Accuracy: Minimal side effects may occasionally reject complex, necessary updates that violate simple heuristics.
  • Heuristic Completeness: There is a need for a more formal mathematical characterization of "updates to views."
  • Knowledge Gaps: Future iterations could benefit from integrating case structure semantics or tracking dialog focus to better capture user intent.

Summary updated

BibTeX
@inproceedings{kaplan1981interpreting,
  author = {S. Jerrold Kaplan and Jim Davidson},
  title = {{Interpreting Natural Language Database Updates}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1981},
  doi = {10.3115/981923.981961},
}
Figure