Representing Facts and Rules in RDF

Bridging conventional predicate representations and RDF

Graham Klyne
Created: 19 July 2001
Revised: 02-Dec-2002

[[[NOTE: Work in progress]]]

This note has roots in my work with Baltimore Technologies' research group, where I was involved in designs for an RDF-driven expert system shell to experiment with applying expert system techniques to web-based RDF data [1]. While RDF on the Web may be a useful open-ended source of knowledge from which an expert system may reason, it is not obvious how to use it as a basis for defining facts and rules needed to develop, test and prime an expert system shell.

Table of Contents

• 1. Background
• 1.1 Facts
• 1.2 Rules
• 1.3 RDF
• 1.4 Names: URIs and QNames
• 2. Non-RDF format for facts and rules
• 2.1 Values, resources
• 2.2 Literals
• 2.3 Variables
• 2.4 Facts
• 2.5 Rules
• 2.6 Ranging rules over predicates
• 2.7 Goal statements
• 2.8 Knowledge base structure
• 3. RDF format for facts and rules
• 3.1 Naming of values
• 3.2 Dyadic ground facts
• 3.3 Monadic ground facts
• 3.4 Facts of arbitrary arity
• 3.4.1 Examples of the general fact representation
• 3.4.2 Statements with literal first arguments
• 3.5 Using non-asserted facts in expressions
• 3.6 Representation of rules
• 3.7 Variables and variable scope
• 3.8 Facts containing variables
• 3.9 Representation of goal statements
• 4. References

1. Background

1.1 Facts

In common with many similar systems, our base facts are represented as n-place predicate functions; i.e. an asserted fact is an n-place predicate that is presumed to have the value true; e.g.

parents( Alfred, Bob, Carol )

may be used to assert that the parents of Alfred are Bob and Carol.

1.2 Rules

Rule, or inference rules, are constructs that are used to infer new facts from other facts; e.g. the inference rule:

IF parents( ?a, ?b, ?c ) AND parents( ?b, ?d, ?e ) AND parents( ?c, ?f, ?g )
THEN grandparents( ?a, ?d, ?e, ?f, ?g )

may be used to infer from:

parents( Alfred, Bob, Carol ) AND
parents( Bob, David, Ethel ) AND
parents( Carol, Fred, Gill )

the new fact:

grandparents( Alfred, David, Ethel, Fred, Gill )

For our expert system shell design, we chose a slightly richer form of rule that allows several facts to be inferred by a single rule:

IF a1 AND a2 AND ... THEN c1 AND c2 AND ....

Some work to represent rules in the Web, and in particular using XML, is being undertaken by the RuleML Initiative [2] (Rule Markup Language).

1.3 RDF

RDF is defined as a standard metadata format for the Web [4] [5]. There are several ways of looking at RDF and how it represents information (e.g. [3]). For our purposes here, these are the salient considerations:

• The fundamental unit of information in RDF is a binary predicate; e.g.
• father(Alice,Bob)
• Unary predicates are sometimes represented as RDF type values; e.g.
• isPerson(Alice) -> type(Alice,aPerson)
• Predicates with more than two parameters are not directly represented in RDF, and the information they convey must somehow be encoded in the binary predicate representation.
• All non-literal values are identified by URIs [6]. The importance of this is underscored by Tim Berner-lee's discussion of building applications for the World Wide Web [7].
• In addition to URIs, literal values (Unicode character strings) may appear the second parameter of a binary predicate.

1.4 Names: URIs and QNames

URIs have certain advantages, but they can be somewhat cumbersome to use as names. Ther XML namespace specification [8] introduces the concept of Qualified Names, or QNames, as a relatively convenient way to use URIs as identifiers. A QName consists of a prefix, a colon (':') and a local name part, where the prefix is bound separately to a namespace URI (in XML, by a namespace declaration attribute). RDF further defines that a URI is derived from a QName by concatenating the namespace URI with the local part.

In the rest of this note, QNames may be used in place of URIs, in some cases with an appropriate namespace binding assumed. A small extension to the QName format defined by the XML namespace recommendation is needed so that every URI can be represented thus; the 'LocalPart' of a QName may be empty, thus allowing QNames of the form 'prefix:'. This allows URIs that end with a non-name character to be represented in the QName format.

