Minimal-Change Integrity Maintenance Using Tuple Deletions

Details Minimal-Change Integrity Maintenance Using Tuple Deletions Minimal-Change Integrity Maintenance Using Tuple Deletions

2002-12-05

arxiv.org/abs/cs/0212004v1

Computer Science

Databases

Scientific paper

We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. We assume that integrity-restoration actions are limited to tuple deletions. We identify two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers (is a tuple an answer to a given query in every repair of a given database?). We study the computational complexity of both problems, delineating the boundary between the tractable and the intractable. We consider denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints. Our results shed light on the computational feasibility of minimal-change integrity maintenance. The tractable cases should lead to practical implementations. The intractability results highlight the inherent limitations of any integrity enforcement mechanism, e.g., triggers or referential constraint actions, as a way of performing minimal-change integrity maintenance.

Affiliated with

Also associated with

No associations

Rating

Minimal-Change Integrity Maintenance Using Tuple Deletions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimal-Change Integrity Maintenance Using Tuple Deletions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal-Change Integrity Maintenance Using Tuple Deletions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-702824