|
 |
|
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
-
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.
|
