Nodes and Lists

The Atomic Units of Knowledge Repository Structure

An explanation of the class/object that forms the “atomic unit” of a knowledge repository. The original inspiration for this discussion are the insights that grew out of Doug Engelbart’s “Unfinished Revolution” colloquium at Stanford in the winter of 2000.

Originally published 2001

Overview and Motivation

The general data structures needed for representing the kind of complex information contained in a knowledge repository were first identified in Requirements for a Collaborative Design/Discussion/Decision System, and was further refined in XML Data Structures. Here, the focus is on object-oriented data structures suitable for programming. (The XML version of the data structures will need to change to reflect the further refinements included here.)

In reality, this document tends to describe two systems. The majority of the description revolves around an initial kernel library (KRNL) that was written in Java. The remaining descriptive material outlines the kind of system that can be built on the KRNL — the kind of system the KRNL was designed to accommodate. In part, those generalized sketches and hand-waving exercises form the real motivation behind the KRNL. It was only in figuring out how the problems could be solved that the KRNL’s requirements were identified. In addition, those “usage notes” show what the next layer in the system needs to do to use the KRNL effectively, in order to solve those problems. Hopefully, the result is still fairly readable and the concepts are not overly (or hopelessly) intertwined.

Note:
At this point, some of the code isn’t even compilable, much less testable. But it provides a foundation to start building on. A list of open issues and action items necessary to complete the design are stored in the KRNL ToDo List. (I’m happy to say that at one point, Lee Iverson had taken up the mantle, and had found ways to improve on the original design.)

Basic Structure: Nodes and Lists

The basic structure consists of nodes and lists. There are many kinds of nodes, and many kinds of lists, but all the elements in the systems are extensions of these two basic types.

In general, a node has both content and structure. For a basic node, the content consists of simple text. Think of a node as the equivalent of a paragraph — a “unit of thought” in good writing practice. Headings are nodes, too. A heading summarizes in a single phrase the contents of a section, and is therefore a perfect example of a hierarchical “unit of thought”.

The structure under a node, on the other hand, consists of other nodes it contains. For example the paragraphs and subheadings under a heading constitute the structure under that heading.

Nodes link to other nodes in a multitude of ways. There is no simple hierarchy, but rather a complex nest of interlinking. That is the only representational mechanism that can possibly parallel the complexities of real knowledge. However, instead of linking nodes directly, nodes are linked through lists. Each list contains a homogeneous collection of nodes that relates to the current node in some way. For example, a structure list points to a collection of nodes that correspond to the structure under that node (also known as its substructure, or its list of subnodes).

So: Nodes are organized into lists, and a list is an ordered collection of nodes. So far, we are describing a simple hierarchy. What makes knowledge repository nodes different from a simple hierarchy is the fact that a node has multiple substructure lists.

Note:
The content of a node is in reality a list. That structure lets node content be expressed as a hierarchy, as well. For example, that structure allows inline elements like bold and italics to be nested arbitrarily deep as part of a node’s content.

Basic List and Node Data Types

To keep the list apart, each of the lists has a type, as do the nodes. The type defines the kind of list or node it is. Depending on the type, the node or list (atom?) may have other attributes, as well. For example, a list structure in a document could have an attribute that describes it as ordered (numbered) or unordered (bulleted). Those are the kind of list-structures that HTML is capable of rendering, but note that the kind of numbers or bullets to use depend on the surrounding context. For example, an ordered list would ordinarily be numbered, but if it were included under a numbered item in another list, then it might well be rendered with lowercase alphabetics: a, b, c, etc.

Internally, then, the system must of necessity consist of a bizarre conglomeration of nodes, each linking to the others in a maze of criss-crossing connections. Externally though, the system can give the appearance of hierarchy. Starting from a particular node and viewing a specific list of nodes under it (and the list of the same type under the subnodes) produces a hierarchy. For example, when structure nodes are viewed, and each subnode’s structure list is displayed as well, the result is a standard “outline”. (In essence, then, an “outline” is a first-order structure, where the number of substructures is equal to one.)

Note:
When a link goes back to a node that exists earlier in the hierarchy, it can be represented in a way that identifies it as a “cycle” in the graph, thus “flattening” the graph into hierarchy, for viewing purposes. It is also possible that in some cases, three dimensional modeling will be appropriate. In such circumstances, multiple kinds of subnodes can be viewed at one time. But for ordinary, every day use, any given view into the network of nodes can be viewed as a hierarchy.

For coding, both to take advantage of polymorphism and to permit validation of internal structures, the generic AbstractEntity and AbstractList classes are defined, and then extended to produce the specific node types:

• StructureNode
• AbstractContentNode
  • TextNode
  • InlineNode
• AttributeNode
• CategoryNode

And the specific list types:

• StructureList
• ContentList
• AttributeList
• CategoryList

Note that the list classes are fundamentally identical to the java.util.LinkedList data type. In fact, they encapsulate an instance of that type and delegate all operations to it. They could simply extend LinkedList, in fact. The reason for defining separate classes is to achieve type safety in the add(), remove(), get(), and replace() operations. That allows us to code:

StructureNode node = structureList.get(0);

Instead of:

StructureNode node = (StructureNode) structureList.get(0);

That becomes even more important when operations are chained, as in the change-reporting operation discussed in the versioning section:

parent.get(n).structureList.reportChange(currVersion);

