Order Indexes: supporting highly dynamic hierarchical data in relational main-memory database systems

Jan Finis; Robert Brunel; Alfons Kemper; Thomas Neumann; Norman May; Franz Faerber

doi:10.1007/s00778-016-0436-3

Order Indexes: supporting highly dynamic hierarchical data in relational main-memory database systems

Jan Finis, Robert Brunel, Alfons Kemper, Thomas Neumann, Norman May, Franz Faerber

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Maintaining and querying hierarchical data in a relational database system is an important task in many business applications. This task is especially challenging when considering dynamic use cases with a high rate of complex, possibly skewed structural updates. Labeling schemes are widely considered the indexing technique of choice for hierarchical data, and many different schemes have been proposed. However, they cannot handle dynamic use cases well due to various problems, which we investigate in this paper. We therefore propose Order Indexes—a dynamic representation of the nested intervals encoding—which offer competitive query performance, unprecedented update efficiency, and robustness for highly dynamic workloads.

Original language	English
Pages (from-to)	55-80
Number of pages	26
Journal	VLDB Journal
Volume	26
Issue number	1
DOIs	https://doi.org/10.1007/s00778-016-0436-3
State	Published - 1 Feb 2017

Keywords

Hierarchical data
Indexing
Nested intervals
Nested intervals
Tree data
Tree indexing

Access to Document

10.1007/s00778-016-0436-3

Cite this

@article{1cd0faafc0ad42bc984c781aa9982183,

title = "Order Indexes: supporting highly dynamic hierarchical data in relational main-memory database systems",

abstract = "Maintaining and querying hierarchical data in a relational database system is an important task in many business applications. This task is especially challenging when considering dynamic use cases with a high rate of complex, possibly skewed structural updates. Labeling schemes are widely considered the indexing technique of choice for hierarchical data, and many different schemes have been proposed. However, they cannot handle dynamic use cases well due to various problems, which we investigate in this paper. We therefore propose Order Indexes—a dynamic representation of the nested intervals encoding—which offer competitive query performance, unprecedented update efficiency, and robustness for highly dynamic workloads.",

keywords = "Hierarchical data, Indexing, Nested intervals, Nested intervals, Tree data, Tree indexing",

author = "Jan Finis and Robert Brunel and Alfons Kemper and Thomas Neumann and Norman May and Franz Faerber",

note = "Publisher Copyright: {\textcopyright} 2016, Springer-Verlag Berlin Heidelberg.",

year = "2017",

month = feb,

day = "1",

doi = "10.1007/s00778-016-0436-3",

language = "English",

volume = "26",

pages = "55--80",

journal = "VLDB Journal",

issn = "1066-8888",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Order Indexes

T2 - supporting highly dynamic hierarchical data in relational main-memory database systems

AU - Finis, Jan

AU - Brunel, Robert

AU - Kemper, Alfons

AU - Neumann, Thomas

AU - May, Norman

AU - Faerber, Franz

PY - 2017/2/1

Y1 - 2017/2/1

N2 - Maintaining and querying hierarchical data in a relational database system is an important task in many business applications. This task is especially challenging when considering dynamic use cases with a high rate of complex, possibly skewed structural updates. Labeling schemes are widely considered the indexing technique of choice for hierarchical data, and many different schemes have been proposed. However, they cannot handle dynamic use cases well due to various problems, which we investigate in this paper. We therefore propose Order Indexes—a dynamic representation of the nested intervals encoding—which offer competitive query performance, unprecedented update efficiency, and robustness for highly dynamic workloads.

AB - Maintaining and querying hierarchical data in a relational database system is an important task in many business applications. This task is especially challenging when considering dynamic use cases with a high rate of complex, possibly skewed structural updates. Labeling schemes are widely considered the indexing technique of choice for hierarchical data, and many different schemes have been proposed. However, they cannot handle dynamic use cases well due to various problems, which we investigate in this paper. We therefore propose Order Indexes—a dynamic representation of the nested intervals encoding—which offer competitive query performance, unprecedented update efficiency, and robustness for highly dynamic workloads.

KW - Hierarchical data

KW - Indexing

KW - Nested intervals

KW - Tree data

KW - Tree indexing

UR - http://www.scopus.com/inward/record.url?scp=84981271755&partnerID=8YFLogxK

U2 - 10.1007/s00778-016-0436-3

DO - 10.1007/s00778-016-0436-3

M3 - Article

AN - SCOPUS:84981271755

SN - 1066-8888

VL - 26

SP - 55

EP - 80

JO - VLDB Journal

JF - VLDB Journal

IS - 1

ER -

Order Indexes: supporting highly dynamic hierarchical data in relational main-memory database systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this