Conditional XPath, the first order complete XPath dialect*

Summary: Introduce Conditional XPath: Core XPath extended with conditional axis relations to express conditional paths (e.g., "do child step while test holds"). Prove on ordered trees it is first-order complete—equally expressive as FO—via since/until-style temporal operators. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1304
Venue: PODS
Year: 2004
Pagerank: 4.5435639e-05
Overall Rank: 8,314 | 42.17%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Maarten Marx

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,491	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.1945683e-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
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
602	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00019352415
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
2,248	The Complexity of XPath Query Evaluation	2003	PODS	9.2038466e-05
2,584	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	8.4948053e-05
2,855	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.0059865e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
2,248	The Complexity of XPath Query Evaluation	2003	PODS	9.2038466e-05
7,681	SXPath - Extending XPath towards Spatial Querying on Web Documents	2011	VLDB	4.6804276e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
9,105	Decidable XPath Fragments in the Real World	2019	PODS	4.3953995e-05
8,200	On XPath with Transitive Axes and Data Tests	2013	PODS	4.5602267e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
12,491	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.1945683e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
3,851	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.7057867e-05