Complete Approximations of Incomplete Queries
This work addresses query completeness in databases for applications requiring reliable data retrieval, but it is incremental as it builds on existing frameworks of completeness rules and approximations.
The paper tackles the problem of answering conjunctive queries over partially complete databases by approximating incomplete queries using completeness rules, showing that maximal complete specializations and minimal complete generalizations can be computed to provide best complete approximations.
This paper studies the completeness of conjunctive queries over a partially complete database and the approximation of incomplete queries. Given a query and a set of completeness rules (a special kind of tuple generating dependencies) that specify which parts of the database are complete, we investigate whether the query can be fully answered, as if all data were available. If not, we explore reformulating the query into either Maximal Complete Specializations (MCSs) or the (unique up to equivalence) Minimal Complete Generalization (MCG) that can be fully answered, that is, the best complete approximations of the query from below or above in the sense of query containment. We show that the MSG can be characterized as the least fixed-point of a monotonic operator in a preorder. Then, we show that an MCS can be computed by recursive backward application of completeness rules. We study the complexity of both problems and discuss implementation techniques that rely on an ASP and Prolog engines, respectively.