Constraint checking with partial information

Reviewer: Robert J. Tufts

Constraint checking is one of many techniques used to ensure data integrity in distributed databases. It involves testing a potential update to ensure the resultant changes do not violate data consistency rules. An example might be testing an update to an employee record to make sure the employee is not younger than a minimum age or earning more than a maximum salary. The problem with constraint checking is that each constraint can be as elaborate as a large, compound query. Checking an update against all constraints can slow down the update process to an unacceptable level. Therefore, some effort has been devoted to determining when an update affects a constraint so that constraint checking can be minimized. The purpose of this paper is to explore the full taxonomy of constraints to determine when constraint satisfaction can be assured without performing a complete range of constraint checks. The paper looks at three classes of checks: constraint definitions only; constraints and updates; and constraints, updates, and local data. Of special interest are tests that can be done in the DBMS query language. The authors approach was to divide constraints into six classes of query language expressions that were of interest. Then they considered three different problem sets, each directly related to the three classes of constraint checks mentioned above. Using the six classes, the authors explored what can be done to minimize constraint checking. The results of the authors research were: With constraints alone, the only active solution is subsumption of the constraints by one or more of the other constraints. This can be expressed as conjunctive queries with a test time that is exponential in the size of the query. With constraints and updates, constraints will still be valid if data updates apply to the set of data used for the constraints, provided the constraint refers to all of the legal entries in the database following the update. Constraints with updates and local data can be represented as a complete local test by using a recursive datalog program with arithmetic. Overall, the authors covered the subject well, albeit from more of a theoretical slant than from a practical implementation approach. I would recommend it for general audiences, but it is most useful for those pursuing research in constraint checking with partial information. The bibliography is up to date, with ten of the references to papers published in the 1990s.