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

Torsten Grust, Maurice van Keulen, Jens Teubner

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

85 Citations (Scopus)
17 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 languageEnglish
Title of host publicationProceedings of 29th International Conference on Very Large Data Bases, VLDB 2003
Subtitle of host publicationBerlin, Germany, September 9-12, 2003
EditorsJohann Christoph Freytag, Peter C. Lockemann, Serge Abiteboul, Michael J. Carey, Patricia G. Selinger, Andreas Heuer
Place of PublicationBerlin, Germany
PublisherMorgan Kaufmann Publishers
Pages524-535
Number of pages12
ISBN (Print)0-12-722442-4
Publication statusPublished - 2003
Event29th International Conference on Very Large Data Bases, VLDB 2003 - Berlin, Germany
Duration: 9 Sep 200312 Sep 2003
Conference number: 29

Conference

Conference29th International Conference on Very Large Data Bases, VLDB 2003
Abbreviated titleVLDB
CountryGermany
CityBerlin
Period9/09/0312/09/03

Keywords

  • DB-XMLDB: XML DATABASES
  • DB-PRJPF: PATHFINDER

Fingerprint Dive into the research topics of 'Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps'. Together they form a unique fingerprint.

Cite this