XML with Data Values: Typechecking Revisited

Summary: Revisits static XML typechecking including data values and tests, showing this realistic extension makes typechecking quickly undecidable. Delineates practical fragments of queries/DTDs that remain decidable, traces a tight decidability boundary and gives complexity results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1230
Venue: PODS
Year: 2001
Pagerank: 7.2045472e-05
Overall Rank: 3,679 | 74.77%
DOI: 10.1145/375551.375570

Incoming Non-self Citations Over Time

Authors

1. Noga Alon (Tel Aviv University)
2. Tova Milo (Tel Aviv University)
3. Frank Neven (Limburgs Universitair Centrum)
4. Dan Suciu (University of Washington)
5. Victor Vianu (University of California San Diego)

BibTeX Citation

@inproceedings{alon_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{XML with Data Values: Typechecking Revisited}},
        url = {https://dl.acm.org/doi/10.1145/375551.375570},
        doi = {10.1145/375551.375570},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Alon, Noga and Milo, Tova and Neven, Frank and Suciu, Dan and Vianu, Victor},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,122	E-Services: A Look Behind the Curtain	2003	PODS	9.1402274e-05
3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	7.5749332e-05
4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.927159e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
6,611	Information Preserving XML Schema Embedding	2005	VLDB	5.8228205e-05
7,270	A Crash Course on Database Queries	2007	PODS	5.6595955e-05
7,361	Static Analysis of Active XML Systems	2008	PODS	5.6340455e-05
9,678	Deciding Well-Definedness of XQuery Fragments	2005	PODS	5.2373357e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
645	Your Mediators Need Data Conversion!	1998	SIGMOD	0.00015338713
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
1,372	Typechecking for XML Transformers	2000	PODS	0.00010994864
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
3,325	On Wrapping Query Languages and Efficient XML Integration	2000	SIGMOD	7.5196252e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
2	12,353	Type-Based Detection of XML Query-Update Independence	2012	VLDB
3	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
4	12,410	Certain Answers for XML Queries	2010	PODS
5	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
6	2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
7	1,372	Typechecking for XML Transformers	2000	PODS
8	1,290	DTD Inference for Views of XML Data	2000	PODS
9	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
10	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS