Welcome to D
SIGMOD'00
PODS'00
= PODS'00 Webs
= Plenary Talk
<<< = PODS'00 Pape>>>
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

DTD Inference for Views of XML Data


Yannis Papakonstantinou and Victor Vianu

  View Paper (PDF)  

Return to XML Technology


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


Note: References link to DBLP on the Web.

[Abi97]
Serge Abiteboul : Querying Semi-Structured Data. ICDT 1997 : 1-18
[AM98]
Gustavo O. Arocena , Alberto O. Mendelzon : WebOQL: Restructuring Documents, Databases, and Webs. ICDE 1998 : 24-33
[AQM+97]
Serge Abiteboul , Dallan Quass , Jason McHugh , Jennifer Widom , Janet L. Wiener : The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1) : 68-88(1997)
[B+99]
Chaitanya K. Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu : XML-Based Information Mediation with MIX. SIGMOD Conference 1999 : 597-599
[BDFS97]
Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350
[BDHS96]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[BKMW98]
...
[BM99]
Catriel Beeri , Tova Milo : Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999 : 296-313
[BPSM]
Tim Bray , Jean Paoli , C. M. Sperberg-McQueen : Extensible Markup Language (XML). World Wide Web Journal 2(4) : 27-66(1997)
[Bun97]
Peter Buneman : Semistructured Data. PODS 1997 : 117-121
[CD]
...
[CDSS98]
Sophie Cluet , Claude Delobel , Jérôme Siméon , Katarzyna Smaga : Your Mediators Need Data Conversion! SIGMOD Conference 1998 : 177-188
[CM90]
Mariano P. Consens , Alberto O. Mendelzon : GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990 : 404-416
[dBV93]
Jan Van den Bussche , Gottfried Vossen : An Extension of Path Expressions to Simplify Navigation in Object-Oriented Queries. DOOD 1993 : 267-282
[DFF+]
Alin Deutsch , Mary F. Fernandez , Daniela Florescu , Alon Y. Levy , Dan Suciu : Xml-ql: A Query Language for XML. http://www.w3.org/TR/NOTE-xml-ql/
[FFLS98]
Mary F. Fernandez , Daniela Florescu , Jaewoo Kang , Alon Y. Levy , Dan Suciu : Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998 : 414-425
[FLS98]
Daniela Florescu , Alon Y. Levy , Dan Suciu : Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998 : 139-148
[FS98]
Mary F. Fernandez , Dan Suciu : Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998 : 14-23
[GJ79]
M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[GS97]
...
[GW97]
Roy Goldman , Jennifer Widom : DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997 : 436-445
[HU79]
John E. Hopcroft , Jeffrey D. Ullman : Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02888-X
[Inca]
...
[Incb]
...
[KS95]
David Konopnicki , Oded Shmueli : W3QS: A Query System for the World-Wide Web. VLDB 1995 : 54-65
[LJM+]
...
[MD]
...
[Mit90]
John C. Mitchell : Type Systems for Programming Languages. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990 : 365-458
[Mit96]
...
[MP]
...
[MS99]
Tova Milo , Dan Suciu : Type Inference for Queries on Semistructured Data. PODS 1999 : 215-226
[MSV]
Tova Milo , Dan Suciu , Victor Vianu : Typechecking for XML Transformers. PODS 2000 : 11-22
[MW95]
Alberto O. Mendelzon , Peter T. Wood : Finding Regular Simple Paths in Graph Databases. SIAM J. Comput. 24(6) : 1235-1258(1995)
[MZ98]
Tova Milo , Sagit Zohar : Using Schema Matching to Simplify Heterogeneous Data Translation. VLDB 1998 : 122-133
[NAM98]
Svetlozar Nestorov , Serge Abiteboul , Rajeev Motwani : Extracting Schema from Semistructured Data. SIGMOD Conference 1998 : 295-306
[NdB98]
Frank Neven , Jan Van den Bussche : Expressiveness of Structured Document Query Languages Based on Attribute Grammars. PODS 1998 : 11-17
[Nev99]
...
[NS99]
Frank Neven , Thomas Schwentick : Query Automata. PODS 1999 : 205-214
[NUWC97]
Svetlozar Nestorov , Jeffrey D. Ullman , Janet L. Wiener , Sudarshan S. Chawathe : Representative Objects: Concise Representations of Semistructured, Hierarchial Data. ICDE 1997 : 79-90
[PAGM96]
Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina : Object Fusion in Mediator Systems. VLDB 1996 : 413-424
[PV]
...
[PV99a]
Yannis Papakonstantinou , Vasilis Vassalos : Query Rewriting for Semistructured Data. SIGMOD Conference 1999 : 455-466
[PV99b]
Yannis Papakonstantinou , Pavel Velikhov : Enhancing Semistructured Data Mediators with Document Type Definitions. ICDE 1999 : 136-145
[SPS99]
...
[Suc98]
Dan Suciu : Semistructured Data and XML. FODO 1998 : 0-
[VLP00]
Bertram Ludäscher , Yannis Papakonstantinou , Pavel Velikhov : Navigation-Driven Evaluation of Virtual Mediated Views. EDBT 2000 : 150-165

Referenced by

  1. Frank Neven , Thomas Schwentick : Expressive and Efficient Pattern Languages for Tree-Structured Data. PODS 2000 : 145-156
  2. Tova Milo , Dan Suciu , Victor Vianu : Typechecking for XML Transformers. PODS 2000 : 11-22

BIBTEX


@inproceedings{DBLP:conf/pods/PapakonstantinouV00,
  author    = {Yannis Papakonstantinou and
                Victor Vianu},
   title     = {DTD Inference for Views of XML Data},
   booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
                on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
                USA},
   publisher = {ACM},
   year      = {2000},
   isbn      = {1-58113-214-X},
   pages     = {35-46},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.