Caosd Research group


Fix Operator

The fix operator repairs an invalid configuration of an FM, returning as a result a valid configuration.

Fix configuration

The input configuration is fixed in two stages:

  1. The configuration is repaired to satisfy the tree constraints.
  2. Once the tree constraints are satisfied, the configuration is repaired to satisfy the CTCs too.

Along the execution of the operator, it is necessary to exclude some features because they are not compatible with the features that have been already added to the configuration. These excluded features are incorporated in the set Fe.

Fix tree constraints

This algorithm ensures that the tree constraints are satisfied, including in the resulting configuration as many features from Cin as possible. In the case that Cin is empty, at least the root feature fR is included in the output configuration, because an empty configuration is invalid and not useful for our purpose. This algorithm works recursively, which means that in the case that a feature is included in the configuration, it ensures that its parent and mandatory children are also included.

Include feature

This algorithm incorporates a feature in an input FM configuration. It is a recursive algorithm, including all the necessary features to ensure that the resulting FM configuration satisfies all the tree constraints too. First, if it is feasible to include the feature f in the configuration, it is incorporated (lines 1-2). Then, in the case that the feature f is in an XOR group, the rest of the features in the group are excluded (lines 3-7).

In lines 9-11 the parent of f is incorporated in the configuration, and in the following lines, the algorithm adds children features as necessary. The children of f are randomly traversed to explore different ways in different executions of the algorithm. On the one hand, if a child feature is in an OR or XOR group, a feature of the group is randomly selected, giving preference to those features which are part of the input configuration Cin. On the other hand, if the child feature is mandatory, it is incorporated in the configuration.

Check whether a feature can be included in a configuration

This algorithm looks for incompatibilities when a feature is going to be incorporated in a configuration C. A feature f can be incorporated in a configuration C if it is not excluded and its parent can also be included in the configuration.

Exclude a feature from an FM configuration

This algorithm excludes a feature that is not compatible with the features that are currently included in a configuration. The algorithm is recursive and, therefore, when a feature is excluded, its descendants are excluded too.

Fix cross-tree constraints

This algorithm tries to repair an FM configuration, which satisfies the tree constraints but not the set C of CTCs. CTCs are specified in CNF notation, and are traversed in random order. A CNF expression is a boolean disjunction of positive and negative variables and, therefore, it is satisfied if, at least, one of the positive variables is true or one of the negative ones is false.

For each CTC that is not satisfied, the algorithm tries to repair the configuration incorporating one of the CTC’s positive features in the configuration. In the case that the configuration is modified to satisfy a CTC, it is necessary to check all the previous CTCs again, because one or more of the features incorporated in the configuration can be negative features in other CTCs.