The problem of computing the certain answer to a conjunctive query over a relational instance subject to primary key constraints is a classical hard problem in database research. On the theoretical side, we present a decomposition and pruning strategy that reduces, in polynomial time, the original problem to a collection of smaller problems of the same sort that can be solved independently. From a practical perspective, we discuss an experiment on large data sets that shows the effectiveness of the overall technique and its implementation in ASP.
Decomposing and pruning primary key violations from large data sets
Manna, Marco;Ricca, Francesco;Terracina, Giorgio
2017-01-01
Abstract
The problem of computing the certain answer to a conjunctive query over a relational instance subject to primary key constraints is a classical hard problem in database research. On the theoretical side, we present a decomposition and pruning strategy that reduces, in polynomial time, the original problem to a collection of smaller problems of the same sort that can be solved independently. From a practical perspective, we discuss an experiment on large data sets that shows the effectiveness of the overall technique and its implementation in ASP.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.