XPath Satisfiability in the Presence of DTDs

Summary: Complexity map of XPath satisfiability under DTDs across practical fragments, isolating effects of upward axes, recursion, data-value joins and negation. Results: negation-free—PTIME/NP; with negation—PSPACE→EXPTIME; negation+data—NEXPTIME→undecidable; DTD-specific tractable cases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1337
Venue: PODS
Year: 2005
Pagerank: 9.4878711e-05
Overall Rank: 1,916 | 86.86%
DOI: 10.1145/1065167.1065172

Incoming Non-self Citations Over Time

Authors

1. Michael Benedikt (AT&T)
2. Wenfei Fan (AT&T; University of Edinburgh)
3. Floris Geerts (University of Edinburgh; University of Limburg)

BibTeX Citation

@inproceedings{benedikt_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{XPath Satisfiability in the Presence of DTDs}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065172},
        doi = {10.1145/1065167.1065172},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Benedikt, Michael and Fan, Wenfei and Geerts, Floris},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,795	Inferring XML Schema Definitions from XML Data	2007	VLDB	8.115421e-05
3,185	Inference of Concise DTDs from XML Data	2006	VLDB	7.6567423e-05
4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.927159e-05
4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.6592957e-05
4,669	Generating XML Structure Using Examples and Constraints	2008	VLDB	6.5736436e-05
5,457	Destabilizers and Independence of XML Updates	2010	VLDB	6.2131072e-05
6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.8776391e-05
6,611	Information Preserving XML Schema Embedding	2005	VLDB	5.8228205e-05
7,361	Static Analysis of Active XML Systems	2008	PODS	5.6340455e-05
8,547	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	5.4119882e-05
12,500	Simplifying XML Schema: Effortless Handling of Nondeterministic Regular Expressions	2009	SIGMOD	5.093636e-05
12,684	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
1,372	Typechecking for XML Transformers	2000	PODS	0.00010994864
2,757	Secure XML Querying with Security Views	2004	SIGMOD	8.1601016e-05
2,969	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	7.9147299e-05
3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	7.5749332e-05
3,917	Tree Logical Classes for Efficient Evaluation of XQuery	2004	SIGMOD	7.0182992e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,564	Conjunctive Queries over Trees	2004	PODS
2	395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS
3	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
4	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
5	2,817	On the minimization of XPath queries	2003	VLDB
6	4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
7	9,249	Decidable XPath Fragments in the Real World	2019	PODS
8	12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS
9	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
10	8,440	On XPath with Transitive Axes and Data Tests	2013	PODS