Vi studerar det nya problemet med att effektivt beräkna uppdateringsavståndet för ett par relationsdatabaser. I analogi med redigeringsavståndet för strängar definierar vi uppdateringsavståndet för två databaser som det minimala antalet set-orienterade infoga, ta bort och ändra åtgärder som krävs för att omvandla en databas till den andra. Vi visar hur detta avstånd kan beräknas genom att traversera ett sökutrymme av databasinstanser som är anslutna genom uppdateringsoperationer. Denna insikt leder till en familj av algoritmer som beräknar uppdateringsavstånd eller approximationer av det. I våra experiment lade vi märke till att en enkel heurist presterar förvånansvärt bra i de flesta fall. Vår motivation för att studera distansåtgärder för databaser kommer från området vetenskapliga databaser. Där finns ofta kopior av en enda databas på olika webbplatser, vilket vanligtvis leder till (oavsiktliga eller planerade) skillnader i deras innehåll. För att återskapa en konsekvent syn måste dessa skillnader lösas. En sådan ansträngning kräver en förståelse av den process som frambringade dem. Vi fann att minimala uppdateringssekvenser av setorienterade uppdateringsoperationer är en korrekt och koncis representation av systematiska fel, vilket ger värdefulla ledtrådar till domänexperter som ansvarar för konfliktlösning.
Müller m.fl. har föreslagit begreppet uppdateringsavstånd, dvs. "det minsta antal uppsättningsorienterade infoga, radera och ändra åtgärder som krävs för att omvandla en databas till en annan." Hoppa över det.
Describing differences between databases
{'venue': "CIKM '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}