2. Non-RDF format for facts and rules

This section describes some formats for input and display of facts and rules that are used by the RDF expert system shell, in addition to RDF formats. The syntax description notation used here is defined in the XML specification [11].

This is a representation that is intended to be reasonably human-friendly and "scribblable". Some of the ideas are taken from N3 [9]. Subsequent sections will look at how this can be encoded in RDF.

2.1 Values, resources

Values, which in RDF are resources, are represented by a QName [8], which in turn maps to a URI of the resource value.

Value     ::= QName

QName     ::= Prefix ':' (LocalName)? | (':')? LocalName

LocalName ::= Name

Prefix    ::= Name

Name      ::= ( Letter | '_' ) (NameChar)*

NameChar  ::= ( Letter | Digit | '.' | '-' | '_' )

A QName of the form 'Prefix:' maps to the URI associated with the given prefix (this is not allowed for QNames per XML namespaces [8].) A QName of the form ':LocalName' or 'LocalName' is associated with the default namespace.

Where appropriate, namespace prefixes are declared using the following syntax (adopted from N3 [9]):

PrefixDef ::= "@prefix" Name ":"  URI-ref '.' |
              "@prefix"      ":"  URI-ref '.'

URI-ref   ::= '<' URI-reference '>' |
              QName

The empty namespace name defines a default namespace.

2.2 Literals

Literal values are enclosed in double quote characters. Within a literal, any non-quote ('"'), non-escape ('\'), non-control, non-surrogate Unocode character may appear, or any of the following escape sequences:

Escape Sequence	Meaning
\\	Backslash (\)
\"	Double quote (")
\n	ASCII Linefeed (LF)
\r	ASCII Carriage Return (CR)
\t	ASCII Horizontal Tab (TAB)
\uhhhh	Unicode character with hex value hhhh
\Uhhhhhhhh	Unicode character with hex value hhhhhhhh

Except for the numeric escape convention, this is a subset of the literal values allowed for N3. The syntax for literals is defined as:

Literal  ::= '"' LitElem* '"'

LitElem  ::= LitChar | Escape

LitChar  ::= Char - '"' - '\'

Escape   ::= '\\' | '\"' | '\n' | '\r' | '\t' |
             '\u' HexDigit HexDigit HexDigit HexDigit |
             '\U' HexDigit HexDigit HexDigit HexDigit
                  HexDigit HexDigit HexDigit HexDigit

HexDigit ::= [0-9a-fA-F]

