RIF Production Rule Dialect

W3C Editor's Draft 21 November 2008

This version:

http://www.w3.org/2005/rules/wg/draft/ED-rif-prd-20081121/

Latest editor's draft:

http://www.w3.org/2005/rules/wg/draft/rif-prd/

Previous version:

http://www.w3.org/2005/rules/wg/draft/ED-rif-prd-20080922/ (color-coded diff)

Editors:

Christian de Sainte Marie, ILOG

Adrian Paschke, Free University Berlin

Gary Hallmark, Oracle

---

Copyright © 2008 W3C^® (MIT, ERCIM, Keio), All Rights Reserved. W3C liability, trademark and document use rules apply.

Abstract

Status of this Document

May Be Superseded

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

Set of Documents

This document is being published as one of a set of 5 documents:

1. RIF Use Cases and Requirements
2. RIF Core
3. RIF Datatypes and Built-Ins 1.0
4. RIF Production Rule Dialect (this document)
5. RIF (Rule Interchange Format) Test Cases

Please Comment By 2008-11-25

The Rule Interchange Format (RIF) Working Group seeks public feedback on these Working Drafts. Please send your comments to public-rif-comments@w3.org (public archive). If possible, please offer specific changes to the text that would address your concern. You may also wish to check the Wiki Version of this document for internal-review comments and changes being drafted which may address your concerns.

No Endorsement

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

Patents

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Production rules are rules with an "if" part and a "then" part. The "if" part, also called a "condition", is like the condition part of logic rules (as covered by the basic logic dialect of the W3C rule interchange format, RIF-BLD). The "then" part of production rules may contain actions, unlike the conclusion of logic rules that may contain only a logical statement. Actions can modify the facts, not only the knowledge base; and they can have other side-effects.

Example 1.1. «A customer becomes a "Gold" customer as soon as his cumulative purchases during the current year top $5000»; «Customers that become "Gold" customers must be notified immediately, and a golden customer card will be printed and sent to them within one week»; «For shopping carts worth more than $1000, "Gold" customers receive an additional discount of 10% of the total amount», are all examples of production rules.

As a production rule interchange format, RIF-PRD specifies an abstract syntax that is shared by many concrete production rule languages for the most widely used features, and associates each abstract construct with normative semantics (section 2, Abstract syntax and Semantics) and a normative XML concrete syntax (section 3, XML syntax).

Production rules are statements of programming logic that specify the execution of one or more actions in the case that their conditions are satisfied. Production rules therefore have an operational semantic (formalizing state changes, e.g., on the basis of a state transition system formalism). The OMG Production Rule Representation specification [PRR] summarizes it as follows:

1. Match: the rules are instantiated based on the definition of the rule conditions and the current state of the data source;
2. Conflict resolution: select rule instances to be executed, per strategy;
3. Act: change state of data source, by executing the selected rule instances’ actions. If a terminal state has not been reached, the control loops back to the first step (Match).

In the section Operational semantics of rules and rule sets, the semantics for rules and rule sets is specified, accordingly, as a label terminal transition system [ref Plotkin].

However, as a RIF dialect, RIF-PRD has also been designed to maximize interoperability between rule languages over the World Wide Web. In RIF, this is achieved by sharing the same syntax for constructs that have the same semantics across multiple dialects. As a consequence, RIF-PRD shares most of the syntax for rule conditions with RIF-BLD, and the semantics associated to the syntactic constructs used for representing the condition part of rules in RIF-PRD is specified, in the section Semantics of conditions, in terms of a model theory, as it is in the specification of RIF-BLD as well. In addition to emphasizing the similarity between the two dialects, it allows them to share the same definition for data types and built-ins by reference to the RIF data types and built-ins specification.

In the section Operational semantics of actions, the semantics associated with the constructs used to represent the action part of rules in RIF-PRD is specified in terms of a transition relation between successive states of the data source, as defined by the condition formulae that they entail, thus making the link between the model-theoretic semantics of conditions and the operational semantics of rules and rulesets.

The abstract syntax is specified in mathematical english, and the abstract syntactic constructs defined in section 2, Abstract syntax and Semantics, are mapped one to one onto the concrete XML syntax in section 3, XML syntax. A lightweight notation is also defined along with the abstract syntax, to allow for a human-friendlier specification of the semantics. A more complete presentation syntax is specified using an EBNF in section 4. However, only the XML syntax and the associated semantics are normative. A normative XML schema will also be provided in future versions of the document;

Example 1.2. In RIF-PRD presentation syntax, the first rule in example 1.1. might be represented as follows:

