RIFRAF analysis for WRL

http://www.w3.org/2005/rules/wg/track/actions/15
http://www.w3.org/2006/05/16-rif-minutes.html

As promised in may 16th teleconf, I repeat the exercise of my previous 
mail on WRL. Thanks to Jos De Bruijn for assisting me with this analysis.

WRL (Web Rule Language) is a member submission which influenced this WG 
charter, see:  http://www.w3.org/Submission/2005/08/
So, probably most of you are aware of it.

Still, I recap the essence:

WRL is located in the Semantic Web stack next to the Description Logic
based Ontology language OWL. WRL defines three variants, namely Core,
Flight and Full. The Core variant marks the common fragment between
WRL and OWL. WRL-Flight is a rule language based on the Datalog fragment
of F-Logic, extended with stratified negation. WRL-Full is
a full-fledged rule language based on the Horn subset of F-Logic, 
extended with negation under the Well-Founded Semantics.

WRL can be reduced to regular LP rules; this allows the use of many 
existing reasoners for WRL. The WSML2Reasoner framework 
(http://dev1.deri.at/wsml2reasoner/) enables using different existing 
rule engines such as DLV, KAON2, and MINS to reason with WSML-Rule, a 
superset of WRL-Full. On online demo is available at: 
http://tools.deri.org/wsml/rule-reasoner/

-------------------------------------------------------------------

CLASSIFYING WRL AS A RULE LANGUAGE

===== SYN: SYNTACTIC DISCRIMINATORS =====

SYN.1. RESTRICTED VS. UNRESTRICTED USE OF LOGIC VARIABLES

   SYN.1.1. SINGLE OCCURRENCE VS. MULTIPLE OCCURRENCE (IMPLICIT VARIABLE
      EQUALITY)

      [WRL] Variables are scoped over rules, no global variables.
            Variables may be typed using classes in an ontology.

         --> comment axel: As mentioned in the DLV part a
             discriminator for typing variables
             seems to be missing, or was this meant in SYN1.3?

    SYN.1.2. RANGE-RESTRICTED RULES (NO HEAD-ONLY VARIABLES)
           VS. NON-RANGE-RESTRICTED RULES

      [WRL] Safety is only required in WRL Core and Flight,
            but not in WRL Full.
            There are no other restrictions on variable ranges.

   SYN.1.3. (FURTHER RESTRICTIONS FROM STATIC ANALYSIS RESEARCH)

     --> comment axel: still unclear for me

SYN.2. PREDICATE VARIABLES PERMITTED VS. NOT PERMITTED

     * 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])

    [WRL] WRL Core doesn't support higher order syntax and also limits
          attribute names, predicate names, class names and objects to be
          disjoint.
          WRL Flight and Full allow variables to occur in the place of
          class and attribute names. Variables are not allowed in
          arbitrary predicate positions.

