In:
it – Information Technology, Walter de Gruyter GmbH, Vol. 56, No. 1 ( 2014-2-28), p. 4-12
Kurzfassung:
In an increasing number of use cases, databases face the challenge of
managing heterogeneous data. Heterogeneous data is characterized by a quickly evolving variety of entities without a common set of
attributes. These entities do not show enough regularity to be captured in a traditional database schema. A common solution is to
centralize the diverse entities in a universal table. Usually, this leads to a very sparse table. Although today's techniques allow
efficient storage of sparse universal tables, query efficiency is still a problem. Queries that address only a subset of attributes
have to read the whole universal table including many irrelevant entities. A solution is to use a partitioning of the table, which
allows pruning partitions of irrelevant entities before they are touched. Creating and maintaining such a partitioning manually is
very laborious or even infeasible, due to the enormous complexity. Thus an autonomous solution is desirable. In this article, we define the Online Partitioning Problem for
heterogeneous data. We sketch how an optimal solution for this problem can be determined based on hypergraph partitioning. Although
it leads to the optimal partitioning, the hypergraph approach is inappropriate for an implementation in a database system. We present
Cinderella, an autonomous online algorithm for horizontal partitioning of heterogeneous entities in universal tables. Cinderella is designed
to keep its overhead low by operating online; it incrementally assigns entities to partition while they are touched anyway during
modifications. This enables a reasonable physical database design at runtime instead of static modeling.
Materialart:
Online-Ressource
ISSN:
2196-7032
,
1611-2776
DOI:
10.1515/itit-2014-1015
Sprache:
Englisch
Verlag:
Walter de Gruyter GmbH
Publikationsdatum:
2014
ZDB Id:
2102301-3
ZDB Id:
144419-0
ZDB Id:
165820-7
ZDB Id:
2028598-X
ZDB Id:
6242-X
ZDB Id:
1146417-3
Bookmarklink