Minimal spatio-temporal database repairs

Markus Mauder, Markus Reisinger, Tobias Emrich, Andreas Züfle*, Matthias Renz, Goce Trajcevski, Roberto Tamassia

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


This work addresses the problem of efficient detection and fixing of inconsistencies in spatiotemporal databases. In contrast to traditional database settings, where integrity constraints pertain to explicitly stored values and values defined via views and aggregates, spatiotemporal data may exhibit other types of constraint violations that cannot be tied to stored or aggregated values. The main reason is that spatiotemporal phenomena are continuous but their database representations are discrete. Thus, the constraints are semantic in nature, as opposed to being dependent on the actual stored data. We give a general definition of semantic constraints of a trajectory database and define rules to repair violations of these constraints. In order to minimize the distortion of the state of the database, we aim at minimizing the changes needed for repairing violations of such semantic constraints. Towards this goal, we define a measure of dissimilarity between the initial database and its repaired state. Also, to minimize dissimilarity, we propose several simple rules of space- and timedistortion that shift inconsistent observations in space and time to remove inconsistencies. Our evaluation shows that these rules often run into local minima, and thus may not be able to repair a database. To remedy this problem, we propose a hybrid approach that chooses between several possible space and time distortions. We show that a greedy approach which always chooses the locally best repair may still run into local minima and propose a simulated-annealing approach that combines greedy and random repairs to avoid these local minima.

Original languageEnglish (US)
Article numberA14
Pages (from-to)255-273
Number of pages19
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - 2015
Event14th International on Symposium on Spatial and Temporal Databases, SSTD 2015 - Hong Kong, China
Duration: Aug 26 2015Aug 28 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Minimal spatio-temporal database repairs'. Together they form a unique fingerprint.

Cite this