Tree Awareness for Relational DBMS Kernels : Staircase Join

Lade...
Vorschaubild
Dateien
Datum
2003
Autor:innen
Grust, Torsten
Keulen, Maurice van
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
BLANKEN, Henk, ed., Torsten GRABS, ed., Hans-Jörg SCHEK, ed., Ralf SCHENKEL, ed., Gerhard WEIKUM, ed.. Intelligent Search on XML Data. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 231-245. Lecture Notes in Computer Science. 2818. ISBN 978-3-540-40768-3. Available under: doi: 10.1007/978-3-540-45194-5_16
Zusammenfassung

Relational database management systems (RDBMSs) derive much of their efficiency from the versatility of their core data structure: tables of tuples. Such tables are simple enough to allow for an efficient representation on all levels of the memory hierarchy, yet sufficiently generic to host a wide range of data types. If one can devise mappings from a data type Tau to tables and from operations on Tau to relational queries, an RDBMS may be a premier implementation alternative. Temporal intervals, complex nested objects, and spatial data are sample instances for such types Tau . The key to efficiency of the relational approach is that the RDBMS is made aware of the specific properties of Tau . Typically, such awareness can be implemented in the form of index structures (e.g., R-trees [7] efficiently encode the inclusion and overlap of spatial objects) or query operators (e.g., the multi-predicate merge join [11] exploits knowledge about containment of nested intervals). This chapter applies this principle to the tree data type with the goal to turn RDBMSs into efficient XML and XPath processors [1]. The database system is supplied with a relational [8] XML document encoding, the XPath accelerator [5]. Encoded documents (1) are represented in relational tables, (2) can be efficiently indexed using index structures native to the RDBMS, namely B-trees, and (3) XPath queries may be mapped to SQL queries over these tables. The resulting purely relational XPath processor is efficient [5] and complete (supports all 13 XPath axes). We will show that an enhanced level of tree awareness, however, can lead to a query speed-up by an order of magnitude. Tree awareness is injected into the database kernel in terms of the staircase join operator, which is tuned to exploit the knowledge that the RDBMS operates over tables encoding treeshaped data. This is a local change to the database kernel: standard B-trees suffice to support the evaluation of staircase join and the query optimizer may treat staircase join much like other native join operators.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690GRUST, Torsten, Maurice van KEULEN, 2003. Tree Awareness for Relational DBMS Kernels : Staircase Join. In: BLANKEN, Henk, ed., Torsten GRABS, ed., Hans-Jörg SCHEK, ed., Ralf SCHENKEL, ed., Gerhard WEIKUM, ed.. Intelligent Search on XML Data. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 231-245. Lecture Notes in Computer Science. 2818. ISBN 978-3-540-40768-3. Available under: doi: 10.1007/978-3-540-45194-5_16
BibTex
@inproceedings{Grust2003Aware-6262,
  year={2003},
  doi={10.1007/978-3-540-45194-5_16},
  title={Tree Awareness for Relational DBMS Kernels : Staircase Join},
  number={2818},
  isbn={978-3-540-40768-3},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Intelligent Search on XML Data},
  pages={231--245},
  editor={Blanken, Henk and Grabs, Torsten and Schek, Hans-Jörg and Schenkel, Ralf and Weikum, Gerhard},
  author={Grust, Torsten and Keulen, Maurice van}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6262">
    <dc:creator>Grust, Torsten</dc:creator>
    <dcterms:title>Tree Awareness for Relational DBMS Kernels : Staircase Join</dcterms:title>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6262/1/Tree_Awareness_for_Relational_DBMS_Kernels_2003.pdf"/>
    <dcterms:bibliographicCitation>First publ. in:  Intelligent search on XML data : applications, languages, models, implementations, and benchmarks / Henk Blanken ... (ed.). - Berlin; Heidelberg [u.a.] : Springer, 2003. - S. 231-246. - (Lecture notes in computer science ; 2818). - ISBN 3-540-40768-5</dcterms:bibliographicCitation>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6262"/>
    <dc:rights>terms-of-use</dc:rights>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:format>application/pdf</dc:format>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:issued>2003</dcterms:issued>
    <dcterms:abstract xml:lang="deu">Relational database management systems (RDBMSs) derive much of their efficiency from the versatility of their core data structure: tables of tuples. Such tables are simple enough to allow for an efficient representation on all levels of the memory hierarchy, yet sufficiently generic to host a wide range of data types. If one can devise mappings from a data type Tau to tables and from operations on Tau to relational queries, an RDBMS may be a premier implementation alternative. Temporal intervals, complex nested objects, and spatial data are sample instances for such types Tau . The key to efficiency of the relational approach is that the RDBMS is made aware of the specific properties of Tau . Typically, such awareness can be implemented in the form of index structures (e.g., R-trees [7] efficiently encode the inclusion and overlap of spatial objects) or query operators (e.g., the multi-predicate merge join [11] exploits knowledge about containment of nested intervals). This chapter applies this principle to the tree data type with the goal to turn RDBMSs into efficient XML and XPath processors [1]. The database system is supplied with a relational [8] XML document encoding, the XPath accelerator [5]. Encoded documents (1) are represented in relational tables, (2) can be efficiently indexed using index structures native to the RDBMS, namely B-trees, and (3) XPath queries may be mapped to SQL queries over these tables. The resulting purely relational XPath processor is efficient [5] and complete (supports all 13 XPath axes). We will show that an enhanced level of tree awareness, however, can lead to a query speed-up by an order of magnitude. Tree awareness is injected into the database kernel in terms of the staircase join operator, which is tuned to exploit the knowledge that the RDBMS operates over tables encoding treeshaped data. This is a local change to the database kernel: standard B-trees suffice to support the evaluation of staircase join and the query optimizer may treat staircase join much like other native join operators.</dcterms:abstract>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6262/1/Tree_Awareness_for_Relational_DBMS_Kernels_2003.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:35Z</dc:date>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:35Z</dcterms:available>
    <dc:language>deu</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Keulen, Maurice van</dc:contributor>
    <dc:contributor>Grust, Torsten</dc:contributor>
    <dc:creator>Keulen, Maurice van</dc:creator>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen