Satisfiability of Downward XPath with Data Equality Tests

Summary: Proves satisfiability of downward XPath with data equality/inequality (descendant*, child, =) is decidable and ExpTime-complete, even with Kleene-star and without DTDs or the sibling axis. Introduces a novel data-tree automaton with ExpTime emptiness and pins exact complexities of several downward fragments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hbf17e11a137f2d87
Venue: PODS
Year: 2009
Pagerank: 4.9793485e-05
Overall Rank: 12,781 | 14.07%
DOI: 10.1145/1559795.1559827

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Diego Figueira (Ecole Normale Superieure Cachan; INRIA; National Centre for Scientific Research)

BibTeX Citation

@inproceedings{figueira_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Satisfiability of Downward XPath with Data Equality Tests}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559827},
        doi = {10.1145/1559795.1559827},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Figueira, Diego},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,609	On XPath with Transitive Axes and Data Tests	2013	PODS	5.3030884e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3,795	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.0167646e-05
4,135	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.7875138e-05
6,571	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.7457654e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,974	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
2	1,599	Conjunctive Queries over Trees	2004	PODS
3	4,596	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
4	9,422	Decidable XPath Fragments in the Real World	2019	PODS
5	409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS
6	4,636	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
7	6,571	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
8	4,135	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
9	1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS
10	8,609	On XPath with Transitive Axes and Data Tests	2013	PODS