SYN.3. MONOTONIC LLOYD-TOPOR EXTENSIONS ALLOWED VS. NOT ALLOWED

     * SYNTACTIC SUGAR FOR EXTENDING HORN LOGIC WITH DISJUNCTION IN RULE
       BODIES AS WELL AS CONJUNCTION AND CLASSICAL IMPLICATION IN RULE
       HEADS [HTTP://WWW.W3.ORG/SUBMISSION/SWSF-SWSL/#SWSL-RULES-MON-LT]

   [WRL] WRL Core does not have Lloyd-Topor extensions. WRL-Flight has
         monotonic Lloyd-Topor (disjunction in the body and implication
         and conjunction in the head). WRL Full allows full Lloyd-Topor
         (i.e., arbitrary first-order formulas in the body of a rule),
         and unstratified negation (under the Well-Founded Semantics).

SYN.4. EXPLICIT VS. IMPLICIT RULE SCOPE

     * ALLOWING FORMULAS AND/OR NAMES DENOTING WHAT HAS BEEN CALLED
       MODULES, CONTEXTS, RULESETS, OR MODELS
       [HTTP://WWW.ISI.EDU/~ARGOS/MATTHEW/TRIPLE_BY_EXAMPLE.HTML]

       [WRL] does not support modules in the sense of e.g. Triple or
             Flora-2.

     SYN.4.1. SLOTTED (KEYED, ROLE-NAMED) VS. POSITIONAL ARGUMENTS

         * ALLOWING N-ARY ATOMS WITH A SET OF N 'ATTRIBUTE=VALUE' PAIRS
           AS IN RDF/OWL PROPERTIES, F-LOGIC METHODS, AND OBJECT-ORIENTED
           SYSTEMS [HTTP://WWW.RULEML.ORG/INDOO]

       [WRL] WRL core extend OWL in the sense that it supports inly
             binary relations, which amount to RDF/OWL properties, or
             F-LOGIC methods.

SYN.5. WEBIZED VS. NON-WEBIZED NAMES

     * ALLOWING URIS AS OIDS FOR CONSTANTS, FUNCTIONS, SLOTS, PREDICATES,
       CLASSES, AND/OR LABELS
       [HTTP://WWW.W3.ORG/2000/10/SWAP/PRIMER.HTML]

     [WRL] Yes.

===== SES: SYNTACTIC-ENTAILING-SEMANTIC DISCRIMINATORS =====

SES.1. HOMOGENEOUS (BODY HAS SINGLE EXPRESSIVENESS CLASS) VS. HYBRID 
(BODY HAS TWO EXPRESSIVENESS CLASSES) RULES

   [WRL] does supports not support the splitting body in a resolution and
         a query part.

SES.2. FACT-ONLY (DATABASE TABLES) VS. RULE-ONLY VS. FACT-AND-RULE BASES

   [WRL] facts and rules

SES.2.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS 
(ALSO UNDER "VARIABLE-FUL VS. ... CLAUSES")

      [WRL]  non-ground facts amount to unsafe rules and are thus allowed
             in WRL Full.

SES.3. FUNCTION-FUL (FO HORN LOGIC) VS. FUNCTION-FREE (FO DATALOG)

     [WRL] WRL full supports function symbols.

  SES.3.1. FUNCTION ARITY/ARITIES

      [WRL] In WRL Full, the same function symbol can be used with
            different arities (interpreted as syntactic sugar as
            different function symbols)

SES.3.2. FIXED VS. UNFIXED FUNCTION NESTING DEPTH

      [WRL] WRL Full supports arbitrary nesting of function symbols.

  SES.3.3. UNINTERPRETED VS. INTERPRETED FUNCTIONS

      [WRL] supports a basic set of datatype wrappers and builtins, which
      are syntactilly distinguished from uninterpreted functions.

SES.4. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) CLAUSES

   SES.4.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS
   (ALSO UNDER "FACT-ONLY ... BASES")

       [WRL] non-ground clauses allowed, for WRL core and Flight safety
             restriction.

SES.5. PREDICATE ARITY/ARITIES

      [WRL] The same predicate/relation can be used with different
      arities (interpreted as syntactic sugar as different
      predicate/relation symbols)

SES.6. NUMBER OF PREMISES IN RULES

      [WRL] unrestricted.

SES.7. LABELED (ANCHORED, OIDED) VS. UNLABELED CLAUSES

      [WRL] rules/axioms can be identified in WRL, but this is not
      subject to further semantic use of these labels.

   SES.7.1. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF USER
   PREDICATES

     [WRL]  Relation arguments are not labeled/named in WRL.

   SES.7.2. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF
   PRIORITY-GIVING SYSTEM PREDICATE 'OVERRIDES' (CF. SCLP)

    [WRL] There is no preference/priority mechanism defined in WRL.

   SES.8. CERTAIN VS. UNCERTAIN CLAUSES AND ATOMS

    [WRL]  No uncertainty in WRL.

===== SEM: SEMANTIC DISCRIMINATORS =====

  SEM.1. TERMINATING (ALL QUERIES TERMINATE) VS. NON-TERMINATING (AT 
LEAST ONE
     QUERY DOES NOT TERMINATE) RULEBASES

     [WRL] Core and Flight yes, Full no. Considerations regarding
     built-in predicates and termination from [DLV] apply as well.

  SEM.2. FINITE-MODEL VS. INFINITE-MODEL RULEBASES (CF. DECIDABILITY)

     [WRL] Core and Flight finite, Full no. Considerations regarding
     built-in predicates and termination from [DLV] apply as well.

SEM.3. MODALITY/INTENTIONALITY (BEYOND FOL)

    [WRL] No modalities.

===== PRAG: PRAGMATIC DISCRIMINATORS =====

PRAG.1. INFERENCE CONTROL

   PRAG.1.1. FORWARD CHAINING VS. BACKWARD CHAINING VS. BIDIRECTIONAL
   CHAINING

    [WRL] no commitment made; WRL is declarative.

   PRAG.1.2. INCREMENTAL VS. EXHAUSTIVE

     [WRL] no committment made.

   PRAG.2. COMPLEXITY

     [WRL] Complexity of WRL Core/Flight and WRL Full without function
     symbols is P/EXPTIME (data/program complexity).
     With function symbols, WRL Full entailment is undecidable.

   PRAG.3. INTEROPERABILITY

     [WRL] lossless interoperability with OWL on the intersection
           (DLP/WRL core)

    PRAG.3.1. ANNOTATIONS (INCLUDING CONTROLLED ENGLISH)

     [WRL] classes, relations, instances and rules can be annotated with
           arbitrary properties; recommended are the Dublin Core
           properties.

   PRAG.3.2. TEST CASES

      [WRL] No extensive test suites available yet; these are under
            development in several European projects.

   PRAG.3.3. MAPPINGS

     [WRL] Each layer (Core/Flight/Full) is a strict syntactic and
           semantic extension of the lower layers.

Received on Wednesday, 17 May 2006 15:20:52 UTC