The Expressivity of XPath with Transitive Closure*

Summary: Extend Core XPath with transitive closure and path equalities to define Regular XPath*, proven expressively complete for FO* (first-order logic with a binary transitive-closure operator). Consequences: closure under path intersection/complementation and characterizations of the *-positive fragment and mu-Regular XPath (least fixed points). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1404
Venue: PODS
Year: 2006
Pagerank: 7.1778094e-05
Overall Rank: 3,711 | 74.55%
DOI: 10.1145/1142351.1142398

Incoming Non-self Citations Over Time

Authors

1. Balder ten Cate (University of Amsterdam)

BibTeX Citation

@inproceedings{cate_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{The Expressivity of XPath with Transitive Closure*}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142398},
        doi = {10.1145/1142351.1142398},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cate, Balder ten},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.6592957e-05
4,641	High-Performance Complex Event Processing over XML Streams	2012	SIGMOD	6.5913488e-05
6,137	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS	5.9643797e-05
6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.8776391e-05
7,409	From Regular Expressions to Nested Words: Unifying Languages and Query Execution for Relational and XML Sequences	2010	VLDB	5.6243e-05
7,410	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	5.6242786e-05
9,249	Decidable XPath Fragments in the Real World	2019	PODS	5.2987261e-05
12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
2,132	The Complexity of XPath Query Evaluation	2003	PODS	9.119436e-05
2,969	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	7.9147299e-05
7,172	Query Translation from XPath to SQL in the Presence of Recursive DTDs	2005	VLDB	5.6837389e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,564	Conjunctive Queries over Trees	2004	PODS
2	7,876	Extended Path Expressions for XML	2001	PODS
3	12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS
4	9,249	Decidable XPath Fragments in the Real World	2019	PODS
5	395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS
6	8,440	On XPath with Transitive Axes and Data Tests	2013	PODS
7	12,684	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
8	8,550	Conditional XPath, the first order complete XPath dialect*	2004	PODS
9	4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
10	6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS