On XPath with Transitive Axes and Data Tests

Summary: Decidability result: XPath with data-equality tests over reflexive-transitive axes (following-/preceding-sibling-or-self, descendant-or-self) is decidable; algorithm in 3ExpSpace. Gives an equivalent normal form in 2ExpSpace and shows undecidability if reflexivity is dropped. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1598
Venue: PODS
Year: 2013
Pagerank: 4.5558541e-05
Overall Rank: 8,199 | 43.02%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Diego Figueira

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,104	Decidable XPath Fragments in the Real World	2019	PODS	4.3911866e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,951	Secure XML Querying with Security Views	2004	SIGMOD	9.9907874e-05
12,304	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,348	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1905499e-05
6,153	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1796878e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
12,500	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.1905499e-05
9,104	Decidable XPath Fragments in the Real World	2019	PODS	4.3911866e-05
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
1,933	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010049404
4,076	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.4657154e-05
12,304	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	4.1905499e-05