AtomicModify

Editor

Christian de Sainte Marie, IBM

1 Introduction

In RIF-PRD, Modify is defined as a [compound action]^PRD, that is, an action that is, by definition, semantically equivalent to a pre-defined sequence of atomic actions.

A rule that includes a compound Modify will remain [fireable]^PRD as long as its condition remains true. That is because a coumpound Modify action has, by definition, the exactly the same behaviour as a Retract followed by an Assert: this results in a rule that contains a compound Modify action never being [refracted]^PRD, if the condition tests the modified fact, since there is always, at least notionally, a [transitional state of the system]^PRD where the condition does not hold, after the fact under modification has been retracted and before it has been asserted again with the new value.

Example 1. Consider Rule_1: if the control value of a Widget is higher than 10, it must be decreased by 10% decrements until it is below the threshold

Rule_1: Forall ?w such that ?w # ex:Widget
          If Exists ?c (And ?w[ex:control->?c]
                            pred:numeric-greater-than(?c 10) )
          Then Do((?c ?w[ex:control->?c])
                  Modify( ?w[ex:control->func:numeric-multiply(?c 0.9)] ) )

Suppose there are the following facts in the facts base:

{_myWidget # ex:Widget, _myWidget[ex:control->15]}

Rule_1 will be executed four times, modifying the ex:control value of _myWidget successively to 13.5, 12.15, 10.935 and 9.8415, before the rule instance is not added back in the agenda anymore; which is the desired behaviour.

The compound Modify action has been specified in RIF-PRD to permit the serialization of the contruct that most, and maybe all, production rule languages offer to write rules that exhibit the kind of looping behaviour shown in example 1.

According to RIF-PRD operational semantics of rules and rule sets, as specified in [RIF-PRD], section 4.2, the looping behaviour of Rule_1, in example 1, is explained by the compound Modify being equivalent to an action that retract the to-be-modified frame, followed by an action that asserts the frame with the new value. After the original frame _myWidget[ex:control->15] has been removed from the facts base, and before the new frame _myWidget[ex:control->13.5] is added, the system is in a [transitional state]^PRD where the condition of the [rule instance]^PRD, that binds ?w to _myWidget, is not satisfied; as a consequence, the [rule instance]^PRD is eligible to be re-added in the agenda as soon as the condition is satisfied again, which happens after the compound Modify action is completed, and the frame _myWidget[ex:control->13.5] has been added to the facts base.

Example 2. consider Rule_2: all the senior managers with a salary below 100K get a 10% raise.

Not_Rule_2: Forall ?m such that ?w # ex:SeniorManager
          If Exists ?s (And ?m[ex:salary->?s]
                            pred:numeric-less-than(?c 100000) )
          Then Do((?s ?m[ex:salary->?s])
                  Modify( ?m[ex:salary->func:numeric-multiply(?s 1.1)] ) )

Suppose there are the following facts in the facts base:

{_John # ex:SeniorManager, _John[ex:salary->80000]}

Not_Rule_1 will be executed three times, until _John's wage has been raised to 106,480; which is not the behaviour that is intended from Rule_2.

Many production rule language offer a construct that allows to write Rule_2, with the intended behavior, in a natural way, without having to check, in the condition, whether the salary a particular senior manager has already been raised or not. RIF-PRD does not.

This specification specifies an action that has the same effect as the compound Modify, while being atomic. That atomic modify action extends RIF-PRD with a capability to serialize rules that modify the value of an attribute in an object and that do not loop, if the new value still satisfies the condition after the modification.

Example 3.

Rule_2: Forall ?m such that ?w # ex:SeniorManager
         If Exists ?s (And ?m[ex:salary->?s]
                           pred:numeric-less-than(?c 100000) )
         Then Do((?s ?m[ex:salary->?s])
                 AtomicModify( ?m[ex:salary->func:numeric-multiply(?s 1.1)] ) )

After Rule_2 has been executed once, with ?m bound to _John, _John's salary has been raised to 88K in the facts base, and the condition of that [rule instance]^PRD remains satisfied in every [states]^PRD that the system traverses. As a consequence, the [rule instance]^PRD is refracted and not eligible for firing anymore; which is the desired behaviour.

2 Abstract syntax

The alphabet of the RIF-PRD action language is extended to include a symbol to denote the replacement of all the values of an object's attribute by a single, new value,

Definition (Atomic modify action). Atomic modify is an [atomic action]^PRD, defined as follows:

• Modify fact as an atomic transaction: if φ is a frame in the RIF-PRD condition language: φ = o[s->v]; then AtomicModify(φ) is an atomic action. φ is called the target of the action.  ☐

Definition (Well-formed atomic modify action). The definition of well-formed action is extended to add the following alternative:

• An action α is well-formed if α is an AtomicModify and its target is a well-formed frame.  ☐

3 XML syntax

A atomic modification is serialized using the AtomicModify element.

The AtomicModify element has one target sub-element that contains one Frame that represents the target of the action.

    <AtomicModify>
         <target> Frame </target>
    </AtomicModify>

4 Operational semantics of AtomicModify

The definition of the [RIF-PRD transition relation]^PRD, that specifies the operational semantics of RIF-PRD actions, is extended to account for AtomicModify, as follows.

Let W denote the set of all the states of the fact base.

Definition (Atomic modify transition). The [RIF-PRD transition relation]^PRD, →_RIF-PRD, is extended to include the following transitions:

• (w, α, w') ∈ →_RIF-PRD if w ∈ W, w' ∈ W, α is AtomicModify(o[s->v]), where o, s and v are constants, and w' = (w \ {o[s->v'] | for all the values of v'}) ∪ {o[s->v]};

☐

5 References

[RIF-PRD]

RIF Production Rule Dialect, Ch. de Sainte Marie, A. Paschke, G. Hallmark, Editors. W3C Recommendation 22 June 2010. This version is http://www.w3.org/TR/2009/WD-rif-prd-20090703/. The latest version is available at http://www.w3.org/TR/rif-prd.

6 Appendix A: Glossary (non-normative)

In this section, the definitions from the RIF-PRD recommendation are reproduced for the reader's convenience. The definitions in the glossary are non-normative: the only normative definitions are as specified in the RIF-PRD specification.

Atomic action (from [RIF-PRD], section 3.1.1)

An atomic action is a construct that represents an atomic transaction.

Compound action (from [RIF-PRD], section 3.1.1)

A compound action is a construct that can be replaced equivalently by a pre-defined, and fixed, sequence of atomic actions.

Conflict set (from [RIF-PRD], section 4.2.3)

Given a rule set and a system state, the conflict set determined by the rule set in the system state is the set of all the different instances of the rules in the rule set that match the state of the fact base in the system state.

Fireable (from [RIF-PRD], section 4.2.3)

The rule instances that are in the [conflict set]^PRD are, sometimes, said to be fireable.

Refraction (from [RIF-PRD], section 4.2.5)

The essential idea of refraction is that a given instance of a rule must not be fired more than once as long as the reasons that made it eligible for firing hold. In other terms, if an instance has been fired in a given state of the system, it is no longer eligible for firing as long as it satisfies the states of facts associated to all the subsequent system states (cycle and transitional).

RIF-PRD transition relation (from [RIF-PRD], section 3.2)

the semantics of the ground atomic actions in the RIF-PRD action language determines a relation, called the RIF-PRD transition relation: →_RIF-PRD ⊆ W × L × W, where W denotes the set of all the states of the fact base, and where L denotes the set of all the ground atomic actions in the RIF-PRD action language.

Rule instance (from [RIF-PRD], section 4.2.3)

Given a rule, r ∈ R, and a ground substitution, σ, such that CVar(r) ⊆ Dom(σ), where CVar(r) denotes the set of the rule variables in r, the result, ri = σ(r), of the substitution of the constant σ(?x) for each variable ?x ∈ CVar(r) is a rule instance (or, simply, an instance) of r.

System state (from [RIF-PRD], section 4.2.3)

A production rule system state (or, simply, a system state) is either a system cycle state or a system transitional state. Every production rule system state, s, cycle or transitional, is characterized by

• a state of the fact base;
• if s is not the current state, an ordered set of rule instances, defined as follows:
  • if s is a system cycle state: the ordered set of rule instances picked by the conflict resolution strategy, among the set of all the rule instances that matched the state of the fact base that characterize s;
  • if s is a system transitional state: the empty set;
• if s is not the initial state, a previous system state.

7 Appendix B: XML schema

<xs:schema targetNamespace="http://www.w3.org/2007/rif#"
           xmlns:xs="http://www.w3.org/2001/XMLSchema"
           elementFormDefault="qualified">

  <xs:annotation>
    <xs:documentation xml:lang="en">

       This is the XML Schema for the AtomicModify element.
       The AtomicModify elemnt is an addition to the set of
       RIF-PRD atomic actions, defined in the group named ACTION
       in the RIF-PRD schema.

       The proper way to use this extension is to include this
       extension schema in the schema to be extended schema and
       to redefine the ACTION group. E.g.

       <xs:schema targetNamespace="http://www.w3.org/2007/rif#"
                  xmlns:xs="http://www.w3.org/2001/XMLSchema"
                  elementFormDefault="qualified">

         <xs:include schemaLocation="http://www.w3.org/2010/rif-schema/prd/extensions/AtomicModify.xsd">

         <xs:redefine schemaLocation="http://www.w3.org/2010/rif-schema/prd/PRD.xsd">
           <xs:group name="ACTION">
             <xs:choice>
               <xs:group ref="ACTION"/>
               <xs:element ref="AtomicModify"/>
             </xs:choice>
           </xs:group>
         </xs:redefine>
       </xs:schema>
	
    </xs:documentation>
  </xs:annotation>


  <xs:element name="AtomicModify">
    <xs:complexType>
      <xs:sequence>
        <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/>
        <xs:element name="target" minOccurs="1" maxOccurs="1">
          <xs:complexType> 
            <xs:sequence>
              <xs:element ref="Frame"/>
            </xs:sequence>
          </xs:complexType>
        </xs:element>
      </xs:sequence>
    </xs:complexType>
  </xs:element>

</xs:schema>