A logic programming approach to query completeness

Abstract

How to manage incomplete information has been studied in database research almost from the beginning. The focus was on how to represent incomplete information and how to compute certain answers.<br />Less attention has been given to describing which parts of a database are complete and how to find out whether a query returns complete answers over a partially complete database.<br />To address these questions, we build on previous work by Motro (1989) and Levy (1995) who formalized when a query is complete over a partially complete database and what it means that parts of the tables are complete. Recently, Razniewski and Nutt (2011) characterized the complexity of various reasoning tasks in this setting. It was open, however, how to implement completeness reasoners in practice.<br />In this work, we introduce the problem of query completeness reasoning and show that it can be mapped elegantly to answer set programming (ASP) over datalog with negation. Then we consider extensions of the original problem that take into account foreign key constraints and finite domain constraints. To encode the extensions, we make use of Skolem functions and of datalog rules with disjunctions in the head. We show the correctness and completeness of the encodings by several characterization theorems. We also discuss a possible approach that takes into account comparisons and show how it can solve this problem if comparisons satisfy some syntactical restrictions.<br />With our encodings we can solve completeness reasoning tasks using the DLV system, which implements answer set programming for disjunctive logic programs. DLV is being developed at TU Vienna and at the University of Calabria.<br />