An Injection with Tree Awareness: Adding Staircase Join to PostgreSQL

Sabine Mayer, Torsten Grust, Maurice van Keulen, Jens Teubner

Research output: Contribution to conferencePaperAcademicpeer-review

24 Downloads (Pure)

Abstract

The syntactic wellformedness constraints of XML (opening and closing tags nest properly) imply that XML processors face the challenge to efficiently handle data that takes the shape of ordered, unranked trees. Although RDBMSs have originally been designed to manage table-shaped data, we propose their use as XML and XPath processors. In our setup, the database system employs a relational XML document encoding, the XPath accelerator [1], which maps information about the XML node hierarchy to a table, thus making it possible to evaluate XPath expressions on SQL hosts. Conventional RDBMSs, nevertheless, remain ignorant of many interesting properties of the encoded tree data, and were thus found to make no or poor use of these properties. This is why we devised a new join algorithm, staircase join [2], which incorporates the tree-specific knowledge required for an efficient SQL-based evaluation of XPath expressions. In a sense, this demonstration delivers the promise we have made at VLDB 2003 [2]: a notion of tree awareness can be injected into a conventional disk-based RDBMS kernel in terms of staircase join. The demonstration features a side-by-side comparison of both, an original and a staircase-join enhanced instance of PostgreSQL [4]. The required changes to PostgreSQL were local, the achieved eect, however, is significant: the demonstration proves that this injection of tree awareness turns PostgreSQL into a high-performance XML processor that closely adheres to the XPath semantics.
Original languageEnglish
Pages1305-1308
Number of pages4
Publication statusPublished - Sep 2004

Fingerprint

XML
Demonstrations
Syntactics
Particle accelerators
Semantics

Keywords

  • DB-PRJPF: PATHFINDER
  • EWI-7280
  • IR-63509
  • DB-XMLDB: XML DATABASES

Cite this

@conference{7e50b28c237941a9ac1b737dde1c7291,
title = "An Injection with Tree Awareness: Adding Staircase Join to PostgreSQL",
abstract = "The syntactic wellformedness constraints of XML (opening and closing tags nest properly) imply that XML processors face the challenge to efficiently handle data that takes the shape of ordered, unranked trees. Although RDBMSs have originally been designed to manage table-shaped data, we propose their use as XML and XPath processors. In our setup, the database system employs a relational XML document encoding, the XPath accelerator [1], which maps information about the XML node hierarchy to a table, thus making it possible to evaluate XPath expressions on SQL hosts. Conventional RDBMSs, nevertheless, remain ignorant of many interesting properties of the encoded tree data, and were thus found to make no or poor use of these properties. This is why we devised a new join algorithm, staircase join [2], which incorporates the tree-specific knowledge required for an efficient SQL-based evaluation of XPath expressions. In a sense, this demonstration delivers the promise we have made at VLDB 2003 [2]: a notion of tree awareness can be injected into a conventional disk-based RDBMS kernel in terms of staircase join. The demonstration features a side-by-side comparison of both, an original and a staircase-join enhanced instance of PostgreSQL [4]. The required changes to PostgreSQL were local, the achieved eect, however, is significant: the demonstration proves that this injection of tree awareness turns PostgreSQL into a high-performance XML processor that closely adheres to the XPath semantics.",
keywords = "DB-PRJPF: PATHFINDER, EWI-7280, IR-63509, DB-XMLDB: XML DATABASES",
author = "Sabine Mayer and Torsten Grust and {van Keulen}, Maurice and Jens Teubner",
note = "Imported from EWI/DB PMS [db-utwente:inpr:0000003577], Demo paper.",
year = "2004",
month = "9",
language = "English",
pages = "1305--1308",

}

An Injection with Tree Awareness : Adding Staircase Join to PostgreSQL. / Mayer, Sabine; Grust, Torsten; van Keulen, Maurice; Teubner, Jens.

2004. 1305-1308.

Research output: Contribution to conferencePaperAcademicpeer-review

TY - CONF

T1 - An Injection with Tree Awareness

T2 - Adding Staircase Join to PostgreSQL

AU - Mayer, Sabine

AU - Grust, Torsten

AU - van Keulen, Maurice

AU - Teubner, Jens

N1 - Imported from EWI/DB PMS [db-utwente:inpr:0000003577], Demo paper.

PY - 2004/9

Y1 - 2004/9

N2 - The syntactic wellformedness constraints of XML (opening and closing tags nest properly) imply that XML processors face the challenge to efficiently handle data that takes the shape of ordered, unranked trees. Although RDBMSs have originally been designed to manage table-shaped data, we propose their use as XML and XPath processors. In our setup, the database system employs a relational XML document encoding, the XPath accelerator [1], which maps information about the XML node hierarchy to a table, thus making it possible to evaluate XPath expressions on SQL hosts. Conventional RDBMSs, nevertheless, remain ignorant of many interesting properties of the encoded tree data, and were thus found to make no or poor use of these properties. This is why we devised a new join algorithm, staircase join [2], which incorporates the tree-specific knowledge required for an efficient SQL-based evaluation of XPath expressions. In a sense, this demonstration delivers the promise we have made at VLDB 2003 [2]: a notion of tree awareness can be injected into a conventional disk-based RDBMS kernel in terms of staircase join. The demonstration features a side-by-side comparison of both, an original and a staircase-join enhanced instance of PostgreSQL [4]. The required changes to PostgreSQL were local, the achieved eect, however, is significant: the demonstration proves that this injection of tree awareness turns PostgreSQL into a high-performance XML processor that closely adheres to the XPath semantics.

AB - The syntactic wellformedness constraints of XML (opening and closing tags nest properly) imply that XML processors face the challenge to efficiently handle data that takes the shape of ordered, unranked trees. Although RDBMSs have originally been designed to manage table-shaped data, we propose their use as XML and XPath processors. In our setup, the database system employs a relational XML document encoding, the XPath accelerator [1], which maps information about the XML node hierarchy to a table, thus making it possible to evaluate XPath expressions on SQL hosts. Conventional RDBMSs, nevertheless, remain ignorant of many interesting properties of the encoded tree data, and were thus found to make no or poor use of these properties. This is why we devised a new join algorithm, staircase join [2], which incorporates the tree-specific knowledge required for an efficient SQL-based evaluation of XPath expressions. In a sense, this demonstration delivers the promise we have made at VLDB 2003 [2]: a notion of tree awareness can be injected into a conventional disk-based RDBMS kernel in terms of staircase join. The demonstration features a side-by-side comparison of both, an original and a staircase-join enhanced instance of PostgreSQL [4]. The required changes to PostgreSQL were local, the achieved eect, however, is significant: the demonstration proves that this injection of tree awareness turns PostgreSQL into a high-performance XML processor that closely adheres to the XPath semantics.

KW - DB-PRJPF: PATHFINDER

KW - EWI-7280

KW - IR-63509

KW - DB-XMLDB: XML DATABASES

M3 - Paper

SP - 1305

EP - 1308

ER -