Storing semistructured data with STORED

ABSTRACT

Systems for managing and querying semistructured-data sources often store data in proprietary object repositories or in a tagged-text format. We describe a technique that can use relational database management systems to store and manage semistructured data. Our technique relies on a mapping between the semistructured data model and the relational data model, expressed in a query language called STORED. When a semistructured data instance is given, a STORED mapping can be generated automatically using data-mining techniques. We are interested in applying STORED to XML data, which is an instance of semistructured data. We show how a document-type-descriptor (DTD), when present, can be exploited to further improve performance.

REFERENCES

• 1: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68- 88, April 1997.
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Catriel Beeri , Tova Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, Proceeding of the 7th International Conference on Database Theory, p.296-313, January 10-12, 1999
• 4: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 5: 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
• 6: Mary Fernández , Daniela Florescu , Jaewoo Kang , Alon Levy , Dan Suciu, Catching the boat with Strudel: experiences with a Web-site management system, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.414-425, June 01-04, 1998, Seattle, Washington, United States
• 7: Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for a Web-site management system, ACM SIGMOD Record, v.26 n.3, p.4-11, Sept. 1997 [doi>10.1145/262762.262763]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 10: Klemens Böhm , Karl Aberer , Erich J. Neuhold , Xiaoya Yang, Structured document storage and refined declarative and navigational access mechanisms in HyperStorM, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.4, p.296-311, November 1997 [doi>10.1007/s007780050047]
• 11: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 12: Marc Volz , Karl Aberer , Klemens Böhm, Applying a Flexible OODBMS-IRS-Coupling for Structured Document Handling, Proceedings of the Twelfth International Conference on Data Engineering, p.10-19, February 26-March 01, 1996
• 13: Svetlozar Nestorov , Serge Abiteboul , Rajeev Motwani, Extracting schema from semistructured data, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.295-306, June 01-04, 1998, Seattle, Washington, United States
• 14: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 15: Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina, Object Fusion in Mediator Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.413-424, September 03-06, 1996
• 16: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 17: Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Querying Semistructured Heterogeneous Information, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.319-344, December 04-07, 1995
• 18: Dimitri Theodoratos , Timos K. Sellis, Data Warehouse Configuration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.126-135, August 25-29, 1997
• 19: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: A Versatile Tool for Physical Data Independence, Proceedings of the 20th International Conference on Very Large Data Bases, p.367-378, September 12-15, 1994
• 20: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 21: Ke Wang , Huiqing Liu, Discovering typical structures of documents: a road map approach, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.146-154, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290982]
• 22: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design, Documentation, Experimentation, Languages, Management, Measurement, Performance, Theory