An English language question answering system for a large relational database

ABSTRACT

By typing requests in English, casual users will be able to obtain explicit answers from a large relational database of aircraft flight and maintenance data using a system called PLANES. The design and implementation of this system is described and illustrated with detailed examples of the operation of system components and examples of overall system operation. The language processing portion of the system uses a number of augmented transition networks, each of which matches phrases with a specific meaning, along with context registers (history keepers) and concept case frames; these are used for judging meaningfulness of questions, generating dialogue for clarifying partially understood questions, and resolving ellipsis and pronoun reference problems. Other system components construct a formal query for the relational database, and optimize the order of searching relations. Methods are discussed for handling vague or complex questions and for providing browsing ability. Also included are discussions of important issues in programming natural language systems for limited domains, and the relationship of this system to others.

REFERENCES

• 1: Brown, J. S. and Burton, R. R. Multiple representations of knowledge for tutorial reasoning. In Representation and Understanding, Bobrow, D. G. and Collins, A. Ed., Academic Press, New York, 1975, pp. 311-349.
• 2: Bruce, B. Case systems for natural language. Artificial Intelligence 6, 4 (Winter 1975), 327-360.
• 3: Carbonell, J. R. et al. On the psychological importance of time in a time-sharing system. Human Factors 10, 2 (April 1968), 135-142.
• 4: Codd, E. F. Seven steps to RENDEZVOUS with the casual user. Proc. IFIP TC-2 Working Conf. on Data Base Management Systems, (April 1974) North-Holland Publ. Co., Amsterdam, 1974, 179-200.
• 5: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 6: Codd, E. F. A data base sublanguage founded on the relational calculus. Proc. ACM-SIGFIDET Workshop on Data Description, Access and Control, Nov. 1971, ACM, New York, 35-68.
• 7: Codd, E. F. Relational completeness of data base sublanguages. Courant Computer Science Symposium 6: Data Base Systems, Prentice-Hall, New York, 1971, pp. 33-64.
• 8: Codd, E. F. Normalized data base structure: a brief tutorial. Proc. ACM-SIGFIDET Workshop on Data Description, Access, and Control, Nov. 1971, ACM, New York, 1971, 1-17.
• 9: Conrad, F. P. BROWSER: a user oriented information retrieval system. M.S. thesis, Dept. of Computer Science, U. of Illinois, Urbana, I11., Oct. 1976. (to be issued as Coordinated Science Lab. tech. rpt.)
• 10: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: Fillmore, C. The case for case. In Universals in Linguistic Theory, Bach and Harms Ed., Holt, Rinehart and Winston, New York, 1968.
• 12: Gabriel, R. P. and Waltz, D. L. Natural language based information retrieval. Proc. 12th Allerton Conf. on Circuit and Sys. Theory, U. of Illinois, Urbana, Oct. 1974, pp. 875-884.
• 13: Green, F. R. Implementation of a query language based on the relational calculus. M.S. thesis, Dept. of Computer Science, U. of Illinois, Urbana, 111., Oct. 1976. (to be issued as Coordinated Science Lab. tech. rpt.)
• 14: Hawkinson, L. The representation of concepts in OWL. Adv. papers 4th Intl. Joint Conf. on Artificial Intelligence, Tbilisi, U.S.S.R. Sept. 1975, 107-114. (available through MIT A1 Lab., Cambridge, Mass.)
• 15: Heidorn, G. E. Automatic programming through natural language dialogue: a survey. IBM J. Res. Develop. 20, 4 (July 1976), 302-313.
• 16: Hendrix, G. G. Human engineering for applied natural language processing. Proc. Fifth Intl. Joint Conf. on Artificial Intelligence, MIT., Cambridge, Mass., Aug. 1977, 183-191. (Available through Comp. Sci. Dept. Carnegie-Mellon Univ., Pittsburgh, PA.)
• 17: Malhotra, A. Knowledge-based English language systems for management support: an analysis of requirements. Adv. Papers 4th Intl. Joint Conf. on Artificial Intelligence, Tbilisi, U.S.S.R. Sept. 1975, 842-847. (available through MIT AI Lab., Cambridge, Mass.)
• 18: Mylopoulos, J., Cohen, P., Borgida, A., and Sugar, L. Semantic networks and the generation of context. Adv. Papers 4th Intl. Joint Conf. on Artificial Intelligence, Tbilisi, U.S.S.R. Sept. 1975, 134-142. (available through MIT AI Lab., Cambridge, Mass.)
• 19: Mylopoulos, J., Borgida, A., Cohen, P., Roussopoulos, N., Tsotsos, J., and Wong, H. TORUS--a natural language understanding system for data management. Adv. Papers 4th Intl. Joint Conf. on Artificial Intelligence, Tbilisi, U.S.S.R. Sept. 1975, 414--421. (available through MIT AI Lab., Cambridge, Mass.)
• 20: NALDA (Naval Air Logistics Data Analysis) system data requirements determination report. Naval Aviation Integrated Logistics Support Center, Patuxent River, MD.
• 21: Palermo, F. P. A data base search problem. 4th Intl. Symp. on Computer and lnfo. Technology, Dec. 1972, Plenum Press, New York, 1972, 67-101.
• 22: Petrick, S. R. On natural language based computer systems. IBM J. Res. Develop. 20, 4 (July 1976), 314-325.
• 23: Schank, R. C. Identification of conceptualizations underlying natural language. In Computer Models of Thought and Language, Schank, R. C. and Colby, K. M. Ed., Wott, Freeman, San Francisco, CA, 1973, 187-247.
• 24: Sowa, J. F. Conceptual graphs for a data base interface. IBM J. Res. Develop. 20, 4 (July 1976), 336-357.
• 25: Tenczar, P. J. and Golden, W. M. Spelling, word, and concept recognition. Rep., Computer-based Education Research Lab., U. of Illinois, Urbana, 1972.
• 26: Waltz, D. L. Natural language access to a large database: an engineering approach. Adv. Papers 4th Intl. Joint Conf. on Artificial Intelligence, Tbilisi, U.S.S.R. Sept. 1975, 868-872. (available through MIT AI Lab., Cambridge, Mass.)
• 27: Waltz, D. L. Natural language to a large database. Naval Research Reviews XXIX, 1 (Jan. 1976), 11-25. Reprinted in Computers and People 25, 4 (April 1976), 19-26.
• 28: Waltz, D. L. and Goodman, B. A. Writing a natural language database system. Proc. Fifth International Joint Conference on Artificial Intelligence, MIT, Cambridge, Mass., Aug. 1977, pp. 144-150. (available through CS Dept., Carnegie-Mellon Univ., Pittsburgh, PA.)
• 29: Wilks, Y. A preferential, pattern-seeking, semantics for natural language inference. Artificial Intelligence 6, 1 (Spring 1975), 53-74.
• 30: Terry Winograd, Understanding Natural Language, Academic Press, Inc., Orlando, FL, 1972
• 31: W. A. Woods, Transition network grammars for natural language analysis, Communications of the ACM, v.13 n.10, p.591-606, Oct. 1970 [doi>10.1145/355598.362773]
• 32: Woods, W. A., Kaplan, R. M., and Nash-Webber, B. The lunar sciences natural language system: final report. Rep. No. 2378, Bolt Beranek and Newman Inc., Cambridge, Mass., 1972.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Natural language

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Natural language interfaces

General Terms:
Design, Human Factors, Languages, Management, Performance, Theory

Keywords:
artificial intelligence, database front end, dialogue, information retrieval, natural language, natural language programming, query generation, question answering, relational database