HDM - A Model-Based Approach to Hypertext Application
FRANCA GARZOTTO, PAOLO PAOLINI,
Politecnico di Milano
Pontificia Universidade Católica do Rio de Janeiro.
ACM Transaction on Information Systems, vol. 11,
nº 1, January 1993, pages 1-26
Hypertext development should benefit from a systematic, structured
development, especially in the case of large and complex applications.
A structured approach to hypertext development suggests the notion
of authoring-in-the-large. Authoring-in-the-large allows
the description of overall classes of information elements and
navigational structures of complex applications without much concern
with implementation details, and in a system-independent manner.
The paper presents HDM (Hypertext Design Model), a first step
towards defining a general purpose model for authoring-in-the-large.
Some of the most innovative features of HDM are: the notion of
perspective, the identification of different categories
of links (structural links, application links, and perspective
links) with different representational roles; the distinction
between hyperbase and access structures; and the
possibility of easily integrating the structure of a hypertext
application with its browsing semantics. HDM can be used in different
manners: as a modeling device or as an implementation device.
As a modeling device, it supports producing high level specifications
of existing or to-be developed applications. As an implementation
device, it is the basis for designing tools that directly support
application development. One of the central advantages of HDM
in the design and practical construction of hypertext applications
is that the definition of a significant number of links can be
derived automatically from a conceptual-design level description.
Examples of usage of HDM are also included.
Categories and Subject Descriptors: H.2.1 [Database Management]: Logical Design -data models; H.3.4 [Information Storage and Retrieval]: Systems and Software; H.4.1 [Information Systems Applications]: Office Automation; 1.7 [Text Processing]: Miscellaneous-hypertext
General Terms: Design, Languages
Additional Key Words and Phrases: Derived links, HDM, Hypertext design models, Hypertext applications, Hypertext structures, models
This work was sponsored in part by the Commission of the European Communities, in the scope of the HYTEA Project (P 5252) of the ESPRIT II Program. D. Schwabe developed this work while on sabbatical leave from PUC and was partially supported by CNPq-Brasil.
Authors' addresses: F. Garzotto and P. Paolini, Department of Electronics, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy. Phone: + 39-2-23993520: fax: + 39-2-23993411; e-mail: firstname.lastname@example.org; email@example.com; D. Schwabe: Departamento de Informática, Pontificia Universidade Católica do Rio de Janeiro, R. M. de S. Vicente, 225, CEP 22453, Rio de Janeiro, Brasil. Phone: +55-21-274.4449; fax: +55-21-274 4546; e-mail: firstname.lastname@example.org.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
© 1993 ACM 1046-8188/93/0100-0001 $01.50
2. A MODEL-BASED APPROACH TO AUTHORING-IN-THE-LARGE
3. EXAMPLE OF HYPERTEXT MODELING WITH HDM
1.2 Current Approaches to Hypertext Application Design
The degree of success of a hypertext application is directly related to the author's ability to capture and organize the structure of a complex subject matter in such a way as to render it clear and accessible to a wide audience. To control the potential explosion of the number of links, a hypertext application does not really interconnect everything, but rather tries to directly interconnect only the most important and meaningful parts of the information so as to convey the overall meaning in a more natural way.
In a rational design approach, a hypertext application developer faces at least two different (but strongly correlated) task categories: "global" tasks, such as defining overall classes of information elements and navigational structures of applications, and "local" tasks, such as filling in contents of nodes. This is very similar to what happens when developing a highly modular software system: designing the topology and the interconnections among modules is different from writing the code for the content of the modules themselves. By analogy with software engineering, we use the following terminology: authoring-in-the-large, to refer to the specification and design of global and structural aspects of the hypertext application, and authoring-in-the-small, to refer to the development of the contents of the nodes [16, 17].
Authoring-in-the-small is very much related to the specific application area, while authoring-in-the-large has common characteristics across many different applications in a given application domain. Authoring-in-the-small is strongly dependent on the tools used for implementation and on the medium used for storing information (e.g., putting the text in a node is much different than putting an animation, or a sound, or a picture). Authoring-in-the-large can be at some extent independent from these aspects. However, authoring-in-the-large and authoring-in-the-small are typically very interwoven, and influence each other, much more than programming-in-the-large and in-the-small in the current software engineering practice.
This paper presents a model for authoring-in-the-large, named HDM - Hypertext Design Model [16, 17, 18, 36]. HDM prescribes the definition of an application schema, which describes overall classes of information elements in terms of their common presentation characteristics, their internal organization structure, and the types of their mutual interconnections. A schema, therefore, captures semantic and structural regularities in the representation structures for a given class of applications. Once a schema has been specified, the model also allows it to define a particular application, by providing primitives to describe a schema instance, i.e., actual instances of information classes and of connection types. In defining a schema instance, a significant number of connections can be left implicit, since they can be automatically derived from a conceptual-design level description.
HDM is mainly a modeling device. It provides ways of describing, concisely and in a system independent manner, existing or to-be-developed hypertext applications; it helps the author to conceptualize a given application without too much regard to "implementation details"; and it can be used as a communication language between designers, implementors, and users.
Additionally, HDM can be used to generate running implementations
of hypertext applications [26, 36]. From this perspective, the
model is a first step towards the development of application generators,
in a similar way as CASE tools are used in software engineering
environments. Implementation of an HDM application requires the
definition of a browsing semantics, which specifies dynamic behavior
and visualization properties of HDM representation structures.
HDM is not closed with respect to any particular browsing semantics.
So far, we have specified a default browsing semantics,
more suitable for relatively simple card-oriented classes of systems.
1.2 Current Approaches to Hypertext Application Design
In the very closely related data base design field, models have played a crucial role in changing the data base development task from being a "hand-crafted" (and sometime inconsistent) activity into becoming a structured and rational process, based on well defined design methods . Database models were born as means to define useful abstractions on large amounts of raw information ("logical" data models) and to express the intrinsic application oriented data semantics ("conceptual" and "semantic" data models [6, 21]). However, the peculiarities of hypertext (e.g., the role of links, the complexity of structures, the multimedia facility, the navigation paradigm, etc.) require the development of brand new models, specific for peculiar features of hypertext.
In the hypertext field, some approaches attempt to explicitly model the semantics of specific application domains by adopting predefined representation structures which reflect such "deep" semantics. g-IBIS , for example, is a hypertext tool for exploratory policy discussion. It helps capturing, storing, and retrieving the large amount of informal information which express the rationale of a system design process. g-IBIS explicitly models the semantics of its domain by assuming a well defined theory of the design process and by providing a set of specific node and link types that represent conceptual objects in the domain model. Thus g-IBIS encourages to share this model while seeking to discourage less disciplined argumentation modes.
Other works should be regarded more as "system" oriented models than as application oriented design models. They are attempts to define in an unambiguous, rigorous way some important abstractions found in a wide range of existing (and future) systems rather than of existing (and future) applications. The goal of the Dexter Hypertext Reference Model  is to serve as a standard against which to compare and contrast the static information structures and the functionalities of different hypertext systems. Its building blocks for defining the static aspects of a hypertext system are low level objects: nodes, links, and anchors. The Dexter model purposefully does not model the content and structure within the components of hypertext networks. It treats them, as well as their layout and visualization properties, as being outside the model per se. Garg's set-theoretical model  is a formalization of hypertext networks viewed as static, syntactic structures, and provides a mathematical framework to define abstraction mechanisms useful to describe or derive static syntactic properties of hypertext networks. Garg's model (as other similar ones ) assumes low level objects as building blocks, such as nodes (and even node components), and node-to-node links. The Trellis model  is mainly a "behavioral" model for hypertext. Hypertext networks are modeled as Petri nets, and various browsing semantics (that is, how information is to be visited) are discussed in terms of Petri nets computations.
Tompa  adopts a hypergraph formalism to model generic hypertext structures, to formalize identification of commonalties in these structures, and to directly refer to "groups of nodes" having a common 'link semantics. A dynamic behavior is also specified through the notion of node markings, with an end result much similar to the Trellis model.
Other, less formal, approaches emphasize preferred topological structures as building blocks to create the structure of hypertext networks. This requirement is often embodied in a concrete system implementation, and enforced by the editing tools the system provides. In Hypercard , for example, linear structures play a central organization role. Even if each card can be arbitrarily linked to any other card, each Hypercard node must belong to a sequence ("stack") of cards, and links to the successor node, to the first and the last node in the sequence are automatically provided by the system. Guide  also prescribes the extensive use of linear structures to clarify the organization of hyperdocuments. KMS  prescribes the extensive use of hierarchical structures to organize information, in order to encourage a top-down, step-wise design of hyperdocuments. Each KMS node (frame) belongs to- a single hierarchy; however, KMS also allows "special links" that are cross-hierarchical and induce a more complex topology on the network of nodes.
Several existing approaches provide "template" facilities to help designers generate hypertext structures more easily and systematically, by allowing authors to create multiple copies of individual structures all sharing a number of common properties. HyperCard, for example, has "backgrounds" as the lay-out and linking template. The lay-out and button properties of a background are inherited and shared by all the different nodes sharing that background. NoteCards' notion of (hierarchy of) node types and link types lets writers create as many instances of a class of hypertext nodes as they require . Object Lens  encourages a similar style of node creation, by providing an object-oriented environment which allows definition of templates corresponding to high-level abstractions in an application domain. IDE , an extension of NoteCards, is an interactive design and development system which assists designers with the process of creating complex hypertext material, mainly (but not only) for instruction purposes. IDE provides built-in representation primitives for describing the substance of a course and the rationale for the course design in terms of hypertext structures. IDE moreover, provides a number of domain independent mechanisms ("structure accelerators") that facilitate the rapid and accurate creation of regular network patterns in hypertext by permitting authors to create entire webs of nodes and links in a single operation. The template facility in Intermedia [38, 48] plays a similar role as IDE structure accelerators. Stotts et al.  introduce the notion of style templates to denote styles of structuring and browsing Trellis-based hypertext. Different style templates correspond to different translations from generic authoring notations of hypertext content elements and linkages into structured Trellis documents with a specific browsing behavior. Translations are basically mappings from string-grammars (the authoring language) to graph grammars (the abstract language for Trellis documents).
Other approaches help to organize and modularize existing hypertext material. Trigg's Guided Tours and Tabletops [29, 42], for instance, are extensions of NoteCards which help designers to group and visualize existing hypertext material in a way that it is more appropriate for a particular reader, and to provide preferred paths through a hyperbase.
The remainder of the article is divided as follows: Section 2
discusses the advantages of the model-based approach to authoring
in the large and presents HDM in detail; Section 3 gives an example
of HDM use in hypertext application design; Section 4 draws the
conclusions, by comparing HDM to other approaches, by evaluating
the model's utility on the basis of a number of experiences done
so far, and by outlining our future work.
2. A MODEL-BASED APPROACH TO AUTHORING-IN-THE-LARGE
2.2 HDM Primitives
2.3 Derived Links and Derived Link Types
2.4 Browsing Semantics
There are many advantages in having a design model for hypertext applications, which we summarize here.
Improvement of communication. A design model provides a language which can be used by an application analyst to specify a given application. Thus it facilitates the communication between the analyst and the end user; between the analyst and the system designer; and between the system designer and the implementor. At the very least, a basis for discussing the similarities of hypertext applications exists. To paraphrase Halasz et al. : Hypertext Application Models can be regarded as an attempt to provide a principled basis for answering questions such as "what do hypertext applications such as Voyager's Beethoven's 9th Symphony , Harvard University's Perseus , ACM's compilation Hypertext for Hypertext , Eastgate's Elections of 1912 . have in common?" "How do they differ?"
Development of design methodologies and of rhetorical styles. Design models provide a framework in which the authors of hypertext applications can develop, analyze, and compare methodologies and rhetorical styles of "hyperauthoring", at a high level of abstraction, without having to resort to looking at the detailed contents of units of information or at their particular visualizations
Reusability. As a matter of fact, the availability of a modeling language paves the way for (partial) reuse of the back-bone structure of applications since model-based specifications capture the essential semantics" of applications, and can therefore be reused when the semantics of two applications are similar enough.
Providing consistent and predictable reading environments. It is clear that tools for specifying hypertext structures can help authors to avoid structural inconsistencies and mistakes , and that applications developed according to a model will result in very consistent and predictable representation structures. As a consequence, navigation environments will also be predictable, thereby helping readers to master complex documents and reducing the disorientation problem [31, 33, 43].
Use by design tools. Design models are the basis for the
development of Design Tools  that support a systematic, structured
development process allow the designer to work at a level of abstraction
which is closer to the application domain, and provide a systematic
translation process to the implementation level.
2.2 HDM Primitives
HDM is a model to describe hypertext applications. It has a number of peculiarities that make it overall different from other models, but at the same time borrows many of its detail features from existing models. From a terminological point of view, we had two extreme choices: either to create a set of brand new terms for all the features of the model, or to use only preexisting terms (and concepts), perhaps reassembled in a novel fashion. We have chosen a compromise course: some of the terms are new, others are taken from preexisting models in the database or hypertext field. Preexisting terms should be understood with the caveat that the reader should never assume that our use of the term exactly corresponds to the notion that he is already aware of.
An HDM application consists of sizeable structures of information chunks called entities. An entity denotes a physical or conceptual object of the domain. Entities are grouped in entity types. An entity is the smallest "autonomous" piece of information which can be introduced or removed from an application. In this context, "autonomous" piece of information means that its existence is not conditioned by the existence of other information objects. In HDM, only entities are autonomous, while components and units (see below) are not, as discussed in the following sections.
An entity is an hierarchy of components. Components are in turn made of units. Each unit shows the content of a component under a particular perspective (see proper subsection for details and examples). Entities therefore derive their information content from their components, which in turn derive it from their units. Units are the smallest chunks of information which can be visualized in an HDM application, and they have a lot in common with the standard notions of hypertext "nodes."
HDM information structures can be interconnected by links. HDM distinguishes among three categories of links. Structural links connect together components belonging to the same entity. Perspective links connect together the different units that correspond to the same component. Application links denote arbitrary, domain dependent relationships and connect together components and entities, of the same or different types, in arbitrary patterns set up by the author. Application links are grouped in link types. All perspective links, and most structural links, do not need to be defined explicitly by the author, since they can be derived automatically from the structure of entities. Some application links can be derived by exploiting semantic properties (e.g., symmetry and transitive closure) of the corresponding domain relationships.
As any other design model, HDM makes a clear distinction between the notion of schema and the notion of instance of a schema. A schema is a collection of type definitions that describe an application at the global level; an instance of a schema is a collection of entities, components, units, and links that satisfy the definitions of the schema. Outlines, i.e., access structures, provide reader-oriented entry points to directly access information structures in an instance of a schema.
A browsing semantics has the purpose of specifying how
information structures are visualized to the reader, and how he
can navigate across them. HDM provides a relatively simple default
browsing semantics as built-in; different browsing semantics however
could be defined, to describe more sophisticated visualization
effects for applications specified with HDM.
2.2.1 Entities and Entity Types. An entity is a (relatively large) structure of information which represents some real world object of the application domain; a law (say "Law 19/8/89"), a musical Opera (say Verdi's "La Traviata"), a piece of equipment (say "electric engine") could be examples of entities.
Entities are naturally grouped in entity types, which correspond to classes of objects of the real world. "Law", "Musical Opera" and "Equipment" could be examples of entity types.
The notion of entity (and the related notion of entity type) is commonly recognized as a suitable notion to model information in the data base field. The most popular design model, the Entity-Relationship (E-R) model , and the several other related models derived from it, are based upon the notion of entity and entity class.
We should warn the reader, however, that although we have kept
the term and the basic nature of the concept of Entity, in practice
HDM entities are very different from E-R entities. For example,
HDM entities have complex inner structures (with links inside,
see Subsection 2.2.7), while E-R entities are essentially flat;
HDM entities have a (default) browsing semantics associated with
them (see Subsection 2.4.1); HDM entities can be interwoven, via
application links (see Subsection 2.2.8), in patterns much more
complex than those allowed by relationships in the E-R model.
2.2.2 Components. An HDM entity is a collection of components arranged in a tree-like fashion (ordered hierarchy). A component is an abstraction for a set of units (see Subsection 2.2.4), which are the actual containers of information, and derives its content from its units1. A component, being part of a hierarchy, in general has a parent (but for the root component), a number of siblings (which are arranged in a linear order) and a number of children (but for the leaf components). Components "inherit" their type from their entity and can only exist as part of an entity; in this sense, they are not autonomous.
1 For model simplicity, and also because we have verified
that so par we do not need the feature. entities cannot be used
as components of other entities.
Examples of components, for the entities introduced in the previous subsection, could be "Article 1" (component of "Law 19/8/89"), "Article 1-Subsection 1.2" (child of "Article 1" component), "Ouverture" (component of "La Traviata"), "condenser" (component of "electric engine").
Many authors have observed that hierarchies are very useful to
help user orientation when navigating in a hypertext [1, 7].
HDM recognizes this via the notion of entities made up of components
organized into hierarchies. Hierarchies can be induced by many
semantic criteria (i.e., domain relations). The "Is-part-of"
relation, for example, is one of the most commonly used. HDM,
however, does not acknowledge the (possibly) different semantic
nature of different hierarchies, since it is not intended to be
a semantic model. In HDM, a hierarchy is a purely syntactical
device to organize information in regular building blocks within
a (possibly large) application.
2.2.3 Perspectives. In hypertext applications it is often the case that the same topic must be presented in several alternate ways. There are several different reasons why this need may arise. In multinational applications, for example, the same topic must be represented with different languages (e.g., Italian, Portuguese, English, etc.). In educational applications, it may be useful to present the same topic using different rhetorical styles (e.g., discursive, synthetic, schematic,. . . ), according to different needs of the readers. In recent applications, very often different media can be used for presenting the same piece of information (text, graphics, image, video, sound, etc.).
In HDM this notion of having different presentations for the same
content is captured by the concept of perspective. If
an entity has two possible perspectives (say "Italian"
and "English", or "Score" and "Sound"),
all the components belonging to it also have two possible perspectives.
The set of perspectives are shared by all entities of a given
entity type, and are defined at entity type level.
Perspectives are just a syntactical device to organize information.
HDM does not acknowledge any predefined semantics behind this
concept, and does not interpret it. The author has to decide
when and how to use the notion of perspective, and what is its
intended meaning. HDM only prescribes consistency in using the
different ways for presenting information in entities of the same
2.2.4 Units. A unit corresponds to a component associated with a specific perspective. A unit is characterized by a name (its identifier) and a body. Bodies of units are the place where the actual content of an HDM application is filled in. "Ouverture/sound", "Ouverture/score" (of the entity "La Traviata"), "Article l/Official Text", "Article 1/Annotated Text" (of the entity "Law 19/8/89"), "assembly instruction/Italian-text", "assembly instruction/ English-text", "assembly instruction/Italian-graphics", "assembly instruction/English-graphics" (of the entity "Electric Engine"), are examples of units.
If the reader tries to relate HDM units to traditional hypertext notions, units, roughly speaking, may be thought as corresponding to the standard notions of "nodes". This correspondence is not completely true; for example, units can be created only in the proper context (of components and entities, under the proper perspectives), and arbitrary nodes are not allowed in HDM.
Filling in a body, corresponds to authoring-in-the-small (in our terminology), which is purposefully outside the scope of HDM. Therefore HDM units are the border-line between authoring-in-the-large and authoring-in-the-small: identifying the units and putting them in the proper context belongs to authoring-in-the-large; filling the bodies of units with actual content is authoring-in-the-small.
In HDM, different units are allowed to share their body. This
is, methodologically speaking, not encouraged in HDM; in fact,
sharing of bodies implies that the same content can be accessed
in different (not mutually exclusive) contexts, and this is a
typical source of disorientation for the reader. Additionally,
we have verified that the need for sharing of bodies arises, quite
often, from a poor design of the schema and a bad use of application
links (see Subsection 2.2.8). Still we have introduced the notion
of body sharing since we have acknowledged that, in some applications,
a good use of it can simplify the application specification for
the designer (but at the possible expense of clarity for the reader).
2.2.5 Links in General. Links in hypertext have a twofold role: a representational role (i.e., capturing domain relations) and a navigational role (i.e., capturing navigation patterns). Sometimes these two different purposes are consistent with each other, sometimes they can be at odds. It may happen that domain relations are not suitable for navigation, i.e., they induce navigation patterns that are not relevant for an application, while, on the contrary, useful navigational links may have vague semantic meaning. Definition of links is therefore a trade-off between representational and navigational goals. However, the more the meaning of a link is made explicit and approximates a relationship of the application domain that a reader is aware of, the more the same reader will be at ease in using the hypertext, since links will evoke familiar associations.
HDM is not intended to be a semantic model. However, HDM acknowledges
three categories of links: perspective links, structural
links, and application links. The distinction among
the three classes simplifies the job of the application designer,
induces a consistent use of most links, creates more predictable
navigation patterns, and finally makes it possible to introduce
additional features such as derivation of links (see Subsection
2 3) and definition of a default browsing semantics (see Subsection
2.2.6 Perspective Links. Perspective links interconnect units corresponding to the same component. Perspective links will connect, for instance, the units "assembly instruction/Italian-text" and "assembly instruction/Italian graphics", thus allowing an Italian reader to "switch from the text description of an assembly operation to the picture (in Italian) that schematizes it.
Perspective links are navigationally very simple for the reader,
since activating a perspective link leaves the current topic (i.e.,
the reader's focus of attention) unchanged.
2.2.7 Structural Links. Structural links connect components belonging to the same entity. There are several different structural links, each of them corresponding to a relationship induced by the ordered tree structure of entities. Examples of structural links are "Up", connecting a component to its parent, "Down", connecting a component to its children, "Down-1", connecting a component to its first child, "Next-sibling", connecting a component to the following child of the same father, "Root", connecting a component to the root of the tree, and so on.
Structural links can be used by the reader to navigate among chunks
of information belonging to the same entity. Navigationally,
they are a little more complex than perspective links, but they
are still quite simple, since they leave the reader inside the
same information context, i.e., the same entity, with limited
danger of getting lost. In the worst case the "Root"
link can always take the reader to a safe point (i.e., the root
of the entity).
2.2.8 Application Links and Link Types. Application links represent the most expressive portion of any non trivial hypertext; they represent domain dependent relationships among entities, or their components. These relationships are chosen by the author as both navigationally and semantically relevant.
Application links are organized into types. An application link type, or link type for short, is specified in HDM by a name, a set of source and target entity types, and a symmetry attribute, which can assume two values-symmetric or asymmetric. Source and target entity types define what can be linked to what. Once a link type has been defined as having source entity type A and target entity type B, instances of this link type are allowed to connect entities or components of type A to entities or components of type B only. The symmetry attribute defines a semantic property of the link type-whether or not each link of that type has an inverse link. This property can be exploited for automatic derivation of application links (see Subsection 2.3).
An example of application link type is "is-author-of", whose instances connect entities or components of type "Composer" to entities or components of type "Musical Opera". Another example is "is-justified-by", whose instances connect entities or components of type of "Contract", to entities or components of type "Law".
The semantic depth or arbitrariness of an application link type can vary, and is left to the author's responsibility. If establishing the composer of an opera corresponds to expressing a purely matter-of-fact truth, deciding that a given law is particularly relevant for a (portion of) contract, may express an arbitrary and debatable judgment.
In HDM, the choice of application link types and the placement of their instances is completely left to the author. By requiring the specification of source and target entity types in the link type definition, HDM only enforces syntactic consistency, and therefore it would not allow, for example, to establish an "is-author-of" link from a "Musical Opera" to a "Law".
From a navigational point of view, application links are typically
the most troublesome, since when traversing application links
the reader perceives that his information context is abruptly
changed. Assume that the reader is examining a contract. While
he is navigating among its different parts (following structural
or perspective links), he is always within the same familiar information
context. If now he follows an application link of type "is-justified-by",
he will find himself looking at an article of a law and not at
the clause of a contract. After having followed a number of application
links, the reader might get disoriented by the different information
contexts (i.e., entities of different types) he has traversed.
2 2.9 Entity Types Revisited. We can now reexamine
the notion of entity type and characterize it in a more precise
fashion. All the entities belonging to the same type have certain
features in common: (1) the name of the their entity type; (2)
the set of perspectives under which their content (i.e., the body
of their units) is presented; (3) the types of their outgoing
and incoming application links.
2.2.10 HDM Schema. An HDM specification of a hypertext application consists of a schema definition and a set of instances definitions. A schema definition specifies a set of entity types and link types. Instances are allowed to be inserted in the application only if they obey the constraints specified by the schema.
The notion of schema is relatively new in the hypertext field, but it is obviously derived from the current practice in the database field. Database schemas started (in the early sixties) as simple templates, describing file structures, that allowed generic operations such as "find" or "search" to be performed, independently from structural and implementation details of files. With time these file descriptors have become more complex, incorporating more semantic features.
In the hypertext field the evolution seems to start following
the same course; developers of applications, who need to perform
several times the same operations on complex node/link structures,
have acknowledged that "templates"-descriptors of network
patterns-are useful to save effort and to ensure consistency [27,
38]. Most existing template mechanisms in hypertext, however,
are defined essentially on a syntactic basis. Taking advantage
of the historical experience of the Data Base field, HDM attempts
to go directly to an advanced notion of Schema that is able to
represent some semantic features of hypertext applications, as
well as to exploit syntactical regularities.
2.2.11 Outlines. According to the HDM terminology, a hypertext application can be, roughly speaking, divided in two portions: a hyperbase and a set of access structures.
The hyperbase represents the core of the application; it consists of all the elements defined in the previous sections: entities, components, units, and links of all the categories previously discussed-structural, perspective, and application links. The reader can explore the hyperbase by traversing the links defined there.
Before he can start this navigation, however, the reader must have entry points to get a view of what the hyperbase is about, and to locate the most convenient starting point. Access structures have the purpose of allowing the reader to properly select the entry points for further navigation.
In HDM, so far, we have mainly focused our attention on modeling the hyperbase, which represents the most relevant portion of any hypertext. For access structures, at the moment, we provide a unique primitive, the outline, explained below. In the Conclusions (Subsection 4.4) current work for the enhancement of this part of HDM is described.
Outlines are structurally quite similar to hyperbase entities, but they have a number of restrictions and peculiarities that make them substantially different from entities. An outline is an ordered tree of components. Each component (but for leaf components) is connected to its child components, to its siblings, and to its parent (but for the root component), via structural links. Differently from entities, however, these are the only outgoing or incoming links for nonleaf components; additionally, leaf components must have a number of outgoing (untyped) links to entities or components of the hyperbase. Outlines are not typed and are not specified in the schema-they can be freely added or modified, at will, in an application, in order to provide the appropriate entry points for the reader.
An outline for applications in the legal field, for example, provides
an access to "European Laws", or "National Laws"
in the root component. Selecting "National Laws" corresponds
to traversing a link to a component where a further choice is
presented among different categories of national laws-say, for
example, "Laws concerning real estate sale", "Laws
concerning donation", etc. There is an outgoing link for
each of the above categories of laws; each one of these links
points to a leaf component, which has a number of links to specific
entities of type "Law" of the selected subcategory (say,
for example, "Law 10/21/87", "Law 3/5/75").
2.3 Derived Links and Derived Link Types
One of the central advantages of HDM in the design and practical construction of hypertext applications is that defining a significant number of links can be left implicit-being induced from structural properties of the model-or can be defined intentionally and algorithmically derived. At the conceptual level, the author needs to provide a much smaller number of links than the number of links that will actually be present in the application- once the proper interpreter is provided, all implicit or derivable links can be generated automatically from the design level description, by using the schema definitions.
All perspective links can be left implicit and can be automatically derived from the definition of components and units. For example, if perspectives "score" and "sound" are defined for entity type "Opera", two perspective links will be generated for each component of an entity of this type: the first connecting the unit of the component under "score" perspective to the unit under "sound" perspective of the same component; the second being the inverse of the first.
Defining an entity is equivalent to defining a set of components plus the minimal set of "basic" structural links that are necessary to induce an ordered hierarchy relationship on the set of components: links from any (nonleaf) component to its first child, and links from any component to the next child of the same parent. A large number of other structural links can be defined intentionally, and can be computed, from the basic ones. For example: "down(N" (N positive integer) -connecting a component directly to its N th child; "down"-connecting a parent component to all its children; "up" -connecting a component to its parent; "to-top"-connecting a component to the root of the entity.
Derived structural link types can be defined in terms of operators such as "inversion", "composition", "composition(N)" (repeated composition, N times), "transitive closure", and "closure"-applied to basic structural links. All instances of derived structural link types can be automatically computed from the basic structural links, by a proper interpreter "executing" the corresponding derivation clauses.
A similar approach can be applied to application links. For example, from application link types that have been defined as "symmetric" (see Section 2.2.8), the corresponding inverse link types can be specified by using the inversion operator, and their instances can be automatically generated. As a more sophisticated case, we can specify derivation rules such as: "given an application link type, if an instance of it exists between two components of different entities, then an instance of the same link type is derived between the roots of the corresponding entities."
Assume for example that a component of an entity of type "legal
document" -say "section 1.1" of a contract "X",
has been connected by the author to a component of an entity of
type "law"-say "Article 2" of law "T'-by
a link of type "justified-by" (see Figure 1). Then
assume that the author wants to represent also the fact that,
at a different level of detail, the whole contract X "is-justified"
by the whole law Y. This fact can be expressed by a link between
the root of contract "X" (which is intended to represent
the whole entity "X") and the root of law "Y".
(which is intended to represent the whole entity "Y").
This link can be derived by composing the inverse of link "to-top"-outgoing
from component "section 1.1" -with the link "is-justified-by"
-outgoing from the same component- and then composing the result
with the link "to-top" outgoing from component "Article
2.4 Browsing Semantics
The actual use of a hypertext is largely defined by its browsing semantics , which will determine what the information objects are for "human consumption" (in HDM terms, entity types, link types, entities, outlines components, or units), what the perceived links between these objects are and what the behavior when links are activated is.
Given the specification of a particular browsing semantics compatible with a given target hypertext systems, it becomes possible to translate HDM application specifications into running applications, once the mapping from HDM primitives into implementation structures of the target environment has been provided. By applying different browsing semantics to the same HDM static specifications, it is possible to deliver the same HDM application under different versions, each one characterized by different visual features and dynamic behaviors, or running in different hypertext systems.
The particular browsing semantics will be closely dependent on
the particular hypertext development system being used for implementation.
HDM, as discussed so far, does not prescribe a priori any specific
browsing semantics for hypertexts specified with it, nor does
it include any high level primitive for defining browsing semantics.
However, we have defined a minimal browsing semantics, compatible
with plain nodes -and- links structures found in most hypertext
systems, and we have adopted it for our experiments on automatic
translation of HDM specifications into running applications (see
Section 4.3). For the
moment, this browsing semantics is considered as the default browsing
semantics for HDM.2
2 The default browsing semantics has been implemented in a prototype system, which uses a relational database description of HDM specifications, and generates a tabular description that can be imported into Hypercard and manipulated using Hypertalk. This prototype is described in detail in .
2.4.1 Default Browsing Semantics. HDM default browsing semantics assumes that only units can be perceived by the readers as standard "nodes", i.e., "loci of navigation control", and that only one node is active at any time. As a consequence, readers can perceive links only among units, and so, in the end, actual, navigable connections must be established among units.
Since in HDM only perspective links connect units, while structural
and application links are established among components or/and
entities, the latter must be properly translated into unit-to-unit
links. We will call "abstract" the links among components
and/or entities, and "concrete" the unit-to-unit links.
22.214.171.124 From Abstract to Concrete Links. HDM default rules for translating abstract links into concrete links are based on the idea of having a default representative for each abstract object (component or entity). Defining default representatives of entities and components is done by introducing a default perspective for each entity type, and then assuming that the default representative for a component is its unit under the default perspective and the default representative for an entity is the default representative of its root component. This corresponds to saying that the root component of an entity, in its default perspective, "stands" for that entity.
Given this notion, entity-to-entity application links translate into concrete links between their default representatives. Each component-to-component application link is translated into a set of concrete links connecting each unit of the source component to the default representative of the target component.
To illustrate this rule, consider the following situation occurring in a hypermedia music listening guide; "La Traviata-Ouverture" component (of entity "La Traviata" of type "Musical Work"), is linked to "Verdi-1" component (root of entity "Verdi" of type "Author"), through a "Composer of" application link. Consider furthermore that "Author" entity type has perspectives "Picture" (showing the person) and "Text" (with a textual description), while "Musical Work" has "Text" (with the music score) and "Music" perspectives. "Picture" is the default perspective for entity type "Author".
In the above case, the actual concrete links corresponding to
the abstract link connecting the two components, will connect
both "La Traviata-Ouverture: Text" unit and "La
Traviata-Ouverture: Music" unit to "Verdi-l: Picture"
unit. This is an example where one link at the abstract level
corresponds to two concrete navigable links. The situation is
illustrated in Figure 2.
The default rule for component-to-component structural
links translation is the following: if a component C1 has a structural
link to a component C2 then, for each perspective P, each unit
of C1 having this perspective is linked to the unit of C2 having
the same perspective. Therefore, in an entity of type
T having N perspectives, N concrete links correspond to each structural
link defined at the conceptual level.
126.96.36.199 Perception of Links: Anchors and Anchor Types. In hypertext connections among pieces of information are usually perceived through "anchors" (or "buttons"). Anchors are link place-holders that show the existence of connection in nodes, and can be selected ("clicked") by the reader in order to get into the link target(s). An anchor type specifies the properties of anchors that represent links of the same type, or of a group of link types.
Consider for example, that a "Procedure" entity type has an outgoing link type "Formal-Legal-Justification" to a "Law" and an outgoing link type "Informal-Justification" to an "Informal-Regulation". The author might want to provide to certain classes of users a single reading link, simply labelled "Justification", since the distinction between formal and informal justifications might not be important for readers of that class. This can be achieved by specifying the anchor type "Justification" to be the union of application link types "Formal-Legal-Justification" and "Informal-Justification".
Another design requirement of the author might be to hide links of a given type for a specific application (since they might be relevant at design and specification level but not at reader level). This can be achieved by simply not assigning any anchor type to that link type. Anchor types, therefore, provide a mechanism for the author to present groups of link types together, also renaming or hiding them, as desired.
When an anchor actually refers to several possible destination
nodes, the HDM default browsing semantics has the notion of chooser,
i.e., a structure that is associated with an anchor and allows,
via a "menus", to select one of the multiple targets
of the anchor.3
3 Choosers can be generated automatically from the specification of the concrete links in the hypertext application.
3. EXAMPLE OF HYPERTEXT MODELING WITH HDM
This section will describe a hypertext application designed with HDM -a subset of a larger prototype application for banking environment named Expert Dictionary  which has been developed by ARG SpA and Politecnico di Milano within the European Esprit project SUPERDOC.
The goal of the Expert Dictionary is to provide an organized way to access to a large set of information of vastly different but interrelated nature handled by credit organizations. A credit organization manipulates Documents according to Procedures. Documents and Procedures are defined according to Laws, Regulations, and Informal Norms. Laws are issued by the state to discipline and control credit granting and taking activity. Most of the times laws are too broad, and must be made more specific by Regulations issued by some authority, on the basis of the text of the law. Finally, these regulations are interpreted within an organization with the addition of Informal Norms, which are of course valid only for that organization.
Entity types and application link types that model the above state
of affairs are sketched in Figure 3. Each of these entity types
has a set of perspectives associated with it, which are
omitted for lack of space. For example: Laws and Regulations
have Structure* and Official
Text perspectives; Documents have Structure*,
Official Text, and Description perspectives; Procedures
have Flow Diagram Structure* ("Structure''
for short) and Description perspectives. The perspective
marked with a "*" is the default. All application link
types are "symmetric" (see Section 2.2.8),
i.e., they represent a relation and its inverse. Thus we have
drawn link types only once, but we assume that for each application
link type, there is a derivable link type that corresponds to
A fragment of an instance of the schema above is depicted in Figure
4. It shows an entity of type Procedure named Mortgage
Loan Procedure, which is made up of a root component introducing
the whole entity and several other components denoting subprocedures
or subprocedure steps. Another entity is Circular HyperBank
21/10/89 of type Regulation, which is made up of a root
and four components. Units Involved, Subject, Operational
Norms in Request Verification, and Data Entry Rules.
These last two components represent information that respectively
affect the way the procedure (sub) steps Request Verification
and Request Data Entry are performed; therefore, application
links of type has-effects-on are included. Entity Circular
HyperBank 21/10/89, in turn, is motivated-by entities Law
19 /8/89 and Administrative Council Deliberation 20/9/89.
The small black rectangle on the right-hand side of the picture
is an outline named Access to Mortgage Loan Client Information,
which allows us to directly access entities describing documents
needed for the compilation of a Mortgage Loan Request (in the
picture, Mortgage Loan Request Form and Notary Statement).
The following figures show a few examples of screens (corresponding to HDM units of the appropriate components) from the Hypercard implementation of the Expert Dictionary, which was generated adopting the default browsing semantics described in Section 2.4.1. The same application, with the same browsing semantics, has been implemented also in Hyperpad.
Figure 5 shows the "Structure" perspective of a component
of entity "Circular HyperBank 21/10/89" of type Regulation.
Notice that all the links of type "Justified by" have
been grouped under the anchor (button) "Motivations".
Figure 6 shows the same component under the perspective "Official
Anchors corresponding to application links ("Effects",
"Motivations") and perspective links ("Description"
and "Offficial Text" in Figure 5, and "Structure"
and "Description" in Figure 6) are at the bottom of
the screen. If the user is interested in seeing, for example,
the effects of the regulation shown in Figures 5 and 6, he can
click on the anchor "Effects". Since this in reality
groups several outgoing links, a chooser is activated; from it,
the user can select which of the possible destinations he wishes
to go to.
4.1 Comparison with Other Works
4.2 Evaluation, Experiences, and Feedback
4.3 Tools and Implementation
4.4 Further Developments
4.1 Comparison with Other Works
HDM shares some apparent similarities with the Entity Relationship (E-R) model . However, there is no E-R notion equivalent to HDM perspectives. Additionally, HDM Entities are much more structured than E-R entities, which are essentially flat and do not have structural links. Most importantly, whereas in the E-R model relations are included for representational reasons, HDM links are included also with the goal of providing navigation paths.
HDM differs from g-IBIS  in the fact that it does not freeze, a priori, the application domain, and therefore its representation primitives are more "general", oriented towards allowing the design of hypertext applications in most domains. HDM philosophy shares with IDE  the aim of supporting representation tasks in hypertext and of encouraging the creation of regular and consistent network structures. IDE has surely anticipated a number of concepts exploited in HDM. However, IDE is basically a development tool, while HDM is also a conceptual design device which can be useful even without an implementation of its primitives. Moreover, HDM provides richer modeling primitives -the notion of perspective, the distinction between different categories of links, the separation between hyperbase and access structures, and between authoring structures and reading structures (i.e., browsing semantics). Object Lens  classes resemble somewhat HDM entity types. Object Lens, however, does not impose any constraint on possible connections between object class instances and no real discipline on actual instances creation.
With respect to other hypertext models discussed in Section 1.2, HDM differs in the fact that it is aimed at modeling applications rather than systems. HDM shares with the Trellis model  and Tompa's model  the idea of abstracting from the contents and structure of the "nodes", which are allowed to contain arbitrarily complex information structures. Differently from HDM, however, these models are more concerned with behavioral aspects of hypertext, or with operational features, rather than on representational issues.
The approach introduced in  shares with HDM the idea of distinguishing
between authoring language, for defining hypertext structures
in a system independent manner, and browsing semantics language.
As far as browsing semantics is concerned, the work presented
in  goes a step ahead with respect to HDM, by providing a
graph-grammar based language for specifying patterns of visual
and dynamic behaviors (style templates), and general techniques
for translating generic authoring notations into systematically
structured hypertext. In this sense, this work is somehow complementary
to HDM, whose major focus for the moment is on static representational
4.2 Evaluation, Experiences, and Feedback
The HDM model can be used in different manners: as a modeling device or as an implementation device. As a modeling device, it allows to lay down clear and concise specifications of applications to be developed, or to describe applications already developed, in a system independent manner. Using HDM as an implementation device, means to directly support the development effort by HDM related tools, as described in Section 4.3.
A number of experiences have shown that significant gains in the quality and speed of the whole process of application development can be achieved by using HDM as modeling device. In particular, we have observed that HDM is especially suitable for applications where regularity, organization, modularization, and consistency are important factors. Typical examples of such applications are, for example, technical documentation, training and education [12, 27], auditing systems , and in general, large applications for corporate environments. It is therefore true that "creative" applications , where the author tends to follow his feelings in a somehow unpredictable way (e.g., inventing new nodes and new navigation patterns on the fly) rather than planning his exercise in advance, are not conveniently modeled by HDM. Our conjecture (not yet fully tested) is that most of the intensively used, existing or future, hypertext applications are unlikely to be of the "creative" kind, but rather they are planned, cohesive, and carefully organized.
As a modeling device, HDM has been successfully used several times. Beside the authors. several different research groups in four different countries are using HDM in a significant number of different application fields, which range from administration and technical manuals, to university class notes, literature, philosophy encyclopedias, art collections, and exhibitions [9, 23, 24, 25, 34]. All of them have reported that the model can be relatively easily grasped both by the users and by designers, and that a more productive cooperation can be achieved among the persons involved in the process of application development-analysts and domain experts, analysts and implementors, different implementors. Domain experts are able to discuss the design of the application in HDM terms, and to autonomously modify and improve it. This implies a tremendous gain in the efficiency and quality of knowledge and requirement analysis processes. Members of the implementation team are able to discuss the application with the analysts and to get a deep and precise understanding of the requirements of their work without the need of prototyping it. This makes it possible to split the implementation tasks among different persons, still obtaining consistent applications. Since implementors are guided by clear and precise specifications, arbitrariness is virtually eliminated.
An interesting side effect of using HDM in team work has been the fact that people who use HDM as a modeling device, tend to invest a quite extensive time in discussing "organization style" issues (e.g., the best way of organizing a set of information, the choice between establishing perspective links versus application links, etc.). These discussions are extremely effective: the overall quality of applications improves, in general, and, more interesting, groups tend to develop a common, consistent design style across different application domains.
Additionally, HDM and related tools have been shown to be quite
useful in making the development of the same application in different
versions easier, by "switching" from one environment
to another. Target systems, so far, have been Hypercard, Supercard,
Hyperpad, Toolbook, Director (the latter for animations embedded
in Hypercard-based hypertext).
4.3 Tools and Implementation
We have developed so far a number of elementary HDM-tools to speed up the development of our applications. For the time being, these tools perform the following operations:
For implementation purposes, HDM has not been yet tested on a
sufficiently large scale; the initial results, however, are quite
encouraging. Even in their rudimentary stage of development,
the above tools have greatly increased the effectiveness of our
development, by a ratio of four to one, and we have achieved enormous
savings in the development effort. For example, in an educational
application based on six entity types and eighteen link types,
six hundred units ("nodes"), and four thousand link
instances, all the visual templates for nodes of the different
types have been automatically generated, and 80% of the link instances
have been derived. It is easy to understand why this happens;
just think of the effectiveness of automatic generation of visual
templates, including anchors and their associations to links,
and, above all, automatic generation of derived links.
4.4 Further Developments
All the above tools, although effective in their own respect, do not constitute a well defined consistent development environment. The research project HYTEA , within the CEC ESPRIT program, is currently aiming at the development of a full size HDM-based development environment for hypertext applications. The project involves four different companies and two research institutions, and is scheduled to be completed by March 1993. Within the HYTEA project, the modeling primitives of HDM have been "transferred" into the concrete syntax of a language, named HDL-HDM definition language , which has been omitted here for lack of space. HDL is more a reference language than a language which will be directly used by application designers. In the final HYTEA environment, authoring in HDM will be based on visual programming, rather than on traditional programming. Some work on defining visual objects corresponding to HDM design primitives is already in progress. A reference language is still useful, however, in order to define precisely the semantics of the interactive operations offered by the HDM authoring environment.
HDM is, obviously, an evolving model: as we gain applicative experience,
we will modify the model according to the new emerging needs.
In particular, access structures currently provided by HDM are
restricted to the relatively unsophisticated notion of outline,
which has been proved to be too limited. Looking at complex corporate
environments, we found out that a typical situation is to have
several different categories of readers using the same hyperbase.
Each category of users naturally perceives the organization of
the material according to its needs. From this observation, we
came to the conclusion that access structures should evolve from
just providing entry points to the hyperbase to becoming something
like "hypertext views", i.e., ways of presenting "fictitious"
hypertext environments, specifically tailored for a class of readers.
"Fictitious" means that these environments are not
implemented on their own, but are rather "simulated"
by a suitable mapping on the underlying hyperbase. For this purpose,
the notions we are working on are "derived entities"
(i.e., entities assembled out of pieces of other, preexisting,
entities), "user-derived" links (i.e., links derived
only within a given reading environment), "parametric guided
tours" (i.e., intentionally defined guided tours), and others
of a similar kind. Another important aspect we are currently
working on is multimediality. In the current version of HDM images,
animation, or video clips can be introduced as part of the authoring-the-small
process. We have a prototype application, for example, where
entities of type "history" are made of "history
notes" (as their components), and each history note has two
perspectives-text and animation. The reader can choose, according
to his interest, either to read the textual description of an
historical event or to watch the animated version of the same
event. This approach works fine for simple applications, where
multimedia has the limited role of presenting small chunks of
information with a different perspective. In other applications,
however, multimedia may have a larger role. A video showing a
maintenance procedure, for example, touches different subjects;
it would be artificial (and ineffective) to model it as a unit
associated to a single component. We are currently working around
the idea that "active" information objects such as animation
or videoclips could play the role of "automated" guided
tours [32, 42, 44], i.e., devices which automatically take the
reader along different active information units of an underlying
hyperbase, and are "synchronized" with interlinked chunks
of static information. We are currently developing a large-scale
application  around this idea. On the basis of the fourthcoming
results we will introduce the proper extensions to HDM.
The ideas that originated the HDM work were first developed in
the context of an ESPRIT project, SUPERDOC, led by ARG-Applied
Research Group SpA We must acknowledge the technical contribution
of the ARG team in general, and Cristina Borelli, SUPERDOC Project
Leader, in particular. Many of the ideas described here benefited
from discussions with Mark Bernstein, Norman Meyrowitz, John Mylopolous,
and the members of the HYTEA Project Team, Andrea Caloini and
Luca Mainetti in particular. We are grateful to the TOIS Associate
Editor, Polle Zellweger, and to the TOIS anonymous reviewers for
their extraordinarily helpful comments on previous versions of