DTD inference for views of XML data

ABSTRACT

We study the inference of Data Type Definitions (DTDs) for views of XML data, using an abstraction that focuses on document content structure. The views are defined by a query language that produces a list of documents selected from one or more input sources. The selection conditions involve vertical and horizontal navigation, thus querying explicitly the order present in input documents. We point several strong limitations in the descriptive ability of current DTDs and the need for extending them with (i) a subtyping mechanism and (ii) a more powerful specification mechanism than regular languages, such as context-free languages. With these extensions, we show that one can always infer tight DTDs, that precisely characterize a selection view on sources satisfying given DTDs. We also show important special cases where one can infer a tight DTD without requiring extension (ii). Finally we consider related problems such as verifying conformance of a view definition with a predefined DTD. Extensions to more powerful views that construct complex documents are also briefly discussed.

REFERENCES

• Abi97: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• AM98: Gustavo O. Arocena , Alberto O. Mendelzon, WebOQL: Restructuring Documents, Databases, and Webs, Proceedings of the Fourteenth International Conference on Data Engineering, p.24-33, February 23-27, 1998
• AQM+97: 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), 1997.
• B+99: Chaitan Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu, XML-based information mediation with MIX, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.597-599, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• BDFS97: Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu, Adding Structure to Unstructured Data, Proceedings of the 6th International Conference on Database Theory, p.336-350, January 08-10, 1997
• BDHS96: 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
• BKMW98: A. Bruggemann-Klein, M. Murata, and D. Wood. Regular tree languages over nonranked alphabets, 1998. Available at ftp:// ftp I I. inf ormat ik. tu-muenchen, de/pub/mis c /caterpillars/.
• BM99: 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
• BPSM: T. Bray, J. Paoli, and C. Sperberg-McQueen. Extensible markup language (XML) 1.0, W3C recommendation. Latest version available at http://www, w3. org. TR/REC-xml.
• Bun97: Peter Buneman, Semistructured data, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-121, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263675]
• CD: J. Clark and S. Deach. Extensible stylesheet language (xsl) 1.0, W3C working draft. http://www, w3. org/TR/WD-xsl.
• CDSS98: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• CM90: 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]
• dBV93: J. Van den Bussche and G. Vossen. An extension of path expressions to simplify navigation in object-oriented queries. In Proc. of Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), 1993.
• DFF+: A. Deutch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. XML-QL: A query language for XML. Submission to W3C. Latest version available at http://www, w3. org/TR/NOTE-xml-ql.
• FFLS98: 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
• FLS98: Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275503]
• FS98: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• GJ79: 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
• GS97: Grzegorz Rozenberg , Arto Salomaa, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• GW97: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• HU79: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Inca: Bluestone Inc. Visual XML. http://www, bluestone, com/xml/Visual-XML/.
• Incb: SoftQuad Inc. XMetal editor. http://www, sq. com/products/xmetal/.
• KS95: David Konopnicki , Oded Shmueli, W3QS: A Query System for the World-Wide Web, Proceedings of the 21th International Conference on Very Large Data Bases, p.54-65, September 11-15, 1995
• LJM+: A. Layman, E. Jung, E. Maler, H. Thompson, J. Paoli, J. Tigue, N. Mikula, and S. De Rose. XML-Data. Available at http: //www. w3. org/TR/1998/NOTE-XML-dat a.
• MD: E. Maler and S. DeRose. XML pointer language (XPointer). http://www, w3. org /TR/1998/WD-xpt r- 19980303.
• Mit90: John C. Mitchell, Type systems for programming languages, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• Mit96: John C. Mitchell, Foundations of programming languages, MIT Press, Cambridge, MA, 1996
• MP: K. Munroe and Y. Papakonstantinou. BBQ: A visual interface for integrated browsing and querying of XML. Available at http ://www. db. ucsd. edu/publications/ BBO. pdf.
• MS99: Tova Milo , Dan Suciu, Type inference for queries on semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303998]
• MSV: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• MW95: Alberto O. Mendelzon , Peter T. Wood, Finding Regular Simple Paths in Graph Databases, SIAM Journal on Computing, v.24 n.6, p.1235-1258, Dec. 1995 [doi>10.1137/S009753979122370X]
• MZ98: Tova Milo , Sagit Zohar, Using Schema Matching to Simplify Heterogeneous Data Translation, Proceedings of the 24rd International Conference on Very Large Data Bases, p.122-133, August 24-27, 1998
• NAM98: 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
• NdB98: Frank Neven , Jan Van den Bussche, Expressiveness of structured document query languages based on attribute grammars, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-17, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275489]
• Nev99: Frank Neven, Extensions of Attribute Grammars for Structured Document Queries, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.99-116, September 01-03, 1999
• NS99: Frank Neven , Thomas Schwentick, Query automata, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303997]
• NUWC97: Svetlozar Nestorov , Jeffrey D. Ullman , Janet L. Wiener , Sudarshan S. Chawathe, Representative Objects: Concise Representations of Semistructured, Hierarchial Data, Proceedings of the Thirteenth International Conference on Data Engineering, p.79-90, April 07-11, 1997
• PAGM96: 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
• PV: Y. Papakonstantinou and P. Velikhov. The use and computation of specialized DTDs in the MIX mediator system. Manuscript, available at http://www, db. ucsd. edu/ publicat ions/UseComputeDTD, pdf.
• PV99a: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• PV99b: Y. Papakonstantinou and P. Velikhov. Enhancing semistructured data mediators with document type definitions. In Proc. ICDE Conf., 1999.
• SPS99: S.Abiteboul, P.Buneman, and D. Suciu. Data on the Web. Morgan Kauffman, 1999.
• Suc98: D. Suciu. Semistructured data and XML. In Proc. 5th International Conference of Foundations of Data Organization (FODO'98), 1998.
• VLP00: Bertram Ludäscher , Yannis Papakonstantinou , Pavel Velikhov, Navigation-Driven Evaluation of Virtual Mediated Views, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.150-165, March 27-31, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Experimentation, Theory