Relaxation as a Platform for Cooperative Answering
Computer Science Department,
University of Maryland
The complete paper is available in:
Responses to queries posed by a user of a database do not
always contain the information desired. Database answers to a query,
although they may be logically correct, can sometimes be misleading.
Research in the area of cooperative answering for databases and
deductive databases seeks to rectify these problems. We introduce a
cooperative method called relaxation for expanding deductive database
and logic programming queries. The relaxation method expands the scope
of a query by relaxing the constraints implicit in the query. This
allows the database to return answers related to the original query as
well as the literal answers themselves. These additional answers may be
of interest to the user. In section 1 we introduce the problem and
method. In section 2 we give some background on the research done in
cooperative answering. Section 3 discusses the relaxation method, a
potental control strategy, and uses. Section 4 looks at a semantic
counterpart to this notion. In section 5 we explore some of the control
and efficiency issues. We enumerate open issues in section 6, and
conclude in section 7. This work was supported by the Air Force Office
of Scientific Research under grant number AFSOSR-91-0350. ^L
Relaxation as a Platform for Cooperative
Answering p. 1 of 21
[AKN86] H. A"it-Kaci and R. Nasr. LOGIN: A Logic Programming
Language with Built-In Inheritance. Journal of Logic Programming,
3(3):185-215, October 1986.
[AP86] J. F. Allen and C. R. Perrault. Analyzing
intention in utterances. In Barbara J. Grosz, Karen Sparck
Jones, and Bonnie Lynn Weber, editors, Readings in Natural Language
Processing, pages 441-458. Morgan Kaufmann Publishers, Inc., Los Altos,
[BKM90] C. Baral, S. Kraus, and J. Minker. Communicating between
multiple knowledge based systems with different languages. In Draft
Proceedings of the International Working Conference on Cooperative
Knowledge Based Systems, pages 121-125, University of Keele, England,
October 3-5, 1990.
[Bra83] R. J. Brachman. What IS-A Is and Isn't: An Analysis of
Taxonomic Links in Semantic Networks. Computer, 16(10):30-36, October
[CCL90] W. W. Chu, Q. Chen, and R. Lee. Cooperative query
answering via type abstraction hierarchy. Technical report, University
of California at Los Angeles, October 1990. Relaxation as a Platform
for Cooperative Answering p. 20 of 21
[CD88] F. Cuppens and R. Demolombe. Cooperative answering: a
methodology to provide intellegent access to databases. In Larry
Kershberg, editor, Proc. of the Second International Conference on
Expert Database System, pages 333-353, George Mason University, April
[CD89] F. Cuppens and R. Demolombe. How to recognize
interesting topics to provide cooperative answering. Information
Systems, 14(2):163-173, 1989.
[Cha85] U. Chakravarthy. Semantic Query Optimization in Deductive
Databases. PhD thesis, University of Maryland, Department of Computer
Science, College Park, 1985.
[Che76] P. P. S. Chen. The entity-relationship model: Towards a
unified view of data. ACM Transactions on Database Systems, 1(1), March
[End72] H. B. Enderton. A Mathematical Introduction to Logic.
Academic Press, New York, New York, 1972.
[Gal88] A. Gal. Cooperative Responses in Deductive Databases.
PhD thesis, Department of Computer Science, University of Maryland,
College Park, 1988.
[GGL+ 90] T. Gaasterland, M. Giuliano, A. Litcher, Y. Liu, and J.
Minker. Using integrity constraints to control search in knowlege base
systems. Technical Report UMIACS-TR-90-27, CS-TR-2416, University of
Maryland, College Park, Dept. of Computer Science, 1990.
[GM85] A. Gal and J. Minker. A Natural Language Database
Interface that Provides Cooperative Answers. Proceedings of the Second
Conference on Artificial Intelligence Applications, December 11-13,
[GM88] A. Gal and J. Minker. Informative and Cooperative Answers
in Databases Using Integrity Constraints. In V. Dahl and P.
Saint-Dizier, editors, Natural Language Understanding and Logic
Programming, pages 277-300. North Holland, 1988.
[GM90] A. Gal and J. Minker. Producing cooperative answers in
deductive databases. In P. Saint-Dizier and S. Szpakowics, editors,
Logic and Logic Grammar for Language Processing. L.S. Horward, Ltd.,
[GMR90] T. Gaasterland, J. Minker, and A. Rajasekar. Deductive
Database Systems and Knowledge Base Systems. In Proceedings of VIA 90,
Barcelona, Spain, October 1990.
[Imi88] T. Imielinski. Intelligent Query Answering in Rule Based
Systems. In J. Minker, editor, Foundations of Deductive Databases and
Logic Programming. Morgan Kaufman Publishers, Washington, D.C., 1988.
[Jan81] J. M. Janas. On the feasiblity of informative answers. In
H. Gallaire, J. Minker, and J.M. Nicolas, editors, Advances In Database
Theory: Volume 1, pages 397-414. Plenum Press, New York, 1981.
[Kap82] S. Jerrold Kaplan. Cooperative responses from a portable
natural language query system. Artificial Intelligence, 19(2):165-187,
[Kow79] R.A. Kowalski. Logic for Problem Solving. Artificial
Intelligence Series. North-Holland, New York, 1979.
[Llo87] J.W. Lloyd. Foundations of Logic Programming.
Springer-Verlag, second edition, 1987.
[McC88] K. McCoy. Reasoning on a highlighted user model to respond
to misconceptions. Computational Linguistics, 14:52-63, September
[McS76] James McSkimin. The Use of Semantic Information in
Deductive Question-Answering Systems. PhD thesis, University of
Maryland, Department of Computer Science, College Park, 1976.
[MM77] J. R. McSkimin and J. Minker. A predicate
calculus based semantic network for questionanswering systems.
Technical report, Department of Computer Science, University of
Maryland, March 1977.
[MM79] J.R. McSkimin and J. Minker. Predicate Calculus
Based Semantic Network for QuestionAnswering Systems. In N.
Findler, editor, Associative Networks - The Representation and Use of
Knowledge in Computers, pages 205-238. Academic Press, New York, 1979.
[Mot86a] A. Motro. Extending the Relational Model to Support Goal
Queries. In Proceedings from the First International Workshop on
Expert Database Systems, pages 129-150. Benjamin/Cummings, 1986.
[Mot86b] A. Motro. SEAVE: A Mechanism for Verifying User
Presuppositions in Query Systems. ACM Transactions on Office
Information Systems, 4(4), October 1986.
[Mot90] A. Motro. FLEX: A Tolerant and Cooperative User Interface
to Database. IEEE Transactions on Knowledge and Data Engineering,
2(2):231-245, June 1990.
[NY78] J-M. Nicolas and K. Yazdanian. Integrity checking in
deductive databases. In H. Gallaire J. Minker, editor, Logic and
Databases, pages 325-599. Plenum, New York, 1978.
[Pol83] M. Pollack. Generating Expert Answers through Goal
Inference. Technical report, SRI International, Stanford,CA, October
[Rei88] R. Reiter. On Integrity Constraints. In M. Vardi, editor,
Proceedings of the Second Conference on Theoretical Aspects of
Reasoning and Knowledge, pages 97-111. Morgan Kaufmann Publishers,
[Rei90] R. Reiter. On Asking What a Database Knows. In J. W.
Lloyd, editor, Computational Logic: Symposium Proceedings.
Springer-Verlag, November 1990.
[SM87] C. Shum and R. Muntz. Implicit Representation for
Extensional Answers. In Larry Kershberg, editor, Expert Database
Systems, Tysons Corner, VA, 1987.
[SS86] L.S. Sterling and E.Y. Shapiro. The Art of Prolog. MIT
[WMB83] W. Wahlster, H. Marburger, and A. Jameson S. Busemann.
Over-Answering Yes-No Questions: Extended Responses in a NL Interface
to a Vision System. In Proceedings of IJCAI 1983, Karlsruhe, West
Germany, August 1983.