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.00010049404
Overall Rank: 1,933 | 86.57%
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,869	Inferring XML Schema Definitions from XML Data	2007	VLDB	7.9841565e-05
3,149	Inference of Concise DTDs from XML Data	2006	VLDB	7.4803351e-05
4,076	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.4657154e-05
4,214	Generating XML Structure Using Examples and Constraints	2008	VLDB	6.346632e-05
4,362	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2478748e-05
5,453	Destabilizers and Independence of XML Updates	2010	VLDB	5.4972307e-05
6,153	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1796878e-05
6,651	Information Preserving XML Schema Embedding	2005	VLDB	4.9714449e-05
7,288	Static Analysis of Active XML Systems	2008	PODS	4.7695781e-05
8,305	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	4.5392079e-05
12,314	Simplifying XML Schema: Effortless Handling of Nondeterministic Regular Expressions	2009	SIGMOD	4.1905499e-05
12,500	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.1905499e-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.00021654356
712	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017714027
970	Typechecking for XML Transformers	2000	PODS	0.00014924533
1,236	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013107769
1,951	Secure XML Querying with Security Views	2004	SIGMOD	9.9907874e-05
2,155	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4164126e-05
2,590	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	8.4863884e-05
3,091	Tree Logical Classes for Efficient Evaluation of XQuery	2004	SIGMOD	7.5887319e-05
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
7,357	Extended Path Expressions for XML	2001	PODS	4.7479042e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
12,348	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1905499e-05
3,089	On the minimization of Xpath queries	2003	VLDB	7.5938563e-05
4,362	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2478748e-05
9,104	Decidable XPath Fragments in the Real World	2019	PODS	4.3911866e-05
12,304	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	4.1905499e-05
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
8,199	On XPath with Transitive Axes and Data Tests	2013	PODS	4.5558541e-05