Prefix(ex1 http://rif.example.com/2008/prd#)
(* ex1:rule_1 *)
Forall ?customer ?purchasesYTD (
 If      And( ?customer#ex1:Customer
                ?customer[ex1:purchasesYTD->?purchasesYTD]
                External(pred:numeric-greater-than(?purchasesYTD 5000)))
 Then ex1:Gold(?customer) )

RIF-PRD and RIF-BLD share more than part of their condition language, and whole RIF documents have the same syntax and the same intended meaning in both dialects. The correspondence between RIF-PRD and RIF-BLD is detailed in Appendix: Compatibility with RIF-BLD.

This document is mostly intended for the designers and developers of RIF-PRD implementations, that is, applications that serialize production rules as RIF-PRD XML (producer applications) and/or that deserialize RIF-PRD XML documents into production rules (consumer applications).

Note to the reader: this section depends on Section Constants, Symbol Spaces, and Datatypes of [RIF-DTB].

Notice that the production rule systems for which RIF-PRD aims to provide a common XML serialization use only externally specified functions, e.g. builtins. This is one of two points where the syntaxes for conditions in RIF-PRD and RIF-BLD differ, since RIF-BLD specifies, in addition, a construct for serializing the logic functions that logic languages also use.

The second point of difference between the syntaxes for conditions in RIF-PRD and RIF-BLD is that, unlike RIF-PRD, RIF-BLD does not specify a construct for negation. This is because logic rule languages use many different kinds of negations, none of them prevalent enough to justify inclusion in the basic logic dialect of RIF (see also the RIF framework for logic dialects).

Note that atomics are sometimes also called terms, e.g. in the realm of logic languages: the specification of RIF-BLD, in particular, follows that usage. The abstract syntactic elements that are called terms in this specification, are called basic terms in the specification of RIF-BLD.

• If s occurs as a function symbol in a term of the form s(...) with arity α then s occurs in the context of an external function symbol with arity α (or simply the context of a function symbol with arity α, since RIF-PRD knows only external functions).
• If s occurs as a predicate in an atomic subformula of the form s(...) with arity α then s occurs in the context of a predicate symbol with arity α.
• If s occurs as a predicate in an atomic subformula External(s(...)) with arity α then s occurs in the context of an external predicate symbol with arity α.

Definition (Well-formed formula). A formula φ is well-formed iff:

• every constant symbol mentioned in φ occurs in exactly one context.
• Whenever a formula contains a function term t or an external atomic formula External(t), t must be an instance of the coherent set of external schemas (Section Schemas for Externally Defined Terms of [RIF-DTB]) associated with the language of RIF-PRD.
• If t is an instance of the coherent set of external schemas associated with the language then t can occur only as a function term t or as an external atomic formula External(t).

Definition (RIF-PRD condition language). The RIF-PRD condition language consists of the set of all well-formed formulas that can be serialized using the RIF-PRD XML syntax.

For compatibility with other RIF specifications (in particular, RIF data types and builtins), and to make the interoperability with RIF logic dialects (in particular RIF-Core and RIF-BLD), the intended semantics for RIF-PRD condition formulas is specified in terms of a model theory.

The key concept in a model-theoretic semantics of a logic language is the notion of a semantic structure [Enderton01, Mendelson97].

Definition (Semantic structure). A semantic structure, I, is a tuple of the form <TV, DTS, D, D_ind, I_C, I_V, I_P, I_NP, I_frame, I_sub, I_isa, I₌, I_external, I_truth>. Here D is a non-empty set of elements called the domain of I, and D_ind is a nonempty subset of D. D_ind is used to interpret the elements of Const that are individuals. As before, Const denotes the set of all constant symbols and Var the set of all variable symbols. TV denotes the set of truth values that the semantic structure uses and DTS is a set of identifiers for primitive datatypes (please refer to Section Datatypes of [RIF-DTB] for the semantics of datatypes).

As far as the assignement of a standard meaning to formulas in the RIF-PRD condition language is concerned, the set TV of truth values consists of just two values, t and f.

The other components of I are total mappings defined as follows:

• I_C maps Const to D.
  This mapping interprets constant symbols;
• I_V maps Var to D_ind.
  This mapping interprets variable symbols;
• I_P maps D to functions D*_ind → D (here D*_ind is a set of all sequences of any finite length over the domain D_ind).
  This mapping interprets positional predicate symbols;
• I_NP maps D to the set of total functions of the form SetOfFiniteSets(ArgNames × D_ind) → D.
  This mapping interprets predicate symbols with named arguments. This is analogous to the interpretation of positional predicate symbols with two differences:
  • Each pair <s,v> ∈ ArgNames × D_ind represents an argument/value pair instead of just a value in the case of a positional atom;
  • The arguments of a term with named arguments constitute a finite set of argument/value pairs rather than a finite ordered sequence of simple elements. So, the order of the arguments does not matter;
• I_frame maps D_ind to total functions of the form SetOfFiniteBags(D_ind × D_ind) → D.
  This mapping interprets frame terms. An argument, d ∈ D_ind, to I_frame represents an object and the finite bag {<a1,v1>, ..., <ak,vk>} represents a bag of attribute-value pairs for d. We will see shortly how I_frame is used to determine the truth valuation of frame terms.
  Bags (multi-sets) are used here because the order of the attribute/value pairs in a frame is immaterial and pairs may repeat: o[a->b a->b]. Such repetitions arise naturally when variables are instantiated with constants. For instance, o[?A->?B ?C->?D] becomes o[a->b a->b] if variables ?A and ?C are instantiated with the symbol a and ?B, ?D with b. (We shall see later that o[a->b a->b] is equivalent to o[a->b];)
• I_sub gives meaning to the subclass relationship. It is a mapping of the form D_ind × D_ind → D.
  The operator ## is required to be transitive, i.e., c1 ## c2 and c2 ## c3 must imply c1 ## c3. This is ensured by a restriction in Section Interpretation of condition formulas;
• I_isa gives meaning to class membership. It is a mapping of the form D_ind × D_ind → D.
  The relationships # and ## are required to have the usual property that all members of a subclass are also members of the superclass, i.e., o # cl and cl ## scl must imply o # scl. This is ensured by a restriction in Section Interpretation of condition formulas;
• I₌ is a mapping of the form D_ind × D_ind → D.
  It gives meaning to the equality operator;
• I_external is a mapping from the coherent set of schemas for externally defined functions to total functions D* → D. For each external schema σ = (?X₁ ... ?X_n; τ) in the coherent set of external schemas associated with the language, I_external(σ) is a function of the form Dⁿ → D.
  For every external schema, σ, associated with the language, I_external(σ) is assumed to be specified externally in some document (hence the name external schema). In particular, if σ is a schema of a RIF built-in predicate or function, I_external(σ) is specified in [RIF-DTB] so that:
  • If σ is a schema of a built-in function then I_external(σ) must be the function defined in the aforesaid document;
  • If σ is a schema of a built-in predicate then I_truth ο (I_external(σ)) (the composition of I_truth and I_external(σ), a truth-valued function) must be as specified in [RIF-DTB];
• I_truth is a mapping of the form D → TV.
  It is used to define truth valuation for formulas.

For convenience, we also define the following mapping I from terms to D:

• I(k) = I_C(k), if k is a symbol in Const;
• I(?v) = I_V(?v), if ?v is a variable in Var;
• I(p(t₁ ... t_n)) = I_P(I(p))(I(t₁),...,I(t_n));
• I(p(s₁->v₁ ... s_n->v_n)) = I_NP(I(p))({<s₁,I(v₁)>,...,<s_n,I(v_n)>})
  Here we use {...} to denote a set of argument/value pairs;
• I(o[a₁->v₁ ... a_k->v_k]) = I_frame(I(o))({<I(a₁),I(v₁)>, ..., <I(a_n),I(v_n)>})
  Here {...} denotes a bag of attribute/value pairs. Jumping ahead, we note that duplicate elements in such a bag do not affect the value of I_frame(I(o)) -- see Section Interpretation of condition formulas. For instance, I(o[a->b a->b]) = I(o[a->b]);
• I(c1##c2) = I_sub(I(c1), I(c2));
• I(o#c) = I_isa(I(o), I(c));
• I(x=y) = I₌(I(x), I(y));
• I(External(t)) = I_external(σ)(I(s₁), ..., I(s_n)), if t is an instance of the external schema σ = (?X₁ ... ?X_n; τ) by substitution ?X₁/s₁ ... ?X_n/s₁.
  Note that, by definition, External(t) is well-formed only if t is an instance of an external schema. Furthermore, by the definition of coherent sets of external schemas, t can be an instance of at most one such schema, so I(External(t)) is well-defined.

The effect of datatypes. The set DTS must include the datatypes described in Section Primitive Datatypes of [RIF-DTB].

The datatype identifiers in DTS impose the following restrictions. Given dt ∈ DTS, let LS_dt denote the lexical space of dt, VS_dt denote its value space, and L_dt: LS_dt → VS_dt the lexical-to-value-space mapping (for the definitions of these concepts, see Section Primitive Datatypes of [RIF-DTB]. Then the following must hold:

• VS_dt ⊆ D_ind; and
• For each constant "lit"^^dt such that lit ∈ LS_dt, I_C("lit"^^dt) = L_dt(lit).

That is, I_C must map the constants of a datatype dt in accordance with L_dt.

RIF-PRD does not impose restrictions on I_C for constants in symbol spaces that are not datatypes included in DTS.

• Positional atomic formulas: TVal_I(r(t₁ ... t_n)) = I_truth(I(r(t₁ ... t_n)));
• Atomic formulas with named arguments: TVal_I(p(s₁->v₁ ... s_k->v_k)) = I_truth(I(p(s₁->v₁ ... s_k->v_k)));
• Equality: TVal_I(x = y) = I_truth(I(x = y)).
  To ensure that equality has precisely the expected properties, it is required that:
  • I_truth(I(x = y)) = t if and only if I(x) = I(y) and that I_truth(I(x = y)) = f otherwise. This is tantamount to saying that TVal_I(x = y) = t iff I(x) = I(y);
• Subclass: TVal_I(sc ## cl) = I_truth(I(sc ## cl)).
  To ensure that the operator ## is transitive, i.e., c1 ## c2 and c2 ## c3 imply c1 ## c3, the following is required:
  • For all c1, c2, c3 ∈ D,   if TVal_I(c1 ## c2) = TVal_I(c2 ## c3) = t   then TVal_I(c1 ## c3) = t;
• Membership: TVal_I(o # cl) = I_truth(I(o # cl)).
  To ensure that all members of a subclass are also members of the superclass, i.e., o # cl and cl ## scl implies o # scl, the following is required:
  • For all o, cl, scl ∈ D,   if TVal_I(o # cl) = TVal_I(cl ## scl) = t   then   TVal_I(o # scl) = t;
• Frame: TVal_I(o[a₁->v₁ ... a_k->v_k]) = I_truth(I(o[a₁->v₁ ... a_k->v_k])).
  Since the bag of attribute/value pairs represents the conjunctions of all the pairs, the following is required, if k > 0:
  • TVal_I(o[a₁->v₁ ... a_k->v_k]) = t if and only if TVal_I(o[a₁->v₁]) = ... = TVal_I(o[a_k->v_k]) = t;
• Externally defined atomic formula: TVal_I(External(t)) = I_truth(I_external(σ)(I(s₁), ..., I(s_n))), if t is an atomic formula that is an instance of the external schema σ = (?X₁ ... ?X_n; τ) by substitution ?X₁/s₁ ... ?X_n/s₁.
  Note that, by definition, External(t) is well-formed only if t is an instance of an external schema. Furthermore, by the definition of coherent sets of external schemas, t can be an instance of at most one such schema, so I(External(t)) is well-defined;
• Conjunction: TVal_I(And(c₁ ... c_n)) = t if and only if TVal_I(c₁) = ... = TVal_I(c_n) = t. Otherwise, TVal_I(And(c₁ ... c_n)) = f.
  The empty conjunction is treated as a tautology, so TVal_I(And()) = t;
• Disjunction: TVal_I(Or(c₁ ... c_n)) = f if and only if TVal_I(c₁) = ... = TVal_I(c_n) = f. Otherwise, TVal_I(Or(c₁ ... c_n)) = t.
  The empty disjunction is treated as a contradiction, so TVal_I(Or()) = f;
• Negation: TVal_I(Not(c)) = f if and only if TVal_I(c) = t. Otherwise, TVal_I(Not(c)) = t;
• Existence: TVal_I(Exists ?v₁ ... ?v_n (φ)) = t if and only if for some I*, described below, TVal_I*(φ) = t.
  Here I* is a semantic structure of the form <TV, DTS, D, D_ind, D_pred, I_C, I*_V, I_P, I_frame, I_NP, I_sub, I_isa, I₌, I_external, I_truth>, which is exactly like I, except that the mapping I*_V, is used instead of I_V.   I*_V is defined to coincide with I_V on all variables except, possibly, on ?v₁,...,?v_n.

Let Term be the set of the terms in the RIF-PRD condition language (as defined in section Terms).

Definition (Substitution). A substitution is a finitely non-identical assignment of terms to variables; i.e., a function σ from Var to Term such that the set {x ∈ Var | x ≠ σ(x)} is finite. This set is called the domain of σ and denoted by Dom(σ). Such a substitution is also written as a set such as σ = {t_i/x_i}_i=0..n where Dom(σ) = {x_i}_i=0..n and σ(x_i) = t_i, i = 0..,n.

Definition (Ground Substitution). A ground substitution is a substitution σ that assigns only constants to the variables in Dom(σ): ∀ x ∈ Dom(σ), σ(x) ∈ Const.

Definition (Matching Substitution). Let ψ be a condition formula; let σ be a ground substitution for the free variables of ψ, that is, such that: Var(ψ) ⊆ Dom(σ); and let Φ be a set of ground formulas that satisfies ψ. We say that σ is matching Ψ to Φ (or simply, matching, when there is no ambiguity with respect to Ψ and Φ) if an only if, for every semantic structure I that is a model of all the ground formulas φ_i in Φ, there is at least one semantic structure I*, such that:

1. I* is a model of ψ: I* |= ψ;
2. I* is exactly like I, except that a mapping I*_V is used instead of I_V, such that   I*_V is defined to coincide with I_V on all variables except, possibly, on the variables ?v₀ ... ?v_n that are free in ψ, that is, such that: Var(ψ) = {?v₀ ... ?v_n};
3. I*_V(?x_i) = I_C(σ(?x_i)), for all ?x_i in Var(ψ).

In the definition of a matching substitution, conditions 1 and 2 are the same as in the definition of Condition Satisfaction, and they guarantee that the Φ-consistency of a substitution for the free variables in ψ is defined with respect to the same semantic structures that make Φ satisfy ψ. Condition 3 guarantees that Φ |= ψ[σ], where ψ[σ] denotes the ground condition formula obtained by substituting σ(?x) for every occurence of ?x in ψ, for every variable ?x in Var(ψ).

In other words, a formula ψ matches a ground formula And(φ₁, ..., φ_n), n > 0, with respect to a ground substitution σ, in the usual sense of pattern matching algorithms, e.g. [REFERENCE], if and only if σ is a matching substitution for the free variables of ψ with respect to the set of ground formulas Φ = {φ₁, ..., φ_n}.

(See also: Proposed modified abstract syntax and semantics, taking csma's comments into account)

• α is an atomic action or a well-formed action block, and
• every constant symbol mentioned in α occurs in exactly one context, and
• whenever a formula contains a function term t or an external atomic formula External(t), t must be an instance of the coherent set of external schemas (Section Schemas for Externally Defined Terms of [RIF-DTB]) associated with the language of RIF-PRD, and
• if t is an instance of the coherent set of external schemas associated with the language then t can occur only as a function term t or as an external atomic formula External(t).

Definition (RIF-PRD action language). The RIF-PRD action language consists of the set of all the well-formed actions.

The function Var(f), that has been defined for condition formulae, is extended to actions, and, further, to rules, as follows:

• if f is an atomic action with target formula t, then Var(f) = var(t);
• if f is an action block that binds variables ?v₁ ... ?v_n, n ≥ 0, and that contains actions a₁ ... a_m, m ≥ 1, then Var(f) = U_{1 ≤ i ≤ m} Var(a_i) - {?v₁ ... ?v_n};
• if f is an conditional action where c is the condition formula and a is the action, then Var(f) = Var(c) ∪ Var(a);
• if f is a quantified rule where ?v₁ ... ?v_n, n > 0, are the declared variables; p₁ ... p_m, m ≥ 0, are the binding patterns, and r is the rule, then Var(f) = (Var(r) ∪ Var(p₁) ∪ ... ∪ Var(p_m)) - {?v₁ ... ?v_n}.

Definition (Well-formed rule). A rule, r, is a well-formed rule if and only if it contains no free variable, that is, Var(r) = 0, and either:

• it is an unconditional well-formed action, a;
• or it is a conditional action where the condition formula, c, is a well-formed condition formula, and the action, a, as a well-formed action;
• or it is a quantified rule, Forall V (P) (c), and each of the declared variables in V = {?v_i}_{0 ≤ i ≤ n} is free in some of the binding patterns in P = {p_j}_{0 ≤ j ≤ m} or in the quantified rule, r; that is, V ⊆ Var(r) ∪ Var(p₁) ∪ ... ∪ Var(p_m), m ≥ 0.

Definition (Well-formed group). A well-formed group is either a group that contains only well-formed rules and well-formed groups, or a group that contains no rule or group (an empty group).

The set of the well-formed groups contains all the production rulesets that can be meaningfully interchanged using RIF-PRD.

For the purpose of specifying the semantics of a RIF-PRD rule or group of rules, a production rule system PRS is defined as a labeled terminal transition system (e.g. PLO04).

Definition (labeled terminal transition system): A labeled terminal transition system is a structure {C, L, →, T}, where

• C is a set of elements, c, called configurations, or state;
• L is a set of elements, a, called actions (or labels);
• → ⊆ C × L × C is the transition relation, that is: (c, a, c' ) ∈ → iff there is a transition labelled a from the state c to the state c' or, more appropriately in the case of a PRS, the execution of action a in the state c causes a transition to state c' . We note: c + a → c' or c ^a→ c';
• T ⊆ C is the set of final states, that is, the set of all the states c from which there are no transitions: T = {c ∈ C | ∀ a ∈ L, ∀ c' ∈ C, (c, a, c' ) ∉ →}.

A labeled transition system is a structure {C, L, →} (without a set T of final states).

The idea of describing a PRS as a labeled terminal transition system is that, given a set of production rules RS and a set of facts w₀, the rules in RS that are satisfied, in some sense, in w₀ determine an action a₁, which execution results in a new set of facts w₁; the rules in RS that are satisfied in w₁ determine an action a₂ to execute in w₁, and so on, until the system reaches a final state and stops. The result is the set of facts w_n when the system stops.

Example 3.1. Judicael, one follower of Joe the Hen Public's method, has four chickens, Joe, Jack, Joe and Julia, that own three potatoes (BigPotato, SmallPotato, UglyPotato) among them:

• Joe (daily grain allowance = 10) is 12 months old, Jack (daily grain allowance = 12) is 9 months old, Joe (daily grain allowance = 6) is 6 months old and Julia (daily grain allowance = 14) is 10 months old;
• BigPotato weights 70g, SmallPotato weights 10g, UglyPotato weights 50g;
• Joe owns BigPotato, Jack and Woof own SmallPotato jointly (Woof is the farm's dog. It inherited joint ownership of SmallPotato from its aunt Georgette) and Joe owns UglyPotato.

That is the initial set of facts w₀. Paula's rule set contains one single rule, that is, Joe's CMP rule:

(* joe:ChickenAndMashedPotatoes *)
Forall ?chicken ?potato ?allowance ?age ?weight (
  Do( Execute(joe:mash(?potato)) 
      Retract(?chicken[joe:allowance->?allowance])
      ?chicken[joe:allowance->External(func:numeric-multiply(?allowance 1.1))]
      Retract(joe:owns(?chicken ?potato)) )
  :-
  And( ?chicken#joe:Chicken 
       ?chicken[joe:age->?age joe:allowance->?allowance]
       External(pred:numeric-greater-than(?age, 8))
       ?potato#joe:Potato 
       ?potato[joe:weight->?weight]
       joe:owns(?chicken ?potato)
       External(pred:numeric-greater-than(?weight External(func:numeric-divide(?age 2))))
       External(pred:string-not-equals(External(joe:today()), "Tuesday"))
       Not(External(joe:foxAlarm())) ))

When the rule is applied to w₀:

• the first 3 conjuncts select {Joe/?chicken, Jack/?chicken, Julia/?chicken} as possible values for variable ?chicken (Joe is too young);
• conjuncts 4-7 select {(Joe/?chicken, BigPotato/?potato)} as the only possible substitution for the variables ?chicken and ?potato (UglyPotato does not belong to either Joe, Jack or Julia and SmallPotato is too small);

Suppose that Judicael's implementation of today() returns Monday and that the foxAlarm() is false when the CMP rule is applied: the condition is satisfied, and the actions in the conclusion are executed with BigPotato substituted for ?potato, Joe substituted for ?chicken, and 10 substituted for ?allowance. This results in the following changes in the set of facts:

• BigPotato is mashed (and removed from the list of potatoes to be considered in future applications of the CMP rule);
• the daily grain allowance of Joe is now 11;
• Joe does not own a potato anymore.

The resulting set of facts w₁ is thus:

• Joe (daily grain allowance = 11) is 12 months old, Jack (daily grain allowance = 12) is 9 months old, Joe (daily grain allowance = 6) is 6 months old and Julia (daily grain allowance = 14) is 10 months old;
• SmallPotato weights 10g, UglyPotato weights 50g;
• Jack and Woof own SmallPotato jointly and Joe owns UglyPotato.

When the CMP rule in applied to w₁, the first External predicate still selects {Joe/?chicken, Jack/?chicken, Julia/?chicken} as possible values for variable ?chicken, but the joe:own relation and the second External predicate do not select any possible substitution for the couple (?chicken, ?potato) anymore: the rule cannot be satisfied, and the system, having detected a final state, stops.

The result of the execution of the system is w₁.

In the remainder of this section, as in the section on the operational semantics of actions, W denotes the set of all the ground condition formulas in the RIF-PRD condition languages, and L denotes the set of all the ground atomic actions in the RIF-PRD action language. In addition, LC denotes the set of the formulas in the RIF-PRD condition language, and R denotes the set of all the rules in the RIF-PRD rule language. Finally, given a set X, P(X) will denote the power set of X and S(X), the set of all the finite sequences of elements of X.

For the purpose of this section, an instance of a rule, r ∈ R, is defined as a couple (r^id, σ), where r^id uniquely identifies r and σ is a ground substitution such that Var(r) ⊆ Dom(σ). Given a rule instance ri = (r^id, σ), rule(ri) denotes the rule that is uniquely identified by r^id, and substitution(ri) denotes σ.

Similarly, an instance of a rule set RS is a set of rule instances ri_i, where ∀ i, rule(ri_i) ∈ RS. Given a rule set RS, Inst(RS) denotes the set of all the possible instances of RS.

A RIF-PRD production rule system is defined as a labelled terminal transition system: given a rule set RS ⊆ R, let C_RS ⊆ P(W) × S(Inst(RS)) be a set of states, where a state is a pair c = (w, ri_c), such that w ⊆ W is a set of facts, and ri_c ∈ S(Inst(RS)) is an ordered instance of RS. Given a state c = (w, ri_c), let facts(c) denote the first element, the set of facts w; and let picked(c) denote the second element, the ordered ruleset instance, ri_c.

The idea is that a state, c, is made of a set, w, of ground FORMULAe that represent a state of facts; and of the ordered list, ri_c, of all the instances of the rules in the considered ruleset RS that are fired, in some sense to be further specified, in that state of facts.

Further, let H_RS ⊆ S(C_RS) be a set of histories, where a history, h, is an ordered list of states c_i: h = (c_n...c₁), n≥ 0. Given a history, h ∈ H_RS, current(h) will be used to denote the first element of h and history(h) will be used to denote h minus current(h): if h = (c_n...c₁), n≥ 1, current(h) denotes c_n and history(h) denotes the ordered list (c_n-1...c₁), n≥ 1. If h = () is the empty list, current(h) = history(h) = ∅.

The idea is that a history, h, represents the stack of the states that have been successively traversed by a production rule system, in the current run, from its initial state to the current state: current(h) represents the current state of the system; history(h) represents its history, that is, the states of facts that held and the instances that were fired in the previous cycles, ordered from most recent to initial.

Let further assume three functions:

• INSTANTIATE: P(W) × P(R) → P(Inst(R)), that, given a set of facts, w and a set of rules, RS, returns the set of all the instances of the rules in RS that are satisfied in w, in a sense that is determined by the specification of the function;
• PICK: P(W) × H_RS × P(R) × Strat → S(Inst(R)), where Strat is the set of the conflict resolution strategies identifiers. Given a state of facts, w, a history h, a rule set RS and a conflict resolution strategy, s, PICK(w, h, RS, s) returns the ordered subset, ori ⊆ INSTANTIATE(w, RS), selected and ordered according to the input strategy, s, of the rule instances that determine the ordered list of ground actions to be implemented, that is, the sequence of transitions to be executed from the input state;
• FINAL: H_RS × P(R) → {true, false}, that, given a history and a set of rules, returns true or false, depending on whether or not the history is terminal.

Let extractActions: S(Inst(R)) → S(L), be a helper function that, given an ordered set, ori, of rule instances, returns the sequence of ACTIONs that is the concatenation, preserving the order in ori, of the sequences of ground actions determined by each of the rule instances in ori.

Editor's Note: extractActions is underdefined. Need be fixed at some point.

Given a ruleset RS and the associated conflict resolution strategy LS, a RIF-PRD production rule system is defined as a labelled terminal transition system PRS_RS,LS = {H_RS, S(L), →_RS,LS, T_RS,LS}, where :

• H_RS is a set of histories;
• S(L) is the set of labels;
• The transition relation →_RS,LS ⊆ H_RS × S(L) × H_RS, is defined as follows:
  ∀ (h, s h' ) ∈ H_RS × S(L) × H_RS, (h, s, h' ) ∈ →_RS,LS if and only if all of the following hold:
  1. s = extractACTIONS(picked(current(h));
  2. (facts(current(h)), s, facts(current(h'))) ∈ →^*_RIF-PRD, where →^*_RIF-PRD denotes the transitive closure of the transition relation →_RIF-PRD that is defined by the specification of the semantics of actions;
  3. picked(c') = PICK(facts(current(c'), history(c'), RS, LS)
  4. and h ∉ T_RS,LS
• A history h is final iff FINAL(h, RS, LS) = true: T_RS,LS = {h ∈ H_RS | FINAL(h, RS, LS) = true}.

Intuitively, the first condition in the definition of the transition relation →_RS,LS says that a RIF-PRD production rule system can transition from one history to another only if the implementation of the actions picked in the current state of the former history produce the state of facts in the current state of the latter, according to the semantics of the individual actions, as specified in the relation →_RIF-PRD. Condition 2 guarantees that only the selection strategy and the specification of the function PICK determine which are the allowed transition paths out of a given state. And condition 3 guarantees that the system halts as soon as it encounters a terminal state.

Or, using →^*_RS,LS to denote the transitive closure of the transition relation:

Given the specification of PRS_RS,LS, the intended operational semantics of a production ruleset represented by a RIF-PRD Group RS is completely specified by the specification of the three functions INSTANTIATE, PICK and FINAL.

The evaluation of the function INSTANTIATE corresponds to the step that is often called matching in the description of production rule systems (e.g. PRR07). Given a collection of rules, it considers all possible ground rule instances, obtained by assigning ground terms to the variables occuring in them. Its semantics is defined, in accordance with the semantics of the RIF-PRD condition language.

Let ExtractCONDITIONS: R → LC be a function that, given a rule, r ∈ R, returns a well-formed condition formula defined recursively as follows:

• if r is of the form ACTION, then ExtractCONDITIONS(r) = And();
• if r is of the form if FORMULA then ACTION_BLOCK, then ExtractCONDITIONS(r) = FORMULA;
• if r is of the form Forall Var+ Pattern* (RULE), then ExtractCONDITIONS(r) = And(Pattern* ExtractCONDITIONS(RULE)).

Let InstantiateRULE: P(W) × R → P(Inst(R)), be a function that, given a set of facts w ∈ W and a rule r ∈ R, returns the set, ir ⊆ Inst(R), of all the instances of r that are satisfied in w, where a rule instance ri = (r^id, σ) satisfies a set of fact w if and only if σ matches ExtractCONDITIONS(rule(r^id)) to w.

The evaluation of the function INSTANTIATE(w, RS), where w ⊆ W and RS ⊆ R, can now be specified as a simple terminal transition system where:

• a state is a triple (w, rs, ri), where rs ⊆ RS and ri ⊆ P(Inst(RS - rs));
• the transition relation is defined by the single rule:
  (w, rs, ri) → (w, a, rs - r, ri ∪ InstantiateRULE(w, r))
• states with an empty rule set component are final: T = {(w, ∅, ri)}.

The input function is defined as:

The output function is defined as:

Example 3.4. TBD

Editor's Note: This section is still under discussion (see ISSUE-65). This version specifies a single, default halting test: future version of this draft may specify additional halting tests, and/or a different default. The Working Group seeks feedback on which halting tests and which combinations of tests should be supported by RIF-PRD and/or required from RIF-PRD implementations; and which halting test should be the default, if any.

By default, the specification for a terminal state that is intended for a set of production rules, when no halting test is explicitely associated to its representation as a RIF-PRD Ruleset, is when no rule instance is fireable: this is the case when INSTANTIATE returns an empty set of rule instances, or when all the rule instances that are satisfied in the state, according to the semantics of INSTANTIATE, have already been fired in a state that has not since changed significantly. That latter condition guarantees, in particular, that the system halts when it reaches a fixpoint.

Formally, ∀ RS ⊆ R, ∀ c ∈ C_RS, PICK(c, RS) = true if and only if instance(c) - history(c) = ∅. Otherwise, PICK(c, RS) = false.

Syntax such as xsd:string should be understood as a compact URI (CURIE) -- a macro that expands to a concatenation of the character sequence denoted by the prefix xsd and the string string. The compact URI notation is used for brevity only, and xsd:string should be understood, in this document, as an abbreviation for http://www.w3.org/2001/XMLSchema#string.

<!-- sample pseudo-schema -->
    <defined_element
          required_attribute_of_type_string="xs:string"
          optional_attribute_of_type_int="xs:int"? >
      <required_element />
      <optional_element />?
      <one_or_more_of_these_elements />+
      [ <choice_1 /> | <choice_2 /> ]*
    </defined_element>

This section specifies the XML constructs that are used in RIF-PRD to serialize condition formulae.

The TERM class of constructs is used to serialize terms, be they simple terms, that is, constants and variables; or positional terms or terms with named arguments, both being, per the definition of a well-formed formula, representations of externally defined functions.

As an abstract class, TERM is not associated with specific XML markup in RIF-PRD instance documents.

    [ Const | Var | External ]

In RIF, the Const element is used to serialize a constant.

The Const element has a required type attribute and an optional xml:lang attribute:

• The value of the type attribute is the identifier of the Const symbol space. It must belong to the type xsd:anyURI. In the RIF data types and builtins document, the section about [DTB#Constants.2C_Symbol_Spaces.2C_and_Datatypes|Constants, Symbol spaces and Datatypes]] lists the builtin symbol spaces and data types that all implementations of RIF-PRD must support. Rule sets that are exchanged through RIF-PRD can use additional, user-defined symbol spaces;
• The xml:lang attribute, as defined by 2.12 Language Identification of XML 1.0 or its successor specifications in the W3C recommendation track, is optionally used to identify the language for the presentation of the Const to the user. It is allowed only in association with constants of the type rif:text. A compliant implementation MUST ignore the xml:lang attribute if the type of the Const is not rif:text.

The content of the Const element is the constant's litteral, which can be any Unicode character string.

    <Const type=xsd:anyURI [xml:lang=xsd:language]? >
        Any Unicode string
    </Const>

\{\{EdNote|text=The case of non-standard data types, that is, of constants that do not belong or cannot be cast in one of RIF builtin types for interchange purposes, is still under discussion in the WG. The WG seeks feedback on whether they should be allowed and why.\}\}

Example 2.1. In each of the examples below, a constant is first described, followed by its serialization in RIF-PRD XML syntax.

a. A constant with builtin type xsd:integer and value 123:

<Const type="xsd:integer">123</Const>

b. A constant which symbol today is defined in Joe the Hen Public's namespace http://rif.examples.com/2008/joe#. The type of the constant is rif:iri:

<Const type="rif:iri">
   http://rif.examples.com/2008/joe#today
</Const>

c. A constant with symbol BigPotato that is local to the set of rules where it appears (e.g. a RuleSet specific to Paula's farm). The type of the constant is rif:local:

<Const type="rif:local">BigPotato</Const>

d. A constant with non-builtin type xsd:int and value 123:

<Const type="xsd:int">123</Const>

In RIF, the Var element is used to serialize a variable.

The content of the Var element is the variable's name, serialized as an Unicode character string.

    <Var> any Unicode string </Var>

Example 2.2. The example below shows the XML serialization of a reference to a variable named: ?chicken.

<Var> chicken <Var>

As a TERM, the External element is used to serialize a positional term or a term with named arguments. In RIF-PRD, a positional or a named-argument term represents always a call to an externally specified function, e.g. a builtin, a user-defined function, a query to an external data source...

The External element contains one content element, which in turn contains one Expr element that contains one op element, followed zero or one args element or zero of more slot elements:

• The content and Expr element ensure compatibility with the RIF Basic Logic Dialect, RIF-BLD, that allows non-evaluated (that is, logic) functions to be serialized using an Expr element;
• The content of the op element must be a Const. When the External is a TERM, the content of the op element serializes a constant symbol of type rif:iri that must uniquely identify the evaluated function to be applied to the args TERMs. In the RIF data types and builtins document, the section List of RIF Builtin Predicates and Functions lists the builtin functions that all implementations of RIF-PRD must support. The content of the op element can also identify an user-defined function: it is the responsibility of the producers and consumers of RIF-PRD rulesets that reference non-builtin functions to agree on their semantics;
• The optional args element contains zero or more constructs from the TERM abstract class. The args element is used to serialise the arguments of a positional term. The order of the args sub-elements is, therefore, significant and MUST be preserved. This is emphasized by the required value "yes" of the required attribute rif:ordered;
• Each optional slot element contains one required Name sub-element, that contains an Unicode string that serializes the slot key, and a required TERM that serializes its value. The slot element is used to serialize an argument name-value pair in a term with named arguments. The order of the slot elements is, therefore, not significant;

    <External>
       <content>
          <Expr>
             <op> Const </op>
             [ <args rif:ordered="yes"> TERM* </args>?
               |
               <slot rif:ordered="yes">
                  <Name> Any Unicode string </Name>
                  TERM
               <slot>* ]
          </Expr>
       </content>
    </External>

Editor's Note: The slotted, or named arguments form of the External TERM construct is still under discussion (see also ISSUE-68). The working group seeks feedback on whether or not it should be included in PRD.

Example 2.3.

a. The first example below shows one way to serialize, in RIF-PRD, the sum of integer 1 and a variable ?x, where the addition conforms to the specification of the builtin fn:numeric-add.

The prefix fn is associated with the namespace http://www.w3.org/2007/rif-builtin-function#.

<External>
   <content>
      <Expr>    
         <op> <Const type="rif:iri"> fn:numeric-add </Const> </op>
         <args rif:ordered="yes"> 
            <Const type="xsd:integer"> 1 </Const>
            <Var> x </Var>
         </args>
      </Expr>
   </content>
</External>

b. Another example, that shows the RIF XML serialization of a call to the application-specific nullary function today(), which symbol is defined in the example's namespace http://rif.examples.com/2008/joe#:

<External>
   <content>
      <Expr>    
         <op>
            <Const type="rif:iri">
               http://rif.examples.com/2008/joe#today
            </Const>
         </op>
      </Expr>
   </content>
</External>

The ATOMIC class is used to serialize atomics: positional and named-arguments atoms, equality, membership and subclass atomics, frame atomics and externally defined atomics..

As an abstract class, ATOMIC is not associated with specific XML markup in RIF-PRD instance documents.

    [ Atom | Equal | Member | Subclass | Frame | External ]

In RIF, the Atom element is used to serialize a positional atomics or an atomic with named arguments.

The Atom element contains one op element, followed by zero or one args element or zero or more slot arguments:

• The content of the op element must be a Const. It serializes the predicate symbol (the name of a relation);
• The optional args element contains zero or more constructs from the TERM abstract class. The args element is used to serialize the arguments of a positional atomic. The order of the arg's sub-elements is, therefore, significant and MUST be preserved. This emphasized by the required value "yes" of the required attribute rif:ordered;
• Each optional slot element contains one required Name sub-element, that contains an Unicode string that serializes the slot key, and a required TERM that serializes its value. The slot element is used to serialize an argument name-value pair in an atomic with named arguments. The order of the slot elements is, therefore, not significant;

    <Atom>
       <op> Const </op>
       [ <args rif:ordered="yes"> TERM* </args>?
         |
         <slot rif:ordered="yes">
            <Name> Any Unicode string </Name>
            TERM
         <slot>* ]
    </Atom>

Editor's Note: The slotted, or named arguments form of the Atom construct is still under discussion (see also ISSUE-68). The working group seeks feedback on whether or not it should be included in PRD.

Example 2.4. The example below shows the RIF XML serialization of the positional atomicsowns(?c ?p), where the predicate symbol owns is defined in the example namespace http://rif.examples.com/2008/joe#.

<Atom>
   <op>
      <Const type="rif:iri">
         http://rif.examples.com/2008/joe#owns
      </Const>
   </op>
   <args rif:ordered="yes">
      <Var> c </Var>
      <Var> p </Var>
   </args>
</Atom>

In RIF, the Equal element is used to serialize equality atomics.

The Equal element must contain one left sub-element and one right sub-element. The content of the left and right elements must be a construct from the TERM abstract class. The order of the sub-elements is not significant.

    <Equal>
       <left> TERM </left>
       <right> TERM </right>
    </Equal>

In RIF, the Member element is used to serialize membership atomics.

The Member element contains two unordered sub-elements:

• the instance elements must be a construct from the TERM abstract class. It is required;
• the class element must be a construct from the TERM abstract class. It is required as well.

    <Member>
       <instance> TERM </instance>
       <class> TERM </class>
    </Member>

Example 2.5. The example below shows the RIF XML serialization of a boolean expression that tests whether the individual denoted by the variable ?c is a member of the class Chicken that is defined in the example namespace http://rif.examples.com/2008/joe#.

<Member>
   <instance> <Var> c </Var> </instance>
   <class>
      <Const type="rif:iri">
         http://rif.examples.com/2008/joe#Chicken
      </Const>
   </class>
</Member>

In RIF, the Subclass element is used to serialize subclass atomics.

The Subclass element contains two unordered sub-elements:

• the sub element must be a construct from the TERM abstract class. It is required;
• the super elements must be a construct from the TERM abstract class. It is required.

    <Subclass>
       <sub> TERM </sub>
       <super> TERM </super>
    </Subclass>

In RIF, the Frame element is used to serialize frame atomics.

Accordingly, a Frame element must contain:

• an object element, that contains an element of the TERM abstract class, the content of which serializes the individual;
• zero to many slot elements, each containing a Prop element that serializes an attribute-value pair as a pair of elements of the TERM abstract class, the first one that serializes the name of the attribute (or property); the second that serializes the attribute's value. The order of the slot's sub-elements is significant and MUST be preserved. This is emphasized by the required value "yes" of the required attribute rif:ordered.

    <Frame>
       <object> TERM </object>
       <slot rif:ordered="yes"> TERM TERM </slot>*
    </Frame>

Example 2.6. The example below shows the RIF XML syntax that serializes an expression that states that the object denoted by the variable ?c has the value denoted by the variable ?a for the property Chicken/age that is defined in the example namespace http://rif.examples.com/2008/joe#.

<Frame>
   <object> <Var> c </Var> </object>
   <slot rif:ordered="yes"> 
      <Const type="rif:iri">
         ttp://rif.examples.com/2008/joe#Chicken/age
      </Const>
      <Var> a </Var>
   </slot>
</Frame>

Editor's Note: The example uses an XPath style for the key. How externally specified data models and their elements should be referenced is still under discussion (see ISSUE-37).

In RIF-PRD, the External element is also used to serialize an externally defined atomic.

When it is a ATOMIC (as opposed to a TERM; that is, in particular, when it appears in a place where an ATOMIC is expected, and not a TERM), the External element contains one content element that contains one Atom element. The Atom element serializes the externally defined atom properly said:

    <External>
       <content>
          Atom
       </content>
    </External>

The op Const in the Atom element must be a symbol of type rif:iri that must uniquely identify the externally defined predicate to be applied to the args TERMs. It can be one of the builtin predicates specified for RIF dialects, as listed in section List of RIF Builtin Predicates and Functions of the RIF data types and builtins document, or it can be application specific. In the latter case, it is up to the producers and consumers of RIF-PRD rulesets that reference non-builtin predicates to agree on their semantics.

Example 2.7. The example below shows the RIF XML serialization of an externally defined atomic that tests whether the value denoted by the variable named ?a (e.g. the age of a chicken) is greater than the integer value 8, where the test is intended to behave like the builtin predicate op:numeric-greater-than as specified in XQuery 1.0 and XPath 2.0 Functions and Operators.

In the example, the prefix op: is associated with the namespace http://www.w3.org/2007/rif-builtin-predicate#.

<External>
   <content>
      <Atom>    
         <op> <Const type="rif:iri"> op:numeric-greater-than </Const> </op>
         <args rif:ordered="yes">
            <Var> ?a </Var>
            <Const type="xsd:decimal"> 8 </Const>
         </args>
      </Atom>
   </content>
</External>

The FORMULA class is used to serialize condition formulas, that is, atomic formulas, conjunctions, disjunctions, negations and existentials.

As an abstract class, FORMULA is not associated with specific XML markup in RIF-PRD instance documents.

    [ ATOMIC | And | Or | NmNot | Exists ]

An atomic formula is serialized using a single ATOMIC statement. See specification of ATOMIC, above.

A conjunction is serialized using the And element.

The And element contains zero or more formula sub-elements, each containing an element of the FORMULA group.

    <And>
       <formula> FORMULA </formula>*
    </And>

A disjunction is serialized using the Or element.

The Or element contains zero or more formula sub-elements, each containing an element of the FORMULA group.

    <Or>
       <formula> FORMULA </formula>*
    </Or>

A negation is serialized using the NmNot element.

The NnNot element contains exactly one formula sub-element. The formula element contains an element of the FORMULA group, that serializes the negated statement.

    <NmNot>
       <formula> FORMULA </formula>
    </NmNot>

Editor's Note: The name of that construct may change, including the tag of the XML element.

An existentially quantified formula is serialized using the Exists element.

The Exists element contains:

• one or more declare sub-elements, each containing a Var element that serializes one of the existentially quantified variables;
• exactly one required formula sub-element that contains an element from the FORMULA abstract class: the FORMULA serializes the formula in the scope of the quantifier.

    <Exists>
       <declare> Var </declare>+
       <formula> FORMULA </formula>
    </Exists>

Example 2.8. The example below shows the RIF XML serialization of a boolean expression that tests whether the chicken denoted by variable ?c is older than 8 months, by testing the existence of a value, denoted by variable ?a, that is both the age of ?c, as serialized as a Frame element, as in example 2.6, and greater than 8, as serialized as an External ATOMIC, as in example 2.7.

<Exists>
   <declare> <Var> a </Var> </declare>
   <formula>
      <And>
         <Frame>
            <object> <Var> c </Var> </object>
            <slot rif:ordered="yes"> 
               <Const type="rif:iri">
                  http://rif.examples.com/2008/joe#Chicken/age
               </Const>
               <Var> a </Var>
            </slot>
         </Frame>
         <External>
            <content>
               <Atom>    
                  <op> <Const type="rif:iri"> op:numeric-greater-than </Const> </op>
                  <args rif:ordered="yes">
                     <Var> a </Var>
                     <Const type="xsd:decimal"> 8 </Const>
                  </args>
               </Atom>
            </content>
         </External>
      </And>
   </formula>
</Exists>

    [ ATOMIC_CONCLUSION | ATOMIC_ACTION | ACTION_BLOCK | CONCLUSION_BLOCK ]

    [ Atom | Frame | Member | Subclass ]

    [ Assert | Retract ]

    <Assert>
         <target> ATOMIC_CONCLUSION </target>
    </Assert>

    <Retract>
       <target> [ Atom | Frame | TERM ] </target>
    </Retract>

Example 2.10. The example below shows the RIF XML representation of an action that updates the chicken-potato ownership table by removing the predicate that states that the chicken denoted by variable ?c owns the potato denoted by variable ?p. The predicate is represented as in example 2.4.

<Retract>
   <target>
      <Atom>
         <op>
            <Const type="rif:iri">
               http://rif.examples.com/2008/joe#owns
            </Const>
         </op>
         <args rif:ordered="yes">
            <Var> c </Var>
            <Var> p </Var>
         </args>
      </Atom>
   </target>
</Retract>

    <Do rif:ordered="yes">
       <declare> Var+ </declare>?
       <binding> [ New | Frame ] </binding>*
       <action> ATOMIC_ACTION  </action>+
    </Do>

    <New>
       <instance> Var </instance>?
    </New>

<Do rif:ordered="yes">
   <declare><Var>p</Var></declare>
   <binding>
      <New>
         <instance><Var>p</Var></instance>
      </New>
   </binding>
   <action>
      <Assert>
         <target>
            <Member>
               <instance><Var>p</Var></instance>
               <class>
                  <Const type="rif:iri">http://rif.examples.com/2008/joe#Potato</Const>
               </class>
            </Member>
         </target>
      </Assert>
   </action>
   <action>
      <Assert>
         <target>
            <Frame>
               <object><Var>p</Var></object>
               <slot rif:ordered="yes">
                  <Const type="rif:iri">http://rif.examples.com/2008/joe#weight</Const>
                  <Const type="xsd:decimal">100</Const>
               </slot>
            </Frame>
         </target>
      </Assert>
   </action>
</Do>

    <And>
       <formula> ATOMIC_CONCLUSION </formula>+
    </And>

In RIF-PRD, the RULE class of constructs is used to serialize rules, that is, unconditional as well as conditional actions, or rules with bound variables.

As an abstract class, RULE is not associated with specific XML markup in RIF-PRD instance documents.

    [ Implies | Forall | ACTION ]

An unconditional action block is serialized, in RIF-PRD XML, using the ACTION class of construct.

Editor's Note: To be updated based according ot the uptodate version of the XML syntax for actions.

Conditional actions are serialized, in RIF-PRD, using the XML element Implies.

The Implies element contains an optional if sub-element and a then sub-element:

• the optional if element contains an element from the FORMULA class of constructs, that serializes the condition of the rule;
• the required then element contains a non-empty list of elements from the ACTION class of constructs. The order of the ACTION constructs in the then element is significant and MUST be preserved.

Editor's Note: To be updated based according ot the uptodate version of the XML syntax for actions.

    <Implies>
       <if> FORMULA </if>?
       <then rif:ordered="yes">
          ACTION
          ACTION*
        </then>
     </Implies>

The Forall construct is used, in RIF-PRD, to represent rules with bound variables.

The Forall element contains:

• one or more declare sub-elements, each containing a Var element that represents one of the universally quantified variable;
• zero or more pattern sub-elements, each containing an element from the FORMULA group of constructs, serializing one binding pattern;
• exactly one formula sub-element that serializes the formula in the scope of the variables binding, and that contains an element of the RULE group.

    <Forall>
       <declare> Var </declare>+
       <pattern> FORMULA </pattern>*
       <formula> RULE </formula>
    </Forall>

Editor's Note: Nested Foralls make explicit the scope of the declared variables, and, thus, impose an order on the evaluation of the pattern and if FORMULAe in a rule. That ordering and the use of patterns to constrain the binding of variables may be of practical significance for some production rule systems, but they are irrelevant with respect to the intended semantics of the rules being interchanged (although they would be relevant if RIF-PRD was to be extended to support some kind of "else" or "case" construct). In addition, RIF-BLD does not allow nested Forall and does not support the association of contraining patterns to declared variables. The working group seeks feedback regarding whether nested Forall and constrainting pattern should be supported in RIF-PRD, to the cost of reducing the interoperability with RIF-BLD.

Example 2.10. The example below shows how the CMP rule extract: "if a chicken owns a potato and ..." could be serialized using a binding pattern FORMULA:

<Forall>
   <declare><Var>chicken</Var></declare>
   <formula>
      <Forall>
         <declare><Var>potato</Var></declare>
         <pattern>
            <External>
               <content>
                  <Atom>
                     <Const type="rif:iri">
                        http://rif.examples.com/2008/joe#owns
                     </Const>
                     <Args rif:ordered="yes">
                        <Var>chicken</Var>
                        <Var>potato</Var>
                     </Args>
                  </Atom>
               </content>
            </External>
         </pattern>
         <formula>
            ...
         </formula>
      </Forall>
   </formula>
</Forall>

The Group construct is used to serialize a group.

The Group element has zero or one behavior sub-element and zero or more sentence sub-elements:

• the behavior element contains
  • zero or one ConflictResolution sub-element that contains exactly one IRI. The IRI identifies the conflict resolution strategy that is associated with the Group; and
  • zero or one Priority sub-element that contains exactly one signed integer between -10,000 and 10,000. The integer associates a priority with the Group's sentences;
• a sentence element contains either a Group element or an element of the RULE abstract class of constructs.

    <Group>
       <behavior>
          <ConflictResolution> xsd:anyURI </ConflictResolution>?
          <Priority> -10,000 ≤ xsd:int ≤ 10,000 </Priority>?
       </behavior>?
       <sentence> [ RULE | Group ] </sentence>*
    </Group>

    <Document>
       <payload> Group </payload>?
    </Document>

    CLASSELT = [ TERM | ATOMIC | FORMULA | ACTION | RULE | Group | Document ]

   <CLASSELT>
       <id> Const </id>?
       <meta>
          [ Frame 
            |
            <And>
               <formula> Frame </formula>*
            </And>
          ]
       </meta>?
       other CLASSELT content
    </CLASSELT>

It is suggested to use Dublin Core, RDFS, and OWL properties for metadata, along the lines of http://www.w3.org/TR/owl-ref/#Annotations -- specifically owl:versionInfo, rdfs:label, rdfs:comment, rdfs:seeAlso, rdfs:isDefinedBy, dc:creator, dc:description, dc:date, and foaf:maker.

Example 2.11. TBC

The presentation syntax is designed to be very close to RIF-BLD. A line by line comparison of the EBNF will show these few differences:

1. the addition of Not
2. the removal of Expr, the syntactic class of logical functions,
3. the replacement of ATOMIC in rule conclusions with ACTION, and the addition of Do(ACTION*) and And(ASSERT*) instead of And(ATOMIC*) in rule conclusions.
4. definition of Assert, New, Retract, and Do actions.

It is intended that the syntax and semantics of RIF-BLD and RIF-PRD are the same when the rule conclusion contains a only Atoms and Frames, "Not" is not used, and logical functions are not used.

The following EBNF is from RIF-BLD, with lines prefixed with ! indicating a change for RIF-PRD:

  FORMULA        ::= 'And' '(' FORMULA* ')' |
                     'Or' '(' FORMULA* ')' |
                     'Exists' Var+ '(' FORMULA ')' |
                      ATOMIC |
                     'External' '(' Atom | Frame ')' |
!                    'Not' '(' FORMULA ')'
  ATOMIC         ::= Atom | Equal | Member | Subclass | Frame
  Atom           ::= UNITERM
  UNITERM        ::= Const '(' (TERM* <| (Name '->' TERM)*) ')'
  Equal          ::= TERM ' = ' TERM
  Member         ::= TERM '#' TERM
  Subclass       ::= TERM '##' TERM
  Frame          ::= TERM '[' (TERM '->' TERM)* ']'
! TERM           ::= Const | Var | 'External' '(' Expr ')'
  Expr           ::= UNITERM
  Var            ::= '?' UNICODESTRING

The following EBNF is taken from RIF-DTB and is unchanged for PRD. Its purpose is to provide shortcuts for constants.

  ANGLEBRACKIRI  ::= '<' IRI_REF '>'
  STRING         ::= '"' UNICODESTRING '"'
  CURIE          ::=  PNAME_LN | PNAME_NS   → see RIF-DTB
  Const          ::= STRING '^^'ANGLEBRACKIRI
                   | STRING '^^' CURIE
                   | ANGLEBRACKIRI     → shortcut for rif:iri
                   | CURIE             → shortcut for rif:iri
                   | STRING            → shortcut for xsd:string
                   | NumericLiteral    → shortcut for xsd:integer,xsd:decimal,xsd:double
                   | '_' LocalName     → shortcut for rif:local

The following EBNF is from RIF-BLD and defines rules, groups of rules, and the containing document. Changed lines are prefixed with !. Metadata can be associated with Document, Group, and RULE constructs.

! Document     ::= IRIMETA? 'Document' '('  Group? ')'
  Group        ::= IRIMETA? 'Group' '(' (RULE | Group)* ')'
! RULE         ::= (IRIMETA? 'Forall' Var+ '(' Implies ')') | Implies | INITIAL_FACT
! INITIAL_FACT ::= ASSERT | Member
! Implies      ::= IRIMETA? ACTION ':-' FORMULA
  IRIMETA      ::= '(*' Const? (Frame | 'And' '(' Frame* ')')? '*)'
  IRI          ::= UNICODESTRING
  Profile      ::= UNICODESTRING

Finally, the following EBNF describes the syntax of PRD actions.

  ACTION             ::= ATOMIC_CONCLUSION | ATOMIC_ACTION | ACTION_BLOCK | CONCLUSION_BLOCK 
  ATOMIC_CONCLUSION  ::= Atom | Frame | Member | Subclass
  ATOMIC_ACTION      ::= Assert | Retract
  Assert             ::= 'Assert' '(' ATOMIC_CONCLUSION ')'
  Retract            ::= 'Retract' '(' Atom | Frame | TERM ')'
  ACTION_BLOCK       ::= 'Do' Var* '(' ( ACTION_VAR_BINDING+ ';' )? ATOMIC_ACTION+ ')' 
  ACTION_VAR_BINDING ::= New | Frame
  New                ::= 'New' '(' Var ')'
  CONCLUSION_BLOCK   ::= 'And' '(' ATOMIC_CONCLUSION ATOMIC_CONCLUSION+ ')' 

[CIR04]

Production Systems and Rete Algorithm Formalisation, Cirstea H., Kirchner C., Moossen M., Moreau P.-E. Rapport de recherche n° inria-00280938 − version 1 (2004).

[CURIE]

CURIE Syntax 1.0 - A compact syntax for expressing URIs, W3C note 27 October 2005, M. Birbeck (ed.).

[HAK07]

Data Models as Constraint Systems: A Key to the Semantic Web, Hassan Ait-Kaci, Constraint Programming Letters, 1:33--88, 2007.

[PLO04]

A Structural Approach to Operational Semantics, Gordon D. Plotkin, Journal of Logic and Algebraic Programming, Volumes 60-61, Pages 17-139 (July - December 2004).

[PRR07]

Production Rule Representation (PRR), OMG specification, version 1.0, 2007.

[RDF-CONCEPTS]

Resource Description Framework (RDF): Concepts and Abstract Syntax, Klyne G., Carroll J. (Editors), W3C Recommendation, 10 February 2004, http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/. Latest version available at http://www.w3.org/TR/rdf-concepts/.

[RDF-SCHEMA]

RDF Vocabulary Description Language 1.0: RDF Schema, Brian McBride, Editor, W3C Recommendation 10 February 2004, http://www.w3.org/TR/2004/REC-rdf-schema-20040210/. Latest version available at http://www.w3.org/TR/rdf-schema/.

[RFC-3066]

RFC 3066 - Tags for the Identification of Languages, H. Alvestrand, IETF, January 2001, http://www.isi.edu/in-notes/rfc3066.txt.

[RFC-3987]

RFC 3987 - Internationalized Resource Identifiers (IRIs), M. Duerst and M. Suignard, IETF, January 2005, http://www.ietf.org/rfc/rfc3987.txt.

[XDM]

XQuery 1.0 and XPath 2.0 Data Model (XDM), W3C Recommendation, World Wide Web Consortium, 23 January 2007. This version is http://www.w3.org/TR/2007/REC-xpath-datamodel-20070123/. Latest version available at http://www.w3.org/TR/xpath-datamodel/.

[XML-SCHEMA2]

XML Schema Part 2: Datatypes Second Edition, W3C Recommendation, World Wide Web Consortium, 28 October 2004, http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/. Latest version available at http://www.w3.org/TR/xmlschema-2/.

[XPath-Functions]

XQuery 1.0 and XPath 2.0 Functions and Operators, W3C Recommendation, World Wide Web Consortium, 23 January 2007, http://www.w3.org/TR/2007/REC-xpath-functions-20070123/. Latest version available at http://www.w3.org/TR/xpath-functions/.

RIF-PRD and RIF-BLD share essentially the same presentation syntax and XML syntax.

The syntactic differences between the two dialects are summarized below:

• RIF-BLD allows logic and externally specified, fixed-interpretation functions as TERM, whereas RIF-PRD accepts only externally specified functions;
• RIF-BLD allows ATOMIC or And(ATOMIC*) in rule conclusions, whereas RIF-PRD allows ACTION or Do(ACTION*). In RIF-PRD it is not possible to conclude equality or class membership.
• RIF-PRD allows Not(FORMULA), which RIF-BLD does not accept;
• RIF-PRD defines ASSERT and Retract actions that are not allowed in RIF-BLD.

Below is a complete, construct by construct, comparison table of RIF-PRD and RIF-BLD presentation and XML syntaxes. A construct is tagged "BLD" or "PRD" if it is specific to the dialect, or tagged "Core" if it is common to both.

Editor's Note: RIF-Core will be equal to or included in the intersection of RIF-PRD and RIF-BLD. The exact scope of RIF-Core is still under discussion. Until RIF-Core is specified more precisely, this document assumes that it will be equal to the intersection of RIF-PRD and RIF-BLD.

[Const | Var | Expr | External]

[Const | Var | External]

'"' UNICODESTRING '"^^' SYMSPACE

<Const type=xsd:anyURI [xml:lang=xsd:language]? >
   Any Unicode string
</Const>

'?' Any Unicode string

<Var>
   Any Unicode string
</Var>

Const '(' (TERM* | (Name '->' TERM)*) ')'

<Expr>
   <op> Const </op>
   [
    <args rif:ordered="yes"> TERM* </args>?
    |
    <slot rif:ordered="yes">
       <Name> Any Unicode string </Name>
       TERM
    </slot>*
   ]
</Expr>

Undefined except when wrapped in an External (as TERM), as follows.

'External' '(' Expr ')'

<External>
   <content>
      Expr
   </content>
</External>

[Atom | Equal | Member | Subclass | Frame]

Const '(' (TERM* | (Name '->' TERM)*) ')'

<Atom>
   <op> Const </op>
   [
    <args rif:ordered="yes"> TERM* </args>?
    |
    <slot rif:ordered="yes">
       <Name> Any Unicode string </Name>
       TERM
    </slot>*
   ]
</Atom>

TERM = TERM

<Equal>
   <left> TERM </left>
   <right> TERM </right>
</Equal>

TERM # TERM

<Member>
   <instance> TERM </instance>
   <class> TERM </class>
</Member>

TERM ## TERM

<Subclass>
   <sub> TERM </sub>
   <super> TERM </super>
</Subclass>

TERM ' [ ' (TERM ' -> ' TERM)* ' ] '

<Frame>
   <object> TERM </object>
   <slot rif:ordered="yes"> TERM TERM </slot>*
</Frame>

[ATOMIC | External | And | Or | Exists]

[ATOMIC | External | And | Or | NmNot | Exists]

'External '(' [Atom | Frame] ')'

<External>
   <content>
      [ Atom | Frame ]
   </content>
</External>

'And' '(' FORMULA* ')'

<And>
   <formula> FORMULA </formula>*
</And>

'Or' '(' FORMULA* ')'

<Or>
   <formula> FORMULA </formula>*
</Or>

Undefined

'Not' '(' FORMULA ')'

<NmNot>
   <formula> FORMULA </formula>
</NmNot>

'Exists' Var+ '(' FORMULA ')'

<Exists>
   <declare> Var </declare>+
   <formula> FORMULA </formula>
</Exists>

Undefined

[ ASSERT | Retract ]

Undefined

[ Atom | Frame ]

Undefined

'Retract' '(' Atom | Frame ' ) '

<Retract>
   <target>
      [ Atom | Frame ]
   </target>
</Retract>

[ Forall | Implies | ATOMIC ]

[ Forall | Implies | ACTION ]

' Forall ' Var+ ' ( ' [Implies | ATOMIC] ' ) '

<Forall>
   <declare> Var </declare>+
   <formula>
       [Implies | ATOMIC ] 
   </formula>
</Forall>

' Forall ' Var+ (' ( ' FORMULA ' ) ')* ' ( ' RULE ' ) '

<Forall>
   <declare> Var </declare>+
   <pattern> FORMULA </pattern>*
   <formula> RULE </formula>
</Forall>

(ATOMIC | 'And' '(' ATOMIC* ')') ':-' FORMULA

<Implies>
   <if> FORMULA </if>
   <then>
      [ ATOMIC
        |
        <And>
           <formula>
              ATOMIC
           </formula>*
        </And>
      ]
   </then>
</Implies>

(ACTION | 'Do' '(' ACTION* ')') ':-' FORMULA

<Implies>
   <if> FORMULA </if>
   <then>
      ACTION
      ACTION*
   </then>
</Implies>

METADATA? 'Group' '(' ([RULE | Group])* ')'

<Group>
   <sentence> [ RULE | Group ] </sentence>*
</Group>

'Import' '(' IRI Profile? ')'

<Import>
   <location>lAny Unicode string</location>
   <profile><Profile>Any Unicode String1</Profile></profile>
</Import>

Undefined in this version of the draft

METADATA? 'Document' '(' [Import | Prefix | Base]* Group? ')'

<Document>
  <directive>
     [ Import | Prefix | Base]*
  </directive>
  <payload> Group </payload>?
</Document>

METADATA? 'Document' '(' Group? ')'

<Document>
  <payload> Group </payload>?
</Document>

'(*' Const? (Frame | 'And' '(' Frame* ')')? '*)'

<AnyClassTag>
   <id> Const </declare>?
   <meta>
      [ Frame 
        |
        <And>
           <formula> Frame </formula>
        </And>
       ]
   </meta>?
   other content of AnyClassTag
</AnyClassTag>

The intended semantics of any RIF XML document which is both a syntactically valid RIF-PRD document and a syntactically valid RIF-BLD document is the same whether it is considered a RIF-PRD or a RIF-BLD document. For any input set of facts, the set of rules contained in the document must produce the same output set of facts whether it is consumed as a RIF-PRD or a RIF-BLD document.

Proof. TBC