Open Hypermedia Systems Working Group

Domains compendium

1997.10.15

5.0 Domains

The OHS is looking into developing standard protocols for many different kinds of structure servers. Although the group began its work by looking at standardizing a protocol between link servers and their clients, we have recently expanded our focus to include other kinds of structure, such as that found in spatial hypertext, taxonomic hypertext, or transclusion structures. Work in these other areas is still immature - nonetheless, we intend to address these areas in the near future. Currently, only the navigation area is under active development.

5.1 Navigation domain

There have been a number of "open" hypertext systems discussed in the literature, but as yet these systems do not inter-operate. Meanwhile, the World Wide Web has been universally adopted, and part of this success must be attributed to the open protocols, which have allowed system developers to produce their own servers and clients which inter-operate with others. This section presents a general data model for hypertext and proposes a standard protocol for client side applications to communicate with link servers for the purpose of storing, retrieving and navigating hypertext objects. Adoption of this protocol would enable developers and researchers to re-use standard viewers and link servers within their systems.

• Introduction
• A Common Data Model
• The Assumed Architecture
• A Proposal for an Open Hypertext Protocol
• Future Work
• A Discussion on Behaviors, v3 (also available, v2 and v1)
• Appendices
• A. Location Specifications
• B. Presentation Specifications
• C. Content Specifications
• D. Script Specifications
• References

The mailing list for the group working in this area is called ohs-nav. To subscribe, mail a message to listproc@csdl.tamu.edu with a message body "sub ohs-nav <your-name>". Once you are subscribed, you can post to this list by mailing your post to ohs-nav@csdl.tamu.edu.

5.1.1 Link traversal behavior v0.3

Still to do:

1. Provide IDL to ground the discussions of traversal behaviors.

2. The descriptions below finesse the refID vs refSpec question by using ref throughout. Need to decide exactly what form of ref we're trafficking in for the operations described here.

3. Need a better name than "client foo". See comments before Ken Anderson's code in Section 5.

4. Add links to other OHS web pages arising from the Århus workshop. I couldn't find where these are. See my comments in brackets in the opening paragraphs, and in the first paragraph of Section 4.

5. From Ken Anderson: "I think we should specify how the server maps from a ref to a particular client application. I.E. there must be someway of doing ref1 -> FrameMaker so that something (most likely the client foo) can invoke FrameMaker if it's not already running." Ken has some ideas on how to do this. Should that be here or in its own document?

----------------

Updates 12/08:

• Modified the language in a few places to be less minutes-like.

Updates 10/15:

• Incorporated Andrew Pam's three suggestions: The major one is to the description of nodeSpec in Section 1.
• I added Ken Anderson's proposed code skeleton for bundled/unbundled link traversal interaction between client and server, to Section 5.

This document is based on the Open Hypermedia Workshop 3.5, and covers possible behaviors that the open hypermedia interface (OHI) should support during link traversal.

This discussion of link traversal behavior depends on our choice of model (a.k.a. data structures), which is described in more detail above. We start with a short recap of the model.

A few bits of the model

Briefly the OHI model is founded on a general notion of reference, called ref. Refs include a nodeSpec and locSpec. A nodeSpec specifies a node, a wrapper of content stored inside or outside the hypermedia system. A node can be thought of as an author's declaration of some content as a "document." A locSpec specifies a location within the contents of such a node. Given a ref, it should be possible to open the document(s) associated with the nodeSpec and position the viewer at the location of the material identified by the locSpec. Likewise, given a selection in a viewer, it should be possible to package the location as a ref.

Links are general hypermedia objects that consist of a collection of endpoints. Each endpoint includes a directionality label, for example, "source" or "destination," and a ref. This simple model of links is powerful enough to capture a variety of structures and behaviors.

Three examples

Here are three examples of link structures and their prefered traversal behavior which will be used in what follows. Each of these is "non-traditional" in some way.

1. A multi-headed link (Dexter): Consider a link with five endpoints, two of which have the directionality label "Source", two labeled "Destination," and the last having the label "Both." The semantics of traversal of such a link might be as follows: Traversal from a Source endpoint brings up both Destination endpoints and the Both endpoint. Starting from the Destination endpoint (possibly requiring the stipulation of reverse link traversal) brings up the two Source endpoints and the Both endpoint. Starting from the Both endpoint brings up the other four endpoints.

2. A "computed" dictionary link (Microcosm): The Source endpoint is a ref whose locSpec is a single text string. The Destination endpoint is a definition node in an online dictionary. The traversal behavior is as follows: When the user clicks on that text string in a viewer, the string is packaged into a locSpec. This locSpec is matched against the endpoints of the applicable links and found to match our computed link's Source endpoint. The result is then to bring up the definition at the Destination endpoint.

