Make your own free website on Tripod.com
back to previous section up to contents on to next section

The Slipnet

a network for knowledge representation


Introduction

The slipnet is a extension of the semantic network representation of a frame (slot-and-filler architecture) or database system. The slipnet consists of objects of two types, nodes and links.

A node represents an object within the system. Although we'll soon see that nodes can be used in a variety of ways, for now let us assume that a node represents a literal (constant) value.

A link represents a relation between two nodes. Links are directed, since in general our relations are too. For example, if our database contains the nodes MrSmith and WashingtonDC, we might express the predicate goesTo(MrSmith,WashingtonDC) (following Prolog notation) as

MrSmith ----goesTo-----> WashingtonDC

Note that this statement is not the same as

WashingtonDC ----goesTo-----> MrSmith

which is rather nonsensical. One of the first semantic networks was implemented by Ross Quillian in order to model structure of human memory.

Hoftstatder's slipnet goes beyond this standard semantic network implementation in two primary ways. Firstly, with every node is associated an activation value, which in a rough sense indicates how important the concept is. A node's activation may change over time, reflecting the changing significance of a concept. Secondly, each link has a length that represents how "closely tied" a pair of concepts are. Length corresponds to the "strength" of a given relationship, allowing a "fuzzy" extension of traditional predicate calculus. Like activation, a link's length may change over time.


Overview of the ROD Model Slipnet

In our implementation, we have sought to both generalize and standardize Hoftstadter and Mitchell's specification of the slipnet. In this section we provide a broad overview of our framework. A closer analysis of the Java source code can be found in later pages.

Our Slipnet is a labeled, directed graph, consisting of Nodes and Links. Each node represents a "concept" within the database, and is required to have a unique name. Nodes have an activation value, which changes over time. Each Link is a collection of three Nodes, a from node, representing the "tail" of the arrow, a to node, representing the "head" of the arrow, and a label node, indicating the relation that the Link represents. As a proposition, a Link would typically be read "from label to" and might be represented in Prolog as "label(from,to)". The label that corresponds to a given Link must appear within the Slipnet as an actual Node, so that "meta-links" can be formed, expressing a relation between relations. (For example, the relations successor_of and predecessor_of may be joined by the relation opposite_of.) In addition, a Link contains intrinsic_length and length values, encoding the default and current "strength" of a relation, respectively.

In addition to the basic Node, we have introduced a number of node "sub-types" that allow the Slipnet to usurp some of the advantages of object oriented databases and frame systems.

A TableNode is a Node that is extended to take advantage of a special class of link, the inst_of (instance of) link. A TableNode corresponds to a table in a traditional SQL implementation, allowing a "class" of objects to be defined. Nodes that are an inst_of a TableNode are known as "rows" in SQL. TableNodes allow us to reduce the number of physical links within the Slipnet, since "class-wide" properties can be expressed by Links of the TableNode, rather than for each individual instance. An instance can, of course, override a given relation by providing its own Link. Tables can be instances of other tables, allowing the recursive refinement of a class of objects.

The real power of object orientation is achieved through SchemedTableNodes, which allow a user to specify a collection of attributes or Links that every instance must provide. A schema corresponds to the specification of a frame. A SchemedTableNode contains a collection of has links that join the SchemedTableNode to a Node representing a link label. Each instance must contain a Link of this type, unless a default value is provided in the SchemedTableNode.

A query language for interacting with the Slipnet has been developed, and is described in the next section.


Comparison to SQL

The industry standard for the creation, specification and interaction with database systems is SQL, the Structured Query Language. Under SQL, data is stored in a fashion quite similar to the standard representation of a spreadsheet.

In SQL, data organized into tables, each of which is composed of attributes (which correspond to the columns of a spreadsheet), and rows. For each row in the table, there is a cell (variable) corresponding to each attribute of the table. Each row is required to "fill in" a value for each attribute. Rows of tables can be cross referenced to one another by providing foreign keys that indicate which row of a given table a row in this table corresponds to. While functional, SQL style database representations of data are restrictive, since all attributes must be specified by the table, as well as expensive, since every cell must be filled. Similarly, the "foreign key" method of cross-referencing data is rather awkward.

RODM solves both of these problems, by providing methods for creating both uniform and heterogeneous databases and by representing each "concept" in the data-set exactly once. In fact, one can formally show that RODM not only achives the functionality of SQL, but surpasses it, as described in another document.

To represent a standard relational table of employee names and phone numbers in this fashion, we begin with a node which will denote the name of the table. We add to the node one link for each attribute or field of the table, and connect it to a a node containing the data for that record. This is essentially a "tree" structure. However, if a row of this table references a row in some other table (e.g. a foreign key to some other primary table), we can simple create a link between the nodes directly, rather than fussing with key values as we would in a relational database. This is a more efficient solution, and makes migrating databases far simpler: It is our belief that database programmers should not have access to the method by which records are keyed (i.e. the physical record number of the foreign and primary keys), but should have an efficient and simple way to cross-reference related information.


Comparison to Predicate Calculus

Like any semantic network, our Slipnet capable of expressing any proposition from first-order predicate calculus. Simple literal expressions, such as "the number seven is prime" can be easily represented, i.e.

seven ----is----> prime

Relations that appear within the Slipnet are assumed to be true, and statements that do not appear are assumed to be false.

Moreover, SchemedTableNodes, together with the RODQL language (described in the next section) allows for the implementation of second-order logic (utilizing quantifiers). For example, the universally quantified statement "for all even numbers X (other than two), X must be composite." may be expressed as:

     EvenNumber has_attribute is.
     EvenNumber is Composite.
     Two inst_of EvenNumber.
     Two is Prime.
     Four inst_of EvenNumber.
     Six inst_of EvenNumber.
     ...
So that "Four is Composite" evaluates to true, while "Two is Composite" evaluates to false. Existentially quantified statements are expressed by the very existence of a relation. Hence the statement "there exists an even number" is implictly encoded by the above statements.

As another example, suppose we are given the TableNodes "mice and "whales" and wish to express the universally quantified relation "biggerthan(whales,mice)". With table nodes, we can express this relation directly.

Moreover, our framework allows the creation of relations between relations. Together with quantifers, this allows users to implement higher-order logic, quantifying relations and relations between relations.

Inference within the Slipnet is simply a search within the directed graph. For example, to determine whether Six is Composite or Prime, we first examine the Links of Six, and then the Link of every table that Six is an instance of, eventually finding the chain "Six inst_of EvenNumber. EvenNumber is Composite."


Comparison to Hoftstadter and Mitchell's Slipnet

In terms of a high level description, our system does not differ greatly from the Copycat slipnet, with the exception of TableNodes and SchemedTableNodes, which allow us to implement the more general frame system (as opposed to a simple semantic network).

At a lower level, we belive that we have effectively streamlined the organization of the framework, simplifying the creation of an arbitrary knowledge base. Moreover, our implementation provides a more symmetric representation of Hoftstatder/Mitchell's workspace, since the creation of meta-relations is built directly into our slipnet and its query language.


Back to the top of this page.


back to previous section up to contents on to next section