Ivanhoe: an RDF-Based Frame System

About the Frame System
Abstract Frame API
Path Grammar
Paths
Frames
Appendix A: Examples
Appendix B: Notes

1. About the Frame System

Ivanhoe^{[name note]} is essentially an API that makes the underlying Wilbur system look like a frame-based representation system, based on the simple idea that RDF graphs can be interpreted (through a node-centric view) as frames, slots, and fillers. Ivanhoe consists of a simple, abstract frame API which is implemented through several low-level, more detailed, APIs. The APIs and the implementation are partially based on the BEEF frame system^[BEEF
note].

Frames in Ivanhoe are nodes of an RDF graph, and are thus represented by instances of the class node. Slots are the arc labels of an RDF graph, and are thus also represented by node instances. Fillers (slot values) can be node instances (i.e., other frames) or any other data used by Wilbur (current implementation allows any Common Lisp objects, but the parser can only produce strings).

Ivanhoe generalizes on the notion of a slot, and allows expressions of a path grammar to be used in all slot access functions (a slot name is just a simple special case of an access path).

OKBC support is considered for the next version of Ivanhoe.

2. Abstract Frame API

The abstract frame API represents...

frame (uri &rest slot/value-pairs) [Generic function]

Creates a frame (a node instance) named by the URI string uri, and initializes slots from slot/value-pairs (dotted pairs of slot & value).

own-slots (frame) [Generic function]

Returns a list of a frame's own slots (a list of node instances, that is)

value (frame &rest paths) [Generic function]

Accesses a value reachable from frame via a path. Returns multiple values, one for each path supplied.

all-values (frame &rest paths) [Generic function]

Accesses all values reachable from a frame via a path, returning the values as a list. Returns multiple lists, one for each path supplied.

add-value (frame slot value) [Generic function]

Adds value (any object) to slot (named by a node) in frame (a node). Corresponds to the addition of a single triple to the underlying RDF model (graph).

del-value (frame slot &optional value) [Generic function]

Deletes value (any object) from slot (named by a node) in frame (a node). If value is not specified or is nil, deletes all values from slot. Corresponds to the deletion of one (or more) triples from the underlying RDF model (graph); essentially the triple (or triples) are found by executing

(db-query *db* frame slot value)

relatedp (source path sink &optional action) [Generic function]

Returns true if sink (a frame, i.e., a node) is reachable from source (also a frame) via path. If supplied, calls action on each frame encountered along the path.

load-db (url &rest options &key error-handling merge-results-p) [Generic function]

Loads and parses the contents of the URL url. If the parameter merge-results-p is true, the results (the resulting triples, i.e., slot filler assignments) are merged to the default database (the one bound to the variable *db*). Other options are the same as for the function parse-db-from-stream. The default value for merge-results-p is

(eq error-handling :signal)

Method implementations of load-db exists for string, file-url and http-url specializations of url.

http-proxy [Variable]

When loading data from HTTP URLs (instances of http-url), load-db uses the value of this variable as the HTTP proxy (as passed to the function http-get). Proxies are instances of http-url (the path component is ignored).

3. Path Grammar

Relation paths can be described using regular expressions. These expressions obey the Common Lisp syntax (that is, prefix notation) and use a set of operators. Traversing a relation actually means matching the relation path to a path grammar pattern; the path grammar operators are used in constructing these patterns. Slot names are used as the atomic elements of path grammar.

The path grammar is based on the one in the graph pattern matcher of the BEEF frame system^{[BEEF note]}.

See Appendix A for examples of the path grammar.

:seq &rest expressions [Path Grammar Operator]

This constructor is satisfied by a relation path if it consists of subpaths satisfying expressions in order. An example: the path grammar expression

(:seq !x !y)

defines a relation path where one first traverses over an !x slot link and then over a !y slot link. The utterance "traversing over a slot link" here means moving from one frame to another frame which is a value of an own slot of the first frame.

:seq+ &rest expressions [Path Grammar Operator]

