Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 3.31 MB
Add to list
  1. Search results
  2. Compact representations of temporal d...

Compact representations of temporal databases

Antoon Bronselaer (UGent) , Christophe Billiet (UGent) , Robin De Mol, Joachim Nielandt (UGent) and Guy De Tré (UGent)
(2019) VLDB JOURNAL. 28(4). p.473-496
Author
Organization
Abstract
This paper investigates the storage compactness of temporal merges. A temporal merge is a joint representation of a set of snapshots of the same database at different points in time. An axiomatic requirement for temporal merges is that each individual snapshot must be derivable from it. We first show that the usual temporal extension of a database is a special kind of temporal merge called a direct merge. For direct merges, finding the most compact representation is easy for separate relations. However, if snapshots feature foreign key dependencies, the representation may contain more tuples than strictly needed. We therefore study inclusion dependencies in temporal databases and show how to use them while maintaining minimality in our representation. Next, we argue that direct merges imply redundancy when they contain non-contiguous, value-equivalent tuples. We therefore introduce a more general kind of temporal merge known as a coherent merge and study its properties in depth. Deriving a minimal coherent merge from a direct one is shown to be NP-hard. However, several greedy algorithms are demonstrated to provide decent results in quadratic time. Next, an incremental algorithm for construction of coherent merges is presented. We provide experimental results on real-life data sets that support the usefulness of the contributions of this paper.
Keywords
Databases, Data Integrity, Coherent merge, Inclusion dependency, RELATIONAL MODEL, TIME, ALGORITHMS, MANAGEMENT

Downloads

  • Download
    (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 3.31 MB

Citation

Please use this url to cite or link to this publication:

MLA
Bronselaer, Antoon, et al. “Compact Representations of Temporal Databases.” VLDB JOURNAL, vol. 28, no. 4, 2019, pp. 473–96, doi:10.1007/s00778-018-0535-4.
APA
Bronselaer, A., Billiet, C., De Mol, R., Nielandt, J., & De Tré, G. (2019). Compact representations of temporal databases. VLDB JOURNAL, 28(4), 473–496. https://doi.org/10.1007/s00778-018-0535-4
Chicago author-date
Bronselaer, Antoon, Christophe Billiet, Robin De Mol, Joachim Nielandt, and Guy De Tré. 2019. “Compact Representations of Temporal Databases.” VLDB JOURNAL 28 (4): 473–96. https://doi.org/10.1007/s00778-018-0535-4.
Chicago author-date (all authors)
Bronselaer, Antoon, Christophe Billiet, Robin De Mol, Joachim Nielandt, and Guy De Tré. 2019. “Compact Representations of Temporal Databases.” VLDB JOURNAL 28 (4): 473–496. doi:10.1007/s00778-018-0535-4.
Vancouver
1.
Bronselaer A, Billiet C, De Mol R, Nielandt J, De Tré G. Compact representations of temporal databases. VLDB JOURNAL. 2019;28(4):473–96.
IEEE
[1]
A. Bronselaer, C. Billiet, R. De Mol, J. Nielandt, and G. De Tré, “Compact representations of temporal databases,” VLDB JOURNAL, vol. 28, no. 4, pp. 473–496, 2019.
@article{8625822,
  abstract     = {{This paper investigates the storage compactness of temporal merges. A temporal merge is a joint representation of a set of snapshots of the same database at different points in time. An axiomatic requirement for temporal merges is that each individual snapshot must be derivable from it. We first show that the usual temporal extension of a database is a special kind of temporal merge called a direct merge. For direct merges, finding the most compact representation is easy for separate relations. However, if snapshots feature foreign key dependencies, the representation may contain more tuples than strictly needed. We therefore study inclusion dependencies in temporal databases and show how to use them while maintaining minimality in our representation. Next, we argue that direct merges imply redundancy when they contain non-contiguous, value-equivalent tuples. We therefore introduce a more general kind of temporal merge known as a coherent merge and study its properties in depth. Deriving a minimal coherent merge from a direct one is shown to be NP-hard. However, several greedy algorithms are demonstrated to provide decent results in quadratic time. Next, an incremental algorithm for construction of coherent merges is presented. We provide experimental results on real-life data sets that support the usefulness of the contributions of this paper.}},
  author       = {{Bronselaer, Antoon and Billiet, Christophe and De Mol, Robin and Nielandt, Joachim and De Tré, Guy}},
  issn         = {{1066-8888}},
  journal      = {{VLDB JOURNAL}},
  keywords     = {{Databases,Data Integrity,Coherent merge,Inclusion dependency,RELATIONAL MODEL,TIME,ALGORITHMS,MANAGEMENT}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{473--496}},
  title        = {{Compact representations of temporal databases}},
  url          = {{http://dx.doi.org/10.1007/s00778-018-0535-4}},
  volume       = {{28}},
  year         = {{2019}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: