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

Torsten Grust; Maurice van Keulen; Jens Teubner

doi:10.1016/B978-012722442-8/50053-7

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

Torsten Grust
, Maurice van Keulen
, Jens Teubner

Databases (Former)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

94 Citations (Scopus)

123 Downloads (Pure)

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.

Original language	English
Title of host publication	Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003
Subtitle of host publication	Berlin, Germany, September 9-12, 2003
Editors	Johann Christoph Freytag, Peter C. Lockemann, Serge Abiteboul, Michael J. Carey, Patricia G. Selinger, Andreas Heuer
Place of Publication	Berlin, Germany
Publisher	Morgan Kaufmann
Pages	524-535
Number of pages	12
ISBN (Electronic)	9780127224428
ISBN (Print)	0-12-722442-4
DOIs	https://doi.org/10.1016/B978-012722442-8/50053-7
Publication status	Published - 2003
Event	29th International Conference on Very Large Data Bases, VLDB 2003 - Berlin, Germany Duration: 9 Sept 2003 → 12 Sept 2003 Conference number: 29

Conference

Conference	29th International Conference on Very Large Data Bases, VLDB 2003
Abbreviated title	VLDB
Country/Territory	Germany
City	Berlin
Period	9/09/03 → 12/09/03

Keywords

DB-XMLDB: XML DATABASES
DB-PRJPF: PATHFINDER

Access to Document

10.1016/B978-012722442-8/50053-7

Grust2003staircaseAccepted author version, 264 KB

http://www.vldb.org/conf/2003/papers/S16P03.pdf

Cite this

Grust, T., van Keulen, M., & Teubner, J. (2003). Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. In J. C. Freytag, P. C. Lockemann, S. Abiteboul, M. J. Carey, P. G. Selinger, & A. Heuer (Eds.), Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003: Berlin, Germany, September 9-12, 2003 (pp. 524-535). Morgan Kaufmann. https://doi.org/10.1016/B978-012722442-8/50053-7

Grust, Torsten ; van Keulen, Maurice ; Teubner, Jens. / Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003: Berlin, Germany, September 9-12, 2003. editor / Johann Christoph Freytag ; Peter C. Lockemann ; Serge Abiteboul ; Michael J. Carey ; Patricia G. Selinger ; Andreas Heuer. Berlin, Germany : Morgan Kaufmann, 2003. pp. 524-535

@inproceedings{c92c1b227e8743fb9c0269d5eb7e808a,

title = "Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps",

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.",

keywords = "DB-XMLDB: XML DATABASES, DB-PRJPF: PATHFINDER",

author = "Torsten Grust and \{van Keulen\}, Maurice and Jens Teubner",

note = "Publisher Copyright: {\textcopyright} 2003 Elsevier Inc. All rights reserved.; 29th International Conference on Very Large Data Bases, VLDB 2003, VLDB ; Conference date: 09-09-2003 Through 12-09-2003",

year = "2003",

doi = "10.1016/B978-012722442-8/50053-7",

language = "English",

isbn = "0-12-722442-4",

pages = "524--535",

editor = "Freytag, \{Johann Christoph\} and Lockemann, \{Peter C.\} and Serge Abiteboul and Carey, \{Michael J.\} and Selinger, \{Patricia G.\} and Andreas Heuer",

booktitle = "Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003",

publisher = "Morgan Kaufmann",

address = "United States",

}

Grust, T, van Keulen, M & Teubner, J 2003, Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. in JC Freytag, PC Lockemann, S Abiteboul, MJ Carey, PG Selinger & A Heuer (eds), Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003: Berlin, Germany, September 9-12, 2003. Morgan Kaufmann, Berlin, Germany, pp. 524-535, 29th International Conference on Very Large Data Bases, VLDB 2003, Berlin, Berlin, Germany, 9/09/03. https://doi.org/10.1016/B978-012722442-8/50053-7

Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. / Grust, Torsten; van Keulen, Maurice; Teubner, Jens.
Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003: Berlin, Germany, September 9-12, 2003. ed. / Johann Christoph Freytag; Peter C. Lockemann; Serge Abiteboul; Michael J. Carey; Patricia G. Selinger; Andreas Heuer. Berlin, Germany: Morgan Kaufmann, 2003. p. 524-535.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Grust, Torsten

AU - van Keulen, Maurice

AU - Teubner, Jens

N1 - Conference code: 29

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - DB-XMLDB: XML DATABASES

KW - DB-PRJPF: PATHFINDER

UR - https://www.scopus.com/pages/publications/84920874675

U2 - 10.1016/B978-012722442-8/50053-7

DO - 10.1016/B978-012722442-8/50053-7

M3 - Conference contribution

SN - 0-12-722442-4

SP - 524

EP - 535

BT - Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003

A2 - Freytag, Johann Christoph

A2 - Lockemann, Peter C.

A2 - Abiteboul, Serge

A2 - Carey, Michael J.

A2 - Selinger, Patricia G.

A2 - Heuer, Andreas

PB - Morgan Kaufmann

CY - Berlin, Germany

T2 - 29th International Conference on Very Large Data Bases, VLDB 2003

Y2 - 9 September 2003 through 12 September 2003

ER -

Grust T, van Keulen M, Teubner J. Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. In Freytag JC, Lockemann PC, Abiteboul S, Carey MJ, Selinger PG, Heuer A, editors, Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003: Berlin, Germany, September 9-12, 2003. Berlin, Germany: Morgan Kaufmann. 2003. p. 524-535 doi: 10.1016/B978-012722442-8/50053-7

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint