Dipartimento di Ingegneria informatica, automatica e gestionale

Incomplete information is ubiquitous in database applications, and yet our understanding of it is still rather basic. The key goal of this work is to see when query answering over databases with incomplete information can be solved by standard query evaluation techniques - this is usually referred to as naive evaluation.Since an incomplete database can represent multiple databases, query answering over them boils down to solving the validity problem, while database systems are good at performing model-checking algorithms on first-order structures. Thus, we need to understand when validity can be reduced to model-checking. We first show that this happens for queries which are monotone with respect to semantic orderings which specify the degree of incompleteness of a database. Then we show that for most commonly used semantics of incompleteness, such monotonicity can be described via homomorphism preservation, for different notions of homomorphisms. Combining the latter with preservation theorems from logic (existing as well as new), we obtain classes of queries for which standard database systems can correctly compute answers over incomplete databases, or, logically speaking, for which validity can be solved by simple model-checking.