Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps

Summary: Introduces staircase join, a DBMS join operator that encapsulates tree-aware reasoning for relational XML/XPath processing. Exploiting pre/post-order regions and subtree properties, it accelerates all XPath axes using simple integer predicates. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h381a3a839bf961b3
Venue: VLDB
Year: 2003
Pagerank: 7.0082358e-05
Overall Rank: 3,814 | 74.36%
DOI: 10.1016/B978-012722442-8/50053-7

Incoming Non-self Citations Over Time

Authors

1. Torsten Grust (University of Konstanz)
2. Maurice van Keulen (University of Twente)
3. Jens Teubner (University of Konstanz)

BibTeX Citation

@article{grust_vldb03,
        title = {{Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps}},
        author = {Grust, Torsten and van Keulen, Maurice and Teubner, Jens},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50053-7},
        url = {https://doi.org/10.1016/B978-012722442-8/50053-7},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,496	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010482718
2,779	XQuery on SQL Hosts	2004	VLDB	8.0293306e-05
5,255	Pathfinder: XQuery—The Relational Way	2005	VLDB	6.2079337e-05
7,592	XQuery Optimization	2003	VLDB	5.4880486e-05
7,624	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD	5.4821096e-05
8,147	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.3908805e-05
9,752	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.1349531e-05
11,076	Cephalopod - Virtual Data Model Composition through Partial Query Translation	2025	CIDR	4.9793485e-05
12,351	Index-Assisted Hierarchical Computations in Main-Memory RDBMS	2016	VLDB	4.9793485e-05
12,767	XPath Whole Query Optimization	2010	VLDB	4.9793485e-05
12,789	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9793485e-05
12,925	XPath on Steroids: Exploiting Relational Engines for XPath Performance	2007	SIGMOD	4.9793485e-05
14,210	An Injection with Tree Awareness: Adding Staircase Join to PostgreSQL	2004	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
86	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00035810622
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020251513
374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019707844
761	Conjunctive Selection Conditions in Main Memory	2002	PODS	0.00014143602
918	Accelerating XPath Location Steps	2002	SIGMOD	0.00013084437
1,128	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00011905274
1,554	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010270419

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,277	XQuery Implementation in a Relational Database System	2005	VLDB
2	12,986	Efficient XSLT Processing in Relational Database System	2006	VLDB
3	1,554	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
4	12,979	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD
5	12,845	Relational-Style XML Query	2008	SIGMOD
6	918	Accelerating XPath Location Steps	2002	SIGMOD
7	2,779	XQuery on SQL Hosts	2004	VLDB
8	12,925	XPath on Steroids: Exploiting Relational Engines for XPath Performance	2007	SIGMOD
9	7,624	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD
10	14,210	An Injection with Tree Awareness: Adding Staircase Join to PostgreSQL	2004	VLDB