RIF Production Rule Dialect

W3C Editor's Draft 30 July 2008

This version:: http://www.w3.org/2005/rules/wg/draft/ED-rif-prd-20080730/
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-20080728/ (color-coded diff)

Editors:: Christian de Sainte Marie, ILOG

Abstract

This document specifies RIF-PRD, a Rule Interchange Format (RIF) dialect to enable the interchange of production rules.

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/.

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

Document Evolution

This is the First Public Working Draft of the RIF production rules dialect. It represents the current state of the design. It is incomplete, and it includes elements that are still under discussion in the WG. These elements are generally marked with editor's notes, and the WG particularly seeks feedback on them.

Please Comment By 2008-09-19

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.

1 Overview
2 Syntax
3 Operational semantics
4 References
5 Appendix: XML Schema for RIF-PRD
6 Appendix: Compatibility with RIF-BLD
- 6.1 Syntactic compatibility between RIF-PRD and RIF-BLD
- 6.2 Semantic compatibility between RIF-PRD and RIF-BLD
7 Appendix: UML-like diagram of RIF-PRD syntax

1 Overview

1.1 Introduction

This document specifies the production rule dialect of the W3C rule interchange format (RIF-PRD). 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 knowledge base and 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 common XML serialisation format for many production rule languages, RIF-PRD specifies an XML syntax for the most widely used features (section 2 - Syntax), and the operational semantics that RIF-PRD constructs are intended to represent (section 3 - Operational semantics).

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).

Editor's Note: This working draft specifies the RIF-PRD serialisation of a set of core constructs only. Future versions of this document will extend the set of RIF-PRD constructs to cover the most widely used features of production rule languages. The working group seeks feedback on what features should be supported by RIF-PRD and what constructs should or should not be required from conformant RIF-PRD implementations.

As a RIF dialect, RIF-PRD has also been designed to maximize interoperability between rule languages over the World Wide Web. In this draft, this is achieved by sharing the same syntax for the subset of RIF documents where the semantics intended for a production ruleset serialized in RIF-PRD, and the semantics intended for a logic rule base serialized in the basic logic dialect of RIF, RIF-BLD, agree. The correspondence between RIF-PRD and RIF-BLD is detailed in Appendix: Compatibility with RIF-BLD.

Editor's Note: Future versions of this working draft will draw on other RIF documents to maximize interoperability with other rule languages, most noticeably the RIF data types and builtins specification, RIF-DTB, and the RIF extensibility framework (currently being specified by the working group; see also the RIF framework for logic dialects, RIF-FLD, that specifies a framework for designing RIF logic dialects).

In the section 2, two related but distinct syntaxes for RIF-PRD components are introduced:

XML syntax. This syntax is the normative XML serialization of RIF-PRD. It is meant, and has been designed, to work as a common XML serialisation for many production rule languages. It is also meant, and has been designed, to work as a common XML serialisation for production rule languages and logic rule languages, wherever they agree on the semantics: as a consequence, RIF-PRD and RIF-BLD share the same XML syntax wherever they agree on the semantics. The XML syntax is specified using textual descriptions and BNF pseudo-schemas. A normative XML schema will also be provided in future versions of the document;
Presentation syntax. A presentation syntax is also specified, to allow a more easily readable presentation of RIF-PRD language fragments (such as examples etc). To make the overlap between RIF-PRD and RIF-BLD visible, RIF-PRD re-uses the presentation syntax of RIF-BLD wherever they share the same XML syntax (and agree on the semantics). The presentation syntax is non normative.

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 (
  ex1:Gold(?customer)
  :-
  And(
    ?customer#ex1:Customer
    ?customer[ex1:purchasesYTD->?purchasesYTD]
    pred:numeric-greater-than(?purchasesYTD 5000) ))

Editor's Note: As a consequence of the re-use of RIF-BLD presentation syntax, examples and fragments written in RIF-PRD non-normative presentation syntax may have an unfamiliar look to production rules developers and users. The working group seeks feedback on this issue as well.

The overall structure of the syntax of RIF-PRD is also presented as an UML-like diagram in appendix: UML-like diagram of RIF-PRD syntax. The diagram provides an overview of RIF-PRD syntactic classes and shows at a glance how they relate to each others. It is provided for informative purposes only.

In the section 3, the intended semantics for RIF-PRD constructs is specified normatively. As can be seen from the examples above, production rules, in general, are not logic rules, and they are not amenable to a model theory: followingly, the intended semantics of rules and set of rules serialized as RIF-PRD is specified operationally, in this document. The compatibility with the model theoretic semantics of RIF-BLD for the contructs they share is explained and proven in appendix: Compatibility with RIF-BLD.

1.2 Notational conventions

1.2.1 Namespaces

Throughout this document, the xsd: prefix stands for the XML Schema namespace URI http://www.w3.org/2001/XMLSchema#, the rdf: prefix stands for http://www.w3.org/1999/02/22-rdf-syntax-ns#, and rif: stands for the URI of the RIF namespace, http://www.w3.org/2007/rif#.

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.

1.2.2 BNF pseudo-schemas

The XML syntax of RIF-PRD is specified for each component as a pseudo-schema, as part of the description of the component. The pseudo-schemas use BNF-style conventions for attributes and elements: "?" denotes optionality (i.e. zero or one occurrences), "*" denotes zero or more occurrences, "+" one or more occurrences, "[" and "]" are used to form groups, and "|" represents choice. Attributes are conventionally assigned a value which corresponds to their type, as defined in the normative schema. Elements are conventionally assigned a value which is the name of the syntactic class of their content, as defined in the normative schema.

<!-- 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>

1.2.3 Syntactic components

Three kinds of syntactic components are used to specify RIF-PRD:

Abstract classes are defined only by their subclasses: they not visible in the XML markup and can be thought of as extension points. In this document, abstract constructs will be denoted with all-uppercase names;
Concrete classes have a concrete definition and they are associated with specific XML markup. In this document, concrete constructs will be denoted with CamelCase names with leading capital letter;
Properties, or roles, define how two classes relate to each other. They have concrete definitions and are associated with specific XML markup. In this document, properties will be denoted with camelCase names with leading smallcase letter.

1.3 Running example

This section describes the fictious RIF-PRD use case of Jim the Hen Handler, and the rule that will be used as a running example in this document.

Jim the Hen Handler developed a very sophisticated program to grow feeble chicks into deliciously plump chickens for a minimal cost. Jim publishes his method on his Web site www.juicychicken.org. Since he is still experimenting to improve his method, the rules to follow change quite often, and Jim decided to publish them in RIF as well, so that his followers can easily, even automatically, implement the very latest version.

Jim's method is a complex exercise of behavioural hen psychology: one aspect that is relevant for the example is that it requires that, under certain internal and/or external conditions, hen own potatoes, hen owned potatoes are mashed, hen daily grain allowance is increased or decreased etc.

Jim's latest addition to his knowledge base is an advice that: on a Monday, if a chicken over 8 months old owns a potato that weights (in decigrams) more than half its age, and if the fox is not in the hen house, then the potato should be mashed and the daily grain allowance of the chicken increased by 10%.

Jim calls it the "Chicken and Mashed Potatoes", or CMP, rule. The CMP rule is a production rule: that is, when the condition is satisfied and the rule is implemented (that is, fired), the consequence is that some actions are executed (mashing potatoes, modifying a chicken's diet, managing ownership relations etc). Therefore, it is best interchanged using RIF-PRD, the production rule dialect of RIF.

The CMP rule might be rephrased in RIF-PRD non-normative presentation syntax as follows:

 (* jim:ChickenAndMashedPotatoes *)
    // The identifier of the rule is the IRI "jim:ChickenAndMashedPotatoes"
 Forall ?chicken ?potato ?allowance ?age ?weight (
    // The Forall construct is used to declare the rule variables: "?chicken" etc
   Do(  // Rule actions list
        Execute(jim:mash(?potato))
        // The first action is to mash the potato that is bound to variable ?potato
        Retract(?chicken[jim:allowance->?allowance]) 
        ?chicken[jim:allowance->External(func:numeric-multiply(?allowance 1.1))]
        // The value of the "allowance" property of the chicken that is bound to ?chicken
        // is increased by 10%
        Retract(jim:owns(?chicken ?potato)) )
   :-   // IF
   And( // Rule conditions
        ?chicken#jim:Chicken 
        // The object bound to ?chicken is a "Chicken" as specified in Jim's object model
        ?chicken[jim:age->?age jim:allowance->?allowance]
        // The value of the "age" property of the "Chicken" object bound to ?chicken is 
        // equal to the value bound to the variable ?age, and the values of the "allowance"
        // property is equal to the value bound to ?allowance
        External(pred:numeric-greater-than(?age 8))
        // The value bound to ?age is greater than 8, where the function "numeric-grater-than"
        // is specified by RIF-PRD and must be supported by all implementations
        ?potato#jim:Potato 
        ?potato[jim:weight->?weight]
        jim:owns(?chicken ?potato)
        External(pred:numeric-greater-than(?weight External(func:numeric-divide(?age 2))))
        External(pred:string-not-equal(External(jim:today()) "Tuesday"))
        Not(External(jim:foxAlarm())) ))

To make sure that his rules can be implemented unambiguously, Jim published a data model (e.g., an XML schema) that identifies Chicken and Potato as two classes of objects:

instances of Chicken represent individual chickens. They have a property called age that represents the chicken's age in months as an xsd:decimal and a property called allowance that represent the chicken's daily grain allowance as an xsd:integer;
instances of Potato represent individual potatoes. They have a property called weight that represents the potato's weight in decigram as an xsd:decimal.

Jim further specifies:

a binary predicate owns(?o ?i) that denotes the ownership relation between owner ?o and owned item ?i;
a nullary function today() that returns the day of the week as a xsd:string;
a boolean fox sensor foxAlarm() that returns true if and only if the fox is in the hen house;
and a command mash(?i), which execution results in the physical item that is denoted by ?i being reduced to a soft pulpy state by beating or pressure (and in the corresponding logical object being removed from the instances of its class, as a consequence).

All these (types and names) are defined in Jim's namespace http://rif.examples.com/2008/jim#.

The assumption is that a system that consumes a RIF document published by Jim knows how to map Jim's published data model and specification of predicates and functions to/from its own underlying data representation. What a consumer is expected to do when this is not the case is still under discussion and will be specified as a conformance clause in a future version of this document.

2 Syntax

This section specifies the XML syntax for serializing the rule conditions and the rule actions, as well as complete production rules, groups of rules and formulae, and any accompanying metadata. Finally, RIF-PRD presentation syntax is specified.

2.1 Conditions

This section specifies the XML syntax that is used to serialize, in RIF-PRD, the different boolean expressions that can be found in production rules. That syntax is sometimes called the condition language, by reference to the condition language of RIF-BLD, which determines what conditions in a logic rule can be represented in RIF-BLD. It plays a similar role in RIF-PRD and, to maximize interoperability, the two dialects share the same constructs everywhere they agree on the semantics.

The most basic construct in RIF is the TERM. The TERM is an abstract construct, concretely visible, in RIF-PRD, as a Const, a Var or an External.

The ATOMIC is the basic building block of RIF. ATOMIC is an abstract class: it is visible in RIF-PRD as either an Atom, an Equal, a Member, a Subclass or a Frame. Each kind of ATOMIC is a composition of TERMs.

The next level of constructs are assemblies of ATOMICs. Together, the various kinds of assemblies form the abstract construct FORMULA. RIF-PRD knows six kinds of FORMULAs: the single ATOMIC, the Externally evaluated Atom or Frame, and the recursively specified And, Or, NmNot and Exists.

The following sections specify each construct separately, grouped by abstract syntactic classes.

Editor's Note: Future version of this document will specify additional constructs to increase the expressive coverage of RIF-PRD, and the precise syntax of some constructs may change. The working group seeks feedback on which additional constructs and/or which extension of specified constructs would be most useful to add.

2.1.1 TERM

The TERM class of constructs is used to represent constants, variables and the application of function symbols to other TERMs.

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

    [ Const | Var | External ]

2.1.1.1 Const

In RIF, the Const construct is used to represent 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;

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>

Constant types. RIF requires that all dialects include the following builtin constant types. Rule sets that are exchanged through RIF can use additional symbol spaces.

xs:string (http://www.w3.org/2001/XMLSchema#string)
xs:time (http://www.w3.org/2001/XMLSchema#time)
xs:date (http://www.w3.org/2001/XMLSchema#date)
xs:dateTime (http://www.w3.org/2001/XMLSchema#dateTime)
xs:double (http://www.w3.org/2001/XMLSchema#double)
xs:integer (http://www.w3.org/2001/XMLSchema#integer)
xs:decimal (http://www.w3.org/2001/XMLSchema#decimal)
The lexical spaces of the above symbol spaces are defined in the document [XML-SCHEMA2].
xs:dayTimeDuration (http://www.w3.org/2001/XMLSchema#dayTimeDuration)
xs:yearMonthDuration (http://www.w3.org/2001/XMLSchema#yearMonthDuration)
These two symbol spaces represent two subtypes of the XML Schema data type xs:duration with well-defined value spaces, since xs:duration does not have a well-defined value space (this may be corrected in later revisions of XML Schema data types, in which case the revised data type would be suitable for RIF DTB). The lexical spaces of the above symbol spaces are defined in the document [XDM].
rdf:XMLLiteral (http://www.w3.org/1999/02/22-rdf-syntax-ns#XMLLiteral).
This symbol space represents XML content. The lexical space of rdf:XMLLiteral is defined in the document [RDF-CONCEPTS].
rif:text (http://www.w3.org/2007/rif#text, for text strings with language tags attached).
This symbol space represents text strings with a language tag attached. The lexical space of rif:text is the set of all Unicode strings of the form ...@LANG, i.e., strings that end with @LANG where LANG is a language identifier as defined in [RFC-3066].
rif:iri (http://www.w3.org/2007/rif#iri, for internationalized resource identifiers or IRIs).
Constants in this symbol space are intended to be used in a way similar to RDF resources [RDF-SCHEMA]. The lexical space consists of all absolute IRIs as specified in [RFC-3987]; it is unrelated to the XML primitive type anyURI. A rif:iri constant must be interpreted as a reference to one and the same object regardless of the context in which that constant occurs.
rif:local (http://www.w3.org/2007/rif#local, for constant symbols that are not visible outside of the RIF document in which they occur).
Constants in this symbol space are local to the RIF documents in which they occur. This means that occurrences of the same rif:local constant in different documents are viewed as unrelated distinct constants, but occurrences of the same rif:local constant in the same document must refer to the same object. The lexical space of rif:local is the same as the lexical space of xs:string.

Editor's Note: The list of builtin constant types may be modified in future versions of this document, based on the content of future versions of the RIF data types and builtins document, RIF-DTB.

Editor's Note: 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.

Symbols with an ill-formed lexical part. Constants that are represented in RIF in one of the aforesaid builtin types must be well-formed, i.e., their representation must belong to the lexical space associated with the type. For instance, 123^^xsd:long (that is, <Const type="xsd:long">123</Const>) has a correct lexical part, since 123 belongs to the lexical space of the data type xsd:long. In contrast, abc^^xsd:long (<Const type="xsd:long">abc</Const>) is ill-formed, as it does not have a correct lexical part. A compliant RIF-PRD translator MUST reject ill-formed symbols.

Example 2.1. In each of the examples below, a constant is first described, followed by its representation 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 Jim the Hen Handler's namespace http://rif.examples.com/2008/jim#. The type of the constant is rif:iri:

<Const type="rif:iri">
   http://rif.examples.com/2008/jim#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>

2.1.1.2 Var

In RIF, the Var construct is used to represent variables.

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

    <Var> any Unicode string </Var>

Example 2.2. The example below shows the XML serialization of the variable ?chicken.

Notice that the content of the Var element is the Unicode string chicken: in the RIF presentation syntax, the ?-prefix is used as a syntactic marker to denote a variable identifier, but RIF leaves it to the implementations to use whatever prefix they choose or require, if any.

<Var> chicken <Var>

2.1.1.3 External

As a TERM, an External element is used to represent 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 represented by 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 represents a function symbol;
The optional args element contains zero or more constructs from the TERM abstract class. The order of the args sub-elements is 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 represents the slot key, and a required TERM that represents its value.

    <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.

Builtin functions. RIF-PRD specifies a subset of XPath/XQuery Functions and Operators (XPath-Functions) that any conformant RIF-PRD implementation MUST support. The RIF-PRD builtin functions are listed in the Data Type and Builtins document.

The op Const must represent a constant symbol of type rif:iri that must uniquely identify the evaluated function to be applied to the args TERMs. It can be one of the builtin functions specified for RIF-PRD, or it can be application specific. In the latter case, it is the responsibility of the producers and consumers of RIF-PRD rulesets that reference non-builtin functions to agree on their semantics.

Example 2.3.

a. The first example below shows one way to represent, 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 representation of a call to the application-specific nullary function today(), which symbol is defined in the example's namespace http://rif.examples.com/2008/jim#:

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

2.1.2 ATOMIC

The ATOMIC class is used to represent atomic truth-valued statements. RIF-PRD covers rule languages in which the truth values of atomic statements can only be "true" or "false": that is, ATOMICs represent boolean statements. Dialects extending RIF-PRD may support additional truth values.

As an abstract class, ATOMIC is not associated with specific XML markup in RIF-PRD instance documents. It is specified in the normative schema as a substitution group.

    [ Atom | Equal | Member | Subclass | Frame ]

2.1.2.1 Atom

In RIF, the Atom element is used to represent a relation (or predicate).

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 represents the predicate symbol (the name of a relation);
The optional args element contains zero or more constructs from the TERM abstract class. The order of the arg's sub-elements is 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 represents the slot key, and a required TERM that represents its value.

    <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 representation of the predicate owns(?c ?p), where the predicate symbol owns is defined in the example namespace http://rif.examples.com/2008/jim#.

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

2.1.2.2 Equal

In RIF, Equal is used to represent equality relations.

The Equal element must contain one left sub-element an done 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>

2.1.2.3 Member

In RIF, the Member element is used to represent membership relations.

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 representation 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/jim#.

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

2.1.2.4 Subclass

In RIF, the Subclass element is used to represent class inclusion relations.

The Subclass element contains unordered two 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>

2.1.2.5 Frame

In RIF, the Frame construct is used to represent relations that hold between an individual, also called an object, and the values of some its properties or attributes: that is, object-attribute-value triples.

Accordingly, a Frame element must contain:

an object element, that contains an element of the TERM abstract class, the content of which represents the individual;
zero to many slot elements, each containing a Prop element that represents an attribute-value pair as a pair of elements of the TERM abstract class, the first one that represents the name of the attribute (or property); the second that represents 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 of 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/jim#.

<Frame>
   <object> <Var> c </Var> </object>
   <slot rif:ordered="yes"> 
      <Const type="rif:iri">
         ttp://rif.examples.com/2008/jim#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).

2.1.3 FORMULA

The FORMULA class is used to represent any truth-valued statement, atomic or not, that is allowed in the condition part of a rule covered by RIF-PRD. In rule languages covered by RIF-PRD, the truth values of statements can be "true" or "false": that is, FORMULAs can only represent boolean statements.

Dialects extending RIF-PRD may support additional truth values.

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

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

2.1.3.1 ATOMIC

A FORMULA can be a single ATOMIC statement. See specification of ATOMIC, above.

2.1.3.2 External

In RIF-PRD, an External represents an externally specified predicate when it is a FORMULA (as opposed to a TERM; that is, in particular, when it appears in a place where a FORMULA is required, and not a TERM).

The External element contains one content element that contains one Atom element:

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

Builtin predicates. RIF-PRD specifies a subset of XPath/XQuery Functions and Operators (XPath-Functions) that any conformant RIF-PRD implementation MUST support. The RIF-PRD builtin predicates are listed in the Data Types and Builtins document.

The op Const in the Atom element must be a symbol of type rif:iri that must uniquely identify the evaluated predicate to be applied to the args TERMs. It can be one of the builtin predicates specified for RIF-PRD, 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 representation of a boolean expression that tests whether the value denoted by variable ?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>

2.1.3.3 And

A FORMULA can represent the conjunction of zero of more statements, each of them represented by a FORMULA. This is represented by the And construct.

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

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

2.1.3.4 Or

A FORMULA can represent the disjunction of zero of more statements, each of them represented by a FORMULA. This is represented by the Or construct.

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

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

2.1.3.5 NmNot

A FORMULA can represent the non-monotonic negation of a statement, itself represented by a FORMULA: this is represenetd by the NmNot construct.

The NnNot element contains exactly one formula element. The formula element contains an element of the FORMULA group, that represents 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.

2.1.3.6 Exists

In RIF, the Exists construct is used to represent an existentially quantified FORMULA.

The Exists element contains:

one or more declare sub-elements, each containing a Var element that represents one of the existentially quantified variables;
exactly one required formula sub-element that contains an element from the FORMULA abstract class: the FORMULA represents 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 representation 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 represented by a Frame as in example 2.6, and greater than 8, as represented by 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/jim#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>

2.2 Actions

This section specifies the XML syntax that is used to serialize, in RIF-PRD, what can appear in the action part of a rule supported by RIF-PRD.

RIF-PRD defines one single abstract class for actions, ACTION, that is realized by:

the ASSERT action, which is concretely represented by the Atom or the Frame to be asserted;
the concrete Retract construct, which is associated with an Atom or a Frame that represents the target of the action.

The following sections specify each construct separately, grouped by abstract syntactic classes.

Editor's Note: This section is still under discussion in the working group (see ISSUE-62). The working group considers adding an Assign action to represent the modification of the value of an attribute in a fact represented by a Frame, and an Execute action to represent the execution of an arbitrary, externally specified procedure. The working group seeks feedback regarding the proposed syntax for the currently specified actions, as well as regarding which constructs for serializing individual actions should be supported by RIF-PRD and/or required from RIF-PRD implementations.

2.2.1 ACTION

The ACTION class of constructs is used to represent the individual actions in the action part of a production rule represented in RIF-PRD.

This version of RIF-PRD covers two ACTIONs: ASSERT and Retract.

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

    [ ASSERT | Retract    ]

2.2.1.1 ASSERT

An ASSERT construct is used to represent actions that result in asserting an atomic statement.

In this version of the draft, only the ASSERTion of an Atom or of a Frame is covered by RIF-PRD.

For compatibility with RIF-BLD, ASSERT is not associated with specific XML markup in RIF-PRD instance documents, and it is represented only as the target Atom or Frame.

    [ Atom | Frame ]

Editor's Note: The working group seeks feedback regarding whether a specific XML element, Assert, modeled after the Retract element, below, should be used to serialize assertions, instead, to the price of reducing the interoperability with RIF-BLD.

2.2.1.2 Retract

The Retract construct is used to represent actions that result in negating an atomic statement.

In this version of the draft, only the Retraction of an Atom or of a Frame is covered by RIF-PRD.

The Retract element has one target sub-element that contains an Atom or a Frame construct that represents the atomic statement to be removed on implementing the action.

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

Example 2.9. 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/jim#owns
            </Const>
         </op>
         <args rif:ordered="yes">
            <Var> c </Var>
            <Var> p </Var>
         </args>
      </Atom>
   </target>
</Retract>

2.3 Production Rules

This section specifies the RIF-PRD constructs that are required, in addition to the ones specified in the sections on Conditions and Actions, to serialize, and interchange, complete production rules and rule sets.

The RULE construct is an abstract class: in RIF-PRD instance documents, it is either visible as a Implies, as a Forall, or as a single ACTIONS:

The Implies associates one optional condition FORMULA and one non-empty ordered list of ACTIONS.
The Forall construct declares one or more Vars, and associates them with zero or more FORMULAs, as patterns that constrain the bindings of the variables, and with one RULE as the formula in its scope.

Editor's Note: This version of the draft does not specify a specific construct to serialize a ruleset in RIF-PRD: the generic Group construct can be used for that purpose - as specified in the next section, Groupings and metadata. Future versions of this draft may specify a specific-purpose construct, especially if semantically significant information has to be associated to rulesets (e.g. parameters etc). The working group seeks feedback on this (see also ISSUE-63).

The following sections specify each construct separately, grouped by abstract syntactic classes.

2.3.1 RULE

In RIF-PRD, the RULE class of constructs is used to represent rules.

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

    [ Implies | Forall | ACTION ]

2.3.1.1 Implies

The Implies construct is used to represent the conditional statement (that is, the "if-then", or condition-conclusion, or antecedent-consequent pair) that is at the core of a rule.

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 represents 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.

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

2.3.1.2 Forall

The Forall construct is used to represent universally quantified rules.

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 that represents a constraint on the bindings of one of the Vars that are declared by the Forall;
exactly one formula sub-element that represents the formula in the scope of the quantifier 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/jim#owns
                     </Const>
                     <Args rif:ordered="yes">
                        <Var>chicken</Var>
                        <Var>potato</Var>
                     </Args>
                  </Atom>
               </content>
            </External>
         </pattern>
         <formula>
            ...
         </formula>
      </Forall>
   </formula>
</Forall>

2.4 Grouping and metadata

This section specifies the additional constructs that are needed to build a complete instance RIF-PRD document, to group rules into rulesets, and to serialize the metadata that is possibly associated with elements of a rule, a group of rules or a RIF-PRD instance document.

2.4.1 Group

The Group construct is used to represent groups of rules. In RIF-PRD, it is used to serialize rulesets, but it can be used more generally.

The Group element has zero or more sentence sub-elements that contain each another Group element or an element of the abstract RULE class of constructs.

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

2.4.2 Document

The Document is the top level construct in a RIF-PRD instance document.

The Document contains zero or one payload sub-element, that must contain a Group element.

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

2.4.3 Metadata

Metadata can be associated with any construct that represents a concrete class element in RIF-PRD: those are the elements with a CamelCase tagname starting with an upper-case character:

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

An identifier can be associated to any construct of the abstract CLASSELT class of constructs, as an optional id sub-element that MUST contain a Const of type rif:local or rif:iri.

Metadata can be included in any instance of a concrete class element using the meta sub-element.

The RIF-PRD Frame construct is used to serialize metadata: the content of the Frame's object sub-element identifies the object to which the metadata is associated:, and the Frame's slots represent the metadata properly said as property-value pairs.

If the all the metadata is related to the same object, the meta element can contain a single Frame sub-element. If metadata related to several different objects need be serialized, the meta role can contain an And with zero or more formula sub-elements, each containing one Frameelement.

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

Notice that the content of the meta sub-element of an instance of a RIF-PRD class element is not necessarily associated to that same instance element: only the content of the object sub-element of the Frame that represents the metadata specifies what the metadata is about, not where it is included in the instance RIF document.

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

2.5 Presentation syntax

This section specifies a presentation syntax for RIF-PRD. The presentation syntax is not normative: its main purpose is to help make the normative specification of the semantics easier to read.

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:

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

It is intended that the syntax and semantics of RIF-BLD and RIF-PRD are the same when the rule conclusion contains a single Atom or Frame, 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+ ('(' FORMULA '))* '(' RULE ')') | CLAUSE
! CLAUSE    ::= Implies | ACTION
! Implies   ::= IRIMETA? (ACTION | 'Do' '(' ACTION* ')') ':-' FORMULA
  IRIMETA   ::= '(*' Const? (Frame | 'And' '(' Frame* ')')? '*)'
  IRI       ::= UNICODESTRING
  Profile   ::= UNICODESTRING

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

  ACTION    ::= ASSERT | Retract 
  ASSERT    ::= Atom | Frame
  Retract   ::= 'Retract' '(' Atom | Frame ')'

3 Operational semantics

3.1 Introduction

For the purpose of specifying the semantics of a RIF-PRD RuleSet, 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;
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 configuration c to the configuration c' or, more appropriately in the case of a PRS, the execution of action a in the configuration c causes a transition to configuration c' . We note: c + a → c' or c ^a→ c';
T ⊆ C is the set of final configurations, that is, the set of all the configurations 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 configurations).

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 configuration and stops. The result is the set of facts w_n when the system stops.

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

Jim (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;
Jim 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, Jim's CMP rule:

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

When the rule is applied to w₀:

the first 3 conjuncts select {Jim/?chicken, Jack/?chicken, Julia/?chicken} as possible values for variable ?chicken (Joe is too young);
conjuncts 4-7 select {(Jim/?chicken, BigPotato/?potato)} as the only possible substitution for the variables ?chicken and ?potato (UglyPotato does not belong to either Jim, 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, Jim 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 Jim is now 11;
Jim does not own a potato anymore.

The resulting set of facts w₁ is thus:

Jim (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 {Jim/?chicken, Jack/?chicken, Julia/?chicken} as possible values for variable ?chicken, but the jim: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 configuration, stops.

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

3.2 Definitions and notation

Let Const be the set of constant symbols that can be represented in RIF-PRD, as determined by the the specification of the Const construct; Var, the set of variable symbols that can be represented in RIF-PRD, as determined by the specification of the Var construct; and Term the set of terms that can be represented in RIF-PRD, as determined by the the specification of the TERM class of constructs. A substitution is defined as follows (e.g. HAK07):

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=1..n where Dom(σ) = {x_i}_i=1..n and σ(x_i) = t_i for i = 1 to n.

Given X, a set of variables, and σ, a substitution such that X ⊆ Dom(σ), σ_X denotes, in this document, the restriction of σ to the variables in X: σ_X = {σ(x)/x | x ∈ X}.

Let Term_Σ be the set of ground terms (that can be represented in RIF-PRD), defined as follows:

if c ∈ Const, then c ∈ Term_Σ;
if f ∈ Const is the symbol of an externally specified function and t_i ∈ Term_Σ for i = 1..n, then External(f(t₁ ... t_n)) ∈ Term_Σ.

Definition (ground substitution): A ground substitution is a substitution σ such that ∀ x ∈ Dom(σ), σ(x) ∈ Term_Σ.

The function Var(e) that maps a RIF-PRD element e to the set of its free or universally quantified variables is defined as follows:

if e ∈ Const, then Var(e) = {};
if e ∈ Var, then Var(e) = {e};
if p ∈ Term and arg_i ∈ Term, for i = 0..n, then, Var(p(arg_i) = Var(p) ∪_i=0..n Var(arg_i);
if p ∈ Term and arg_i ∈ Term, for i = 0..n, then, Var(External(p(arg_i)) = Var(p) ∪_i=0..n Var(arg_i);
if t₁ ∈ Term and t₂ ∈ Term, then Var(t₁ [=|#|##] t₂) = Var(t₁) ∪ Var(t₂);
if o ∈ Term, k_i ∈ Term for i = 1..n, and v_i ∈ Term for i = 1..n, then Var(o[k₁->v₁ ... k_n->v_n]) = Var(o) ∪_i=1..n Var(k_i) ∪_i=1..n Var(v_i);
if f_i are RIF-PRD FORMULAs for i = 0..n, then Var([AND|OR|NOT](f_i)) = ∪_i=0..n Var(f_i);
if f is a RIF-PRD FORMULA and x_i ∈ Var for i = 1..n, then, Var(Exists x₁ .. x_n (f)) = Var(f) - {x_i}.
if a is a RIF-PRD ATOMIC, then Var([ASSERT|RETRACT](a)) = Var(a);
if f is a RIF-PRD FORMULA and a_i, i = 1..n are RIF-PRD ACTIONs, then Var(IF f THEN a₁ ... a_n) = Var(f) ∪_i=1..n Var(a_i);
if r is a RIF-PRD RULE, x_i ∈ Var for i = 1..n, and p_j, j = 0..m, are RIF-PRD FORMULAs, then Var(Forall x₁ ... x_n SUCH THAT p_j (r)) = Var(r) ∪_j=1..m Var(p_j);
if r_i, i = 0..n, are RIF-PRD RULEs, then Var(RULESET(r_i)) = ∪_i=1..n Var(r_i).

Definition (rule instance): An instance of a rule r is a pair (r^id, σ), where r^id uniquely identifies r and σ is a ground substitution such that Var(r) ⊆ Dom(σ). Given a rule r, id(r) denotes r^id, the unique identifier of r; given a rule instance ri = (r^id, σ), rule(ri) denotes the rule that is uniquely identified by r^id.

Definition (ruleset instance): 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 all the rules in RS.

Let W be the set of ground formulas that can be represented in RIF-PRD, defined as follows:

if p ∈ Const is the symbol of an externally specified predicate and t_i ∈ Term_Σ for i = 1..n, then External(p(t₁ ... t_n)) ∈ W;
if p ∈ Const is neither the symbol of an externally specified predicate nor the symbol of an externally specified function, and t_i ∈ Term_Σ for i = 1..n, then p(t₁ ... t_n) ∈ W</sub>;
if t₁ ∈ Term_Σ and t₂ ∈ Term_Σ, then t₁ = t₂ ∈ W;
if t₁ ∈ Term_Σ and t₂ ∈ Term_Σ, then t₁ # t₂ ∈ W;
if t₁ ∈ Term_Σ and t₂ ∈ Term_Σ, then t₁ ## t₂ ∈ W;
if o ∈ Term_Σ, k_i ∈ Term_Σ for i = 1..n, and v_i ∈ Term_Σ for i = 1..n, then o[k₁->v₁ ... k_n->v_n] ∈ W;
if f_i ∈ W for i = 1..n, then AND(f₁ ... f_n) and OR(f₁ ... f_n) are ground formulas;
if f ∈ W, then NOT(f) ∈ W;
if f ∈ W and x_i ∈ Var for i = 1..n, then, ∀ n ≥ 1, Exists x₁ .. x_n (f) ∈ W. By convention, a ground formula Exists x₁ .. x_n (f) is always replaced by the semantically equivalent ground formula f.

Let L be the set of the atomic ground actions that can be represented in RIF-PRD:

if a ∈ W is a ground ATOMIC , then ASSERT(a) ∈ L and RETRACT(a) ∈ L.

Editor's Note: The definition of L is subject to change as the ACTION constructs are still under discussion.

Finally, let R be the set of all the rules that can be represented in RIF-PRD.

In this document, given a set X, P(X) denotes the power set of X, and S(X) denotes the set of the ordered lists of elements of X.

Given an expression f and a set of ground instances w, Eval(f, w) denotes the set of ground formulae that results of evaluating f in the context of w. The expression, f, is evaluated as a black-box: any side-effect of the evaluation, on w or otherwise, depends only on the specification of the semantics of f.

3.3 Operational semantics of actions

Editor's Note: The operational semantics of actions in RIF-PRD is still under discussion (see ISSUE-66). It will evolve as the semantics to be associated with the actions that are already specified is refined, in particular with respect to the creation and delation of objects; and as new ACTION constructs are added. The working group seeks feedback regarding what operational semantics would be most usefully associated with RIF-PRD ACTION constructs.

Let The transition relation →_{_RIF-PRD} ⊆ P(W) × L × P(W) is defined as follows:

∀ w ⊆ P(W), w + ASSERT(f) →_{_RIF-PRD} w' = w ∪ {f};
∀ w ⊆ P(W), w + RETRACT(f) →_{_RIF-PRD} w' = w\f;

Rule 1 specifies that the Assert construct should be used when the intended action is to add a fact to a set of ground facts w. Rule 2 specifies that the Retract construct should be used when the intended action is to remove a fact from w, instead.

The intended semantics of the actions that can be represented in RIF-PRD is completely specified by the definition of the labelled transition system {P(W), L, →_{_RIF-PRD}}.

The relation →^*_{_RIF-PRD} ⊆ P(W) × S(L) × P(W) denote the transitive closure of the transition relation →_{_RIF-PRD}.

3.4 Operational semantics of rule sets

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

The idea is that a configuration, c, is made of a set, w, of ground FORMULAe that represent a state of facts; the set, ri_c, of all the instances of the rules in the considered ruleset RS that are satisfied, in some sense to be further specified, in that state of fact; and a set, h of rule instances that represent a part of the history of the system, in that it collects the rule instances that determined some of the actions that led to the present configuration, and that have been satisfied, in the same sense as before, in all the states of facts that have been traversed since. In the same way, the order among the rule instances, in ri_c, represents another part of the system's history: the longer a rule instance has been continuously satisfied by the states of facts of the traversed configurations, in terms of number of configurations, the farther it is in the ordering. These elements of the history of the system are relevant when selecting the next transition.

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: C_RS × S({priority, recency, all}) → P(Inst(R)), that, given a configuration, c, and a selection strategy, returns the ordered subset, ori ⊆ instance(c), selected according to the input strategy, 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 configuration;
FINAL: C_RS × P(R) → {true, false}, that, given a configuration and a set of rules, returns true or false, depending on whether or not the configuration is terminal.

Let mergeInstances: S(Inst(R)) × P(Inst(R)) → S(Inst(R)), be a helper function that, given an ordered set of rule instances, ori, and an unordered set of rule instances, ri, returns ri, ordered in such a way that the order of ori is preserved among all the rule instances in ri ∩ ori, and the rule instances in ri - ori come first in the order.

Let extractActions: S(Inst(R)) → S(L), be another 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.

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

C_RS is the set of configurations;
S(L) is the set of labels;
The transition relation →_{_RS} ⊆ C_RS × S(L) × C_RS, is defined as follows:
∀ (c, s, c' ) ∈ C_RS × S(L) × C_RS, (c, s, c' ) ∈ →_{_RS} if and only if all of the following hold:
1. s = extractACTIONS(PICK(c, LS))
2. and (facts(c), s, facts(c')) ∈ →^*_{_RIF-PRD}
3. and instance(c') = mergeInstances(instance(c), INSTANTIATE(w, RS))
4. and history(c') = (history(c) ∩ instance(c)) ∪ PICK(c, LS)
5. and c ∉ T_RS
A configuration c is final iff FINAL(c, RS) = true: T_RS = {c ∈ C_RS | FINAL(c, RS) = true}.

Intuitively, the conditions 1 in the definition of the transition relation →_{_RS} guarantees that only the specification of the function PICK and the selection strategy determine which are the allowed transition paths out of a given configuration, and condition 2 guarantees that all transitions are compliant with the semantics of the individual actions, as specified the relation →_{_RIF-PRD}. Condition 3 guarantees that the instance component of any reachable configuration contains all the instances of the rules in RS that are satisfied in the configuration's state of facts, ordered in the appropriate way. Condition 4 means that the systems keeps a memory of the rule instances which action part has been executed, and that have been been part of the instances returned by INSTANTIATE in all the configurations that have been since traversed. And condition 5 guarantees that the system halts as soon as it encounters a terminal configuration.

The input function is defined as:
Eval(RS, w) →_{_RS} (w, INSTANTIATE(w, RS), ∅) ∈ C_RS The output function is defined as:
(w', ri_w', h) ∈ T_RS →_{_RS} w'

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

Eval(RS, w) →^*_{_RS} w'

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

3.4.1 Rules instantiation: INSTANTIATE

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).

Indeed, the function is most easily specified using the widely spread notion of pattern matching. The following definition is adapted from CIR04.

Definition (pattern matching): Given a set w ⊆ W of ground RIF-PRD ATOMICs and a RIF-PRD FORMULA p, p is said to match w with respect to a theory τ and a ground substitution σ, denoted σ(p) «_τ w, iff one of the following is true:

p is a RIF-PRD ATOMIC and ∃ f ∈ w such that σ(p) =_τ f (read: σ(p) is identical to f modulo τ);
p is a RIF-PRD External and σ(p) evaluates to true;
p is a RIF-PRD And that contains no conjunct, that is, p = AND();
p = AND(p₁ ... p_n), i = 1..n, and ∀ p_i, σ(p_i) «_τ w;
p = OR(p₁ ... p_n), i = 1..n, and ∃ p_i such that σ(p_i) «_τ w;
p = NOT(p') and σ(p') does not match w with respect to τ;
p = Exists {x_i} p' , where {x_i}, i = 1..n, denotes the set of the variables that are existentially quantified in p, and there is a substitution θ with {x_i} ⊆ Dom(θ), Dom(σ) ⊆ Dom(θ) and ∀ y ∈ Var(p') - {x_i}, θ(y) = σ(y), such that θ(p') «_τ w.

A set P of RIF-PRD FORMULAe is said to match a set w ∈ W of ground RIF-PRD ATOMICs with respect to a theory τ and a ground substitution σ, denoted σ(P) «_τ w, iff σ(p_i) «_τ w for all p_i ∈ P.

Editor's Note: The matching theory τ to be taken into account includes the equality theory defined between frames, the builtin datatypes, functions and relations, and any externally defined datatypes, classification theory, functions and relations as required by the ruleset. A precise statement of the matching theory with respect to the data types and builtins in the RIF data types and builtins document, RIF-DTB will be added in a future version of this draft. It will be precised further when references to application-specific data models and externals is specified.

Example 3.2. TBD

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 a set, ir ⊆ Inst(R), of instances of r.

The evaluation of InstantiateRULE(w, r) is specified based on a terminal transition system where:

A configuration is a quintuple (w, r, σ, Σ, acc), where w ⊆ W, r ∈ R, σ is either either the empty set, or a substitution such that Var(r) ∈ Dom(σ), Σ is a set of substitutions such that σ ∈ Σ or σ = ∅, and acc is a pair (id, Σ'), where id is the unique identifier of a rule, and Σ' is a set of substitutions;
The transition relation is defined by the following rules:
1. if σ ∈ Σ:
  (w, r, ∅, Σ, acc) → (w, r, σ, Σ - σ, acc)
2. if σ ∈ Σ and either σ(P) «_τ w, or P is empty:
  (w, Forall {x_i} P (r), σ, Σ, acc) → (w, r, σ, Σ, acc)
3. if σ ∈ Σ and ¬(σ(P) «_τ w):
  (w, Forall {x_i} P (r), σ, Σ, (id, Σ')) → (w, rule(id), ∅, Σ, (id, Σ'))
4. if σ ∈ Σ and σ(c) «_τ w:
  (w, IF c THEN a, σ, Σ, (id, Σ')) → (w, rule(id), ∅, Σ, (id, Σ' ∪ {σ}))
5. if σ ∈ Σ and ¬(σ(c) «_τ w):
  (w, IF c THEN a, σ, Σ, (id, Σ')) → (w, rule(id), ∅, Σ, (id, Σ'))
6. (w, THEN a, σ, Σ, (id, Σ')) → (w, rule(id), ∅, Σ, (id, Σ' ∪ {σ}))
Configurations where the set Σ of candidate substitutions is empty are final: T = {(w, r, σ, ∅, acc)}.

Intuitively, a configuration is made of the set of facts, w, against which the rule is instantiated; the rule, r, to be instantiated; the substitution, σ, that is under evaluation as possibly instantiating r in such a way that its condition matches w; the set, Σ, of the candidate substitutions that are still to be evaluated, including σ; and the instances accumulator, acc, that relates the identifier, id, of the input rule, r_input, to the set of the substitutions that have been evaluated and with respect to which the condition of r_input is known to match w.

Given a rule r ∈ R, let Σ_r denote the set of the restrictions to Var(r) of all the subtitutions σ such that Var(r) ⊆ Dom(σ): Σ_r = {σ_Var(r) | ∀ σ, Var(r) ⊆ Dom(σ)}.

The input function can now be defined as:
InstantiateRULE(w, r) → (w, r, ∅, Σ_r, (id(r), ∅))

The output function is defined as:

(w, r, σ, ∅, (id, Σ')) → {(id, σ) | ∀ σ ∈ Σ'}

The role of the function InstantiateRULE is to loop through all the possible substitutions for the variables of the input rule, and to select the ones with respect to which all the pattern FORMULAe in the Foralls of r_input, if any, as well as the if FORMULA, if there is one in r_input, match w.

As a consequence, in the definition of the transition relation, the first rule represents the initialisation of the process, when a substitution σ is selected out of Σ for evaluation. The rules also guarantees that each candidate substitution is evaluated once and only once on each single path.

Rule 2 and 3 progress the instantiation through a rule's nested Forall and guarantee that any pattern formula associated with an enclosing Forall matches w with respect to the substitution under consideration (rule 2) and that σ is not further considered and rejected as soon as a pattern formula does not match w with respect to it; and that the process is re-initiated for another substitution to be evaluated.

Rule 4 and 5 guarantee that a substitution that a substitution is added to the ouput accumulator if (rule 4) and only if (rule 5) the if FORMULA matches w with respect to that substitution; and that the process is re-initiated for the evaluation of another candidate substitution.

In complement to rule 4, rule 6 handles the trivial case where the optional if FORMULA is missing, and thus considered, by convention, matching every set of facts with respect to any substitution and theory.

The input function initializes the transition system with respect to the state of facts and the rule, and the output function transforms the set of selected substitutions in the accumulator in the corresponding set of instances of the input rule.

Example 3.3. TBD

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 configuration 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))
configurations with an empty rule set component are final: T = {(w, ∅, ri)}.

The input function is defined as:

INSTANTIATE(w, RS) → (w, RS, ∅)

The output function is defined as:

(w, ∅, ri) → ri

Example 3.4. TBD

3.4.2 Instances selection: PICK

Editor's Note: This section is still under discussion (see ISSUE-64). This version of RIF-PRD specifies five elementary strategies, a way of combining them, and a default combination. Future working drafts may specify different and/or additional elementary strategies, and no or a different default. The Working Group seeks feedback on which instances selection strategies and which combinations of strategies should be supported by RIF-PRD and/or required from RIF-PRD implementations; and which strategy or combination should be the default, if any.

A rule instance determines a sequences of ground actions, by application of the associated substitution to the variables in the ACTIONs in the then component of the instantiated rule. The decision to implement the sequence of actions that a rule instance determines is often called: firing the rule instance.

Most implementations of production rule languages select the rule instances to be fired, and, therefore, the sequence of actions to be implemented, based on one or a combination of the following strategies (under these or other, idiosyncratic names; and possibly combined with additional, idiosyncratic rules):

No-repetition. The no-repetition strategy excludes from the selection of fireable rule instances, any rule instance that has already been fired, unless the instantiation environment has significantly changed since the actions have been last implemented. This is usually taken to mean that there has been at least one configuration where the state of facts did not satisfy the rule instance, in the sense determined by the specification of the INSTANTIATE function, since the rule instance has been last fired;
Priority. The rule instances are ordered by priority of the instantiated rules, and only the rule instances with the highest priority are selected. This requires that a priority be associated with the RIF-PRD representation of each rule;
Recency. the rule instances are ordered by how long a rule instance has been continuously satisfied by the states of facts of the traversed configurations, and only the most recent ones are selected.
Random. A singleton rule instance is selected at random;
All-at-once. All the rule instances are selected, and they are fired in the order's sequence.

Let fireableINSTANCES: S(Inst(R)) × P(Inst(R)) × {no-repeat, priority, recency, random, all} → S(Inst(R)) be a function that, given an ordered set, ori, of candidate rule instances, a set, h, of excluded rule instances, and a keyword, k, indicative of an single selection strategy, return a subset fri ⊆ ori, selected and ordered according to the strategy indicated by k. The keywords "no-repeat"" and "all" indicate, respectively, the no-repetition and all-at-once selection strategies, and the other keywords indicate each the strategy by the same name.

The function fireableINSTANCES is precisely specified in the next subsection.

The function PICK(c, LS) can be specified with the help of a terminal transition system where:

a configuration is a triple (LS, ori, c) ⊆ S{priority, recency, all} × S(Inst(RS)) × C_RS;
the transition relation is completely specified by the following two rules:
1. if s = "all", then (sLS', ori, c) → (∅, ori, c)
2. if s ≠ "all", then (sLS', ori, c) → (LS', fireableINSTANCES(ori, history(c), s), c)
a configurations (LS, ori, c) is final if and only if LS = ∅.

The input function is defined as:
PICK(c, RS, sLS) → (LS"random", fireableINSTANCES(instance(c), history(c), "no-repeat"), c) The output function against is defined as:
(∅, ori, c) → ori

Intuitively, the strategy for the selection of the rule instances to be fired that is intended for the set of rules represented by a RIF-PRD Ruleset, is :

starting from the ordered set returned by INSTANTIATE in the configuration, to remove the instances that were already fired, as listed in the configuration's history. That is, the no-repetition strategy is always applied first;
successive subsets of instances are selected per the sequence of selection strategies keywords associated with the Ruleset;
and, finally, a single rule instance is selected at random from the resulting subset. That is, the random strategy is always applied at the end of the selection process.

In other words, if the sequence of strategies provided with a RIF-PRD Ruleset is LR, the intended selection strategy is:
"no-repeat" LR "random" The default, when no selection strategy is explicitely indicated for a Ruleset, is, therefore:
"no-repeat" "random" The exception is the all-at-once strategy, represented in RIF-PRD by the keyword : "all". If that keyword appears anywhere in the sequence, the intended strategy is that all the rule instances that have been selected at that point be fired in sequence, in the order of the selection. That is, if the sequence of strategies provided with a RIF-PRD Ruleset is LR₁"all"LR₂, the intended selection strategy is :
"no-repeat" LR₁

3.4.2.1 fireableINSTANCES

The operational semantics of the function fireableINSTANCES depends on its third argument, the elementary selection strategy. It is therefore specified separately for each value of that parameter, that is, for each individual rule instances selection strategy supported by RIF-PRD.

Editor's Note: The precise operational semantics of the "no-repetition", "priority" and "recency" strategies are still under discussion in the working group. In addition, this working draft does not specify a way to specify the intended instance selection strategy for a RIF-PRD ruleset in a RIF document. As a consequence, only the "random" strategy is precisely specified in this version.

No-Repetition. TBD

Priority. TBD

Recency. TBD

Random. fireableINSTANCES(ori, h, "random"), where ori ∈ S(Inst(R)) and h ∈ P(Inst(R)), returns a randomly selected singleton subset of ori:
fireableINSTANCES(ori, h, "random") → {ri}, such that ri ∈ ori.

3.4.3 Halting test: FINAL

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 configuration 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 configuration, according to the semantics of INSTANTIATE, have already been fired in a configuration 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.

4 References

[CIR04]

[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/.

5 Appendix: XML Schema for RIF-PRD

TBD

6 Appendix: Compatibility with RIF-BLD

6.1 Syntactic compatibility between RIF-PRD and RIF-BLD

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.

	Presentation syntax	XML syntax
	TERM ::=
BLD	[Const \| Var \| Expr \| External]
PRD	[Const \| Var \| External]
	Const ::=
Core	'"' UNICODESTRING '"^^' SYMSPACE	<Const type=xsd:anyURI [xml:lang=xsd:language]? > Any Unicode string </Const>
	Var ::=
Core	'?' Any Unicode string	<Var> Any Unicode string </Var>
	Expr ::=
BLD	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>
PRD	Undefined except when wrapped in an External (as TERM), as follows.
	External (as TERM) ::=
Core	'External' '(' Expr ')'	<External> <content> Expr </content> </External>
	ATOMIC ::=
Core	[Atom \| Equal \| Member \| Subclass \| Frame]
	Atom ::=
Core	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>
	Equal ::=
Core	TERM = TERM	<Equal> <left> TERM </left> <right> TERM </right> </Equal>
	Member ::=
Core	TERM # TERM		<Member> <instance> TERM </instance> <class> TERM </class> </Member>
	Subclass ::=
Core	TERM ## TERM	<Subclass> <sub> TERM </sub> <super> TERM </super> </Subclass>
	Frame ::=
Core	TERM ' [ ' (TERM ' -> ' TERM)* ' ] '	<Frame> <object> TERM </object> <slot rif:ordered="yes"> TERM TERM </slot>* </Frame>
	FORMULA ::=
BLD	[ATOMIC \| External \| And \| Or \| Exists]
PRD	[ATOMIC \| External \| And \| Or \| NmNot \| Exists]
	External (as FORMULA) ::=
Core	'External '(' [Atom \| Frame] ')'	<External> <content> [ Atom \| Frame ] </content> </External>
	And ::=
Core	'And' '(' FORMULA* ')'	<And> <formula> FORMULA </formula>* </And>
	Or ::=
Core	'Or' '(' FORMULA* ')'	<Or> <formula> FORMULA </formula>* </Or>
	NmNot ::=
BLD	Undefined
PRD	'Not' '(' FORMULA ')'	<NmNot> <formula> FORMULA </formula> </NmNot>
	Exists ::=
Core	'Exists' Var+ '(' FORMULA ')'	<Exists> <declare> Var </declare>+ <formula> FORMULA </formula> </Exists>
	ACTION ::=
BLD	Undefined
PRD	[ ASSERT \| Retract ]
	ASSERT ::=
BLD	Undefined
PRD	[ Atom \| Frame ]
	Retract ::=
BLD	Undefined
PRD	'Retract' '(' Atom \| Frame ' ) '	<Retract> <target> [ Atom \| Frame ] </target> </Retract>
	RULE ::=
BLD	[ Forall \| Implies \| ATOMIC ]
PRD	[ Forall \| Implies \| ACTION ]
	Forall ::=
BLD	' Forall ' Var+ ' ( ' [Implies \| ATOMIC] ' ) '	<Forall> <declare> Var </declare>+ <formula> [Implies \| ATOMIC ] </formula> </Forall>
PRD	' Forall ' Var+ (' ( ' FORMULA ' ) ')* ' ( ' RULE ' ) '	<Forall> <declare> Var </declare>+ <pattern> FORMULA </pattern>* <formula> RULE </formula> </Forall>
	Implies ::=
BLD	(ATOMIC \| 'And' '(' ATOMIC* ')') ':-' FORMULA	<Implies> <if> FORMULA </if> <then> [ ATOMIC \| <And> <formula> ATOMIC </formula>* </And> ] </then> </Implies>
PRD	(ACTION \| 'Do' '(' ACTION* ')') ':-' FORMULA	<Implies> <if> FORMULA </if> <then> ACTION ACTION* </then> </Implies>
	Group ::=
Core	METADATA? 'Group' '(' ([RULE \| Group])* ')'	<Group> <sentence> [ RULE \| Group ] </sentence>* </Group>
	Import ::=
BLD	'Import' '(' IRI Profile? ')'	<Import> <location>lAny Unicode string</location> <profile><Profile>Any Unicode String₁</Profile></profile> </Import>
PRD	Undefined in this version of the draft
	Document ::=
BLD	METADATA? 'Document' '(' [Import \| Prefix \| Base]* Group? ')'	<Document> <directive> [ Import \| Prefix \| Base]* </directive> <payload> Group </payload>? </Document>
PRD	METADATA? 'Document' '(' Group? ')'	<Document> <payload> Group </payload>? </Document>
	METADATA ::=
Core	'(' Const? (Frame \| 'And' '(' Frame ')')? '*)'	<AnyClassTag> <id> Const </declare>? <meta> [ Frame \| <And> <formula> Frame </formula> </And> ] </meta>? other content of AnyClassTag </AnyClassTag>

6.2 Semantic compatibility between RIF-PRD and RIF-BLD

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

7 Appendix: UML-like diagram of RIF-PRD syntax

The picture below represents the complete syntax of RIF-PRD, according to this version of the draft, except for the Metadata construct, which is omitted for readibility's sake.

UML-like diagram of the syntax of RIF-PRD (the Metadata construct is omitted for readibility reasons)

RIF Production Rule Dialect

W3C Editor's Draft 30 July 2008

Abstract

Status of this Document

May Be Superseded

Set of Documents

Document Evolution

Please Comment By 2008-09-19

No Endorsement

Patents

Contents

1 Overview

1.1 Introduction

1.2 Notational conventions

1.2.1 Namespaces

1.2.2 BNF pseudo-schemas

1.2.3 Syntactic components

1.3 Running example

2 Syntax

2.1 Conditions

2.1.1 TERM

2.1.1.1 Const

2.1.1.2 Var

2.1.1.3 External

2.1.2 ATOMIC

2.1.2.1 Atom

2.1.2.2 Equal

2.1.2.3 Member

2.1.2.4 Subclass

2.1.2.5 Frame

2.1.3 FORMULA

2.1.3.1 ATOMIC

2.1.3.2 External

2.1.3.3 And

2.1.3.4 Or

2.1.3.5 NmNot

2.1.3.6 Exists

2.2 Actions

2.2.1 ACTION

2.2.1.1 ASSERT

2.2.1.2 Retract

2.3 Production Rules

2.3.1 RULE

2.3.1.1 Implies

2.3.1.2 Forall

2.4 Grouping and metadata

2.4.1 Group

2.4.2 Document

2.4.3 Metadata

2.5 Presentation syntax

3 Operational semantics

3.1 Introduction

3.2 Definitions and notation

3.3 Operational semantics of actions

3.4 Operational semantics of rule sets

3.4.1 Rules instantiation: INSTANTIATE

3.4.2 Instances selection: PICK

3.4.2.1 fireableINSTANCES

3.4.3 Halting test: FINAL

4 References

5 Appendix: XML Schema for RIF-PRD

6 Appendix: Compatibility with RIF-BLD

6.1 Syntactic compatibility between RIF-PRD and RIF-BLD

6.2 Semantic compatibility between RIF-PRD and RIF-BLD

7 Appendix: UML-like diagram of RIF-PRD syntax