Incomplete path expressions and their disambiguation

ABSTRACT

When we, humans, talk to each other we have no trouble disambiguating what another person means, although our statements are almost never meticulously specified down to very last detail. We “fill in the gaps” using our common-sense knowledge about the world. We present a powerful mechanism that allows users of object-oriented database systems to specify certain types of ad-hoc queries in a manner closer to the way we pose questions to each other. Specifically, the system accepts as input queries with incomplete, and therefore ambiguous, path expressions. From them, it generates queries with fully-specified path expressions that are consistent with those given as input and capture what the user most likely meant by them. This is achieved by mapping the problem of path expression disambiguation to an optimal path computation (in the transitive closure sense) over a directed graph that represents the schema. Our method works by exploiting the semantics of the kinds of relationships in the schema and requires no special knowledge about the contents of the underlying database, i.e., it is domain independent. In a limited set of experiments with human subjects, the proposed mechanism was very successful in disambiguating incomplete path expressions.

REFERENCES

• 1: Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990 [doi>10.1145/88636.88888]
• 2: Carlo Batini , Tiziana Catarci , Maria Francesca Costabile , Stefano Levialdi, Visual Query Systems: A Taxonomy, Proceedings of the IFIP TC2/WG 2.6 Second Working Conference on Visual Database Systems II, p.153-168, September 30-October 03, 1991
• 3: Daniel G. Bobrow , Allan Collins, Representation and Understanding: Studies in Cognitive Science, Academic Press, Inc., Orlando, FL, 1975
• 4: B Carte, Graphs and Networks, Clarendon Press, Oxford, England, 1979.
• 5: R. Chaffin, D. Herrmann, and M. Winston, An Emp#mcal Taxonomy of Part-Whole Relations : Effects of Part-Whole Relation Type on Relation Identzfication, Language and Cognitive Processes, Vol 3 (10), pp 17- 48, July 1988.
• 6: R. Chaffin and A. Glass, A Comparison of Hyponym and Synonym Decisions, J. of Psycholinguistic Research, Vol 19 (4)4 pp 265-280, 1990.
• 7: Wesley W. Chu , Matthew Merzbacher , Ladislav Berkovich, The design and implementation of CoBase, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.517-522, May 25-28, 1993, Washington, D.C., United States
• 8: P. Cohen and C. Loiselle, Beyond ISA: Structures for Plausible Inference in Semantic Networks, Proc 7th National Conference on Artificial Intelligence, St. Paul, MN, pp 415-420, August 1988.
• 9: A. Collins and M. Quillian, Retrzeval T#me From Semantzc Memory, J. of Verbal Learning and Verbal Behaviour, Vol 8, pp 240-247, 1969
• 10: F. Cuppens and R. Demolombe, Cooperatzve Answer- #ng: A Methodology to Provzde Intelligent Access to Databases, Proc. 2nd Expert Database Systems Conf., Tysons Corner, VA, pp 333-353, April 1988.
• 11: S. Fahlman, NETL: A System for Representing and Using Real World Knowledge, MIT Press, Cambridge, MA, 1979.
• 12: T. Gaasterland, P. Godfrey, and J. Minker, An Overvzew of Cooperatzve A nswemng, J. of Intelligent Information Systems, Vol 1 (2), pp 123-157, Oct. 1992.
• 13: Y. Ioannidis, M. Livny, E. Haber, R Miller. O. Tsatalos, and J. Wiener, Desktop Expemment Management, IEEE Data Engineering, March 1993.
• 14: Y. Ioanmdis (ed.), Advanced User Interfaces for Database Systems, ACM SIGMOD Record, Vol 20 (1), March 1992.
• 15: Yannis Ioannidis , Raghu Ramakrishnan , Linda Winger, Transitive closure algorithms based on graph traversal, ACM Transactions on Database Systems (TODS), v.18 n.3, p.512-576, Sept. 1993 [doi>10.1145/155271.155273]
• 16: T. Kunii (ed.), Vzsual Database Systems, North- Holland, Amsterdam, The Netherlands, 1989.
• 17: Y. Lashkari, Domain Independent Disambtguation of Vague Query Specifications, MS Thesis, CS Dept., Univ. of Wisconsin- Madison, July 1993.
• 18: David Maier , David Rozenshtein , David S. Warren, Windows on the world, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 19: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• 20: G. Miller and C. Fellbaum, Semantic Networks of English, Cognition, Vol 41 (1-3), pp 197-229, 1991.
• 21: A. Motro, FLEX: A Tolerant and Cooperative User Interface to Databases, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.231-246, June 1990 [doi>10.1109/69.54722]
• 22: J. Norman, and G. Campbell, Application of a Plant- Environment Model to Problems tn Irrigation, "Advances in Irrigation II', D. Hillel (ed), Academic Press, New York, NY, pp 155-188, 1983
• 23: Arnon Rosenthal , Sandra Heiler , Umeshwar Dayal , Frank Manola, Traversal recursion: a practical approach to supporting recursive applications, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.166-176, May 28-30, 1986, Washington, D.C., United States
• 24: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 25: D. S. Touretzky, Implicit ordering of defaults in inheritance systems, Readings in uncertain reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 26: Janet L. Wiener , Yannis E. Ioannidis, A Moose and a Fox Can Aid Scientists with Data Management Problems, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.376-398, August 30-September 01, 1993
• 27: M. Winston, R. Chaffin, and D. Herrmann, A Taxonomy of Part-Whole Relations, Cognitive Science, Vol 11, pp 417-444, 1987.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Algorithms, Experimentation, Languages, Performance