ABSTRACT
This chapter describes the mechanism of data dependencies, which solves this problem and is useful for other purposes besides. The basic data structure for keeping track of data dependencies in our Reason Maintenance System (RMS) is the data-dependency clause (DD clause). The propagation of labels in the network is driven by the presence of active links in DD clauses. A link in a DD clause is active if it is the only link in that clause that is not misaligned. When a new DD clause is asserted, it may force a T or NIL labeling onto one or more nodes. There are three possibilities for each node to which this happens: The node may have formerly been unlabeled, in which case it just gets the new label; the node may have formerly been labeled with that label already, in which case nothing needs to be done; and with a different label, in which case there is a contradiction.
