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: 4213
Venue: SIGMOD
Year: 2009
Pagerank: 5.8015211e-05
Overall Rank: 6,688 | 54.12%
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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
721	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014631814
1,582	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010295367
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
6,462	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	5.8717744e-05
6,543	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.8461929e-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
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00022278876
474	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017894953
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
719	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014637695
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,460	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010710674
1,795	Least Expected Cost Query Optimization: What Can We Expect?	2002	PODS	9.738718e-05
1,900	StatiX: Making XML Count	2002	SIGMOD	9.5168326e-05
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
9,671	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.238674e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,265	XQuery Implementation in a Relational Database System	2005	VLDB
2	12,583	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB
3	7,460	XQuery Optimization	2003	VLDB
4	12,799	The NEXT Framework for Logical XQuery Optimization	2004	VLDB
5	2,720	XQuery on SQL Hosts	2004	VLDB
6	12,635	XPath on Steroids: Exploiting Relational Engines for XPath Performance	2007	SIGMOD
7	4,576	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB
8	8,066	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB
9	12,800	ROX: Relational Over XML	2004	VLDB
10	12,703	R-SOX: Runtime Semantic Query Optimization over XML Streams	2006	VLDB