Typing and Querying XML Documents: Some Complexity Bounds

Summary: Systematic complexity study of XML validation and XPath query evaluation on unranked ordered trees under DTDs, XML Schema, and tree automata. Establishes data vs. combined complexity bounds and pinpoints tractable vs. intractable XPath fragments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1c1dea22ac6a0f1d
Venue: PODS
Year: 2003
Pagerank: 7.839851e-05
Overall Rank: 2,934 | 80.28%
DOI: 10.1145/773153.773170

Incoming Non-self Citations Over Time

Authors

1. Luc Segoufin (INRIA)

BibTeX Citation

@inproceedings{segoufin_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Typing and Querying XML Documents: Some Complexity Bounds}},
        url = {https://dl.acm.org/doi/10.1145/773153.773170},
        doi = {10.1145/773153.773170},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Segoufin, Luc},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,177	The Complexity of XPath Query Evaluation	2003	PODS	8.9153711e-05
3,746	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.0557724e-05
4,807	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.4079967e-05
5,368	Buffering in Query Evaluation over XML Streams	2005	PODS	6.1597369e-05
7,592	XQuery Optimization	2003	VLDB	5.4880486e-05
12,923	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.9793485e-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
662	Your Mediators Need Data Conversion!	1998	SIGMOD	0.00015001476
679	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014837097
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011058412
1,807	Validating Streaming XML Documents	2002	PODS	9.5963125e-05
2,177	The Complexity of XPath Query Evaluation	2003	PODS	8.9153711e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,746	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
2	1,807	Validating Streaming XML Documents	2002	PODS
3	3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS
4	2,177	The Complexity of XPath Query Evaluation	2003	PODS
5	5,474	Running Tree Automata on Probabilistic XML	2009	PODS
6	12,824	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
7	1,599	Conjunctive Queries over Trees	2004	PODS
8	1,976	XPath Satisfiability in the Presence of DTDs	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