Retrieval from hierarchical texts by partial patterns

ABSTRACT

Structured texts (for example dictionaries and user manuals) typically have a heirarchical (tree-like) structure. We describe a query language for retrieving information from collections of hierarchical text. The language is based on a tree pattern matching notion called tree inclusion. Tree inclusion allows easy expression of queries that use the structure and the content of the document. In using it a user need not be aware of the whole structure of the database. Thus a language based on tree inclusion is data independent, a property made necessary because of the great variance in the structure of the texts.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: J. André , R. Furuta , V. Quint, By way of an introduction. Structured documents: what and why?, Structured documents, Cambridge University Press, New York, NY, 1989
• 3: Jacques André , Vincent Quint , Richard Furuta, Structured documents, Cambridge University Press, New York, NY, 1989
• 4: Wolfgang Appelt, Document Architecture in Open Systems: The ODA Standard, Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• 5: D.L. Berg, G. H. Gonnet, and F. Win. Tompa. The New Oxford English Dictionary project at the University of Waterloo. Technical Report OED- 88-01, UW Centre for the New OED, 1988.
• 6: E. Bertino , M. Negri , G. Pelagatti , L. Sbattella, Object-Oriented Query Languages: The Notion and the Issues, IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.223-237, June 1992 [doi>10.1109/69.142014]
• 7: G. Elizabeth Blake , Tim Bray , Frank Wm. Tompa, Shortening the OED: experience with a grammar-defined database, ACM Transactions on Information Systems (TOIS), v.10 n.3, p.213-232, July 1992 [doi>10.1145/146760.146764]
• 8: Forbes J. Burkowski, An algebra for hierarchically organized text-dominated databases, Information Processing and Management: an International Journal, v.28 n.3, p.333-348, 1992 [doi>10.1016/0306-4573(92)90079-F]
• 9: Forbes J. Burkowski, Retrieval activities in a database consisting of heterogeneous collections of structured text, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.112-125, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133185]
• 10: R. J. Byrd. LQL user notes: An informal guide to the lexical query language. Technical Report RC 14853 8/17/89, IBM T.J. Watson Research Center, August 1989.
• 11: C J Date, A guide to the SQL standard, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 12: Charles F. Goldfarb, The SGML handbook, Oxford University Press, Inc., New York, NY, 1991
• 13: G. H. Gonnet, R. A. Baeza-Yates, and T. Snider. Lexicographical indices for text: Inverted flies vs. PAT trees. Report OED-91-01, UW Centre for the New Oxford English Dictionary and Text Research, 1991.
• 14: Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States
• 15: P. Kilpel~inen. Tree Matching Problems with Applications to Structured Text Databases. P hD thesis, University of Helsinki, Dept. of Comp. Science, November 1992.
• 16: P. Kilpel~inen, G. Lind6n, H. Mannila, and E. Nikunen. A structured document database system. In R. Furuta, editor, EPgO - Proceedings of the International Conference on Electronic PubIi3hing, Document Manipulation ~4 Typography, The Cambridge Series on Electronic Publishing. Cambridge University Press, 1990.
• 17: Pekka Kilpelainen , Heikki Mannila, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing, v.24 n.2, p.340-356, April 1995 [doi>10.1137/S0097539791218202]
• 18: Pekka Kilpeläinen , Heikki Mannila, The tree inclusion problem, Proceedings of the international joint conference on theory and practice of software development on Colloquium on trees in algebra and programming (CAAP '91): vol 1, p.202-214, April 1991, Brighton, United Kingdom
• 19: Pekka Kilpeläinen , Heikki Mannila, Grammatical Tree Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.162-174, April 29-May 01, 1992
• 20: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 21: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 22: I. A. Macleod, Storage and retrieval of structured documents, Information Processing and Management: an International Journal, v.26 n.2, p.197-208, 1990 [doi>10.1016/0306-4573(90)90025-W]
• 23: I. A. MacLeod, A query language for retrieving information from hierarchical text structures, The Computer Journal, v.34 n.3, p.254-264, June 1991 [doi>10.1093/comjnl/34.3.254]
• 24: David Maier , David S. Warren, Computing with logic: logic programming with Prolog, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• 25: V. Quint, Systems for the manipulation of structured documents, Structured documents, Cambridge University Press, New York, NY, 1989
• 26: V. Quint and I. Vatton. Grif: An interactive system for structured document manipulation. In J. C. van Vliet, editor, Text Processing and Document Manipulation, pages 200-213. Cambridge University Press, 1986.
• 27: L. Sterling and E. Shapiro. The Art of Prolo9. MIT Press, 1986.
• 28: Jean Tague , Airi Salminen , Charles McClellan, Complete formal model for information retrieval systems, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.14-20, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122862]
• 29: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 30: D. H. D. Warren. Efficient processing of interactive relational database queries expressed in logic. In Proceedings of the Seventh International Conference on Very Large Data Bases, pages 272-281. Computer Society Press, 1981.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Documentation, Languages