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: hcff27389784ee7c6
Venue: SIGMOD
Year: 2005
Pagerank: 5.4054691e-05
Overall Rank: 8,022 | 46.07%
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,462	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.1221387e-05
12,674	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	4.9793485e-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
86	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00035810622
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029294114
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
326	Storing Semistructured Data with STORED	1999	SIGMOD	0.00020963333
679	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014837097
733	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014379182
918	Accelerating XPath Location Steps	2002	SIGMOD	0.00013084437
1,498	Advanced Query Processing in Object Bases Using Access Support Relations	1990	VLDB	0.00010472681
2,366	Efficient Assembly of Complex Objects	1991	SIGMOD	8.5648664e-05
2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.1432169e-05
2,958	Dual-Buffering Strategies in Object Bases	1994	VLDB	7.8077689e-05
4,136	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB	6.7872141e-05

Semantically Similar Papers

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