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: he582828e4633f4d3
Venue: PODS
Year: 2000
Pagerank: 0.00010749818
Overall Rank: 1,406 | 90.55%
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
679	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014837097
958	XPath Queries on Streaming Data	2003	SIGMOD	0.00012860244
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011058412
1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.2797174e-05
2,942	Numerical Document Queries	2003	PODS	7.8318328e-05
3,756	XML with Data Values: Typechecking Revisited	2001	PODS	7.0446245e-05
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6972871e-05
5,768	Exchanging Intensional XML Data	2003	SIGMOD	6.0013282e-05
6,626	Representing and Querying XML with Incomplete Information	2001	PODS	5.7291244e-05
7,420	A Crash Course on Database Queries	2007	PODS	5.5326094e-05
8,043	Extended Path Expressions for XML	2001	PODS	5.4011538e-05
12,700	The ACM PODS Alberto O. Mendelzon Test-of-Time-Award 2010	2010	PODS	4.9793485e-05
12,743	Transforming XML Documents as Schemas Evolve	2010	VLDB	4.9793485e-05
12,865	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	4.9793485e-05
13,101	Query-preserving Watermarking of Relational Databases and XML Documents	2003	PODS	4.9793485e-05
14,157	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	14,265	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
2	12,914	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS
3	2,317	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
4	12,656	The Complexity of Text-Preserving XML Transformations	2011	PODS
5	2,934	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
6	12,924	Querying XML with Update Syntax	2007	SIGMOD
7	6,265	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS
8	4,145	XML Type Checking with Macro Tree Transducers	2005	PODS
9	3,756	XML with Data Values: Typechecking Revisited	2001	PODS
10	3,343	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS