Approximation algorithms for querying incomplete databases

摘要: Abstract Certain answers are a widely accepted semantics of query answering over incomplete databases. As their computation is coNP-hard problem, recent research has focused on developing (polynomial time) evaluation algorithms with correctness guarantees, that is, techniques computing sound but possibly set certain answers. The aim to make the feasible in practice, settling for under-approximations. In this paper, we present novel which provide better approximations than current techniques, while retaining polynomial time data complexity. central tools our approach conditional tables and queries. We propose different strategies evaluate conditions, leading approximation algorithms—more accurate have higher running times, they pay off more being returned. Thus, offers suite enabling users choose technique best meets needs terms balance between efficiency quality results.