Show simple item record

2006-04-12Buch DOI: 10.18452/2461
On the Distance of Databases
dc.contributor.authorMüller, Heiko
dc.contributor.authorFreytag, Johann-Christoph
dc.contributor.authorLeser, Ulf
dc.date.accessioned2017-06-15T17:09:55Z
dc.date.available2017-06-15T17:09:55Z
dc.date.created2006-04-12
dc.date.issued2006-04-12
dc.identifier.issn0863-095X
dc.identifier.urihttp://edoc.hu-berlin.de/18452/3113
dc.description.abstractWe study the novel problem of efficiently computing the update distance for a pair of relational databases. In analogy to the edit distance of strings, we define the update distance of two databases as the minimal number of set-oriented insert, delete and modification operations necessary to transform one database into the other. We show how this distance can be computed by traversing a search space of database instances connected by update operations. This insight leads to a family of algorithms that compute the update distance or approximations of it. In our experiments we observed that a simple heuristic performs surprisingly well in most considered cases. Our motivation for studying distance measures for databases stems from the field of scientific databases. There, replicas of a single database are often maintained at different sites, which typically leads to (accidental or planned) divergence of their content. To re-create a consistent view, these differences must be resolved. Such an effort requires an understanding of the process that produced them. We found that minimal update sequences are a proper representation of systematic errors, thus giving valuable clues to domain experts responsible for conflict resolution.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Informatik
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc004 Informatik
dc.titleOn the Distance of Databases
dc.typebook
dc.identifier.urnurn:nbn:de:kobv:11-10062551
dc.identifier.doihttp://dx.doi.org/10.18452/2461
dc.subject.dnb28 Informatik, Datenverarbeitung
local.edoc.container-titleInformatik-Berichte
local.edoc.pages42
local.edoc.type-nameBuch
local.edoc.container-typeseries
local.edoc.container-type-nameSchriftenreihe
local.edoc.container-volume2006
local.edoc.container-issue199
local.edoc.container-year2006
local.edoc.container-erstkatid2942054-4

Show simple item record