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: 1597
Venue: PODS
Year: 2013
Pagerank: 5.4248063e-05
Overall Rank: 8,440 | 42.10%
DOI: 10.1145/2463664.2463675

Incoming Non-self Citations Over Time

Authors

1. Diego Figueira (University of Edinburgh)

BibTeX Citation

@inproceedings{figueira_pods13,
        address = {New York, NY, USA},
        series = {{PODS} '13},
        title = {{On XPath with Transitive Axes and Data Tests}},
        url = {https://dl.acm.org/doi/10.1145/2463664.2463675},
        doi = {10.1145/2463664.2463675},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Figueira, Diego},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,249	Decidable XPath Fragments in the Real World	2019	PODS	5.2987261e-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
2,757	Secure XML Querying with Security Views	2004	SIGMOD	8.1601016e-05
12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
2	6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
3	395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS
4	1,564	Conjunctive Queries over Trees	2004	PODS
5	12,684	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
6	9,249	Decidable XPath Fragments in the Real World	2019	PODS
7	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
8	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
9	4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
10	12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS