ACM Computing Surveys 31(4), December 1999, http://www.acm.org/surveys/Formatting.html. Copyright © 1999 by the Association for Computing Machinery, Inc. See the permissions statement below.

Unlinking the Link

Janet Verbyla
Flinders University of South Australia
School of Information Science and Technology,
Email: janet@ist.flinders.edu.au

In memorium
Paul Thistlewaite

Abstract

The aim of this review paper is to provide a "big picture snapshot" of the multiple facets of hypermedia linking. In providing this snapshot, the paper overviews key issues in both categorizing these facets and exploiting them to design effective implementations of links.

The presentation is structured around the process of untying the perception of the link and its capabilities from the limitations of defining it in terms of the currently most pervasive implementation of the link, namely links in HTML. In the process, the paper draws on the work of Paul Thistlewaite on the linking issues for large volatile hyperbases.

Introduction

Not unnaturally, the common current perception of the nature and limitations of hypermedia linking is defined by the properties of the <A> tag in HTML. The pervasiveness of this implementation has led to the HTML link becoming the de facto standard definition. The aim of this paper is to review how the link is potentially much more powerful (and consequently complex) than what this particular implementation indicates. It is also suggested that XML may provide the means to unlocking this potential for the Web.

The following section briefly considers what constitutes the essence of linking. This will highlight the two key aspects of a link namely its specification (how) and its semantics (why). The first section after this will then outline the limitations of the specification of the HTML link and review potential alternatives. The next section will consider the semantics of the HTML link which given the limitations of its specification are surprisingly generic but also difficult to enforce. In the conclusion, the potential of XML to provide a more powerful (and complex) link will be briefly discussed. A naive, but inherently true, definition of a link drawn from usage of the Web would be "something that you select in one context that takes you to a related context" where "context" typically refers to the contents of a graphical interface window displayed on a screen. This definition captures the basic essence of a link, namely, that

  • it has (specifies) a source and destination,
  • it is used to activate (specify) a navigation action at the source which consequently returns the destination, and,
  • it represents some relationship (semantics) between the source and destination.
Hidden in this definition are a number of concepts including those of
  • the source and destination contexts,
  • the association that relates them, and
  • the actual selector (source) object and destination object which are the link's endpoints.
Also included are the operations of selection, transversal or navigation and presentation of ("arrival" at) the destination. An additional hidden operation is the advertising of the link's existence typically by the highlighting in some way of the selector object. (Following the tradition in hypermedia literature, the terms "document" or "nodes" will hereafter be used for "context" but the reader is challenged to think beyond the day-to-day meaning of document to such concepts as documentary which are just as valid in the realm of a multimedia. Similarly "anchor" will be used for the source and destination endpoint objects.)

Specification

The key features of the HTML link are its embedded mark-up, its in-line specification of a pre-determined destination and its generally manual generation. Even tools like Netscape's Composer require manual specification of the destination URL for each individual link. These have been increasingly recognised to be problematic as developers strive to add greater functionality to Web-based links. In other words, they strive to overcome the limitations imposed by the properties of the tag specification of a link such as: In describing his system for the automatic detection and management of certain types of links (discussed later), Thistlewaite [Thistlewaite 1997] further articulates how such properties "make it extremely difficult to author or maintain a large hyperbase." He considers the particular problems arising from the need to automatically detect intra- and inter-document links, and, to automatically maintain the semantic correctness of links despite changes to the hyperbase. The volume of the hyperbases considered makes automation of this process mandatory.

Despite the impression created by the dominance of the HTML link, there are alternatives to the above that could apply. (Various aspects of specific alternatives have been considered by others particularly in the literature on "non-Web-based" hypermedia; see for instance [Ashman 1997], [Davis 1992], and, [Kappe 1993].) Overviewing these alternatives highlights how much more powerful and complex the link could be if unlinked from the limitations of this particular specification:

  • in-line: Could link availability be overlaid on the document when it is presented rather than actually stored with it? Does link availability have to be advertised at all?
Perhaps instead, it could be possible to ask what links are available from a particular context:
  • embedded: Could the link specification be stored externally?
  • computation: How late can source availability be determined? How late can destination be determined? What are the possible means of determination?
  • addressing: What alternative forms of addressing are possible? Does it have to be tag-specific? Could it be relative to tags or determined by other features?
  • direction: Is there value in bi-directional links? Are these more than just two uni-directional links?
  • cardinality: Can a link have multiple destinations? Does it make sense to talk of a single link having multiple sources?
