ROX: Run-time Optimization of XQueries

Summary: ROX: run-time optimization of XQueries by executing, materializing intermediates, and using sampling-based estimation over a Join Graph of equi-joins and XPath steps. Zero-investment operators and XML value indices bound materialization and exploration costs to be linear in sample size, yielding robust query plans with modest runtime overhead on large XML datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hbde379882c9fede8
Venue: SIGMOD
Year: 2009
Pagerank: 5.6593309e-05
Overall Rank: 6,816 | 54.32%
DOI: 10.1145/1559845.1559910

Incoming Non-self Citations Over Time

Authors

1. Riham Abdel Kader (University of Twente)
2. Peter Boncz (Centrum Wiskunde & Informatica)
3. Stefan Manegold (Centrum Wiskunde & Informatica)
4. Maurice van Keulen (University of Twente)

BibTeX Citation

@inproceedings{kader_sigmod09,
        title = {{ROX: Run-time Optimization of XQueries}},
        author = {Kader, Riham Abdel and Boncz, Peter and Manegold, Stefan and van Keulen, Maurice},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559910},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559910},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
689	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014725904
702	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.0001464107
1,614	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010054823
5,029	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.2952031e-05
5,713	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	6.0090633e-05
6,672	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.6975871e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00042977538
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040739114
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034691614
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028910892
180	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026534482
291	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00021898776
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017691682
479	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017595584
568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016221103
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015166402
735	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014329959
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013042589
1,497	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010447125
1,831	Least Expected Cost Query Optimization: What Can We Expect?	2002	PODS	9.5366955e-05
1,969	StatiX: Making XML Count	2002	SIGMOD	9.2805411e-05
3,263	Approximate XML Query Answers	2004	SIGMOD	7.4679565e-05
5,591	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0553413e-05
9,888	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.1020175e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,289	XQuery Implementation in a Relational Database System	2005	VLDB
2	7,612	XQuery Optimization	2003	VLDB
3	12,921	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB
4	13,136	The NEXT Framework for Logical XQuery Optimization	2004	VLDB
5	2,786	XQuery on SQL Hosts	2004	VLDB
6	12,973	XPath on Steroids: Exploiting Relational Engines for XPath Performance	2007	SIGMOD
7	4,694	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB
8	8,261	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB
9	13,137	ROX: Relational Over XML	2004	VLDB
10	13,041	R-SOX: Runtime Semantic Query Optimization over XML Streams	2006	VLDB