• Rulesystem Arrangement Framework

The RIF Rulesystems Arrangement Framework (RIFRAF) is a classification framework for rulesystems to be included in the interchange scope of RIF. The purpose of the framework is to provide enough discriminants to classify a wide variety of rule language features into a common core and a small number of dialects. To keep the number of dialects small, it is likely that some of the discriminants will identify language features that are not supported in any dialect, and conversely that some rule languages will not support all features in any dialect. Another purpose of RIFRAF is to provide a common vocabulary to describe the language features in these dialects, and a mapping between similar concepts in the dialects.

For the curious or non-native speakers, see: http://dictionary.reference.com/search?q=riffraff (note in particular the etymology).

For WG members, there is a Questionnaire for populating the RIFRAF with actual systems. The results will be collected and published here.

Moved elsewhere: RuleLanguageDialects, OriginalRIFRAFDiscriminators, List of Rule Systems

Expressive Discriminators

Expressive Discriminators (or Dimensions) are collected here into five groups:

Purely-Syntactic, Syntactic-entailing-Semantic, Semantic, Pragmatic Discriminators, and Discriminators for Event-Condition-Action (ECA) Rules.

Values of Semantic and Pragmatic Discriminators, stated by Rulebase authors or found by Static Analysis, can of course still be marked up syntactically, e.g. via Semantic/Pragmatic (XML) Attributes on Rulebases, Rules, ..., via (RDF) metadata annotations, etc. In each group, Discriminators, and possibly subgroups of Discriminators, are listed (cf. rdf:subPropertyOf). The numberings of the Discriminators do not reflect priority orderings but are there for ease of reference such as "Syn 1.2" for the Range-restrictedness Discriminator (however, new subgroups may emerge from subsequences of neighbouring Discriminators).

1 Syn: Syntactic Discriminators

• 1.1 Restricted vs. Unrestricted Use of Logic Variables

  • 1.1.1 Single-occurrence variables (no implicit variable equality) vs. Multiple-occurrence variables (implicit variable equality). Does a rule use a variable that occurs repeatedly across its head and body? If a variable occurs only once, its name is not needed for co-reference, hence it can be replaced by an 'anonymous' variable (often written as a stand-alone "?" to enhance readability); e.g., the single-occurrence p(?x,?y,?z) :- q(?w) can be transformed into the anonymized p(?,?,?) :- q(?). If an equality predicate is available, the implicit variable equality tests of multiply occurring variables can be made explicit via explicit tests in a constraint-call extension to the body (separated from the body by an "&" infix); e.g., using an '=' predicate, the multiple-occurrence p(?x,?y,?x) :- q(?y) can be transformed into the single-occurrence p(?x1,?y1,?x2) :- q(?y2) & ?x1=?x2, ?y1=?y2 (the constraint-call repetitions of all four variables are not counted in this definition of "single-occurrence").

    • Multiple variable occurrences per predicate allowed
    • Only single occurrence of variables per predicate
    • Equality test predicate available

    1.1.2 Range-restricted Rules (No Head-Only Variables) vs. non-Range-restricted Rules. Is your rules language range-restricted in the sense that variables which occur in the head or consequence always need to appear the body (condition)? If additionally, the body occurrence must be positive, this condition is also called "safety" sometimes.

    • Head-only variables allowed
    • Head variables must occur in any form in the body/contition
    • Head variables must occur positively in the body/contition (safety)

  1.2 Predicate Variables Permitted vs. Not Permitted

  • Does your language allow predicate variables? Second-Order Syntactic Sugar allowing variables in predicate positions of queries or rule bodies and possibly rule heads (further generalized to function and even atom positions in http://www.w3.org/Submission/SWSF-SWSL/#swsl-rules-hilog), if yes, specify.

  1.3 Monotonic Lloyd-Topor Extensions Allowed vs. not Allowed

  • Does your language allow syntactic Sugar for extending Horn Logic with disjunction in rule bodies as well as conjunction and classical implication in rule heads? See http://www.w3.org/Submission/SWSF-SWSL/#swsl-rules-mon-lt. If yes, specify which.

  1.4 Explicit vs. Implicit Rule Scope

  • Does your language allow formulas and/or names denoting what has been called Modules, Contexts, Rulesets, or Models? See e.g. http://www.isi.edu/~argos/matthew/triple_by_example.html. If yes, specify how.

  1.5 Slotted (Keyed, Role-Named) vs. Positional Arguments

  • Does your language allow n-ary atoms with a set of n 'attribute=value' pairs as in RDF/OWL properties, F-logic methods, and object-oriented systems? See for instace, http://www.ruleml.org/indoo. If yes, specify how.

  1.6 Webized vs. non-Webized Names

  • Does your language support URIs as OIDs for Constants, Functions, Slots, Predicates, Classes, and/or Labels? See http://www.w3.org/2000/10/swap/Primer.html Specify any restrictions.

  1.7 Means to access data in Web formats

  • Does your language have means to access data in Web formats such as HTML, XML, RDF, OWL data. Specify how, e.g. via SPAQRL queries via special query/imnport predicates, etc.
    • Means to access HTML (specify)
    • Means to access XML (specify)
    • Means to access RDF (specify)
    • Means to access OWL (specify)
    • Other specific data formats supported (specify)

2 SeS: Syntactic-entailing-Semantic Discriminators

• 2.1 Homogeneous (Body has Single Expressiveness Class) vs. Hybrid (Body has Two Expressiveness Classes) Rules

  • Are your rule bodies/conditions split into deveral parts, such as a query and a constraint part or similar?
    • Body has Single Expressiveness Class
    • Body has Two Expressiveness Classes (query part and constraint part)
    • Other (please specify)

  2.2 Fact-only (Database Tables) vs. Rule-only vs. Fact-and-Rule Bases

  • Does your language make a distinction between facts and rules?
    • Variable-free (Ground) Facts only
    • Variable-ful (Non-Ground) Facts allowed
    • No distinction between rules and data is made (Clauses)

  2.3 Function-ful (FO Horn Logic) vs. Function-free (FO Datalog)

  • 2.3.1 Function Arity/Arities

    • Does your language limit the arity of function symbols?
      • Arbitrary arity
      • Unary functions
      • Binary functions
      • Other restriction (specify)

    2.3.2 Fixed vs. Unfixed Function Nesting Depth

    • Does your language limit the nesting depth of terms?
      • Arbitrary nesting
      • constants as terms
      • function symbols of defth one (no nesting)
      • Other restriction (specify)

    2.3.3 Uninterpreted vs. Interpreted Functions

    • Does you language have interpreted function sybols? Does you language have uninterpreted function sybols?
      • Uninterpreted function symbols
      • Interpreted function symbols (specify how)

  2.4 Variable-ful (Non-Ground) vs. Variable-free (Ground) Clauses

  • Does your language allow variables at all or is it propositional? Do variables range over single rules or can they have a wider scope (global, module, etc)?
    • no variables (propositional)
    • variables scoped per rules
    • variables scoped over whole rule base (global)
    • Other (specify)

  2.5 Predicate Arity/Arities

  • Does your language limit the arity of predicate symbols?
    • Arbitrary arity
    • Unary predicates
    • Binary predicates
    • Other restriction (specify)

  2.6 Number of premises in Rules

  • Does your language limit the number of elements in the bodies/conditions?
    • One predicate/query per body/condition only
    • Arbitrary body/condition size
    • Other restriction (specify)

  2.7 Labeled (Anchored, OIDed) vs. Unlabeled Clauses

  • Does your language allow labeling of clauses and are these labels semantically relevant?
    • Rule/Clause labels allowed
    • Rule/Clause labels can be used as arguments of user predicates and/or System Predicates.
    • Rule/Clause labels in predicate arguments have semantic implications on such as for instance in SCLP's priority-giving 'overrides' predicate (specify which!)

  2.8 Certain vs. Uncertain Clauses and Atoms

  • Does your language allow qualitative/quantitative uncertainty in clauses and atoms? In any case, specify your answer.
    • Fuzzy uncertainty (specify)
    • Probabilistic uncertainty (specify)
    • Qualitative uncertainty such as default rules (specify)
    • Other (specify)

  2.9 Priority

  • 2.9.1 Numeric priorities

    • Static vs. Dynamic: Static priority does not change. It could be specified using a numeric constant, a list of rule (labels) with lesser (or greater) priority, or the position of rules within a ruleset document could be significant. Dynamic priority can change during rule execution. In either case specify.
      • You language supports static priority per rule (specify)
      • You language supports static priority per predicate (specify)
      • You language supports dynamic priority per rule (specify)
      • You language supports dynamic priority per predicate (specify)
      • Other (specify)

    2.9.2 Rule or predicate order

    • Is the priority of rules/consequences determined by rule order or order of the consequences in the rules? In any case specify, e.g. "All applicable rules are tried in priority order, or only the highest priority rule is tried."
      • You language supports priority by rule order(specify)
      • You language supports priority by order of the rule consequences per rule (specify)
      • You language allows to explicitly specify priority of rules by defining a partial order over rules. (specify)
      • Other (specify)

3 Sem: Semantic Discriminators

• 3.1 Decidability and Expressivity

  • Specify expressivity of your language by describing the class of expressible computations and/or the complexity of typical inferencing tasks. Give details in the text field below if it is not obvious what computation/inference task you refer to. Please also give more specific complexity results (e.g. hardness, membership, completeness) if available.
    • Is the rule language Turing complete?
    • Is inferencing for your language decidable?
    • Is inferencing for your language semi-decidable (in case it is not decidable)?
    • Is inferencing for your language not semi-decidable?
    • Other expressivity/decidability results (specify)

  3.2 Finite-Model vs. Infinite-Model Rulebases

  • In case your language has a defined model-theoretic semantics, are models guaranteed to be finite structures?
    • Does the language have a defined model-theoretic semantics?
    • Are models guaranteed to be finite?

  3.3 Modality allowed or not (beyond FOL)

  • Does your language have modal constructs or higher-order semantics beyond the expressivity of FOL?
    • Does your language have modal or temporal constructs? (specify)
    • Does your language have higher-order expressivity? (not only syntactical, but really beyond FOL expresivity) specify!
    • Other semantic features beyond FOL (specify)

4 Prag: Pragmatic Discriminators

• 4.1 Inference control (Remark: These questions affect implementations of your language or published algorithms.)

  • 4.1.1 Forward chaining vs. backward chaining

    • No chaining (only 'one-shot' rules) vs. forward chaining vs. backward chaining vs. bidirectional chaining. In any case, specify birefly the concept of the algorithm or pointers to evaluate rules in your implementation.
      • Is the implementation of your language based on forward-chaining?
      • Is the implementation of your language based on backward-chaining?
      • Is the implementation of your language based on another procedural semantics?

    4.1.2 Incremental vs. exhaustive

    • Incremental (one solution at a time) vs. exhaustive (all solutions at once). Does your implementation provide sets of solutions or does it produce one solution at a time in an incremental fashion?
      • one solution at a time
      • all solutions at once
      • other (specify)

  4.2 Complexity of the algorithm

  • Computational complexity (the complexity class of the inference procedures; generally this is the worst-case complexity, however most algorithms can be optimized for certain cases; rule systems can be classified by their complexity classes)

  4.3 Interoperability

  • Many rule languages actually describe a family of languages under different semantics and/or syntactic subsets. If your language falls under this category supports several variants dialects, does it support annotations of these variants, syntactic subsets, or semantic variants?

    4.3.1 Annotations of variant

    • Does your language allow the annotation of a ruleset with a syntactic/variant, intended semantics using controlled English. Specify your answer, if applicable.
      • no annotations of ruleset syntactic variant and or intended semantics.
      • extensible annotations, controlled English, referring to an ontology, etc.
      • annotation by fixed language keywords
      • other annotation (specify)

    4.3.2 Mappings

    • Are there mappings specified between the syntactic/semantic variants of your language? Specify your answers if there exist such mappings.
      • the language has no different variants
      • there are different variants, but these are semantically incompatible
      • there are different syntactic variants, and there exist lossless translations between these variants.
      • there are syntactic variants with semantic mismatches, but there exist incomplete mappings.

5 ECA: Discriminators for Event-Condition-Action (ECA) Rules

• This section contains discriminators which particularly apply to Event-Condition-Action Rules. Note that, for such rules, also the discriminators of the previous sections may apply where 'action' may be viewed synonymously with 'head' and 'condition' may be viewed synonymously with 'body'.

  5.1 General

  • 5.1.1 Does the language offer support for programming reactive behaviour (automatically react to situations of interest)? The subsequent questions in this questionnaire only need to be answered in case this one is answered positively

    5.1.2 Are the different parts of a rule(e.g. Event, Condition, Action parts for a ECA rule) clearly separated (separation of concerns)?

    5.1.3 Is language coherency one of the design principles followed during the language's development (meaning that same paradigms are used for all components of a rule, same language for all components of a rule)?

  5.2 Events

  • 5.2.1 Which is the conflict resolution strategy used for rules (in case that the occurrence of an event triggers more than one rule)?

    • non-determinstic: all rules fire
    • non-deterministic: one rule fires
    • deterministic: priority-based selection of rules (Please specify!)
    • other approach (Please specify!)

    5.2.2 Are the event specifications (which express classes of events to react to) implicit (conditions only on the state of the data, as is the case for production rules) or explicit (conditions on events changing the state, as is the case for ECA rules)?

    • Implicit
    • Explicit
    • Other/Mixed (Please specify!)

    5.2.3 Does the language support only atomic events or also composite events (combinations of more than one event such as temporal or sequence)? Only needs to be answered if "expicit" was chosen for question 5.2.2

    • Only atomic events
    • Composite events (Please specify!)

    5.2.4 Can variables be used in event specifications (so as to select data from events that have occurred)? Only needs to be answered if "expicit" was chosen for question 5.2.2

    5.2.5 Can event specifications also refer to events that have occurred in the past (i.e. before the event specification has been registered) or are they forward-looking? Only needs to be answered if "expicit" was chosen for question 5.2.2

    • Forward-looking
    • May refer also to the past (Please specify, how!)

    5.2.6 Does the language support internal and/or external events (i.e. events that occur at remote nodes/entities)? Only needs to be answered if "expicit" was chosen for question 5.2.2

    • Internal events
    • External events

    5.2.7 Which type of event specification is used in the language? Only needs to be answered if "expicit" was chosen for question 5.2.2

    • Algebraic
    • Linear temporal logic
    • Event calculus
    • Other (Please specify!)

    5.2.8 Which is the approach to event consumption used in the language (consumption for a single rule)? Only needs to be answered if "expicit" was chosen for question 5.2.2

    • Events are consumed (events are used once in an event specification)
    • Events are not consumed (same event can be used to match different parts of an event specification)
    • Different modes are provided for event consumption so as to use the approach suitable for the chosen application

  5.3 Conditions

  • 5.3.1 Does the language support conditions on variables that occur in event specifications? Only needs to be answered if "yes" was chosen for question 5.2.3

    5.3.2 It is possible to express conditions on the state before/after/throughout the change?

    • After the change
    • Before the change
    • Throughout the change (intermediate state constriants)
    • Other (Please Sspecify!)
  5.4 Actions

  • 5.4.1 Which types of actions are supported?

    • updates to data
    • updates to rule base (e.g activating or deactivating rules. inserting or deleting rules)
    • raising and sending events
    • procedural attachements (please specify, e.g. Web service calls)
    • control of transactions (e.g commit, abort)
    • Other (Please Sspecify!)

    5.4.2 Does the language support internal and/or external actions (e.g raising and sending events to external entities)?

    • internal actions
    • external actions

    5.4.3 Does the language support the execution of complex actions such as sequences (or even more complex workflows) of updates on data specified in a rule?

    5.4.4 Can variables used in the condition part/condition and event part also be used in the action part of a rule?

6. Types in rule languages

The relationship between a language and its type system is one of the most crucial aspects of engineering the language; this is as true for rule languages as any other formal language intended to be processed automatically. The purpose of this series of questions is to try to ascertain what kind of support there is for types in the rule language. The range of possible type systems is huge, so it is a little difficult to ensure that one questionnaire covers all the possibilities.

We are attempting to answer the following core questions about types: The range of possible types, for example whether types are simple or have structure (i.e., polymorphic types, object types, collection types), whether recursive types are permitted, whether type definitions and/or type renaming are permitted.

1. What relationships between types, such as subtyping, are supported.
2. What the relationship is between types and values in the language.
3. What form of type processing is supported/required by the language: whether types are processed statically (before runtime) or dynamically (at runtime), or both, whether types are inferred or verified only, and so on.

In the following questions, we will use the abbreviation RL to denote the rule language, type-free if appropriate; and TL will refer to the type language. (It is quite possible for TL=RL, in some systems. In general they are distinct.)

• 6.1 Is the language typed?

  • 6.1.1 Does the RL support any form of types on terms, predicates and other program elements? Note: If no, please read following questions, you might decide to re-answer this question. 6.1.2 Does the language support any form of explicit type language (=TL) ? 6.1.3 Does the language require type safety checks on the arity and/or input arguments of built-ins? (E.g., does the arithmetic addition operator verify that the arguments are numbers?) 6.1.4 Can a type violation cause a different kind of result from a normal failure/negative response? Note: if yes, then the language supports dynamic types on terms. If no, may skip remaining questions

  6.2 About the type language

  • 6.2.1 Do types have names? I.e., is type equivalence defined as type name equivalence or structural equivalence (a.k.a. type unification)? 6.2.2 Are TL terms simple names, or may a TL term be a function term (i.e., may a type term contain other type terms as arguments)? Note: if yes, then the type language support parametric polymorphism. 6.2.3 Does the TL support standard complex type terms? 6.2.4 Are collection types supported? 6.2.5 Are array types supported? 6.2.6 Are set/bag types supported? 6.2.7 Are index types supported? (I.e., can the index of an array or collection be typed separately?) 6.2.8 Are list types supported? 6.2.9 Are tuple types/type tuples supported? 6.2.10 Are numeric interval types supported? 6.2.11 Are class types supported? 6.2.12 Are higher-order elements of the RL given specific TL terms? E.g., can function types be used as arguments of other types? 6.2.13 Is there any distinction between primitive types (e.g., numbers) and other types? (I.e., does the term “boxable” apply to the TL?) 6.2.14 Does the language support any form of reference type? Note: Reference types are a kind of pointer type often used in conjunction with re-assignable variables. 6.2.15 For parametric polymorphic type systems, are there any distinctions between the types permitted on reference types as compared to non-reference types? Note: Many functional programming languages have complex rules associated with the type targets of reference types; such as not permitting polymorphism in such cases. 6.2.16 Is it possible to define new types? 6.2.17 Is it possible to define type aliases? 6.2.18 Can a type be defined extensionally? (a.k.a. algebraic types) 6.2.19 Can a type be defined intensionally? 6.2.20 Does the TL permit definition of recursive types? 6.2.21 Is it possible to define arbitrary predicates over type terms? Note: if yes, then the language is likely not type decidable. 6.2.22 Does the language support any predefined predicates over type terms? 6.2.23 Does the language support any form of sub-type relation over type terms? Note: if yes, then the language supports sub-type polymorphism 6.2.24 Does the TL support existential types? E.g., is it possible to write rules that can 'recover' a type of an argument whose type is obscured? 6.2.25 Does the language support type reflection? I.e., can the type of an expression be reified, and can the type of an expression be determined to be consistent with a reified type expression? Note: if yes, then the language must also support type casting. 6.2.26 Does the language support type interfaces? 6.2.27 Can a type interface include assertions as well as pure type descriptions? 6.2.28 Can a type interface capture preconditions/postconditions/invariants?
    1. Preconditions only
    2. Preconditions and postconditions
    3. Preconditions, postconditions and invariants
    6.2.29 Are types of large scale entities such as classes, modules, packages etc. part of the TL.? 6.2.30 Does the type system support the assembly of rule systems from multiple sources? (I.e., are features such as loading of modules also type safe?)

    6.3 Relationship between the TL and the RL 6.3.1 Are TL terms syntactically distinct from RL terms that denote values? 6.3.2 Are TL terms semantically distinct from RL terms that denote values? 6.3.3 Are TL terms permitted as value terms in rules? Note: if yes, then language supports explicit dynamic typing 6.3.4 Which statement is more accurate for the relationship between type terms and other elements of the language:

    1. The type system induces an abstract interpretation over the sets of rules.
    2. The type system partitions the universe of elements into disjoint categories.
    3. The type system represents a system of monadic predicates with a distinguished interpretation.
    4. All of the above.
    5. None of the above.
    Note: this is an attempt to gain a rough characterization of the semantics of types vs the semantics of rules themselves. 6.3.5 Does the language system perform type consistency verification independently of any queries? Note: if yes, then the language supports static type checking 6.3.6 Does the language permit more than one type interpretation of any terms/rules/functions/predicates etc.? Note: if yes, then the language is weakly typed, if no, then the language is strongly typed. 6.3.7 Does the language permit more than one type for any function/predicate/action symbol? Note: if yes, then the language supports overloading. Note: this is different to previous question, it is possible to be strongly type checked and to support overloading. 6.3.8 Are type assignments to RL terms inferred automatically by the type systems? 6.3.9 Can type inference infer recursive types for RL expressions? 6.3.10 Are all elements of the RL associated with unique elements from TL? 6.3.11 Can a type of an element of the RL be left as a type variable? Note: this, together with type terms being structured, means that the language supports parametric polymorphism. On its own, permitting free variables to denote types is a marker for support for generics. 6.3.12 Does the language permit annotations on expressions that further constrain the type of the expression? 6.3.13 Does the RL language permit type casting? 6.3.14 Does the language permit runtime evaluation if one or more type inconsistencies are detected? 6.3.15 Does the language permit individual rules to select on the type of the arguments (as opposed to the values of the arguments)? Note: if yes, the language supports type restrictions. 6.3.16 If the TL and RL support classes, what is the correspondence between a class type and a class implementation:
    1. Each class type has exactly one implementation
    2. An interface can be implemented by any number of implementations
    3. A class type can be implemented by any number of class implementations
    6.3.17 Which statement is more accurate?
    1. Predicates are typed, tuples are not.
    2. Each tuple in a relation carries an independent type assignment.

Further discriminators/refinements to be added

Possible Rule System taxonomy

(this section is probably not up to date with changes made to RIFRAF in June, 2006)

For most Discriminators there exists a lot of literature, under various names. For example, Discriminator SeS 1 on "Homogeneous vs. Hybrid Rules" is discussed, under this name, in Combining Rules and Ontologies. A survey. That paper provides various Subdiscriminators useful for OWL Compatibility. The Hybrid approach is further described in A Realistic Architecture for the Semantic Web.

The RIF-crucial Interoperability Discriminators are regarded here as Pragmatic Discriminators, and grouped under Prag 3.

Given the Discriminators, "Expressive Sublanguages" can be described. For example, using only a subset of the Discriminators, four varieties of "deductive rules" could be given a taxonomy like the following:

• Deductive Rules
  • Homogeneous Positional Logic
    • Horn Logic
      • Function-free Horn Logic (FO Datalog)
        • Variable-free (Ground) Function-free Horn Logic (isom. to FO Propositional Logic)
          • Nullary Horn Logic (isom. to FO Propositional Logic)
          • Ground Function-free Fact Base
      • Unary Horn Logic
      • Binary Horn Logic
      • Unary/Binary Horn Logic
        • Unary/Binary FO Datalog (cf. SWRL)
  • Homogeneous Slotted Logic
    • Slotted Horn Logic
      • Slotted Function-free Horn Logic (Slotted FO Datalog)
        • Slotted Variable-free (Ground) Function-free Horn Logic (isom. to FO Propositional Logic)
          • (Further Distinctions like in "Variable-free Function-free Horn Logic")
      • Slotted Unary Horn Logic (isom. to Unary Horn Logic)
      • Slotted Binary Horn Logic
        • Slotted Unary/Binary FO Datalog
  • Hybrid Positional Logic
    • (Hybrid extension for Types, RDFS, and OWL; rule part as in Homogeneous Positional Logic)
  • Hybrid Slotted Logic
    • (Hybrid extension for Types, RDFS, and OWL; rule part as in Homogeneous Slotted Logic)

The actual taxonomy could be developed by alternating between such a top-down classification and a BottomUpClassification.

Related Reading

• RuleML Modularization

• Combining Rules and Ontologies. A survey.

• A Realistic Architecture for the Semantic Web

• DL+Log: Tight Integration of DLs and Disjunctive Datalog

• REWERSE Classification of Rules

• RuleML classification framework: http://www.ruleml.org/modularization/#Model.

• BottomUpClassification.