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.5602267e-05
Overall Rank: 8,200 | 42.96%
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,105	Decidable XPath Fragments in the Real World	2019	PODS	4.3953995e-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,947	Secure XML Querying with Security Views	2004	SIGMOD	0.00010000435
12,296	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
12,491	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.1945683e-05
9,105	Decidable XPath Fragments in the Real World	2019	PODS	4.3953995e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
1,929	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010058897
4,073	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.4719397e-05
12,296	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	4.1945683e-05