MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane

Peter Boncz, Jan Flokstra, Torsten Grust, Maurice van Keulen, Stefan Manegold, Sjoerd Mullender, Jan Rittinger, Jens Teubner

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

2 Citations (Scopus)
14 Downloads (Pure)

Abstract

Relational XQuery processors aim at leveraging mature relational DBMS query processing technology to provide scalability and efficiency. To achieve this goal, various storage schemes have been proposed to encode the tree structure of XML documents in flat relational tables. Basically, two classes can be identified: (1) encodings using fixed-length surrogates, like the preorder ranks in the pre/post encoding [5] or the equivalent pre/size/level encoding [8], and (2) encodings using variable-length surrogates, like, e.g., ORDPATH [9] or P-PBiTree [12]. Recent research [1] showed a clear advantage of the former for efficient evaluation of XPath location steps, exploiting techniques like cheap node order tests, positional lookup, and node skipping in staircase join [7]. However, once updates are involved, variable-length surrogates are often considered the better choice, mainly as a straightforward implementation of structural XML updates using fixed-length surrogates faces two performance bottlenecks: (i) high physical cost (the preorder ranks of all nodes following the update position must be modified—on average 50% of the document), and (ii) low transaction concurrency (updating the size of all ancestor nodes causes lock contention on the document root).
Original languageUndefined
Title of host publicationProceedings of the 10th International Conference on Extending Database Technology (EDBT 2006)
Place of PublicationBerlin, Germany
PublisherSpringer
Pages1190-1193
Number of pages4
ISBN (Print)978-3-540-32960-2
DOIs
Publication statusPublished - Mar 2006
Event10th International Conference on Extending Database Technology, EDBT 2006 - Munich, Germany
Duration: 26 Mar 200631 Mar 2006
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3896
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Extending Database Technology, EDBT 2006
Abbreviated titleEDBT
CountryGermany
CityMunich
Period26/03/0631/03/06

Keywords

  • METIS-238692
  • EWI-7536
  • DB-XMLDB: XML DATABASES
  • IR-63574
  • DB-PRJPF: PATHFINDER

Cite this

Boncz, P., Flokstra, J., Grust, T., van Keulen, M., Manegold, S., Mullender, S., ... Teubner, J. (2006). MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane. In Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006) (pp. 1190-1193). [10.1007/11687238_89] (Lecture Notes in Computer Science; Vol. 3896). Berlin, Germany: Springer. https://doi.org/10.1007/11687238_89
Boncz, Peter ; Flokstra, Jan ; Grust, Torsten ; van Keulen, Maurice ; Manegold, Stefan ; Mullender, Sjoerd ; Rittinger, Jan ; Teubner, Jens. / MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane. Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006). Berlin, Germany : Springer, 2006. pp. 1190-1193 (Lecture Notes in Computer Science).
@inproceedings{0e9ec3559a914b5c92ed0c0cbe593605,
title = "MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane",
abstract = "Relational XQuery processors aim at leveraging mature relational DBMS query processing technology to provide scalability and efficiency. To achieve this goal, various storage schemes have been proposed to encode the tree structure of XML documents in flat relational tables. Basically, two classes can be identified: (1) encodings using fixed-length surrogates, like the preorder ranks in the pre/post encoding [5] or the equivalent pre/size/level encoding [8], and (2) encodings using variable-length surrogates, like, e.g., ORDPATH [9] or P-PBiTree [12]. Recent research [1] showed a clear advantage of the former for efficient evaluation of XPath location steps, exploiting techniques like cheap node order tests, positional lookup, and node skipping in staircase join [7]. However, once updates are involved, variable-length surrogates are often considered the better choice, mainly as a straightforward implementation of structural XML updates using fixed-length surrogates faces two performance bottlenecks: (i) high physical cost (the preorder ranks of all nodes following the update position must be modified—on average 50{\%} of the document), and (ii) low transaction concurrency (updating the size of all ancestor nodes causes lock contention on the document root).",
keywords = "METIS-238692, EWI-7536, DB-XMLDB: XML DATABASES, IR-63574, DB-PRJPF: PATHFINDER",
author = "Peter Boncz and Jan Flokstra and Torsten Grust and {van Keulen}, Maurice and Stefan Manegold and Sjoerd Mullender and Jan Rittinger and Jens Teubner",
note = "Imported from EWI/DB PMS [db-utwente:inpr:0000003685], demo paper.",
year = "2006",
month = "3",
doi = "10.1007/11687238_89",
language = "Undefined",
isbn = "978-3-540-32960-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "1190--1193",
booktitle = "Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006)",

}

