Interpretation of natural language database queries using optimization methods (linguistics)
William E. Leigh · 1984
The automatic interpretation of natural language (in this work, English), database questions formulated by a user untrained in the technical aspects of database querying is an established problem in the field of artificial intelligence. State-of-the-art approaches involve the analysis of queries with syntactic and semantic grammars expressed in phrase structure grammar or transition network formalisms. With such methods difficulties exist with the detection and resolution of ambiguity, with the mis-interpretation possibilities inherent with finite length look-ahead, and with the modification and extension of a mechanism for other sources of semantic knowledge. This work examines the potential of optimization techniques to solve these problems and interpret natural language, database queries. The proposed method involves developing a 0-1 integer programming problem for each query. The possible values that the set of variables in the optimization may take on is an enumeration of possible such individual associations between the database schema and the query. The solution to the integer programming problem corresponds to a single assignment of database data items and relationships to the words in the query. Constraints are derived from syntactic and database schema knowledge stored as libraries of templates. An objective function is used to rank the possible associations as to their likelihood of agreement with the intent of the questioner. A test mechanism was built to support evaluation of the proposed method. Suitable knowledge source template sets and an objective function were developed experimentally with the test mechanism from a learning sample of queries. Then the performance of the method was compared to that of an established system (PLANES) on a test set of queries. The performance of the new method was found to be comparable to that of the established system.