Localizable constraints for object histories (Q1183583)

The paper deals with localizable constraints for object histories. An object history is described in form of so-called computation-tuple sequences. The properties of computation-tuple sequences are defined by computation-tuple sequence schemes (abbreviated CSS). Computation-tuple sequence schemes are a record based model for the representation of historical data about object histories. A CSS consists of 1. a set of attributes, partitioned into input and evaluation attributes by their roles; 2. functions which calculate values for the evaluation attributes from earlier tuples and the correct values of the input attributes; 3. semantic constraints whose satisfaction is to hold uniformly throughout a computation-tuple sequence; and 4. a set of specific computation-tuple sequences of some bounded length with which to start a valid computation-tuple sequence until all evaluation functions can be applied. A special subset of constraints, called ``local'', has been studied earlier. Local constraints require only a fixed number of the most recent tuples in the sequence to be examined in order to enforce the constraint. Thus they are easier to enforce and are therefore preferred over arbitrary constraints. It therefore is desirable to try to convert in a minimal and simple manner a nonlocal constraint to a local one with the context of a CSS. The paper introduces one such conversion and studies the type of constraints for which this conversion is possible. Two subfamilies of these constraints (CSS-independent localizable and function bounded constraints) are identified and characterizations for each of them presented. Finally, closure properties (under logical connectives \(\wedge\) and \(\vee\) and a set-theoretic operation called concatenation) for each of the three classes are given.