In presenting a binary relational model of the link, Ashman [Ashman 1997a] provides a comprehensive review of the twelve different representations that correspond to all the different forms possible for a link specification. The focus of the review is on how the underlying representation affects the applicability of the links or more specifically "how one asks the navigation questions of each representation". These questions concern the navigating-from issues about the existence of a link source, and, the identification of the destinations from that source as well as the navigating-to issues of the existence of a link destination and the identification of the sources linked to that destination. As discussed later, only the navigating-from issues are generally relevant to the applicability of the link specification.

Because both source existence and destination identification can each be specified either by enumeration or by computation [Ashman 1997a], there are several different ways of implementing links. Links can be explicitly enumerated by hand or they can be automatically created by computation and this can be done at varying points in time: The crafted (or hand-made) links are nearly always created ahead of need although this is not necessary. Indeed in the case of reader annotation, it is conceivable that an annotation link could be created on the spot when first desired.

The time of computation (or re-computation) can vary from the creation of the source document through to immediately prior to the navigation of the selected link. The later are often referred to as dynamic links [Ashman 1997]. The most appropriate time of computation depends on various factors including the semantics of the link (as discussed below), and, the volatility of the source document's content and of the range of destination documents.

For the HTML link, its source existence is frequently pre-crafted although potentially pre-computed when the document is created. Its destination identification is similarly pre-determined although through such technology as CGI scripts, the contents of that destination may actually be computed when the link is followed. One of the great weaknesses of the HTML link is the absolute specification of the destination document. Given the limited average life-time of URLs, this leads to links regularly breaking.

Although the HTML link makes it appear so, advertising the existence of a link source endpoint is not mandatory. Indeed to handle the existence of multiple link sources at the one endpoint, it could be more appropriate not to explicitly advertise at all and instead let the user enquire about link availability perhaps prompted by implicit indications in the context. The response could be presented as a selection list from which the user might choose a link (or not). Such a chooser is present in other hypermedia systems [Verbyla 1994].

The HTML link's approach to the source existence query of the navigating-from questions is one of its most significant limitations. In this approach, the source identification includes the destination identification with both embedded in-line in the document. Web will only really achieve fairly general hypermedia functionality when the physical representation of links is separated from the physical location of the anchors that they connect [DeRose 2000]. (This would be more consistent with HTML's (and SGML's) general principle of separating the meaning specification from the embedded tags.)

This externalisation of the link specification is common to many other hypermedia models and systems [Davis 1992], [Kappe 1993], [Wiil 1997], [Verbyla 1994]. Such externalisation means that potentially:

  • Multiple destination identification specifications can be associated with the one source anchor such as can be done in XML [DeRose 2000].
  • A single identification can identify multiple destinations; source anchors could therefore be nested.
  • Destination identification can be modified without document change
  • Link specification can be more easily automated. For example in [Verbyla 1994], it was shown how links sources and destinations could be automatically determined by just adding a document to the relevant document space.
For externalised links, the source existence identification is critical in that different approaches to the binding of the source anchor (endpoint) to the relevant link specification(s) can affect the fragility of the link(s). If the source is not specifically identified via a marker but for instance by an offset measurement, changes to the document content can lead to an incorrect (logically wrong source) or invalid (no source) link [Davis 1995]. On the other hand, not having an embedded marker opens up scope for link structures to overlay documents that cannot be edited, alternate link structures to overlay the same contents and for a document's link structure to be dynamically changed. These capabilities would permit such functionality as annotation to be supported [Davis 1995] [R–scheisen 1995].

The navigation-to queries are only relevant to bi-directional links. The necessity for which has not been clearly established; some hypermedia models assume such links but the majority does not [Parunak 1989]. As in object-oriented design, there needs to be a differentiation between an association, a relationship, which is inherently bi-directional and the need to provide navigability (permitted direction of movement) which is uni-directional. Specification only has to accommodate the necessary and sufficient semantics not the universality of semantics. For instance, linking references to a staff member to that member's personal page may be the desired navigability although the referential association between the two is bi-directional. The apparent bi-directionality of HTML links provided by the browser's "forward" and "backward" buttons is actually only a localised implementation of an undo or go-back navigation for the user's chosen path. Rarely in the destination context is there a representation of the reverse relationship (i.e. a link to go back).

Before the navigation questions can be considered, and, before source existence and destination identification can be specified, it is necessary to resolve the issues relating to addressing, namely the "pointing" semantics and syntax.

HTML links are limited because their semantics only allow whole documents or pre-embedded "#fragment identifiers" to be addressed. (To appreciate this limitation, compare it with the versatility of cross-referencing possible on paper.) Also, their syntax involves identification by location that has proven to be extremely fragile. The Web Consortium's XML Linking working group is developing specifications of Xpath, and Xpointer which deal with such issues as an extensive variety of fine-grained, fragment identifiers along with user-selected fragments [DeRose 2000]. Others have tackled the fragility via such efforts as URNs (Universal Resource Number) [Moats 1997] and DOI (Document Object Identifier) [Lynch 1997]. [DeRose 2000] further discusses these issues.

Semantics

There have been several link taxonomies proposed. Those based on intended functionality are to assist the user to conceptualise the result of following the link [Parunak 1991], [Trigg 1983]. Allen [Allen 1996] applies a similar purpose-oriented classification having first categorised links on the basis of how they could be detected i.e. pattern matching, information retrieval algorithms, and, natural language techniques. Others constrain link types in order to make them comprehensible to authors and users [Thistlewaite 1997]. This basically involves clustering the more specific purpose-oriented types together on the basis of the nature of the association depicted. This is illustrated below in an example that uses Thistlewaite's classification [Thistlewaite 1997].

Despite the severe limitations of its specification mentioned above, the HTML link arguably has quite generic semantics. The reason for this is that the link source text (and possibly other media such as an image) that is placed between the and tags is fairly unrestricted in content. It is this link source representation which can capture the association between the link's source and destination i.e. tell the user why the link exists. To illustrate this consider the following examples of the four link types identified by Thistlewaite [Thistlewaite 1997]:

  • structural links that relate parts of objects to other parts <a href="/section4.html">Next</a>
  • referential links relate an expression to its referent e.g. person's name to their home page <a href="/fbloggs.html">Fred Bloggs</a>
  • semantic links relate documents that share content, "aboutness" <a href="./xyz.html">More on this topic</a>
  • contingent links relate documents that may be related depending on the applicable degree of "aboutness" <a href="/pqr.html">Another document containing the phrase 'lost in space' </a>
The problem with this genericity is that via this simple syntax there is no means of enforcing the requirement that link source representation be related to the semantics of the link association or vice versa. For instance, the link is still syntactically correct even if invalid semantically e.g. <a href="/mlamb.html">Fred Bloggs</a>

The validity of the link could arguably be better ensured if the link itself was determined by computation that "captured" the semantics of the link. A simple example of this (which can be done using Javascript) is where sections are in pages called sec.html and the link computation for the "next" link, takes the current page name and links to sec.html if this exists, and, similarly for "previous".

Even such computation cannot ensure the validity of the link if after the link's computation, the nature (contents) of the destination or the source document changes. For instance consider a semantic link that determines its destination on the basis of an aboutness measure applied to the contents of the two documents. Unless the computation of the measure is carried out at the time of the navigation of the link, there is potential for the content of either to change such that the link is actually no longer valid.

Thistlewaite [Thistlewaite 1997] highlights another instance of this "link (semantic) decay" that actually arises from computation at the time of navigation. In this case references to the specific position titles such as "The Prime Minister" were automatically linked to the biographical details of the current incumbent. However as the referent page ages, the validity of such a link is at some stage going to disappear if the link is dynamically computed since the referent will no longer be the incumbent.

Conclusion

The proceeding examples of "semantic decay" bring together the two main themes of this review. The first of these is that hypermedia linking is potentially much more than what is achievable via HTML links. As discussed earlier, either or both source existence and destination identification specifications can be externalised and either or both can be crafted or computed at various points in time. The second theme is that this broader scope of specification options enables a richer set of semantics to be captured but at the risk of a mismatch between semantic intention and implementation.

The HTML link has been employed as a baseline measure throughout the paper since it is a de facto standard due to its popularity and pervasiveness. Although its syntax and semantics are limited, the HTML link clearly has immense utility. It also has significant disadvantages and limitations as in the automatic crafting and management of such links on a large-scale, and, the coarse-grained nature and fragility of its addressing. The XPath, XPointer and XLink initiatives associated with the XML link [DeRose 2000] may yet harness for the Web the power of the unlinked link.

References

[Allan 1996] James Allan. "Automatic Hypertext Link Typing" in Proceedings of ACM Hypertext '96, Washington DC, 42-52, [Online: www.cs.unc.edu/~barman/HT96/P34/hyper.html], 1996.

[Ashman 1997] Helen Ashman, Alejandra Garrido, and Harri Oinas-Kukkonen. "Hand-made and Computed Links, Precomputed and Dynamic Links" in Proceedings of Multimedia '97 (HIM '97), Germany, 191-208, 1997.

[Ashman 1997a] Helen Ashman. Theory and Practice of Large-Scale Hypermedia Systems, Ph.D. Thesis, Royal Melbourne Institute of Technology, Australia, 1997.

[Davis 1992] Hugh Davis, Wendy Hall, Ian Heath, Gary J. Hill, and Rob J. Wilkins. "Towards an Integrated Information Environment with Open Hypermedia Systems" in Proceedings of the ACM Conference on Hypertext (ECHT '92), Milano, Italy, 181-190, [Online: http://acm.org/pubs/citations/proceedings/hypertext/168466/p181-davis/], December 1992.

[Davis 1995] Hugh C. Davis. "To Embed or Not to Embed..." in Communications of the ACM (CACM), 38(8), 108-109, August 1995.

[DeRose 2000] Steven J. DeRose. "XML Linking" in ACM Computing Surveys, Symposium on Hypertext and Hypermedia, 2000.

[Kappe 1993] Frank Kappe and Hermann A. Maurer. "Hyper-G: A Large Universal Hypermedia System and Some Spin-offs" in Computer Graphics, special online issue, [Online: zgdv.igd.fhg.de/ papers/multimedia/Kappe.Maurer.PS.Z], 1993.

[Lynch 1997] Clifford Lynch. "Identifiers and Their Roles In Networked Information Applications" in ARL: A Bimonthly Newsletter of Research Library Issues and Actions, 194,Washington, DC: Association of Research Libraries, [Online: http://www.arl.org/newsltr/194/identifier.html], October 1997.

[Moats 1997] Ryan Moats. URN Syntax, IETF RFC 2141, [Online: ftp://ftp.isi.edu/in-notes/rfc2141.txt and http://www.ietf.org/html.charters/urn-charter.html], May 1997.

[Parunak 1989] H. van Dyke Parunak. "Hypermedia Topologies and User Navigation" in Proceedings of ACM Hypertext '89, Pittsburgh, PA, 43-50, November 1989.

[Parunak 1991] H. van Dyke Parunak. " Don't Link Me In: Set-based Hypermedia for Taxonomic Reasoning" in Proceedings of ACM Hypertext '91, San Antonio, TX, 233-242, [Online: http://acm.org/pubs/citations/proceedings/hypertext/122974/p233-van_dyke_parunak/], December 1991.

[R–scheisen 1995] Martin R–scheisen, Christian Mogensen, and Terry Winograd. "Beyond Browsing: Shared Comments, SOAPS, Trails and On-line Communities" in Proceedings of the Third International World Wide Web Conference, Darmstadt, Germany, [Online: http://www.igd.fhg.de/www/www95/proceedings/papers/88/TR/WWW95.html], 1995.

[Thistlewaite 1997] Paul Thistlewaite. "Automatic construction and management of large open webs" in Information Processing and Management, 33(2), 161-173, 1997.

[Trigg 1983] Randall H. Trigg. A Networked Approach to Text Handling for the Online Scientific Community, Ph. D. thesis, University of Maryland, [Online: chapter 4 of the thesis - http://www.parc.xerox.com/spl/members/trigg/thesis/thesis-chap4.html], 1983.

[Verbyla 1994] Janet Verbyla and Helen Ashman. "A User-Configurable Hypermedia-based Interface via the Functional Model of the Link" in Hypermedia 6(3), 193-208, 1994.

[Wiil 1997] Uffe K. Wiil and John J. Leggett. "Workspaces: The HyperDisco Approach to Internet Distribution" in Proceedings of ACM Hypertext 97, Southampton, UK, 13-23, [Online: http://acm.org/pubs/citations/proceedings/hypertext/267437/p13-wiil/], April 1997.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.