Querying Visible and Invisible Tables in the Presence of Integrity Constraints

We provide a wide-ranging study of the scenario where a subset of the tables in a relational schema are visible to a user (that is, their complete contents are known) while the remaining tables are invisible. The schema also has a set of integrity constraints, which may relate the visible tables to invisible ones but also may constrain both the visible and invisible instances. We want to determine whether information about a user query can be inferred using only the visible information and the constraints. We consider whether positive information about the query can be inferred, and also whether negative information (the query does not hold) can be inferred. We further consider both the instance-level version of the problem (the visible table extensions are given) and the schema-level version, where we want to know whether information can be leaked in some instance of the schema. Our instance-level results classify the complexity of these problems, both as a function of all inputs, and in the size of the instance alone. Our schema-level results exhibit an unusual dividing line between decidable and undecidable cases.