Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps


Grust, Torsten and Keulen, Maurice van and Teubner, J. (2003) Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. In: 29th International Conference on Very Large Databases, VLDB 2003, 9-12 Sep 2003, Berlin, Germany (pp. pp. 524-535).

open access
Abstract:Relational query processors derive much of their effectiveness from the awareness of specific table properties like sort order, size, or absence of duplicate tuples. This text applies (and adapts) this successful principle to database-supported XML and XPath processing: the relational system is made tree aware, i.e., tree properties like subtree size, intersection of paths, inclusion or disjointness of subtrees are made explicit. We propose a local change to the database kernel, the staircase join, which encapsulates the necessary tree knowledge needed to improve XPath performance. Staircase join operates on an XML encoding which makes this knowledge available at the cost of simple integer operations (e.g., +, <=). We finally report on quite promising experiments with a staircase join enhanced main-memory database kernel.
Item Type:Conference or Workshop Item
Additional information:Imported from EWI/DB PMS [db-utwente:inpr:0000003277]
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page