SEAVE: a mechanism for verifying user presuppositions in query systems

ABSTRACT

Every information system incorporates a database component, and a frequent activity of users of information systems is to present it with queries. These queries reflect the presuppositions of their authors about the system and the information it contains. With most query processors, queries that are based on erroneous presuppositions often result in null answers. These fake nulls are misleading, since they do not point out the user's erroneous presuppositions (and can even be interpreted as their affirmation). This article describes the SEAVE mechanism for extracting presuppositions from queries and verifying their correctness. The verification is done against three repositories of information: the actual data, their integrity constraints, and their completeness assertions. Consequently, queries that reflect erroneous presuppositions are answered with informative messages instead of null answers, and user-system communication is thus improved (an aspect that is particularly important in systems that often are accessed by naive users). First, the principles of SEAVE are described abstractly. Then, specific algorithms for implementing it with relational databases are presented, including a new method for storing knowledge and an efficient algorithm for processing queries against the knowledge.

REFERENCES

• 1: ARENS, Y. CLUSTER: An approach to contextual language understanding. Ph.D. dissertation, Dept. of Mathematics, Univ. of California, Berkeley, 1986.
• 2: Alexander Borgida, Language features for flexible handling of exceptions in information systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.565-603, Dec. 1985 [doi>10.1145/4879.4995]
• 3: CHAKRAVARTHY, U. S., AND MINKER, J. Processing multiple queries in database systems. Database Eng. 1, 1983.
• 4: Francisco Corella , S. Jerrold Kaplan , Gio Wiederhold , Lena Yesil, Cooperative Responses to Boolean Queries, Proceedings of the First International Conference on Data Engineering, p.77-85, April 24-27, 1984
• 5: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 6: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 8: Michael Hammer , Dennis Mc Leod, Database description with SDM: a semantic database model, ACM Transactions on Database Systems (TODS), v.6 n.3, p.351-386, Sept. 1981 [doi>10.1145/319587.319588]
• 9: Gary G. Hendrix , Earl D. Sacerdoti , Daniel Sagalowicz , Jonathan Slocum, Developing a natural language interface to complex data, ACM Transactions on Database Systems (TODS), v.3 n.2, p.105-147, June 1978 [doi>10.1145/320251.320253]
• 10: JARKE, M. Common subexpression isolation in multiple query optimization. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer-Verlag, New York, 1984.
• 11: Samuel Jerrold Kaplan, Cooperative responses from a portable natural language data base query system., 1979
• 12: KIM, W. Global optimization of relational queries. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer-Verlag, New York, 1984.
• 13: Michael Lebowitz, Generalization and memory in an integrated understanding system, 1980
• 14: LEVESQUE, H. J., AND BRACHMAN, R.J. A fundamental tradeoff in knowledge representation and reasoning. In Readings in Knowledge Representation, R. J. Brachman, and H. j. Levesque, Eds. Morgan Kaufmann, Los Altos, Calif., 1985, pp. 42-70.
• 15: A Motro, Query generalization: a method for interpreting null answers, Proceedings from the first international workshop on Expert database systems, p.597-616, January 1986, Kiawah Island, South Carolina, United States
• 16: Amihai Motro, Completeness Information and Its Application to Query Processing, Proceedings of the 12th International Conference on Very Large Data Bases, p.170-178, August 25-28, 1986
• 17: MOTRO, A. Supporting goal queries in relational databases. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S.C., Apr. 1-4). Institute of Information Management, Technology and Policy, Univ. of South Carolina, Columbia, S.C., 1986, pp. 85-96.
• 18: MYLOPOULOS, J., AND WONG, H. K.T. Some features of the TAXIS data model. In Proceedings of the 6th international Conference on Very Large Data Bases (Montreal, Canada, Oct. 1-3). ACM, New York, 1980, pp. 399-410.
• 19: Timos K. Sellis, Global query optimization, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.191-205, May 28-30, 1986, Washington, D.C., United States
• 20: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 21: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 22: Terry Winograd, Understanding Natural Language, Academic Press, Inc., Orlando, FL, 1972
• 23: ZLOOF, M. Query-by-example: A database language. IBM Syst. J. 16, 4 (Dec. 1977), 324-343.

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Design, Human Factors