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

J.C. Freytag (Editor), Torsten Grust, P.C. Lockemann (Editor), Maurice van Keulen, J. Teubner, S. Abiteboul (Editor), M. Carey (Editor), P. Selinger (Editor), A. Heuer (Editor)

Research output: Contribution to conferencePaperAcademicpeer-review

12 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 languageUndefined
Pages524-535
Number of pages12
Publication statusPublished - Sep 2003

Keywords

  • DB-XMLDB: XML DATABASES
  • EWI-7252
  • IR-63505
  • DB-PRJPF: PATHFINDER

Cite this

Freytag, J. C. (Ed.), Grust, T., Lockemann, P. C. (Ed.), van Keulen, M., Teubner, J., Abiteboul, S. (Ed.), ... Heuer, A. (Ed.) (2003). Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. 524-535.
Freytag, J.C. (Editor) ; Grust, Torsten ; Lockemann, P.C. (Editor) ; van Keulen, Maurice ; Teubner, J. ; Abiteboul, S. (Editor) ; Carey, M. (Editor) ; Selinger, P. (Editor) ; Heuer, A. (Editor). / Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. 12 p.
@conference{cd8e18360209437e884f6956fbe5b3a2,
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, EWI-7252, IR-63505, DB-PRJPF: PATHFINDER",
author = "J.C. Freytag and Torsten Grust and P.C. Lockemann and {van Keulen}, Maurice and J. Teubner and S. Abiteboul and M. Carey and P. Selinger and A. Heuer",
note = "Imported from EWI/DB PMS [db-utwente:inpr:0000003277]",
year = "2003",
month = "9",
language = "Undefined",
pages = "524--535",

}

Freytag, JC (ed.), Grust, T, Lockemann, PC (ed.), van Keulen, M, Teubner, J, Abiteboul, S (ed.), Carey, M (ed.), Selinger, P (ed.) & Heuer, A (ed.) 2003, 'Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps' pp. 524-535.

Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. / Freytag, J.C. (Editor); Grust, Torsten; Lockemann, P.C. (Editor); van Keulen, Maurice; Teubner, J.; Abiteboul, S. (Editor); Carey, M. (Editor); Selinger, P. (Editor); Heuer, A. (Editor).

2003. 524-535.

Research output: Contribution to conferencePaperAcademicpeer-review

TY - CONF

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

AU - Grust, Torsten

AU - van Keulen, Maurice

AU - Teubner, J.

A2 - Freytag, J.C.

A2 - Lockemann, P.C.

A2 - Abiteboul, S.

A2 - Carey, M.

A2 - Selinger, P.

A2 - Heuer, A.

N1 - Imported from EWI/DB PMS [db-utwente:inpr:0000003277]

PY - 2003/9

Y1 - 2003/9

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 - EWI-7252

KW - IR-63505

KW - DB-PRJPF: PATHFINDER

M3 - Paper

SP - 524

EP - 535

ER -

Freytag JC, (ed.), Grust T, Lockemann PC, (ed.), van Keulen M, Teubner J, Abiteboul S, (ed.) et al. Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. 2003.