3. A "button" link having only one endpoint (Microcosm): This link models a button embedded in a document. When the button is clicked, some action is taken. As in the computed link example, the user's click of the button identifies a locSpec corresponding to the button which in turn matches the Source endpoint (the only one) of our "button" link. The link's traversal behavior is not to bring up endpoints at all, but rather to execute the button action.

We use these three examples in what follows to illustrate link traversal algorithms and behaviors.

A generic traversal algorithm

Our general link traversal algorithm is encapsulated in the server-side operation FollowLink. In the simplest version, FollowLink takes a set of refs as input and returns a set of refs, possibly taking some actions along the way. (Actually, the operation is misnamed since, in general, multiple links will be traversed.)

Pre- and post-traversal behavior is also important. In order to build/identify a set of input refs, the user's selection(s) on the client side must first be packaged as refs. In terms of post-behavior, it may be necessary for the server to make a call to the client to display the document and location specified by one or more of the resulting refs. For some clients, such bundled traversal may be desirable. In many cases, however, we expect that clients will want FollowLink to simply return a set of refs. The client can then display representations of these refs for the user so that a subset can be chosen for actual display. The selected refs are then presented either directly by the client, or via a request to the server which takes apart the ref and makes a callback to the client to open the relevant document(s). See Section 5 for further details of both the bundled and unbundled approaches to link traversal.

For the first version of the OHI, we have chosen to leave the behavior of FollowLink up to those who implement the server. What follows is a somewhat longer-term proposal for unpacking that behavior that takes our workshop discussions as jumping off point.

FollowLink details

Parts of the FollowLink operation are simply a matter of mapping from one type of hypermedia object to another. For example, FollowLink requires mapping user selections to refs, refs to endpoints, endpoints to endpoints, endpoints to refs, and refs to selections in node contents. These mapping operations were captured by Peter Nuernberg in a set of filter and association operations bound to each interface object. [Pete, is there a web page we can point to for a specification of filter and association?]

The heart of FollowLink resides in three suboperations, GetApplicableLinks, ApplyLinks and ApplyLink.

Identifying applicable links

Given a set of refs, the first real step of traversal is identifying the links that need to be considered, that is, those that comprise the scope of this FollowLink operation. The discussion on this point at the workshop focused on the means of identifying link contexts, that is, groups of linkSpecs. We didn't reach final agreement on the relationship between link contexts and spaces, collections of arbitrary specs, nor on the precise processes of building, activating and deactivating contexts. However, we did agree that the set of applicable links for a traversal operation could be computed by consulting the currently active link contexts (or perhaps the active spaces). In short, GetApplicableLinks should be a matter of a simple lookup in the current server environment.

Applying a set of links

The second aspect of traversal behavior, ApplyLinks, involves ordering ApplyLink operations and combining their results. There are two general models of ApplyLinks behavior. In what follows, we call the incoming set of refs, In0.

In the first "vertical" model, we simply invoke ApplyLink on the full set of incoming refs In0 for each applicable link. We then return the union of the resulting sets of refs from each ApplyLink invocation.

Though this model is understandable and easy to implement, it can't handle the more sophisticated behavior of systems like HOSS and Microcosm. Link traversal in those systems involves chaining links (or "behaviors" in HOSS, "filters" in Microcosm) in such a way that the results of one ApplyLink are (usually) passed to the next.

A general "horizontal" model that is more in line with HOSS and Microcosm might work as follows. Start by ordering the applicable links into a sequence L1, L2, ...Ln. Pass the incoming refs, In0, to L1 by invoking the operation ApplyLink (described below). Label the resulting set of refs Out1. Each of the refs in Out1 is tagged (by ApplyLink) with zero, one or both of two values, PassAlong and Keep. Those refs in Out1 marked as Keep are added to the final results set R. Those marked as PassAlong are added to In0 to form the set In1. Those having neither label are discarded. The process continues with L2 applied to the incoming set In1. Again, the results of applying L2, Out2, are tagged with zero, one or both of the values, PassAlong and Keep. These are used to build the next incoming set In2, and so forth. The final result set R is formed by adding the Keep refs from Outn to those accumulated from previous ApplyLink calls.

Applying a single link

The third piece of traversal behavior, ApplyLink, applies a single link to a set of refs, yielding another (possibly overlapping) set of refs. The three examples of Section 2 indicate three different behaviors of ApplyLink that we want to support. In the first example, the multi-headed link, we check each incoming ref to see if it matches any of the refs contained in the link's endpoints. If there are any matches, then use the direction labels on the matched endpoints to determine a set of resulting endpoints. Extract their refs to obtain the result set.

In the second example, the link with computed source endpoint, we match each of the refs against that computed ref. If there are any matches, then make the single ref specified by the link's destination endpoint be the result of ApplyLink.

In the third example, the "button" link, we look to see if any incoming ref matches the ref that specifies the button. If so, then execute the action built into the button link. It may return a set of refs which is our result set. Or it may return nothing, in which case we've run it only for the side-effects (say, a direct call to displayDocument).

If it is determined that ApplyLinks should tag the result refs, say, with PassAlong or Keep tags, then the above behaviors need to be suitably modified.

Where are behavior variants stored?

An important open question is how, where and whether to store descriptions of variant behaviors for ApplyLinks and ApplyLink. In the case of ApplyLinks, we decided either to implement a non-customizable default behavior (especially for the first version of OHI), or make the behavior a part of the server environment in the same way that we provide active contexts for use by GetApplicableLinks.

In the case of ApplyLink, we could again consult the server environment for a general ApplyLink behavior. For example, the client might specify a FollowReverse behavior that would traverse the link of our first example from Destination endpoints to Source endpoints. Alternatively, the ApplyLink behavior might be stored as a script on either the pSpec of the link or as one of its attributes. Because scripts are full-fledged objects on the server, we could share a single traversal script among several links.

Invoking scripts at every object?

In a future version of the protocol, every hypermedia object on the server will include a script that is invoked whenever that object is involved in a traversal. (Note that this is not the same as the script mentioned above which is attached to a link and which specifies the ApplyLink behavior.) Such scripts comprise a set of "open points" for tailoring of the server. The documentation should identify when each script is called, what arguments it takes, and what types of results if any, it should return.

To bundle or unbundle

An open question is whether clients should be allowed access to individual steps of the FollowLink algorithm. One motivating scenario involves the display of links prior to traversal. The idea is that the user makes a selection in a viewer and gets a display (possibly a menu) of the links that apply at that point. The user can then select a subset for invocation.

In general, any of our operations are candidates for explicit client calling as long as the arguments to the operation are already objects being passed between client and server.

What follows is a code skeleton that supports both bundled and unbundled interactions between client and server. In particular, the client should be able to hand a locSpec or a ref to FollowLink and be done with it. Alternatively, it should be able to retrieve a set of refs that it can then display to the user.

In the code skeleton, the term "client foo" appears. This refers to a process on the client side that can launch applications and communicate with them. Some applications can set up direct communication channels to our server; others need to use the "client foo." [We need a better name for this.] Eventually, we may need a routine that explicitly asks the "client foo" to handle a traversal for the client.

As it stands, the following code ignores the behaviors aspect of link traversal:

-- for these two operations, the server is expected to perform the

-- link traversal and display destinations as necessary.

void followLink( locSpec a_locSpec );

void followLink( ref a_ref);


-- the following two operations begin to tease apart our generic

-- link traversal algorithm. They essentially request the set of

-- applicable links for a given locSpec or ref. (Pete's association

-- and filter operations provide more generality. These operations

-- could be viewed as simple utility routines.)

sequence(linkSpec) getLinksWithLocSpec( locSpec a_locSpec );

sequence(linkSpec) getLinksWithRef( ref a_ref);


-- after calling the above routines, the client could create a dialog

-- which displays the applicable links and has the user choose which

-- ones apply. They could then use the next two routines to retrieve

-- the destinations. Or they could use the final two routines to skip

-- the above step and go straight to the destinations.

sequence(ref) getDestinationRefs( sequence(linkSpec), locSpec a_locSpec );

sequence(ref) getDestinationRefs( sequence(linkSpec), ref a_ref);

-- note in the above two routines, you must once again specify the source

-- locSpec or ref.

sequence(ref) getDestinationRefs( locSpec a_locSpec );

sequence(ref) getDestinationRefs( ref a_ref);


-- Once the client has all the destination refs, they are responsible for

-- the post-traversal behavior. I.E. they must display the refs themselves

-- or ask the server to display the ref for them.

void displayRef( ref a_ref );


-- Finally, the client could ask the server to route the destination

-- refs to the "client foo". If all clients do this, and the "client foo"

-- is augmented to handle post-traversal behavior, then a certain degree

-- of consistency across clients can be achieved.

void clientFooFollowLink( locSpec a_locSpec );

void clientFooFollowLink( ref a_ref );


5.2 Information analysis domain

This section will host the discussions on the information analysis (spatial hypertext) domain.

5.3 Taxonomic domain

This section will host the discussions on the taxonomic domain.

5.4 Transclusion domain

Insert clever text here!