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: 3743
Venue: SIGMOD
Year: 2005
Pagerank: 5.5294867e-05
Overall Rank: 7,864 | 46.05%
DOI: 10.1145/1066157.1066242

Incoming Non-self Citations Over Time

Authors

1. Carl-Christian Kanne (University of Mannheim)
2. Matthias Brantner (University of Mannheim)
3. Guido Moerkotte (University of Mannheim)

BibTeX Citation

@inproceedings{kanne_sigmod05,
        title = {{Cost-Sensitive Reordering of Navigational Primitives}},
        author = {Kanne, Carl-Christian and Brantner, Matthias and Moerkotte, Guido},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066242},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066242},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,336	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.2612462e-05
12,383	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	5.093636e-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
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
318	Storing Semistructured Data with STORED	1999	SIGMOD	0.00021380325
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
719	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014637695
893	Accelerating XPath Location Steps	2002	SIGMOD	0.00013374715
1,462	Advanced Query Processing in Object Bases Using Access Support Relations	1990	VLDB	0.00010701465
2,317	Efficient Assembly of Complex Objects	1991	SIGMOD	8.759218e-05
2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.3300135e-05
2,902	Dual-Buffering Strategies in Object Bases	1994	VLDB	7.9769977e-05
4,042	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB	6.9407646e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
2	5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB
3	11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
4	430	A Fast Index for Semistructured Data	2001	VLDB
5	2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS
6	348	Regular Path Queries with Constraints	1997	PODS
7	4,305	Reordering Query Execution in Tertiary Memory Databases	1996	VLDB
8	3,067	Evaluating Queries with Generalized Path Expressions	1996	SIGMOD
9	7,423	Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods	2005	VLDB
10	4,109	Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases	1996	VLDB