(In version 1.4 of the Java platform, abstract templating mechanisms are being added. Those facilities may make it possible to easily create type-specific versions of LinkedList.)

An HTML Example using the Basic Types

Here is a diagram that shows how basic nodes and lists combine to render an extremely simple HTML page. (It fits on one page, but doesn’t print nicely when included here).

The node structure is obviously very complex, considering the simple structure it represents. But that complexity is necessary to build the more sophisticated structures that a knowledge repository needs.

These diagrams show the class inheritance and object containment hierarchies for the basic data types:

Attributes and Categories

The AttributeNode class has yet to be defined, will undoubtedly consist of a fairly simple name/value pair. (It may or may not be desirable to allowed hierarchically structured values. I suspect that the added complexity isn’t worth the cost, but that has yet to be determined.

The CategoryNode is a bit more interesting, in that adding a category to a node’s category list must always wind up adding the node to the category’s list as well. So the node will maintain a list of the categories it belongs to, while at the same time the categories maintain a list of the nodes that are included in that category.

Categories must be maintained in a separate set of lists (a tree), that has yet to be defined. Categories references will consist of pointers to entries in that tree. Categories for nodes include concepts like: Response (to an assertion, Comment, Suggestion, Alternative, Question, and the whole gamut of possibilities suggested by Jeff Conklin’s IBIS discussion: The IBIS Manual: A Short Course in IBIS Methodology, at https://www.gdss.com/wp/IBIS.htm.

Since categories exist in a tree structure, it becomes possible to define a hierarchy of categories in the same way that the Traction system does: for example, ToDo:Bug and ToDo:Enhancement, where “ToDo” is a major category, while “Bug” and “Enhancement” are subcategories. It is then an easy matter to select for items in the “ToDo” category, and get the items that match either subcategory.

Versioning

As complex as all the foregoing is, though, it gets infinitely more complex when versioning is added to the equation. The difficulty with hierarchical structures is that either the content of a node or the structure under it may change. So equally important to versioning node content is the task of versioning its substructure.

There are at least two basic mechanisms by which versioning could be implemented:

• Versioning with virtual nodes
• Versioning with category-style lists

Option #1: Versioning with virtual nodes

One way to add versioning is to introduce a VNode (Version Node, or Virtual Node) as well as a VList (Version List, or Virtual List). Such nodes would automatically dereference themselves so that, by default, the system is always dealing with the latest version of a node.

To do that, the VNode must maintain a pointer to the latest node (or list), and the node (or list) must maintain a pointer to the previous version. When a get() operation is invoked on the VNode, it delegates that operation to the latest version. But when a set() operation is invoked, the VNode makes a copy of the current node and sets its “previous version” pointer the the current node. VNode then delegates the change to the copy. After the change is made, the now-modified copy becomes the new current node.

Issue: Competing versions

In a distributed system, version identifiers will be needed, as well, and those identifiers will need to be namespace-qualified in order to distinguish competing versions produced by remote users who have made independent, but conflicting modifications.

The addition of versioning to the system already raises the complexity bar to new highs. But the need for truly distributed operation, and the concomitant possibility of competing versions, gives the term “complexity” entirely new dimensions of meaning.

At bottom, the system needs the ability to detect competing modifications, create a meta-node that points to them, and leave it to the users to determine which version (or a newly edited copy thereof) will become the “official” version. Since any further edits that come via the normal pathway would simply be added to the list of competing versions, a special resolveTo() API is needed that takes a new node (or list) as an argument, which becomes the new version. After resolveTo() is invoked, the previous-version pointer must reference the competing-version list.

So much for the functional requirements. That’s the “easy” part. The harder task is to identify the data structures that will permit such functionality to be developed. At this point, the VNode solution appears to break down, since it doesn’t include a good mechanism for maintaining lists of competing versions. (There may be a patch that would fix the problem, but at the moment I don’t see it.)

Option #2: Versioning with category-style lists

The next option is to do versioning using the moral equivalent of category lists. The version list would contain version nodes, and each version node would identify the (namespace-qualified) version, and point to that version.

With this model, there is no dereferencing step when accessing the current version of a node. A performance penalty is only incurred when accessing a previous version.

When a set() function is invoked to make a change, the current version of the node is copied. The new copy keeps the old ID, but of course that is copy is not the one that the rest of the system is referencing. The existing node (not the copy) therefore needs to get an updated version number, along with the modifications. That way, other references to the node always get the latest version.

A new version node is created that points to the copy. The current node can then be modified. (As an implementation detail, the version list might actually reside on a completely separate storage device, producing both stronger redundancy and higher performance.)

Note:
It is occasionally desirable to define a link (reference) that is invariant. That is, regardless of how many changes the node goes through, the link points to the same version that existed when the link was created. To do that, the link needs to specify the version(s) for the structure node it points to. The system then needs to reconstruct that version of the node when accessing it.

How Versioning Works in a Node Graph

Up to this point, we’ve been carrying on the discussion as the though the term “node version” makes sense. But it’s time to clarify exactly what it means to add versioning to a system that consists of a complex network of information nodes. The first question is: how is used? The second is: How does it work?

How versioning is used

There are two important uses for version information. The first is to recover old versions and undo changes. That kind of capability lets you see how a document evolved over time. It lets you restore a previous versions. And it lets you see who made what changes, when.

A possibly even more important use is for change-detection. When new messages arrives in your inbox, they are highlighted, and flagged as new. The goal is for changes to documents to do the same thing — to display in your system with differences highlighted, so they are easy to find. Like the messaging system, when you view the new and modified nodes, the system can cease highlighting them.

One way to achieve that goal is to do differencing when new documents arrive. But that process requires entire documents to be transmitted, and it is computationally intensive. But if the system maintains version information anyway, that information can be used to detect differences. That strategy increases the complexity of the system, but improves performance and minimizes data transmissions. Since version information needs to be kept anyway, for historical recovery, it makes sense to use it as a basis for differencing.

Note:
A difference engine is still required to detect changed nodes, but instead of comparing old versions to new versions, it can simply look for nodes and lists that have a more recent version identifier. That process is much faster, and much easier to distribute, than the traditional differencing approach. Of the two, it the ease of remote operation that is most important. With a version-based differencing engine, a remote system can tell a target system: “Here is the latest version I have — send me all your chagnes.”

How versioning works

Consider the most fundamental unit in the system: the StructureNode. A structure node contains pointers to a the node’s contents and to its substructure. But what if either of those changes? The StructureNode itself would not have changed, but the information it points to would have. More to the point: what if the structure under the node changes in some way, many levels down?

In all of these cases, references to the original StructureNode would be pointing to a node that hasn’t changed, but whose underpinnings have — unless those changes are reflected in the StructureNode.

But how are the changes to be reflected? The mechanism of copying the StructureNode and storing it in a version list leads to severe resource consumption because every change, no matter how trivial, requires the creation of new StructureNodes, from the changed node all the way up the parent chain. Clearly, that kind of implementation is not a good idea.

The alternative is to track the latest version encompassed by each StructureNode. Then, when a change occurs, the version information is propagated to all of the node’s ancestors. Each ancestor StructureNode stores the latest version information, thereby identifying changes to its substructure.

Such a mechanism implies several requirements:

Multiple version variables

Since a StructureNode has multiple sublists (a content list, a structure list, category list, etc.), it must have multiple “most recent version” indicators, one for each list. That’s easy to do, though it was initially unexpected. (At first, it seemed that a single version list would suffice, but that was on the assumption that the StructureNodes themselves would be versioned. On reflection, that seems like a bad idea for performance reasons. The good news, though, is that StructureNodes are infinitely more stable with this approach. Although their contents may change frequently, the nodes themselves will be fairly permanent. Even when deleted by the user, they will be referenced in the previous version of at least one StructureList that contains it.)

 

List Versions

Recall that the most recent version identifier propogates up to all parents. For any given StructureNode, then, the actual change might have occured many levels deep. That implies the need to keep two version identifiers for StructureList objects — one for the list itself, and one for its contents. If the version ID in the StructureNode tells the difference-engine that something has changed in the substructure, but the StructureList’s identifier is the same, then difference engine knows to look deeper in the substructure.

 

Finding Changes

When the difference engine compares the latest StructureVersionStamp in a StructureNode to the user’s latest StructureVersionStamp, and sees that some change has occurred, it first needs to see if the StructureList itself has changed. If it has, the change information (either the new version of the node or a structure that includes differences) must be delivered. If the StructureList hasn’t changed, then of course that work does not need to be performed.

But, in either case, the engine needs to process the StructureList, inspect every StructureNode in the list, and check its version identifier. When no change has been made to the StructureList itself, the need to do that is obvious — if the StructureList didn’t change, but the StructureNode above it has a more recent version identifier, then a change must have occurred in one or more substructures. But if the StructureList did change, the substructures still need to be checked, because they might contain a change that is less recent than the change to the StructureList, but still more recent than the last version the difference engine is comparing against.

Of course, when doing the processing, the difference engine needs to be on the lookout for nodes that have been removed, and it needs a way to communicate that information to the target system. (The mechanism for handling deletes gets a small section of its own. That’s coming up.)

 

Comparable versions

The really difficult issue in a distributed system is the need for comparable version identifiers. Qualifying the version identifier with the user’s globally unique ID solved one problem — making it possible to distinguish one person’s changes from those made simultaneously by another — but it leaves open the problem of comparing version identifiers. But the process of comparing identifiers is fundamental to the operation of the differencing engine, so some comparison mechanism needs to be found.

Time stamps could be used for that purpose, but we probably don’t want to force the user to be online connected to a time server in order to make changes. And we probably don’t want to check the time server every time we make a change. However, the system might very well keep a list of nodes that have been changed. Then, after going online to exchange differences (but before doing the differencing) it could get a timestamp from one of the many synchronized time servers, and update all of those nodes with the timestamp.

Note:
If time is not set on a version until we go online, then multiple changes to the same node could wind up with identical time stamps. Not good. To fix that, the KRNL’s VersionControl class subtracts the number of entries in the version list from the current time, and then gives each as-yet-unstamped version its own millisecond-unique time stamp, on the theory that it takes more than a millisecond to create a new version of a node. (Computers aren’t that fast — yet.)

That means the VersionStamp class needs an API for setting the time, and the ability to throw an exception if VersionStamp information is accessed before the time has been stamped. Also, rather than having the time supplied as an argument The internal mechanism should get the time itself, to be certain that it comes from a trusted source. The location of the nearest time server could be configurable, but making sure that the time comes from such a server is the best assurance possible that the time is correct.

Globally Unique IDs!!

The combination of a globally unique userID and an accurate time stamp produces an (almost) unique node ID — on the theory that no one user can create two different nodes at the exact same time. Interactively, of course, that is true. On the other hand, the user might have some automated processes running on different systems. But if the version stamp adds the systemID to a millisecond-level time, synchronized-clock time stamp, then duplicate nodeIDs should be effectively impossible. Of course, if the user were running separate processes on a multi-CPU system, collisions are still theoretically impossible. But if the systemID includes a CPU identifer, even that possibility is removed.

Of course, that is a lot of information to carry around for each node. But system IDs and userIDs can be referenced from multiple nodes, so the actual resource cost is only a couple of extra pointers. In addition (fortunately), computing resources are rapidly becoming more abundant and less expensiive.
 

No Setters

Although the system abounds with get methods, there are virtually no set methods. The only way to set the values in a node is by constructing a new one. That is intentional. Making any sort of change therefore forces the construction of a new node, so the old one can be stored in the appropriate version list.

Note:
There is an interesting internal difference between, on the one hand, content lists, structure lists, and category lists and, on the other hand, version lists. One difference, of course, is that the version list should not itself contain versions! But there is another more interesting internal difference that is tantamount to a semantic difference. Content lists and the like are fully contained by a node. That is, the node contains a list, which in turn contains elements which make up the content of that node. But a version list does not exist as a list that can be accessed in that manner. Instead, each node contains a pointer to the previous version of that node. The chain of pointers constitutes a list, but only the head of that list is visible from any given position, not the entirety of the list.

[I remark on this fact only because the need to treat the two kinds of lists differently was not clear to me for quite a while. There is some distinction between these two kinds of lists that I have missed. I note the fact that they must be treated differently, while awaiting the philosophical insight that would have made the necessity for doing so abundantly clear at the outset.]

Undo Information vs. Old Nodes

When storing difference information for lists, it makes the most sense to store UNDO information, because that will be a relatively small amount of information, on average. If many changes occurred, though, it make more sense to copy the old version, rather than attempt to record all the maneuvers that led to the current sequence of nodes. (Imagine shuttling a list around a few dozen times, and leaving things almost exactly the same as they were before. Calculating the real difference would be hard, and saving all of the changes would be painful. The easiest way out is to save the old version intact.

For TextNodes, though, it may make more sense to store the old version of the node. (On the other hand, if UNDO information is kept by the system anyway, it may be easy to store that, as well.)

For both lists and text nodes, then, it might be desirable to store old version information as either the original verison or as undo information. When modifying a list, for example, the original version can be saved. After the user is done making changes, the list of changes can be compared against the original. Whichever is shorter can be kept. Polymorphism can be used, so that a getOriginalVersion() method provides the old value, regardless of how the data is kept internally.

Handling Deletes

There are several possible mechanisms for reporting deletes. Since the new version of the list will be delivered to the the user’s system, along with the version node, the system could do an inspection to find out what has been inspected. But if several items have moved, and some added in a lengthy list, the process of inspection could take a while.

A better solution is to insist that list changes are reported as UNDO information. Deleted nodes are then identified in the undo list. After requesting an update, therefore, the user’s system should receive new nodes accompanied by the undo information necessary to restore them to their previous versions.

Publish/Commit

Thinking about deletes brings up the issue of cut/paste “transactions”. In general, the user needs the capacity to make changes in a hierarchy without worrying about other systems seeing those changes before they are complete. Imagine the yelling if you were moveing a document, and someone requested an update after it was deleted from its new location, but before placing it in its new location. On a larger scale, you may be recording thoughts that are not yet sufficiently well organized to withstand scrutiny.

In essence, you need a separate area in which to work on things. You need to “commit” the changes, the same way you commit a database transaction. That area might be implemented as a copy of things you are working on, or it could be implemented by adding a “committed” flag to the version stamp.

A related concept, though, is that of public and private views of your personal repository. Or, even better, specific views that you share with others. You might have a professional view that you share with co-workers, and multiple hobby views that you share with others who have similar interests. That way, when someone interested in your music group requests updates, their system deluged with anything and everything you are working on.

One way to create the necessary partititioning is of course to have multiple systems. But that precludes interconnections among the information and ideas you have gathered from different sources. A better idea is to use the category structure, and to require all update requests to specify one or more categories. That idea, coupled with the UserID information in the request, lets your system check the request against its Access Control Lists (ACLs).

Back to Competing Versions

The only remaining issue is that of competing versions. The first part of that issue involves detecting the existence of competing versions. Since remote users will be updating nodes independently, it is not possible to use a monotonically increasing version number. A date/time stamp could be used — but only if it was obtained from the same server, or if the accuracy of user’s system clock can be guaranteed. A third alternative, that probably makes the some most sense, is to qualify an incremented version number with the globally unique ID of the user’s system.

When a change is made, both the modified node and the new version node are broadcast (or narrowcast, as the case may be). The ability to detect competing versions is made possible by the version node. If the newly-received version node points to a node with a ID different from the current node, then a competing version has occurred.

The second part of the competing versions issue involves the ability to maintain a list of competing versions. Having identified that competing versions exist, what is the system to do?

The answer is to use links. A new node (StructureNode) that acts as a conflict indicator can be constructed who’s contents read: “Conflicting changes made to these entries:\n”. That text can then be followed by links to the nodes in question. The process of constructing those nodes will be fraught with complexity, but in principle it is doable. The new node then takes its place at the point where the conflict begins. The system’s users can then begin the task of sorting out which version (or edited version) should replace the conflict indicator.

Remote Updates

In a distributed, peer to peer architecture, the problem of remote updates must be solved. When another machine connects to the our system, how do we know which nodes to send it for updates? When we connect to another system, how do we know which nodes to retreive?

Unless we can depend on accurate timestamps (a thought that may be worth considering), we’ll need to know what we have in the way of nodes authored by a particular user. When we connect to a system, we can get the the globally unique ID of that system (or, more likely, that value will be derived from the http address we used to make the connection). We can then search our system for any nodes with that system attribution, and ask for any nodes later than that. (We only need to do that search when we connect to a new system. We can store the value for use thereafter.)

To satisfy such requests ourselves, we need to keep a list of the nodes we have created, ordered by node ID. That can be done in the factory class. (Note: When we modify a node, the existing node gets the new ID and the new copy gets the old ID, the factory’s list must therefore be updated so that the old ID value points to the correct node. And the entire ID-change + factory-list-update process must be atomic.)

Links, Contained Nodes, and Parent Lists

The complexity of the node graph increases with the number of interconnections among nodes. One kind of connection is the now-standard link, like those found in HTML. Another kind of connection is that of parent to child, which in its simplest form produces a hierarchy. However, in this system a child can have multiple parents, which greatly increases the complexity of the system. Although any one view of the system is a hierarchy, the underlying data structure is a graph — which means that the display system must be on the alert for cycles when expanding a node for viewing.

The parent connetion is particularly important, since changes in any subtree must be reported to all parents in the hierarchies to which the changed node belongs. So working out the parent-chain responsibilities is critical to versioning process. The other critical part of the versioning process is the saving of old versions, or the undo information necessary to reconstruct them. That process is worked out in the next section.

Links

Links are maintained in the system using link nodes. Link nodes are similar to inline nodes, in that they are represented as part of the normal flow of text in a node. But they are different in that they must store information that is unique to each lnk. Because of their unique storage requirements, they form a new branch of the class hierarchy:

• AbstractContentNode
  • AbstractLink
    • UrlLink
    • NodeLink

For an HTML-style link, for example, a link needs to store a URL. For an internal-node link, a link needs to store a reference to the target node, of course. More importantly, it needs to store information that describes the view to use when the link is traversed. This concept was first introduced at Stanford, circa 1968. For more information, see Doug Engelbart’s NLS System (review of 1968 video).

Note:
The granularity of the current system is the node, e.g. a paragraph or a heading. A link always points to a node, never within it.

Link Types

In addition, a link needs to store a link type. Link types are a restricted, non-hierarchical set of categories that let the user decide how various kinds of links are displayed. An initial set of link types might include:

• glossary
• citation
• __?other?__

For glossary links, for example, the display system might use normal text, with no highlighting or underlining. The fact that a link is available becomes apparent when the cursor is over the word, but otherwise the existence of the link does not interfere with the readability of the text.

Link Display Policies

The text of a link is always displayed. The link may be represented in some “invisible” fashion, like glossary links. But existence of the link is always discernible in some fashion, if only by a change in cursor shape. And the text of the link is always in view.

In fact, it would be useful to define a link display type named invisible. That type would always take on the the size, font, and color of the text that immediately precedes it. Links of that type would not change their appearance when the target they point to is modified.

For other link types, the display policy needs two mechanisms: one for a normal link, and one for links whose target values have changed. That gives the user a way of knowing that linked material has been modified.

However, parents of the link node are not notified of the change. There may some value in doing that, but it would be extremely difficult to do in the current system. In general, then, a linked document is loosely coupled to the current document. That is, changes in the underlying material, while of interest to the user of the current document, are not so much a “part” of the current document that the current document must be considered to have changed if the underlying material changes. (For tightly coupled connections, see the section on Contained Nodes, coming up.)

Node Names and Link Types

Structure nodes and inline nodes have names, while links have (hard-coded) link types. Hard coding the types creates specific link classes. That makes for greater type safety, but is of course harder to extend. The number of link classes seems small, though, so it seems like the right thing to do.

For structure nodes and inline nodes, on the other hand, the name is a string that is specified when the node is created. That makes the structures as extensible as XML — you can add any kind of node you want, at any time. On the other hand, it is also easy to define nodes that the display system has no idea how to handle.

It seems reasonable for the display system to define some default behavior for nodes it does not recognize. For example, it could display the node name and intent its contents by a default amount. That would make the hierarchcial structure clear, at least.

When importing an XML file, in fact, the only information the import system really needs to know is which XML elements are inline elements, like <b>, <i>, etc. With that information, the import mechanism can construct the appropriate node graph. The import mechansm can even handle XML “mixed content”, when text and/or inline elements occur in a non-content location — somewhere after the first structure element in a list. A new structure node can be created to serve as a home for the misplaced text, and given a name like “unexpected text”. The display system can then highlight that text in red italics, or some such.

Contained Nodes

Although similar to links, contained nodes form a tightly coupled connection between documents. They have more display options, and they are considered an integral part of the current document. When a contained node changes, the current document is marked as changed, as well. (However, the access controls for a contained node is still determined by the context the node came from, rather than the context it now resides in. That discussion is yet to come.)

With the exception of access-list processing, a ContainedNode is essentially equivalent to a structure node, and can occur anywhere that a structure node would occur. In fact, a contained node encapsulates a references to the original structure node. In XML terms, every node is an “entity” that can be included at any point in any hiearchy.

Note:
Since the underlying implementations are vastly different, there is no good way to convert links into contained parents, or vice versa.

Contained Node Types

Like links, ContainedNodes have a type. (TBD: call it a link type? containment type? other?) Initially defined types include:

• comment
• reference
• quotation
• __other??__

The fact that references are distinguished from comments, for example, allows the user to control the display in interesting ways, by setting up preferences that say:

• “Display references as colored, underlined links” (like typical HTML links)
• “Hide comments” (to focus on the original document)
• “Display comments inline” (for a SlashDot-style view)

Display Possibilities

The prefences shown above illustrate the three basic display mechanisms for link types: show link, hide link, and show target content. The existence of the types lets the user customize the display.

Note:
Since links occur as part of a node’s content, it doesn’t make much sense to allow the “display inline” option. But that option makes a great deal of sense when a node is included in another hierarchy, as a contained node.

Parent Lists

The hierarchical parent/child relationship is a much stronger connection than a simple link, because any time a node changes, its ancestor hierarchy is informed of the fact. The notification traverses up the chain from parent, to grandparent, and on the hierachy until no more parents are found.

However, in life, one alwyas has at least two parents. And when you include godfather and godmother, the list of potential “parents” increases to four.

When reference to a structure node is encapsulated as a contained node, the structure node, in effect, acquires another parent. It therefore requires a ParentList to keep track of the parent lists it belongs to, so that allparents can be notified in the event of a change. It is the existence of contained nodes and parent lists that turns the underlying data structure into a graph.

Displaying Contained Nodes

At this stage of development, nodes do not display themselves (although at some point, they should). To do that, they could be passed a ViewControl object and a graphics context with an API like this:

AbstractNode.display(GraphicsContext g, ViewControl vc)

The method would then delegate the display operation to the graphics context, which would handle the details of doing the graphic representation of the node’s content and substructure.

In the ContainedNode class, that method would be overridden to check the appropriate Display Policy object and see how the structureNode it contains should be displayed. If the display policy were “show target content”, then the call would be passed on to structure node. If the policy were “show link”, then a link -representation would be displayed. And if the policy were “hide link” then (version permitting), then method would simply return.

Summary of Display Functionality

If the target of a link changes, and the link should be highlighted, to show that the underlying material has changed. If a contained node changes, the display is also modified. In addition, the change notification proceeds up the chain to all parents.

The following table summarizes the functionality:

Display Policy	LinkNode (weakly coupled)	ContainedNode (strongly coupled)
Hide Link	N/A	Version change recorded. Link becomes visible (very pastel).* Parent nodes notified.**
Show Link	Version changes recorded. Appearance of the link is modified.	Version change recorded. Appearance of the link is modified. Parent nodes notified.
Show Content	N/A	Version change recorded. Appearance of changed nodes modified. Parent nodes notified.

*Note:
Given the ability to hide nodes, it becomes necesary to figure out what happens to them when they are modified. If the link were to stay hidden, and parents were notified, the user could hunt in vain for the cause of the change-notification. And if parents weren’t notified, the entire change-notification mechanism is disrupted. The only alternative is to make the node links visible, perhaps in some very subtle way, for example by using a very pale pastel color, so that the notification is as unobtrusive as possible.

**Note:
When parents are notified that a change has occurred, the display system can use the excellent hierarchical-highlighting mechanism that Netscape’s Messenger email system provides. If a heading is collapsed, then it is highlighted to show that has changes. But if it is expanded, the changed nodes underneath it are highlighted, but the heading itself is no longer highlighted. When a node is “touched” by the cursor, the highlighting disappears. (TBD: Does a touch consist of a click or a mouse over?) Other useful functions include “untouch” (turn highlighting back on) and “go to next unread item”, to traverse to the next change.

Categories, Relationships, and Properties

The section considers the issues surrounding categories. It covers how categories are defined and used, and how they might be displayed.

Defining and Using Categories

StructureLinks let the outer system implement some highly interesting behaviors using the kernel. In particular, they allow for:

• Relationship Categories
• Smart Quotations

Relationship Categories

Some of the “categories” defined in the IBIS methodology are, in fact, relationships. So the “categories” argument:for and argument:against are in reality not intrinsic properties of a given node, but instead define the relationship of one contained node to another. One can easily imagine an argument for one position being used as a counter argument in another context, so it is clear that the “for” and “against” concepts represent relationships. (One shudders at the thought, but there is the very real possibility that the same node might be used as an argument for a position by one person, and as an argument against by someone else!)

Terminology:
Let’s define two kinds of categories: relationships and properties. That choice of terminology will let us distinguish between intrinisic aspects of a node (properties) and extrinsic, context-dependent aspects (relationships), while still allowing us carry on a general discussion using the generic term (categories). Examples of intrinisic properties include: Feature Requirement, Design Note, Implementation Idea.

The ability to add categories to StructureLinks creates the means for tracking relationships. Categories added to StructureNodes, on the other hand, define properties. When a node is referenced in some other hierarchy, the property list is referenced, as well. So all of its intrinsic properties are visible in the new setting.

Smart Quotations

When a StructureLink relationship is defined as a “quotation”, that relationship can cause the outer system to do several interesting things. It can:

• Cause the included material to be margined on the right, as well as indented on the left.
• Cause quotation marks to be added at the beginning of every paragraph (and possibly at the end) to remind the reader of a lengthy section that the material is quoted.
• Cause the linked node’s parent list to be searched for a BOOK, or ARTICLE node, identify its author, and add the appropriate citation at the end of the quotation.
• Collect all such information in some predefined References section in the current work.

  Note:
  The ability to search the parent list implies the ability to search the original parent hierarchy, excluding any other hierachies the node may have been included in. The kernel must therefore make it possible to distinguish those two cases.

Displaying Categories

Different users of the system will define and utilize different categories, for different purposes. At some point, the list of categories that apply to the average node probably begins to get longer than the node itself. In addition, many categories that are useful in one usage context may constitute “noise” in a different context.

For example, “design anthropologists” may trace the course of a design discussion, adding philospophical labels to the discussion. The intent may be to see how decisions are actually reached. So they may add labels like argument ad hominum, appeal to authority, vehement denial, stubborn refusal, counter example, war story, and so on. The intent might be to determine which arguments tended to be most persuasive in a design discussion. (So they might find that from a “respected old hand”, a war story was found to be effective 90% of the time, while from an “unknown newbie”, appeal to authority was the only effective tool in their arsenal.

While fascinatiing, and useful, it is easy to see how categories added for such secondary purposes would begin to clutter up the view, from the designer’s perspective. Such categories should of course have their own slice in the category hierarchy. In the example above, the category tree might have a section entitled “ArgumentType”. The assigned categories, then, would actually be something like: ArgumentType:AdHominum, ArgumentType:AppealToAuthority, etc.

The user of the outer system should then have the ability to restrict the categories that are displayed. At one stroke, the user should be able to show or high display of all categories in the ArgumentType subtree.

Versioning and Undo

In addition to informing parents of changes, the versioning system needs to store the information necessary to reconstruct prior versions — undo information. Lists need the ability to undo adds, deletes, and rearrangements of node order. And text nodes need the ability to restore old versions of their text.

The issues of versioning and undo are very nearly twins. The two concepts are similar enough that it is very tempting to merge one into the other. When editing a document, its important to keep track of changes, so they can be reversed. For useful versioning, you want the ability to show what has been changed. So why not accomplish both goals with the same mechanism?

The Need to Collapse Undo Info

There is only one condition that needs to be fulfilled to convert undo information into versioning information: the ability to collapse multiple bits of undo information into a single bit of versioning information For example, suppose we add this text to a paragraph:

The sam way we did it before.

And then realize we made a spelling error, and correct it:

The same way we did it before.

For undo, that’s two operations. But for versioning, the result is a single change. Similarly, we might move a list item once starting from a list like this:

• a list item
• another list item
• the item that moves

To a new position:

• a list item
• the item that moves
• another list item

And then move it again:

• the item that moves
• a list item
• another list item

To the undo system, that is two moves. But to the versioning system, it’s only one. More importantly, if the item moves back to its original position, the versioning system should report “no change”.

Using the Unstamped Version List

The unstamped-versions list provides the perfect mechanism for finding the relevant bits to collapse. Until the user actually commits the material and “publishes” it (by going online and synchronizing with another system), there is no need to worry about collapsing anything, so that list can function as a global chain of undo operations.

When the user does publish changes, the items on that list can be inspected. If complete copies of old versions have been stored for undo operations, then intermediate undo operations can simply be discarded, leaving the final version and the original version. However, while that mechanism is the easiest to program, it makes it hard for the display-system to highlight changes — particularly when lists have been reordered.

A better mechanism is to package up the list of undo operations into a single version-change. The display system can then use the undo information to highlight changes. It needs mechanisms for identifying deleted material, new material and, in the case of lists, moved material. Let’s say it uses the normal mechanisms of strikethrough text for deleted material, and color italicized text for new material. Suppose it uses dark green for new text. For a list item that moved, it might use a light green for the item in its new position, and strikethrough for the item in its old position.

Of course the display system has to do the appropriate “collapsing” in the display. For example, the list move should appear as:

• the item that moves
• a list item
• another list item
• the item that moves

and not:

• the item that moves
• a list item
• the item that moves
• another list item
• the item that moves

  Note:
  When moving a node from one list to another, both the old version list and the new version list are changed, but the node itself remains unchanged. Full text highlighting is fine for short examples like this. But if the node is an entire paragraph, or if it is a header for an entire section, then full highlighting doesn’t make much sense. The system probably wants to do something less visually obtrusive, although still visually discernible.

KRNL Requirements

For the system to process the unstamped version list effectively, either the versionStamp must contain a pointer to the node that changed — and point to the most recent version of it — or else the unstamped version list must actually point to the nodes themselves, rather than to the versions (which probably makes more sense). Each node can then maintain its own list of version changes.

In addition, the KRNL must somehow provide a meta-level of versioning information that combines all changes to a node into a single set of changes. When versions are time-stamped, the collapse operation can then go into effect, producing the equivalent of a single version-change (for a node or list) from a set of undo operations.

Saving Undo Information

The Undo classes provide the capability for identifying changes and reconstructing prior versions.

Managing Access

The system needs mechanisms for restricting read access. There are many possibilities:

• The mechanisms might be as simple as using two different categories for published/unpublished material, or it might be as complex as having access control lists that use group affiliations to determine what a given individual can read.
   
• The access lists might be created using the existing category mechanisms, or they could be implemented using a separate set of categories.
   
• Authoring-control mechanisms are also needed, so that the users who are allowed to modify a particular node hierarchy (in its original location) can be restricted to some specific group of collaborators. Those mechanisms could be part-and-parcel of the access control mechanism, or it might be useful to separate them into two different lists, one for read-access, and one for write-access.

The exact nature of those mechanisms has yet to be determined. Some form of list processing will undoubtedly be involved, but the most serious general question for the system design is determining how access controls will work in a multiple-parent list.

With a simple hierarchy, it would always be possible to travel up the hierarchy in search of access permissions. That has a certain appeal. If person X is given read or write permission to node Y, then that person retains that permission in the entire subtree rooted at Y, without having to replicate those permissions at every node. But in a multiple-parent list, how does one determine which parent has the appropriate permissions?

One solution is to differentiate between the node’s original parent and any containing nodes it might belong to. However, if that node were removed from its orginal list, it would then be left with no parent at all, even though it be contained in several other lists! From the standpoint of determining access controls, then, that alternative leaves the system with situations it is powerless to resolve.

As a result, it is assumed that when a new node is created, its access controls are always copied from the current context. After all, the user always has some context — some location in the system. When new nodes are created, they are inserted into the sublist rooted at the current node. The current node’s access controls are then copied to the new node. (In general, that copy will be “by reference”, so the actual system cost need not be too high. But every node needs its own pointer to the access controls.)

If a user wants to modify a node they only have read access on, they can always copy the node (along with the subtree under it) and insert it into a new location that they control. They can then make all the modifications they want. When copying a node, therefore, its contents, categories, and substructure are copied, but it’s access list is not. The access list is set when the node is inserted into the user’s list.

A corollary to all of this is that when you change access permissions on a node, the system must create a new version of the access list and then recursively descend through the subtree so that all nodes point to the new list. (In the process, of course, the system will skip ContainedNodes, which always retain their original access controls.)

User IDs

At some point, it should be possible for the using system to automatically turn userIDs into links that go to information about that person. Some interesting observations about that process:

• Links should be URNs
  The location of the information could change, or it could be cached locally. So Universal Resource Names (URNs) should be the norm, rather than Universal Resource Locators (URLs). This requirement implies the existence of some external agency that maps URNS to URLs.
   
• Links should be view-controlled
  A person plays many roles in their life. The “role” a person plays with respect to any given contribution needs to be reflected in the view of that person that a user gets when traversing the link. So I, acting as a “health author” would present one view, while I acting as a “technical contributor” would present a different view.

To do that, a UserLink class is needed. In addition to a UserID , the UserLink class would maintain a ViewControl object, the same way that a NodeLink does. The UserLink could then be displayed wherever an attribution is to shown.

The possibility for doing this is mentioned here, but it is not yet clear where the responsibility for its implementation lies. From the standpoint of the kernel, a user ID, system ID, date/time stamp are all that is needed to ensure uniqueness of nodes. At the same time, links that deliver author-information clearly need to be qualified with respect to the author’s “role”.

Note:
The term “role” is consciously chosen for its “intentional ambiguity” (Paul Fernout’s term for a concept I have previously considered “creative ambiguity”.) On stage, a person “plays a role” in the sense that they present a particular view of themselves, displaying some set of characteristics. In collaborative activities, a person “plays a role” in the sense that they fulfill some purpose in the collaboration. The term “role” therefore implies both meanings: as a view of an individual, and as a part of an organization (ad hoc or otherwise).

One possibility is that a person’s role, or view they present of themselves, is defined at some point in the hierarchy. That role information would then be used in all branches of the subtree stemming from that node. The UserID would always be the same, the UserLink would therefore reflect the current context.

That kind of implementation raises the interesting potential of nodes which exist in different contexts. Let’s say I write a bit about nutrition, which includes a section about its effect on creativity. Later, the concept of creativity is reused in a piece about how one goes about the process of designing a system. The “creativity” section therefore has multiple parents, and might well be dual attributions for that section, to the author “as health expert” and to the author “as technical contributor”.

Possible Extensions

These are additional features that may very well be an important part of the kernel. However, the motivation for adding them is not abundantly clear, at the moment. (They may be “nice to have”, rather than “must have”.) To keep the complexity down to manageable levels, they have been left out of the kernel, at least for the moment.

AttributeNode, AttributeList, AttributeListener

These nodes would add attributes to structure elements. The implementation would be patterned after the category classes.
 

FreeNode, FreeList, FreeListener

A node with a name supplied by the user, contained in a list that also has a user-supplied name. These classes would allow the addition of arbitrary lists to a StructureNode, making it possible to extend the system in ways not yet imagined. However, the flip side of that complexity is the need to to runtime type checking, which can get expensive, and the possibility of corrupting the knowledge base by making an invalid assignment that the rest of the system does not know how to handle. As a result, this feature implies the need for a concomitant “validation and repair” tool that would inspect all lists, make sure they contain the right things, and summarily remove any foreign objects found in them.

Copyright © 2001-2017, TreeLight PenWorks

Please share!