An ASP approach to query completeness reasoning

We address the problem to determine whether a query over a partially complete database can be answered completely, which arises in data integration and decision support. Using so-called table completeness statements, one asserts which parts of a database are complete. The question then is whether these are sufficient to retrieve the same answers as if the database had complete information about the domain of application. Previous work in the area of databases has characterized the complexity of the problem, but did not come up with a practical implementation. In this paper we explore ASP engines as a possible platform to execute completeness reasoning problems. We first generalize the problem by taking into account finite domain constraints and then translate it into rules that may have disjunctions in the heads. The translation allows us to encode completeness problems into cautious reasoning in ASP. We implemented our encoding in two state of the art solvers and tested it on examples that involve many disjunctions, but allow for significant optimizations. It turned out that both engines did not take advantage of the possibilities for optimization.status: publishe