This constructor resembles sequence, but also allows the satisfaction of sub-sequences. One may think that

(:seq+ !x !y)

is equivalent to

(:or !x (:seq !x !y))

:or &rest expressions [Path Grammar Operator]

This constructor is satisfied if any of the patterns in expressions matches the relation path. An example: the path grammar expression

(:or !x !y)

defines a relation path where one either traverses over an !x slot link or over a !y slot link.

:rep* expression [Path Grammar Operator]

This constructor is always satisfied when expression can matched to the relation path any number of times in sequence (including zero). Satisfaction of this operator implise the computation of the transitive closure of expression, and can be costly.

:rep+ expression [Path Grammar Operator]

This constructor is always satisfied when expression can matched to the relation path any number of times in sequence (not including zero).

:inv expression [Path Grammar Operator]

This constructor effectively inverts the path described by expression, that is, it is satisfied if expression can be matched with a path traversed "backwards".

:members [Path Grammar Atom]

Can be used in a path grammar expression to denote any of the index URIs of RDF containers (rdf:_1, rdf_2, etc.). Consequently, if !foo is a frame which has a slot !x whose value is an RDF container (say, rdf:Bag), then

(all-values !foo '(:seq !x :members))

returns a Common Lisp list of all the items of the bag.

:any [Path Grammar Atom]

Can be used in a path grammar expression to denote any slot name. For example, if frame !foo has own slots !x and !y (and no other own slots), then

(all-values !foo :any)

will be the same as

(all-values !foo '(:or !x !y))

4. Paths

path [Class]

Instances of this class represent path grammar expressions. In the current implementation, expressions are actually pre-processed into finite-state automate (FSAs) and cached.

path-expression (path) [Generic function]

Accesses the actual path expression (an s-expression, i.e., a Common Lisp list).

path-fsa (path) [Generic function]

Accesses the low-level implementation of the FSA generated by pre-processing the path expression.

invert (path) [Generic function]

Returns an instance of path which represents the inverse path of the path instance path.

walk-using-fsa (root fsa action) [Function]

This function takes a "root node" (parameter root) and a low-level FSA object (parameter fsa; see the function path-fsa), and walks the RDF graph using the FSA calling the function action on every node at the end of those paths matched by the FSA. The function returns either when the FSA is exhausted or when action returns a non-nil value.

collect-using-fsa (root fsa) [Function]

Walks the RDF graph, starting from the node root, using the FSA fsa, and collects all nodes (as a list) at the ends of those paths which are matched by the FSA.

5. Frames

Frames in Ivanhoe are represented by a node instance, hence all node methods apply. Four generic functions have been added to the API for slot access. Generally these methods differ from the abstract API by taking an explicit database parameter, whereas the abstract API relies on the default database bound to the variable *db*. The following table shows the correspondence of the abstract frame API and the lower-level APIs:

Abstract API	Lower-level API
`frame`	`node` (and uses `add-value`)
`own-slots`	(uses `db-query`)
`value`	`get-value`
`all-values`	`get-all-values`
`add-value`	`db-add-triple`
`del-value`	`db-del-triple`
`relatedp`	`frames-related-p` (which uses `walk-using-fsa`)

get-value (frame path db) [Generic function]

Accesses a single value (a node or other slot filler) reachable from the node frame via the path path. Note that methods exist for get-value where path can be a path instance, a path grammar expression (a cons), or a simple slot (named by a node). The method specialized for "simple" slots (i.e., where the specializer for path is node) returns

(get-value-when-failed frame path db)

if it otherwise were to return nil.

get-all-values (frame path db) [Generic function]

Accesses all values (nodes or other slot fillers) reachable from the node frame via the path path. Note that methods exist for get-all-values where path can be a path instance, a path grammar expression (a cons), a simple slot (named by a node), or one of the keywords (path grammar atoms) :members or :any. The method specialized for "simple" slots (i.e., where the specializer for path is node) returns

(list (get-value-when-failed frame path db))

if it otherwise were to return nil.

get-value-when-failed (frame path db) [Generic function]

This function is called if get-value would return nil. The default method will also return nil, unless path is the node !rdf:type, in which case !rdfs:Resource is returned. Extensions of the frame system are free to introduce new methods for get-value-when-failed. The signature for the default method is (node node db).

frames-related-p (source path sink db action) [Generic function]

Returns true if sink (a frame, i.e., a node) is reachable from source (also a frame) via path. If not nil, calls action on each frame encountered along the path.

Appendix B: Examples

The list of all classes a frame (here denoted by x) is an instance of:

(all-values x
            '(:seq !rdf:type
                   (:rep* !rdfs:subClassOf)))

All instances of a class (here denoted by c), including instances of all subclasses:

(all-values c
            '(:inv (:seq !rdf:type
                         (:rep* !rdfs:subClassOf))))

Turning a DAML list (here denoted by x) into a Common Lisp list:

(all-values x
            '(:seq (:rep* !daml:rest)
                   !daml:first))

Finding out whether a slot value (here denoted by x) satisfies the (disjunctive) range constraints of a property (here denoted by p):

(relatedp x
          '(:seq !rdf:type
                 '(:rep* !rdfs:subClassOf)
                  (:inv !rdfs:range)
                  (:rep* (:inv !rdfs:subPropertyOf)))
          p)

The previous example but with the assumption that range constraints are conjunctive (non-optimized implementation):

(every #'(lambda (c)
           (relatedp x
                     '(:seq !rdf:type
                            (:rep* !rdfs:subClassOf))
                     c))
       (all-values p
                   '(:seq (:rep* !rdfs:subPropertyOf)
                          !rdfs:range)))

Appendix B: Notes

Name note: Why is this system called "Ivanhoe"? It started out as an acronym play: "Wilbur Frame System for DAML" or "WilFreD". Oh well... (but I do like good medieval stories).

BEEF note: BEEF (or "BOSS's Extremely Elegant Frame system") is a frame system originally developed for the Helsinki University of Technology's "BOSS" distributed knowledge-based production scheduling system. BEEF is described in the following publications:

Ora Lassila: "BEEF Reference Manual - A Programmer's Guide to the BEEF Frame System", Second Version, Report HTKK-TKO-C46, Otaniemi (Finland), Department of Computer Science, Helsinki University of Technology, 1991
Juha Hynynen and Ora Lassila: "On the Use of Object-Oriented Paradigm in a Distributed Problem Solver", AI Communications 2(3): 142-151 (1989)

Ivanhoe: an RDF-Based Frame System

1. About the Frame System

2. Abstract Frame API

frame (uri &rest slot/value-pairs) [Generic function]

own-slots (frame) [Generic function]

value (frame &rest paths) [Generic function]

all-values (frame &rest paths) [Generic function]

add-value (frame slot value) [Generic function]

del-value (frame slot &optional value) [Generic function]

relatedp (source path sink &optional action) [Generic function]

load-db (url &rest options &key error-handling merge-results-p) [Generic function]

*http-proxy* [Variable]

3. Path Grammar

:seq &rest expressions [Path Grammar Operator]

:seq+ &rest expressions [Path Grammar Operator]

:or &rest expressions [Path Grammar Operator]

:rep* expression [Path Grammar Operator]

:rep+ expression [Path Grammar Operator]

:inv expression [Path Grammar Operator]

:members [Path Grammar Atom]

:any [Path Grammar Atom]

4. Paths

path [Class]

path-expression (path) [Generic function]

path-fsa (path) [Generic function]

invert (path) [Generic function]

walk-using-fsa (root fsa action) [Function]

collect-using-fsa (root fsa) [Function]

5. Frames

get-value (frame path db) [Generic function]

get-all-values (frame path db) [Generic function]

get-value-when-failed (frame path db) [Generic function]

frames-related-p (source path sink db action) [Generic function]

Appendix B: Examples

Appendix B: Notes

http-proxy [Variable]