  Conceptual dependencies (CDs) are particular kinds of key dependencies (KDs)
and inclusion dependencies (IDs) that precisely characterize relational
schemata modeled according to the main features of the Entity-Relationship (ER)
model. An instance for such a schema may be inconsistent (data violate the
dependencies) and incomplete (data constitute a piece of correct information,
but not necessarily all the relevant information). While undecidable under
general KDs and IDs, query answering under incomplete data is known to be
decidable for CDs. The known techniques are based on the chase -- a special
instance, organized in levels of depth, that is a representative of all the
instances that satisfy the dependencies and that include the initial instance.
Although the chase generally has infinite size, query answering can be
addressed by posing the query (or a rewriting thereof) on a finite, initial
part of the chase. Contrary to previous claims, we show that the maximum level
of such an initial part cannot be bounded by a constant that does not depend on
the size of the initial instance.

Databases