Abstract: We consider the problem of answering queries from databases that may be incomplete. A database is incomplete if some tuples may be missing from some relations, and only a (perhaps empty) part of each relation is known to be complete. This problem arises in several contexts. For example, systems that provide access to multiple heterogeneous information sources often encounter incomplete sources. As another example, a database undergoing a long transaction is temporarily incomplete. The question we address is to determine whether the answer to a specific given query is complete even when the database is incomplete. First, we show that the problem of deciding query-completeness is completely characterized as a problem of deciding whether a query is independent of an insertion update. As a result, we obtain several novel algorithms for deciding query-completeness. Second, we show that an important case of the problem of determining independence of queries from updates can be done in polynomial time, whereas the best known algorithms previously are exponential. This is the case in which the updated tuples are described using constraints with built-in order comparison predicates between attributes in the query and constants. Third, we describe an algorithm that determines whether the answer to the query is complete in the current state of the database (as opposed to em any state of the database). The algorithm uses several auxiliary queries to determine completeness. Finally, we show that we can treat partially-incorrect databases in an analogous fashion .