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

Typechecking for XML Transformers


Tova Milo, Dan Suciu, and Victor Vianu

  View Paper (PDF)  

Return to XML Technology


Abstract

We study the typechecking problem for XML transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a nobust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.


References


Note: References link to DBLP on the Web.

[1]
Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133
[2]
Alfred V. Aho , Jeffrey D. Ullman : Translations on a Context-Free Grammar. Information and Control 19(5) : 439-475(1971)
[3]
...
[4]
Catriel Beeri , Tova Milo : Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999 : 296-313
[5]
Catriel Beeri , Yariv Tzaban : SAL: An Algebra for Semistructured Data and XML. WebDB (Informal Proceedings) 1999 : 37-42
[6]
...
[7]
...
[8]
...
[9]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[10]
...
[11]
...
[12]
Sophie Cluet , Claude Delobel , Jérôme Siméon , Katarzyna Smaga : Your Mediators Need Data Conversion! SIGMOD Conference 1998 : 177-188
[13]
Alin Deutsch , Mary F. Fernandez , Daniela Florescu , Alon Y. Levy , Dan Suciu : A Query Language for XML. WWW8 / Computer Networks 31(11-16) : 1155-1169(1999)
[14]
...
[15]
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
[16]
...
[17]
Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Vasilis Vassalos , Jennifer Widom : The TSIMMIS Approach to Mediation: Data Models and Languages. JIIS 8(2) : 117-132(1997)
[18]
Noa Globerman , David Harel : Complexity Results for Multi-Pebble Automata and their Logics. ICALP 1994 : 73-82
[19]
...
[20]
...
[21]
...
[22]
Jason McHugh , Jennifer Widom : Query Optimization for XML. VLDB 1999 : 315-326
[23]
Tova Milo , Dan Suciu : Type Inference for Queries on Semistructured Data. PODS 1999 : 215-226
[24]
Frank Neven , Thomas Schwentick : Query Automata. PODS 1999 : 205-214
[25]
Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom : Object Exchange Across Heterogeneous Information Sources. ICDE 1995 : 251-260
[26]
Yannis Papakonstantinou , Pavel Velikhov : Enhancing Semistructured Data Mediators with Document Type Definitions. ICDE 1999 : 136-145
[27]
Yannis Papakonstantinou , Victor Vianu : DTD Inference for Views of XML Data. PODS 2000 : 35-46
[28]
...
[29]
...
[30]
Wolfgang Thomas : Automata on Infinite Objects. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990 : 133-192

Referenced by

  1. Yannis Papakonstantinou , Victor Vianu : DTD Inference for Views of XML Data. PODS 2000 : 35-46

BIBTEX


@inproceedings{DBLP:conf/pods/MiloSV00,
  author    = {Tova Milo and
                Dan Suciu and
                Victor Vianu},
   title     = {Typechecking for XML Transformers},
   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     = {11-22},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },




DiSC'01 Copyright ©2002 ACM Inc.