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.
2017
Software; Information Systems
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/276683
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact