Proximal nodes: a model to query document databases by content and structure

ABSTRACT

A model to query document databases by both their content and structure is presented. The goal is to obtain a query language that is expressive in practice while being efficiently implementable, features not present at the same time in previous work. The key ideas of the model are a set-oriented query language based on operations on nearby structure elements of one or more hierarchies, together with content and structural indexing and bottom-up evaluation. The model is evaluated in regard to expressiveness and efficiency, showing that it provides a good trade-off between both goals. Finally, it is shown how to include in the model other media different from text.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: ARNOLD-MOORE, T., FULLER, M., LOWE, B., THOM, J., AND WILKINSON, R. 1995. The ELF data model and SGQL query language for structured document databases. In Proceedings of the 6th Australasian Database Conference. 17-26.
• 3: ARS INNOVANDI. 1992. Search City 1.1 Text Retrieval for Windows Power Users. Ars Innovandi, Santiago, Chile.
• 4: BAEZA-YATES, R. 1994. An hybrid query model for full text retrieval systems. Tech. Rep. DCC-1994-2, Dept. of Computer Science, Univ. of Chile, Santiago, Chile.
• 5: BAEZA-YATES, R. 1996. An extended model for full-text databases. J. Braz. CS Soc. 3, 2 (Apr.), 57-64.
• 6: Ricardo Baeza-Yates , Gonzalo Navarro, Integrating contents and structure in text retrieval, ACM SIGMOD Record, v.25 n.1, p.67-79, March 1996 [doi>10.1145/381854.381890]
• 7: Elisa Bertino , Fausto Rabbiti , Simon Gibbs, Query processing in a multimedia document system, ACM Transactions on Information Systems (TOIS), v.6 n.1, p.1-41, Jan. 1988 [doi>10.1145/42279.42281]
• 8: 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]
• 9: CATTELL, R. 1991. Object Data Management. Addison-Wesley, Reading, Mass.
• 10: Stavros Christodoulakis , Christos Faloutsos, Design and performance considerations for an optical disk-based, multimedia object server, Computer, v.19 n.12, p.45-56, Dec. 1986 [doi>10.1109/MC.1986.1663127]
• 11: V. Christophides , S. Abiteboul , S. Cluet , M. Scholl, From structured documents to novel query facilities, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.313-324, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: CLARKE, C., CORMACK, G., AND BURKOWSKI, F. 1995. An algebra for structured text search and a framework for its implementation. Comput. J.
• 13: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.26 n.1, p.64-69, Jan. 1983 [doi>10.1145/357980.358007]
• 14: Jeff Conklin, Hypertext: an introduction and survey, Computer, v.20 n.9, p.17-41, Sept. 1987 [doi>10.1109/MC.1987.1663693]
• 15: Mariano Consens , Alberto Mendelzon, Hy+: a Hygraph-based query and visualization system, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.511-516, May 25-28, 1993, Washington, D.C., United States
• 16: Mariano P. Consens , Tova Milo, Optimizing queries on files, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.301-312, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: Mariano P. Consens , Tova Milo, Algebras for querying text regions (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-22, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212437]
• 18: DAO, T., SACKS-DAVIS, R., AND THOM, J. 1996. Indexing structured text for queries on containment relationships. In Proceedings of the 7th Australasian Database Conference.
• 19: C. J. Date, An introduction to database systems: vol. 1 (5th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 20: DESAI, B., GOYAL, P., AND SADRI, S. 1986. A data model for use with formatted and textual data. J. ASIS 37, 3, 158-165.
• 21: D{IGITAL. 1991. CDA-DDIF Technical Specification. Digital Equipment Corp., Maynard, Mass.
• 22: Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 23: FAWCETT, H. 1989. PAT 3.3 User's Guide. UW Centre for the New OED and Text Research, Univ. of Waterloo, Ontario, Canada.
• 24: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 25: GAREY, M. AND JOHNSON, D. 1979. Computers and Intractability. W. Freeman and Company.
• 26: Gaston H. Gonnet , Frank Wm. Tompa, Mind Your Grammar: a New Approach to Modelling Text, Proceedings of the 13th International Conference on Very Large Data Bases, p.339-346, September 01-04, 1987
• 27: Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987 [doi>10.1145/45072.45073]
• 28: ISO. 1986. Information processing--Text and office systems--Standard generalized markup language (SGML). ISO 8879-1986, International Standards Organization, Geneva, Switzerland.
• 29: ISO. 1991. Information processing--Text composition--Standard page description language (SPDL). ISO/IEC DIS 10180, International Standards Organization, Geneva, Switzerland.
• 30: ISO. 1992. Information technology--hypermedia/time-based structuring language (Hy- Time). ISO/IEC 10744, International Standards Organization, Geneva, Switzerland.
• 31: ISO. 1994. Information technology--Text and office systems--Document style semantics and specification language (DSSSL). ISO/IEC DIS 10179.2, International Standards Organization, Geneva, Switzerland.
• 32: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 33: 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
• 34: Pekka Kilpeläinen , Heikki Mannila, Retrieval from hierarchical texts by partial patterns, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.214-222, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160722]
• 35: Won Kim , F. H. Lochovsky, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989
• 36: Eila Kuikka , Airi Salminen, Two-dimensional filters for structured text, Information Processing and Management: an International Journal, v.33 n.1, p.37-54, Jan 1, 1997 [doi>10.1016/S0306-4573(96)00040-4]
• 37: Leslie Lamport, Latex: a document preparation system, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 38: MACKIE, E. AND ZOBEL, g. 1992. Retrieval of tree-structured data from disc. In Proceedings of the 3rd Australasian Database Conference. 209-216.
• 39: 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]
• 40: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 41: NAVARRO, G. 1995. A language for queries on structure and contents of textual databases. Master's thesis, Dept. of Computer Science, Univ. of Chile, Santiago, Chile.
• 42: NAVARRO, G. AND BAEZA-YATES, R. 1995a. Expressive power of a new model for structured text databases. In Proceedings of PANEL 95. 1151-1162.
• 43: Gonzalo Navarro , Ricardo Baeza-Yates, A language for queries on structure and contents of textual databases, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.93-101, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215336]
• 44: SACKS-DAVIS, R., ARNOLD-MOORE, T., AND ZOBEL, J. 1994. Database systems for structured documents. In Proceedings of ADTI 94. 272-283.
• 45: SACKS-DAVIS, R., ZOBEL, J., AND RAMAMOHANARAO, K. 1992. Advanced database systems for text retrieval. In Proceedings of the 3rd Australian Database Conference. 1-8.
• 46: SALMINEN, A. AND TOMPA, F. 1992. PAT expressions: An algebra for text search. In COM- PLEX 92. 309-332.
• 47: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 48: Michael Stonebraker , Heidi Stettner , Nadene Lynn , Joseph Kalash , Antonin Guttman, Document processing in a relational database system, ACM Transactions on Information Systems (TOIS), v.1 n.2, p.143-158, April 1983 [doi>10.1145/357431.357433]
• 49: SUBRAHMANIAN, M. AND JAJODIA, S. Eds. 1996. Multimedia Database Systems. Springer- Verlag, New York.
• 50: 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]
• 51: J. K. Wu , Y. H. Ang , P. Lam , H. H. Loh , A. Desai Narasimhalu, Inference and retrieval of facial images, Multimedia Systems, v.2 n.1, p.1-14, June 1994 [doi>10.1007/BF01213579]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Format and notation; Standards; Languages and systems

General Terms:
Algorithms, Design, Human Factors, Languages, Performance

Keywords:
expressivity and efficiency of query languages, hierarchical documents, structured text, text algebras