Boncz, P, Flokstra, J, Grust, T, van Keulen, M, Manegold, S, Mullender, S, Rittinger, J & Teubner, J 2006, MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane. in Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006)., 10.1007/11687238_89, Lecture Notes in Computer Science, vol. 3896, Springer, Berlin, Germany, pp. 1190-1193, 10th International Conference on Extending Database Technology, EDBT 2006, Munich, Germany, 26/03/06. https://doi.org/10.1007/11687238_89

MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane. / Boncz, Peter; Flokstra, Jan; Grust, Torsten; van Keulen, Maurice; Manegold, Stefan; Mullender, Sjoerd; Rittinger, Jan; Teubner, Jens.

Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006). Berlin, Germany : Springer, 2006. p. 1190-1193 10.1007/11687238_89 (Lecture Notes in Computer Science; Vol. 3896).

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

TY - GEN

T1 - MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane

AU - Boncz, Peter

AU - Flokstra, Jan

AU - Grust, Torsten

AU - van Keulen, Maurice

AU - Manegold, Stefan

AU - Mullender, Sjoerd

AU - Rittinger, Jan

AU - Teubner, Jens

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

PY - 2006/3

Y1 - 2006/3

N2 - Relational XQuery processors aim at leveraging mature relational DBMS query processing technology to provide scalability and efficiency. To achieve this goal, various storage schemes have been proposed to encode the tree structure of XML documents in flat relational tables. Basically, two classes can be identified: (1) encodings using fixed-length surrogates, like the preorder ranks in the pre/post encoding [5] or the equivalent pre/size/level encoding [8], and (2) encodings using variable-length surrogates, like, e.g., ORDPATH [9] or P-PBiTree [12]. Recent research [1] showed a clear advantage of the former for efficient evaluation of XPath location steps, exploiting techniques like cheap node order tests, positional lookup, and node skipping in staircase join [7]. However, once updates are involved, variable-length surrogates are often considered the better choice, mainly as a straightforward implementation of structural XML updates using fixed-length surrogates faces two performance bottlenecks: (i) high physical cost (the preorder ranks of all nodes following the update position must be modified—on average 50% of the document), and (ii) low transaction concurrency (updating the size of all ancestor nodes causes lock contention on the document root).

AB - Relational XQuery processors aim at leveraging mature relational DBMS query processing technology to provide scalability and efficiency. To achieve this goal, various storage schemes have been proposed to encode the tree structure of XML documents in flat relational tables. Basically, two classes can be identified: (1) encodings using fixed-length surrogates, like the preorder ranks in the pre/post encoding [5] or the equivalent pre/size/level encoding [8], and (2) encodings using variable-length surrogates, like, e.g., ORDPATH [9] or P-PBiTree [12]. Recent research [1] showed a clear advantage of the former for efficient evaluation of XPath location steps, exploiting techniques like cheap node order tests, positional lookup, and node skipping in staircase join [7]. However, once updates are involved, variable-length surrogates are often considered the better choice, mainly as a straightforward implementation of structural XML updates using fixed-length surrogates faces two performance bottlenecks: (i) high physical cost (the preorder ranks of all nodes following the update position must be modified—on average 50% of the document), and (ii) low transaction concurrency (updating the size of all ancestor nodes causes lock contention on the document root).

KW - METIS-238692

KW - EWI-7536

KW - DB-XMLDB: XML DATABASES

KW - IR-63574

KW - DB-PRJPF: PATHFINDER

U2 - 10.1007/11687238_89

DO - 10.1007/11687238_89

M3 - Conference contribution

SN - 978-3-540-32960-2

T3 - Lecture Notes in Computer Science

SP - 1190

EP - 1193

BT - Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006)

PB - Springer

CY - Berlin, Germany

ER -

Boncz P, Flokstra J, Grust T, van Keulen M, Manegold S, Mullender S et al. MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane. In Proceedings of the 10th International Conference on Extending Database Technology (EDBT 2006). Berlin, Germany: Springer. 2006. p. 1190-1193. 10.1007/11687238_89. (Lecture Notes in Computer Science). https://doi.org/10.1007/11687238_89