Cooperative Responses in Deductive Databases

Annie Gal

PhD Thesis
Computer Science Department
University of Maryland
College Park

The complete paper is available in:

PostScript

Abstract

This thesis addresses the problem of full utilization of the semantics already present in a database, and particularly, integrity constraints, to respond more cooperatively to a questioner. This thesis provides a new use for database integrity constraints, primarily used for maintaining database consistency during updates.

We specify a general apprach to the problem. We explain how to collect information relevant to the user's query, so as to give the user a cooperative response. Then, we describe rules to select from among the collected information, to provide a clear and concise informative answer to the questioner. A general set of heuristic rules are offered for that purpose. An implementation of this approach in the form of a natural language interface is provided.

Our approach to generating cooperative responses is domain-independent, although it uses domain-specific information (contained in the form of integrity constraints, the user's query and the database itself). The method utilizes knowledge already present in a database and can be applied to any deductive database (and also any relational database, since deductive databases are generalizations of relational databases).

Bibliography

[All82] Allen J.: ``Recognizing Intentions from Natural Language Utterances'' in "Computational Models of Discourse," M. Brady edts., MIT Press, 1982.
[Apt87] Apt A.K.: ``Maintenance of Stratified Databases Viewed as a Belief Revision System'', in proceedings ACM-SIGACT-SIGMOD-SIGART-6, Symposium on Principles of Database Systems, San Diego, California, March 1987.
[BR86] Bancilhon F. and Ramakrishnan R.: ``Performance Evaluation of Data Intensive Logic Programs, proceedings of Workshop on Foundations od Deductive Databases and Logic Programming, J. Minker Edts, Washington D.C, August 1986.
[Cad76] Cadiou J.M. ``On Semantics Issues in the Relational Model of Data'' in proceedings of International Symposium of Mathematical Foundations of Computer Science, "Lecture Notes in Computer Science," Spinger-Verlag, Heindelberg, 1976.
[Car83] Carbonell J. and Hayes P.: ``Recovery Strategies for Parsing Extragrammatical Language'' in "American journal of Computational Linguistics," Vol 9, No:3-4, 1983.
[CD88] Cuppens F., Demolombe R.: ``Cooperative Answering: A Methodology to Provide Intelligent Access to Databases'' in proceedings of Expert Database Systems II, Tysons Corner, Virginia, USA, April 1988
[CGM86] Chakravarthy, U.S., Grant J. and Minker J.: ``Foundations of Semantic Query Optimization for Deductive Databases'' in proceedings of Workshop on Foundations od Deductive Databases and Logic Programming, J. Minker Edts, Washington D.C, August 1986.
[Cha83] Charniak E.: ``A Parser with Something for Everyone'' in "Parsing Natural Language," M. King edts., Academic Press, 1983.
[Cha85] Chakravarthy, U.S.: ``Semantics Query Optimization in Deductive Databases'', PhD Thesis, University of Maryland, USA, 1985.
[CL73] Chang C.L and Lee R.C.T: "Symbolic Logic an Mechanical Theorem Proving," Academic Press, New-York, 1973.
[CP79] Cohen P. and Perrault C.: ``Elements of Plan-Based Theory for Speech Acts'', "Cognitive Science," Vol 3, N03, p177-212.
[CP81] Colmerauer A. et Pique J.F.:``About natural Logic'', in "Advances in Database theory," H.Gallaire, J.M. Nicolas et J.Minker edts., Plenum Press, 1981.
[Dat86] Date C.J.: "An Introduction to Databases Systems," 4th edition, Addison-Wesley, Reading, Ma, USA, 1986.
[Del80] Delobel C.: ``Normalization and Hierarchical Dependencies in the Relational Model'' in proceedings IFIP80, North Holland, Amsterdam.
[Fag81] Fagin R.: ``A Normal Form for Relational Databases that is Based on Domains and Keys'' in "ACM Transactions on Databases Systems," Vol 6, N0 3, P387-415, 1981.
[GNM84] Gallaire H., Minker J. et Nicolas J.M.: ``Logic and Databases: A deductive approach'' in "ACM Computing Surveys," Vol 16, 1984.
[Gre69] Green C.: ``Theorem Proving by Resolution as a Basis for Question-Answering systems'' in "Machine Intelligence," Vol 4, p183-205, 1981
[Gri75] Grice H.: ``Logic and Conversation'' in "Syntax and Semantics," P. Cole et J. Morgan edts., Academic Press, 1975.
[Hir85] Hirschberg J. :``Toward a Redefinition of Yes-No Questions'', in procedings of COLING10, Standford University, California, USA, July 1984.
[Jan81] Janas, J.M.: ``On the feasibility of Informative Answers'' in "Advances in Database Theory" H. Gallaire, J. Minker and J.M. Nicolas edts., Plenum-Press, 1981.
[Jos82] Joshi, A.: ``Mutual Beliefs in Question Answering Systems'' in "Mutual Beliefs" N. Smith edts, Academic Press, 1982.
[Kap82] Kaplan J.: ``Cooperatives Responses from a Portable Natural Language Database Query System'' in "Computational Models of Discourse," M. Brady edts., MIT Press, 1982.
[Kow81] Kowalski R.A. :``Logic as a Database Language'', in proceedings of the Advanced Seminar on Theoritical Issues in Databases, Cetraro, Italy, September 1981.
[Leh81] Lehnert W.: ``A Computational Theory of Human Question Answering'' in "Elements of Discourse Understanding," A. Joshi et B. Webber et I. Sag edts.,Cambridge University Press, 1981.
.ip [Lob88] Lobo, J., Minker, J.: ``A Metaprogram Approach to Semantically Optimize Queries in Deductive Databases'', in proceedings of Expert Database Systems II, Tysons Corner, Virginia, USA, April 1988
.ip "[LT85,86] Lloyd J.W. et Topor R.W. :``A basis for deductive database Systems'', in "Journal of Logic Programming," July 1985 and April 1986.
[May80] Mays E.: ``Correcting Misconceptions about Database Structure'' in proceedings CSCSI80.
[McC85] McCoy K. :``Correcting Object-Related Misconceptions'', in proceeedings of COLING10, Standford University, California, USA, July 1984.
[NG78] Nicolas J.M. and Gallaire H.: ``Database: Theory vs Interpretation'', in "Logic and Databases" H. Gallaire and J. Minker edts., Plenum-Press, New-York, 1978.
[Pol85] Pollack M.: ``Information Sought and Information Provided'', in proceedings Chi'85, Association for Computing Machinery, San Francisco, California, USA, April 1985.
[Prz86] Przymusinski C.: ``On the Semantics of Stratified Deductive Databases'' in proceedings of Workshop on Foundations od Deductive Databases and Logic Programming, J. Minker Edts, Washington D.C, August 1986.
[Rei78a] Reiter, R.: ``On Closed World Databases'' in "Logic and Databases" H. Gallaire and J. Minker edts., Plenum-Press, New-York, 1978.
[Rei78b] Reiter, R.: ``Deductive Question-Answering on Relational Databases'' in "Logic and Databases" H. Gallaire and J. Minker edts., Plenum-Press, New-York, 1978.
[Rei84] Reiter R.: ``Toward a Logical Reconstruction of Relational Model Theory'', in "On Conceptual Modeling," M. Brodie et J. Mylopoulos and J.W. Smitdt edts., Springer Verlag, 1984.
[Rei86] Reiter R.: ``On Integrity Constraints'', in proceedings of Theoretical Aspects of Reasoning About Knowledge II, Asimolar, California, 1988.
[Rob65] Robinson J.A.: ``A Machine oriented Logic Based on the Resolution Principle'' in JACM, Vol 12, p23-41.
[Sdi83] St-Dizier P.:``Etude et Re\*'alisation de Esope'', the\*`se, Universite\*' de Rennes, France, 1983.
[Wah83] Wahlster W., Marburger H., Jameson A. et Busemann S. :``Over-Answering Yes-No Questions: Extended Responses in a NL Interface to a Vision System'', in proceedings IJCAI83, Karlsruhe, West Germany, August 1983.
[Web86] Webber B.: ``Questions, Answers and Responses: Interacting with Knowledge Base Systems'' in "On Knowledge Base Management Systems," M. Brodie et J. Mylopoulos edts., Springer Verlag, 1986.