Issues in Natural Language Access to Databases from a Logic Programming Perspective

David H. D. WarrenACL 1982 · DOI

TL;DR

This paper explores natural language (NL) access to databases through the lens of logic programming, specifically detailing the "Chat" system. It argues that logic programming, particularly Prolog, offers a more general and efficient approach to NL interfaces than traditional database systems, enabling interaction with both databases and general programs.

What Problem Does This Paper Address?

The paper tackles the challenge of enabling users to query databases using natural language. Traditional approaches often struggle with the complexity of NL, leading to rigid interfaces and limitations in what users can ask. The authors highlight that current NL interfaces are often restricted to databases, while users would benefit from NL access to broader computer systems. They propose that the limitations of existing database management systems hinder the development of truly flexible NL interfaces, suggesting a shift towards designing "back-end" systems that can support NL interaction rather than forcing NL to fit existing database structures.

Methods

The core of the approach is the use of logic programming, specifically Prolog, as the underlying mechanism for both representing database information and processing NL queries. The "Chat" system employs a three-stage process:

  1. Translation: NL questions are translated into a logic-based representation called "definite closed world" (DCW) logic. DCW logic is a subset of first-order logic that uses "definite" statements and incorporates the "closed world" assumption (what is not known to be true is false).
  2. Planning: This stage is analogous to query optimization in relational databases. The logical form of the NL query is transformed into efficient Prolog code.
  3. Execution: The generated Prolog code is directly executed to produce the answer.

The paper also discusses extensions to DCW logic to handle aggregate functions (using setof(X,P,S)) and a novel approach to managing quantifiers and complex semantic fields within NL queries.

Datasets

Not discussed in the paper. The paper focuses on the system's architecture and approach, using the domain of world geography as an example for query processing.

Key Insights and Ideas

  • Logic Programming as a Unifying Framework: The paper strongly advocates for logic programming (Prolog) as a superior paradigm for NL access to databases. It bridges the gap between the "bottom-up" relational database approach and the "top-down" NL understanding, offering a more general computational formalism.
  • DCW Logic for Efficiency: The choice of "definite closed world" logic is driven by its efficient implementability within Prolog, allowing for fast query processing.
  • Beyond Databases: The logic programming approach allows NL interfaces to interact with general programs, not just databases, significantly expanding their utility.
  • Database Design for NL: The authors suggest that databases should be designed to accommodate NL queries, rather than forcing NL interfaces to conform to existing database limitations. Primitive facts should be stored, with complex information derived through general rules.
  • Handling Plural "The": A significant challenge identified is the precise semantics of plural noun phrases with the definite article ("the"). The paper proposes an "indexed set" approach to handle complex nested definite noun phrases, though acknowledges it's somewhat ad hoc.

Key Results

  • The "Chat" system, using this logic programming approach, can answer most queries in its world geography domain in well under one second.
  • Queries involving joins on relations with thousands of tuples are handled efficiently.
  • The system demonstrates the ability to translate NL queries into logical forms and then into executable Prolog code for efficient retrieval.

Limitations and Future Work

  • Database Size: Current Prolog systems, designed for programming, are not inherently optimized for very large databases. The authors suggest there's no technical obstacle to building Prolog systems comparable to relational database management systems in terms of scale.
  • Semantics of Plural "The": While an approach is presented, the paper acknowledges that defining a coherent and intuitively correct semantics for plural "the" that is compatible with efficient database access remains a pressing problem.
  • Indexed Sets: The treatment of indexed sets, while functional, is described as "somewhat ad hoc," suggesting room for further theoretical development.
  • Future Work: The authors anticipate the development of Prolog systems capable of handling large databases and expect further advancements in defining the semantics of complex NL constructs.

Summary updated

BibTeX
@inproceedings{warren1982issues,
  author = {David H. D. Warren},
  title = {{Issues in Natural Language Access to Databases from a Logic Programming Perspective}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1982},
  doi = {10.3115/981251.981266},
}

Loading related content...

Figure