Vi undersöker komplexiteten i att beräkna en optimal reparation av en inkonsekvent databas, i det fall integritetsbegränsningar är funktionella beroenden (FD). Vi fokuserar på två typer av reparationer: en optimal undergrupp reparation (optimal S-reparation), som erhålls genom ett minsta antal tuple raderingar, och en optimal uppdatering reparation (optimal U-reparation), som erhålls genom ett minsta antal värde (cell) uppdateringar. För att beräkna en optimal S-reparation, presenterar vi en polynom-tid algoritm som lyckas på vissa uppsättningar av FDs och misslyckas på andra. Vi bevisar följande om algoritmen. När det lyckas, kan det också införliva viktade tuples och dubbla tuples. När det misslyckas, problemet är NP-hård och, i själva verket, APX-fullständig (därav, kan inte approximeras bättre än vissa konstant). Således etablerar vi en dikotomi i komplexiteten av att beräkna en optimal S-reparation. Vi presenterar generella analystekniker för komplexiteten i att beräkna en optimal Urepair, några baserade på dikotomi för S-reparationer. Vi drar också en koppling till en tidigare dikotomi i komplexiteten av att hitta en "mest trolig databas" som uppfyller en uppsättning FDs med ett enda attribut på vänster sida; fallet med allmänna FDs lämnades öppet, och vi visar hur vår dikotomi ger den saknade generaliseringen och därmed löser det öppna problemet. Minskning till S-reparationer, där förlusten i approximationen är linjär i antalet attribut. Därför får vi en konstant-förhållande approximation, där konstanten har ett linjärt beroende av antalet attribut. Kolahi och Lakshmanan [33] gav också en approximation för optimala U-reparationer, men deras värsta fall approximation kan vara kvadratisk i antalet attribut. Vi visar en oändlig sekvens av FD-uppsättningar där denna lucka faktiskt realiseras. Men vi visar också en oändlig sekvens där vår approximation är linjär i antalet attribut, men deras förblir konstant. Därför är de två approximationerna i allmänhet ojämförliga, och vi kan kombinera de två genom att köra både approximationer och ta det bästa. Att kliva utanför ramen för reparationer, ett annat tillvägagångssätt för datarengöring är probabilistisk [4, 28, 39]. Tanken är att definiera ett sannolikhetsutrymme över möjliga rena databaser, där sannolikheten för en databas bestäms av i vilken utsträckning den uppfyller integritetsbegränsningarna. Målet är att hitta en trolig databas som i sin tur fungerar som ett rent resultat. Som en omedelbar åtgärd identifierar Gribkoff, Van den Broeck och Suciu [28] probabilistisk rengöring som problemet "Most Probable Database" (MPD): med tanke på en tuple-oberoende probabilistic databas [20, 42] och en uppsättning FDs, hitta den mest sannolika databasen bland dem som uppfyller FDs (eller, sätta annorlunda, villkor sannolikhet utrymme på konsistens). De visar en dikotomi för unary FDs, dvs. FDs med ett enda attribut på vänster sida. Fallet av allmänna (inte nödvändigtvis unary) FDs har lämnats öppet. Det visar sig att det finns minskningar från MPD till att beräkna en optimal S-reparation och vice versa. Följaktligen kan vi generalisera deras dikotomi till alla FD, och därmed helt lösa det öppna problemet. Denna artikel utökar en konferenspublikation av författarna [37]. Jämfört med konferensversionen är förlängningen som följer. För det första har vi stärkt dikotomi i komplexiteten av MPD med hårdhet approximation på den negativa sidan (Theorem 3.8). För det andra har vi lagt till alla bevis och mellanliggande resultat som uteslöts från konferensdokumentet. I synnerhet, Avsnitt 4 är ny och innehåller det fullständiga beviset på vårt huvudsakliga resultat - dikotomi i komplexiteten för S-reparationer (Theorem 3.4). Dessutom har vi lagt till bevisen för Theorems 5. 2, 5.5, 5.12, 5.14 och 5.15 i avsnitt 5. Resten av artikeln är organiserad enligt följande. I avsnitt 2 ger vi de grundläggande definitionerna och problembeskrivningarna. Vi studerar problemet med att beräkna en optimal S-reparation i Avsnitt 3, där vi också diskuterar kopplingen till MPD. Sedan ger vi det fullständiga beviset på vår dikotomi för S-reparationer i Avsnitt 4. I Avsnitt 5 studerar vi problemet med att beräkna en optimal U-reparation. Vi avslutar och diskuterar framtida riktningar i Avsnitt 6. Vi presenterar först några grundläggande terminologier och anmärkningar som vi använder i hela artikeln. Ett exempel på vår datamodell är en enda tabell där varje tuple är associerad med en identifierare och en vikt som anger hur dyrt det är att ändra eller ta bort tuple. En sådan tabell motsvarar en relation schema som vi betecknar med R (A 1,. ., A k ), där R är förhållandet namn och A 1,. .., A k är distinkta attribut. Vi säger att R(A1),. .., A k ) är k-ary, eftersom det har k attribut. När det inte finns någon risk för förvirring, kan vi hänvisa till R(A 1,. ., A k ) genom att helt enkelt R. Vi använder versaler från början av det engelska alfabetet (t.ex., A, B, C), eventuellt med subskript och / eller superskript, för att beteckna individuella attribut, och versaler från slutet av det engelska alfabetet (t.ex., X, Y, Z ), eventuellt med subskript och / eller superskript, för att beteckna uppsättningar av attribut. Vi följer konventionen om att undvika kommatecken och lockigt tandställning när vi skriver uppsättningar av attribut (t.ex. ABC istället för {A, B, C}).
För övre gräns, är den bästa approximationen för delmängd reparation fortfarande 2 erhålls genom att lösa motsvarande vertex cover problem REF utan begränsning av antalet givna FDs.
Computing Optimal Repairs for Functional Dependencies
{'venue': None, 'journal': 'ACM Transactions on Database Systems (TODS)', 'mag_field_of_study': ['Computer Science']}