// Non-control, non-surrogate UNICODE characters
Char     ::= [#x0020-#x007E] |
             [#x0080-#xD7FF] |
             [#xE000-#xFFFD] |
             [#x10000-#x10FFFF]

2.3 Variables

Rules use variables to range over values to which the rule may be applied. The scope of a variable name is limited to the rule in which it appears. (Future developments may allow variables in the extended goal statement).

Variable  ::= '?' Name

Variables may sometimes appear in facts, indicating that any value may be used in its place.

2.4 Facts

A fact is defined using a predicate form:

Fact      ::= QName '(' Value ( ',' Value )* ')'

Value     ::= QName | Literal | Variable

NOTE: there is no restriction here on where a literal may appear in a fact. This must be taken into account when mapping to RDF, which restricts the use of literals.

2.5 Rules

A rule contains anumber of antecedent facts and a number of consequent facts that can be inferred to be true when all of the antecedent facts are determined to be true.

Rule      ::= Fact ( '&' Fact )* '->' Fact ( '&' Fact )*

NOTE: any variables that appear in an inference rule must all bind to the same value when using the rule to infer some fact. In the current use, the scope of a variable name is the rule in which it appears. Future use may create alternative variable scopes for use in goal statements.

2.6 Ranging rules over predicates

The formulation of facts and rules described above requires that the name of any predicate predicate used is explicitly named in any fact or rule; i.e. the predicate cannot be a variable.

There are some rules of inference, and other cases, where it is helpful to have a fact or part of an inference rule that can match a number of different predicates; e.g.

?p1(Item1,?val) -> ?p1(Item2,?val)

might be used to say that any binary predicate that is true of 'Item1' is also true of 'Item2'. This is not allowed under the syntax given above.

[[[For future development -- proceed with caution]]]

2.7 Goal statements

A goal statement contains a sequence of goal steps to be resolved, each of which may resolve a single goal by forward or backward chaining, or be a composite consisting of its own sequence of goal steps. In each case, the goal may be augmented by directives that direct the expert system shell how to resolve that goal. Currently, the options are forward chaining and backward chaining, but this is an area for ongoing investigation and other resolution strategy options may be added in future.

To resolve a goal (or subgoal), each of its goal steps must be resolved in turn, and any new facts inferred in the process added the the knowledge base, before proceeding to the next step. The overall process succeeds if all of the goal steps can be resolved in turn.

Goal      ::= GoalStep ( ';' GoalStep )*


GoalStep  ::= ( Fact ( ',' Fact )* '->' Fact
              | Fact
              | '{' Goal '}' )
              ( '/' Option )*

Option    ::= [[[options -- TBD]]]

NOTE: any variables that appear in an inference rule must all bind to the same value when using the rule to infer some fact. In the current use, the scope of a variable name is the rule in which it appears. Future use may create alternative variable scopes for use in goal statements.

Example:

Parents(?A,?B,?C) -> GrandParents(?A,?D,?E,?F,?G) ;
Cousin(?A,?B)

Which says that the system should first forward chain from all Parents(...) facts to establish new GrandParents(...) facts, then use backward chaining from Cousin(...) to find all any cousins. This presumes that 'Cousin' is defined in terms of the 'GrandParents'. (In the context of a closed knowledge base this may offer little advantage over direct backward chaining; this composite goal facility is intended to provide hooks for further exploratory work.)

2.8 Knowledge base structure

[[[TBD -- Overall syntax for a knowedge base with facts, rules and/or goal statement]]]

[[[Add notation for import]]]

3. RDF format for facts and rules

In this section, we explore ways in which the structures described above can be coded in the standard RDF model, which consists of triples, or binary predicates.

The challenges to be addressed are:

• naming of values
• representation of non-binary facts (i.e. predicates of 1, 3 or more arguments)
• using facts in other expressions
• representation of rules
• representation of variables and variable scope
• representation of facts containing variables
• representation of goal statements

It is important to recognize that RDF alone does not address all of these goals. It would be easy to simply encode all the facts and rules into RDF triples, and declare victory. But that overlooks an important point: the whole reason for building an expert system shell driven by RDF is to be able to leverage information from other applications that also use RDF. So the proposals below are a combinatiopn of using RDF directly, and creating encodings in RDF for new structures.

In the sections that follow, Notation 3 [9], and its derivative N-triples [12], are used to present RDF structures that would typically be represented in RDF/XML [4]. The use here of these alternative presentation formats is for legibility, and should not be interpreted as precluding the use of RDF/XML, or any other syntax for RDF.

3.1 Naming of values

A problem often encountered when looking at converting information to an RDF-based format is that the original does not use URIs for identifiying values. In such situations, it is tempting to represent the non-URI identifiers as literals. While this can work for an isolated application, it fails to take advantage of one of the great strengths of RDF, viz the potential for other RDF applications to access or add to the information thus expressed. So, to be a first-class citizen in the world of RDF appliucations, the naming format used but be based upon or mapped to a URI or equivalent form [7].

Compared with some other conventions for representing facts and rules, the structures outlined in the previous section have addressed this issue of web-friendly naming by using QNames for all value identifiers (with one small extension). Through the mechanisms of XML namespaces, these can be used with RDF, either directly or mapped to URIs depending upon context.

3.2 Dyadic ground facts

By "ground fact", we mean an assertion that uses specified values or literals, without variables.

RDF has a direct representation for dyadic ground facts: the triple. Using N-triples [12] to represent RDF constructs:

@prefix x: <http://example.org/#>
x:p(x:s,x:o)

would map to the following N-triples statement:

<http://example.org/#s>

            <http://example.org/#p>

            <http://example.org/#o> .

3.3 Monadic ground facts

Monadic ground facts can be represented in RDF using the rdf:type property. Under this regime:

@prefix x: <http://example.org/#> .
x:m(x:s) .

This can be represented as a dyadic form using the rdf:type predicate:

@prefix x: <http://example.org/#> .
rdf:typw(x:s,x:m) .

which would map to the following N-triples statement:

<http://example.org/#s>
  <http://www.w3.org/1999/02/22-rdf-syntax-ns#type>
  <http://example.org/#m> .

That is, the monadic predicate is presented as a type label. This convention is established in typed logic, as presented by John Sowa in section 1.3 of his book Knowledge Representation [13].

3.4 Facts of arbitrary arity

In formulating rules and knowledge bases for our expert system shell, to facilitate their construction we have not wanted to be constrained to express all facts in terms of monadic or dyadic predicates that RDF can represent directly. Thus, we have also created an encoding into RDF of arbitrary n-place facts.

NOTE: this section discusses representation of asserted facts; i.e. facts that are stated to be true. For a discussion of representing facts that are used without being asserted, as in the expression of inference rules, see section 3.5: Using facts in other expressions.

The RDF expert system shell design used the rdf:Seq container type to represent the n arguments of a predicate, but this is felt to be unsatisfactory, partly because of the quirks of RDF container types, and partly because this structure is gratuitously different from the RDF representation of dyadic predicates.

For consistency with the normal RDF representations of ground facts (see above), a format is adopted that has the form of a normal RDF statement whose subject is the first argument of the predicate on which the fact is based, whose property is the predicate, and whose object is a list of any remaining arguments. Thus, the predicate:

ex:pred( ex:subj, ex:val2, ex:val3, ... ) .

is represented in RDF (using Notation3 [9]) as something like this:

ex:subj ex:pred [ rdf:type rdf:List ;
                  rdf:first ex:val2 ;
                  rdf:rest  [ rdf:type rdf:List ;
                              rdf:first ex:val3 ;
                              rdf:rest  [ rdf:type rdf:List
                                          :
                                          ... rdf:rest rdf:nil ]]] .

This of facts representation uses a common representation of lists based on constructor elements that reference a head alement and a tail which is the rest of the list. It introduces a number of special resource identifiers, associated here with the namespace prefix rul:, which indicates the namespace URI <http://id.mimesweeper.com/RDFExpert/V1.0/ess#>:

• rdf:List is an auxiliary data type (i.e. an rdfs:Class resource) that describes a list constructor cell, similar to the CONS function in LISP. It constructs a list from a rdf:first element and an rdf:rest sublist.
• rdf:first is a property that designates the head of a list represented by an rdf:List value.
• rdf:rest is a property that designates the tail (i.e. all of the list elements other than head) of a list represented by an rdf:List value.
• rdf:nil is a distinguished value with type rdf:List that represents an empty list. A list is terminated by this value as the rdf:rest property of an rdf:List value.

Reducing to a list of RDF triples, the above list would look something like this:

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix ex:  <http://example.org/#> .

ex:subj ex:pred _:genid1 .
_:genid1 rdf:type rdf:List .
_:genid1 rdf:first ex:val2 .
_:genid1 rdf:rest _:genid2 .
_:genid2 rdf:type rdf:List .
_:genid2 rdf:first ex:val3 .
_:genid2 rdf:rest _:genid3 .
_:genid3 rdf:type rdf:List .
_:genid3 ...
        :
     ... rdf:rest rdf:nil .

 +-------+
 |ex:subj|
 +-------+
      \
    ex:pred
        \
     +-----+-----+
     |     |     |
     +-----+-----+
       /       \
   rdf:first  rdf:rest
     /           \
+-------+   +-----+-----+
|ex:val2|   |     |     |
+-------+   +-----+-----+
              /       \
          rdf:first  rdf:rest
            /           \
       +-------+   +-----+-----+
       |ex:val3|   |     |     |
       +-------+   +-----+-----+
                     /       \
                    :         :
                               \
                             rdf:rest
                                 \
                             +-------+
                             |rdf:nil|
                             +-------+

3.4.1 Examples of the general fact representation

This sub section gives some specific examples of facts represented using the framework described above. In each case, the non-RDF predicate form from the previous section, the standard RDF form where there is a direct representation, followed by the representation using the generic fact representation framework outlines above.

Modadic predicate

Non-RDF predicate:

@prefix ex:  <http://example.org/#> .
ex:pred( ex:subj ) .

Standard RDF/N3:

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix ex:  <http://example.org/#> .
ex:subj rdf:type ex:pred .

Generic fact RDF/N3: