Re: Implementing a graph algebra

"What I meant with my poor terminology was that graphs are insufficient

for knowledge representation, purely on the fact that not all relationships are reducible to dyadic predicates and graphs with their source, target, edge structure are necessarily binary in nature. A good

example is by Darwen (If my memory serves me correctly), who highlighted the following predicate: Teacher A uses Book B to teach Course C."

Hypergraphs represent relations of any arity (as does the relational model). But my approach is different. I posit a very simple base graph structure (not an hypergraph) with properties

1. edges are binary, directed and unlabelled
2. vertices are unlabelled; a vertex is either a datum or a pivot

(a) a datum is an atomic value; the datum *is* the vertex;

(b) a pivot has no associated data (but many distinct pivots may exist)

Then topologies on this base graph are defined that represent complex predicates called "semantic structures" (the notation xy means the edge from x to y):

Attribute. The attribute of subject S with attribute type (=name) T and attribute value V is represented by the topology {Sx, Tx, xV} where x is a pivot called the "attribute instance." An attribute instance may the subject of another attribute relation thus forming chains or trees of attributes as exemplified below.

Set. If S represents a set then the topology {Sx} represents the fact that x is a member of S.

Record. A record is a set of attribute instances.

Etc.

Reasons for this aproach include:

• there is no formal distinction, at the base level, between names of modeling entities (attribute names, set names etc.) and data values; thus there is no different syntactic devices in the query language, no need for so-called "dynamic queries" (see "Using the catalogue")
• attribute types may be complex, not just a name (and that is why I say "type" instead of "name")
• good for implementation; simplicity; the structures map very well from one abstraction level to another; for example Mneson is implemented with ordered sets of edges.

Predicates like "Teacher A uses Book B to teach Course C" can be modeled in several ways (thus requiring a schema):

Way 1: with an attribute UsesToTeach having subattributes Book and Course. The predicate could be expressed thus

A UsesToTeach (Book B, Course C)

with the edges in the base graph being:
A x1
UsesToTeach x1
x1 x2
Book x2
x2 B
x1 x3
Course x3
x3 C

Way 2: with a complex attribute type Teaches having attribute Book

A x1
Teaches x1
x1 C
Teaches x2
Book x2
x2 B Received on Tue Nov 22 2005 - 15:50:15 CET