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: 1338
Venue: PODS
Year: 2005
Pagerank: 0.00010058897
Overall Rank: 1,929 | 86.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,864	Inferring XML Schema Definitions from XML Data	2007	VLDB	7.9863574e-05
3,138	Inference of Concise DTDs from XML Data	2006	VLDB	7.4876241e-05
4,073	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.4719397e-05
4,215	Generating XML Structure Using Examples and Constraints	2008	VLDB	6.3527334e-05
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
5,444	Destabilizers and Independence of XML Updates	2010	VLDB	5.5025148e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
6,652	Information Preserving XML Schema Embedding	2005	VLDB	4.9761854e-05
7,291	Static Analysis of Active XML Systems	2008	PODS	4.7741469e-05
8,311	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	4.5435639e-05
12,306	Simplifying XML Schema: Effortless Handling of Nondeterministic Regular Expressions	2009	SIGMOD	4.1945683e-05
12,491	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.1945683e-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
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
970	Typechecking for XML Transformers	2000	PODS	0.00014939578
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
1,947	Secure XML Querying with Security Views	2004	SIGMOD	0.00010000435
2,150	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4255252e-05
2,584	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	8.4948053e-05
3,086	Tree Logical Classes for Efficient Evaluation of XQuery	2004	SIGMOD	7.596041e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
7,361	Extended Path Expressions for XML	2001	PODS	4.7524599e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
9,105	Decidable XPath Fragments in the Real World	2019	PODS	4.3953995e-05
12,296	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	4.1945683e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
8,200	On XPath with Transitive Axes and Data Tests	2013	PODS	4.5602267e-05