From structured documents to novel query facilities

ABSTRACT

Structured documents (e.g., SGML) can benefit a lot from database support and more specifically from object-oriented database (OODB) management systems. This paper describes a natural mapping from SGML documents into OODB's and a formal extension of two OODB query languages (one SQL-like and the other calculus) in order to deal with SGML document retrieval.Although motivated by structured documents, the extensions of query languages that we present are general and useful for a variety of other OODB applications. A key element is the introduction of paths as first class citizens. The new features allow to query data (and to some extent schema) without exact knowledge of the schema in a simple and homogeneous fashion.

REFERENCES

• 1: ISO/IEC 10744. Information Technology- Hypermedia/ Time- based Structuring Language (Hy- Time), 1992.
• 2: ISO 8879. Information Processing-Text and Office Systems-Standard Generalized Markup Language (SGML), 1986.
• 3: S. Abiteboul and C. Beeri. On the Power of Languages for the Manipulation of Complex Objects. Rapports de Recherche 846, VERSO, INRIA, BP. 105, 78153 Le Chesnay, France, 1988.
• 4: Serge Abiteboul , Sophie Cluet , Tova Milo, Querying and Updating the File, Proceedings of the 19th International Conference on Very Large Data Bases, p.73-84, August 24-27, 1993
• 5: S. Abiteboul, S. Cluet, and T. Milo. More on updating the file. Rapports de recherche, VERSO, INRIA, BP. 105, 78153 Le Chesnay, France, 1994.
• 6: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.159-173, June 1989, Portland, Oregon, United States
• 7: Bernd Amann , Michel Scholl, Gram: a graph data model and query languages, Proceedings of the ACM conference on Hypertext, p.201-211, November 30-December 04, 1992, Milan, Italy [doi>10.1145/168466.168527]
• 8: François Bancilhon , Sophie Cluet , C. Delobel, A query language for the O2 object-oriented databases, Proceedings of the second international workshop on Database programming languages, p.122-138, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 9: AIS Berger-Levrault. SGML/Search, Description du Langage. Internal Document, 34 Avenue du Roule 92200 Neuilly sur Seine, 1993.
• 10: 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]
• 11: 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]
• 12: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States
• 13: Mariano P. Consens , Alberto O. Mendelzon, GraphLog: a visual formalism for real life recursion, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.404-416, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298591]
• 14: P. Dadam , V. Linnemann, Advanced information management (AIM): advanced database technology for integrated applications, IBM Systems Journal, v.28 n.4, p.661-681, 1989
• 15: O. Deux et al., The Story of O2, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.91-108, March 1990 [doi>10.1109/69.50908]
• 16: Euroclid. Le parseur SGML d'Euroclid. Internal Document, 12, Avenue des Prds 78180 Montigny le Bretonneux, 1991.
• 17: Charles F. Goldfarb, The SGML handbook, Oxford University Press, Inc., New York, NY, 1991
• 18: 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
• 19: Ralf Hartmut Güting , Roberto Zicari , David M. Choy, An algebra for structured office documents, ACM Transactions on Information Systems (TOIS), v.7 n.2, p.123-157, April 1989 [doi>10.1145/65935.65939]
• 20: M. Gyssens , J. Paredaens , D. van Gucht, A grammar-based approach towards unifying hierarchical data models, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.263-272, June 1989, Portland, Oregon, United States
• 21: Nancy Ide , Jacques Le Maitre , Jean Véronis, Outline of a model for lexical databases, Information Processing and Management: an International Journal, v.29 n.2, p.159-186, March-April 1993 [doi>10.1016/0306-4573(93)90001-T]
• 22: I. Jaeobs and L. Rideau-Gallot. A CENTAUR tutorial. Rapports Techniques 140, INRIA, BP. 105, 78153 Le Chesnay, France, July 1992.
• 23: Paris Kanellakis , Christophe Lécluse , Philippe Richard, Introduction to the data model, Building an object-oriented database system: the story of 02, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 24: 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
• 25: W. Lee , D. Woelk, Integration of text search with ORION, Data Engineering, v.13 n.1, p.58-62, Mar. 1990
• 26: 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]
• 27: R. Sacks-Davis, W. Wen, A. Kent, and K. Ramamohanarao. Complex Object Support for a Doeument Database System. In Thirteenth Australian Computer Science Conference, pages 322-333, Victoria, Australia, 1990. Monash University.
• 28: Jeffrey D. Ullman, The interface between language theory and database theory, Theoretical studies in computer science: thr, Academic Press Professional, Inc., San Diego, CA, 1991

INDEX TERMS

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

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

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

General Terms:
Algorithms, Languages