Cost-Sensitive Reordering of Navigational Primitives

Summary: Cost-sensitive reordering of navigational primitives for path queries using partial path instances; a physical algebra isolates I/O in a single operator with sequential or asynchronous I/O. No special storage formats; relies on simple tree navigations and standard optimizations; XMark experiments show up to 4× speedup from reordering. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3681
Venue: SIGMOD
Year: 2005
Pagerank: 4.6362551e-05
Overall Rank: 7,848 | 45.41%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,317	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5719038e-05
12,188	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
98	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050023808
153	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00040784455
207	Storing Semistructured Data with STORED	1999	SIGMOD	0.00034611968
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
849	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00015962987
1,027	Accelerating XPath Location Steps	2002	SIGMOD	0.0001458865
1,493	Advanced Query Processing in Object Bases Using Access Support Relations	1990	VLDB	0.00011694373
2,218	Efficient Assembly of Complex Objects	1991	SIGMOD	9.2669145e-05
2,563	Dual-Buffering Strategies in Object Bases	1994	VLDB	8.5320612e-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
3,927	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB	6.6257049e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,046	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00014462307
5,196	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6365164e-05
11,254	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.1945683e-05
415	A Fast Index for Semistructured Data	2001	VLDB	0.00023814619
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
4,421	Reordering Query Execution in Tertiary Memory Databases	1996	VLDB	6.201063e-05
2,503	Evaluating Queries with Generalized Path Expressions	1996	SIGMOD	8.6379665e-05
7,302	Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods	2005	VLDB	4.7687064e-05
3,902	Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases	1996	VLDB	6.6499453e-05