Typechecking for XML Transformers

Summary: Model XML transformers by k‑pebble transducers capturing most XML‑QL and XSLT fragments (excluding data‑value joins); types are regular tree languages. Main result: typechecking is decidable — given input DTD and output regular‑tree spec, verify all transducer outputs conform. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1190
Venue: PODS
Year: 2000
Pagerank: 0.00010994864
Overall Rank: 1,372 | 90.59%
DOI: 10.1145/335168.335171

Incoming Non-self Citations Over Time

Authors

1. Tova Milo (Tel Aviv University)
2. Dan Suciu (AT&T)
3. Victor Vianu (University of California San Diego)

BibTeX Citation

@inproceedings{milo_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Typechecking for XML Transformers}},
        url = {https://dl.acm.org/doi/10.1145/335168.335171},
        doi = {10.1145/335168.335171},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Milo, Tova and Suciu, Dan and Vianu, Victor},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
928	XPath Queries on Streaming Data	2003	SIGMOD	0.00013153017
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
2,875	Numerical Document Queries	2003	PODS	8.0083925e-05
3,679	XML with Data Values: Typechecking Revisited	2001	PODS	7.2045472e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
5,661	Exchanging Intensional XML Data	2003	SIGMOD	6.130087e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05
7,270	A Crash Course on Database Queries	2007	PODS	5.6595955e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05
12,409	The ACM PODS Alberto O. Mendelzon Test-of-Time-Award 2010	2010	PODS	5.093636e-05
12,452	Transforming XML Documents as Schemas Evolve	2010	VLDB	5.093636e-05
12,575	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	5.093636e-05
12,811	Query-preserving Watermarking of Relational Databases and XML Documents	2003	PODS	5.093636e-05
13,846	Regular Rewriting of Active XML and Unambiguity	2005	PODS	-

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
2	12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS
3	2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
4	12,365	The Complexity of Text-Preserving XML Transformations	2011	PODS
5	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
6	12,634	Querying XML with Update Syntax	2007	SIGMOD
7	6,137	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS
8	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
9	3,679	XML with Data Values: Typechecking Revisited	2001	PODS
10	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS