In many database applications there is the need of extracting information from incomplete data. In such scenarios, certain answers are the most widely adopted semantics of query answering. Unfortunately, the computation of certain query answers is a coNP-hard problem. To make query answering feasible in practice, recent research has focused on developing polynomial time algorithms computing sound (but possibly incomplete) sets of certain answers. In this paper, we propose a novel technique that allows us to improve recently proposed approximation algorithms, obtaining a good balance between running time and quality of the results. We report experimental results confirming the effectiveness of the new technique.

Optimizing the Computation of Approximate Certain Query Answers over Incomplete Databases

Fiorentino N.;Molinaro C.;Trubitsyna I.
2019

Abstract

In many database applications there is the need of extracting information from incomplete data. In such scenarios, certain answers are the most widely adopted semantics of query answering. Unfortunately, the computation of certain query answers is a coNP-hard problem. To make query answering feasible in practice, recent research has focused on developing polynomial time algorithms computing sound (but possibly incomplete) sets of certain answers. In this paper, we propose a novel technique that allows us to improve recently proposed approximation algorithms, obtaining a good balance between running time and quality of the results. We report experimental results confirming the effectiveness of the new technique.
978-3-030-27628-7
978-3-030-27629-4
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: http://hdl.handle.net/20.500.11770/296872
 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??? 0
social impact