Frontiers of Tractability for Typechecking Simple XML Transformations

Summary: Characterizes precise tractability frontiers for complete typechecking of top-down XML transformations with XPath, using grammars and tree automata for schemas. Identifies several practical, polynomial-time cases and matching hardness results showing most relaxations become intractable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1304
Venue: PODS
Year: 2004
Pagerank: 7.5749332e-05
Overall Rank: 3,274 | 77.54%
DOI: 10.1145/1055558.1055563

Incoming Non-self Citations Over Time

Authors

1. Wim Martens (Limburgs Universitair Centrum)
2. Frank Neven (Limburgs Universitair Centrum)

BibTeX Citation

@inproceedings{martens_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Frontiers of Tractability for Typechecking Simple XML Transformations}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055563},
        doi = {10.1145/1055558.1055563},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Martens, Wim and Neven, Frank},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
4,051	XML Type Checking with Macro Tree Transducers	2005	PODS	6.9364294e-05
7,270	A Crash Course on Database Queries	2007	PODS	5.6595955e-05
12,452	Transforming XML Documents as Schemas Evolve	2010	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
3,679	XML with Data Values: Typechecking Revisited	2001	PODS	7.2045472e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,412	Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages	2010	PODS
2	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
3	12,634	Querying XML with Update Syntax	2007	SIGMOD
4	12,353	Type-Based Detection of XML Query-Update Independence	2012	VLDB
5	2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
6	12,365	The Complexity of Text-Preserving XML Transformations	2011	PODS
7	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
8	3,679	XML with Data Values: Typechecking Revisited	2001	PODS
9	1,372	Typechecking for XML Transformers	2000	PODS
10	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS