Testing CQC^\neg constraints under limited data access.

Abstract

In many important application areas such as collaborative design, mobile computing and enterprise information systems, total data accessibility can not be assumed. Even if all data can be accessed, some of them may incur such a high cost that their access should only be considered as a last resort. Effciently checking if a local update violates a global integrity constraint spanning several relations poses new challenges when not all these relations are to be looked at. Without being given access to all relations under constraint, how can one meaningfully check a constraint for violation? When the constraint is known to be satisfied prior to the update, the state of the accessible relations can in principle be used to infer something about the inaccessible relations. Under limited data accessibility, the "complete local test" (or CLT in short) represents the best strategy to evaluate if the update can potentially violate the constraint. This paper addresses the problem of finding CLT's for an important class of constraints that are very common in practice: constraints expressible as conjunctive queries with negated subgoals (abbreviated CQC : .) We show that for single updates, all CQC : constraints admit a CLT that can be expressed in nonrecursive Datalog : when each inaccessible relation has a single occurrence in the constraint query. We then extend this result to certain sets of updates. The significance of our results is not only that complete tests for CQC : constraints can be generated and executed effciently, but that they can also be executed on traditional query-evaluation engines.