Jeffrey Morgan

The Hierarchy Editor Tool

One of the types of information that the Document and Code Knowledge Elicitation Toolset (DOCKET) project needs to capture are the hierarchies that exist in systems. This article describes the hierarchy editor tool developed to input hierarchical information into DOCKET. A hierarchy type definition system was developed to enable the generic hierarchy editor to be configured to edit different types of hierarchy.

1. Introduction

One of the types of information that the Document and Code Knowledge Elicitation Toolset (DOCKET) project needs to capture are the hierarchies that exist in systems. This article describes the hierarchy editor tool developed to input hierarchical information into DOCKET.

The remainder of this section describes the DOCKET project, the hierarchical information structures that need to be captured, and the need for a tool to support this capture. Section 2 describes the hierarchy type definition system that was developed to enable the generic hierarchy editor tool to be configured to edit different types of hierarchy. Section 3 describes the user interface of the hierarchy editor tool, and section 5 describes the implementation.

1.1 The DOCKET Project

DOCKET is a four year project that will produce a reverse engineering toolset for making system maintenance more effective. Existing reverse engineering tools examine only the syntactic aspects of a system such as source code. The DOCKET tools will examine both the semantic and the syntactic aspects of a system and take information from higher level knowledge sources such as existing users and documentation, as well as source code.

The DOCKET tools have three sources of knowledge about a system, called external forms: dynamic knowledge, obtained directly from people such as systems analysts; informal knowledge, taken from documentation in natural language such as user manuals; and formal knowledge, also taken from documentation but recorded in a formal language such as source code.

Knowledge from these external forms will be processed from their raw formats into machine readable forms using input tools. This machine readable form will be analyzed by the DOCKET tools to form a structured representation of the knowledge collected about a system from each of the three sources. One type of information that DOCKET tools need to capture is the hierarchical relationships that occur in a system.

1.2 Hierarchies

A hierarchy models information as a set of parent nodes that are connected by links to child nodes. Nodes store information specific to the type of information modelled by the hierarchy. Many different types of hierarchy need to be modelled, such as system functions, user goals, and agent/task hierarchies. The following hierarchy is a functional decomposition hierarchy from an analysis of the Halls And Residences Information System (HARRIS). This is a typical example of the type of hierarchical structure that needs to be captured by DOCKET. Each parent node represents a task that is composed of the sub-tasks represented by its child nodes.

Functional decomposition hierarchy from an analysis of the Halls And Residences Information System (HARRIS)

In a strict hierarchy each child may have only one parent, and sibling nodes have a natural left to right order. The hierarchy models required by DOCKET are loose rather than strict hierarchies. Loose hierarchies, or heterarchies, are hierarchies in which sibling nodes do not have an order and nodes may have more than one parent.

DOCKET also required that the way that nodes are connected must be able to be controlled by a set of link constraints. Each different type of hierarchy will have its own set of link constraints. Three types of link constraints were required: cardinality, mandatory links, and exclusive links. The cardinality link constraint specifies the minimum and maximum number of links between parent and child nodes. If the minimum is zero, the link is optional. If the minimum is one, the link is mandatory. The maximum is optional.

The mandatory link constraint ensures that at least one instance of each mandatory link must be connected to the from node of the link being validated.

The exclusive link constraint ensures that no instance of an exclusive link type are connected to the from node of the link being validated.

1.3 A Hierarchy Editor Tool

DOCKET required a tool for capturing the information in the hierarchies that exist in a system. The remainder of this article describes the hierarchy editor tool that was developed to provide DOCKET with this capability. The hierarchy editor tool enables users to create and edit different types of hierarchies. Rather than produce a separate editor for each type of hierarchy, a generic hierarchy editor was developed that could be configured to edit different types of hierarchies.

The next section describes the hierarchy type definition system that enables users to edit different types of hierarchies.

2. The Hierarchy Type Definition System

Every hierarchy has the same underlying structure: nodes connected by links that conform to a set of constraints. Consider the organisation of staff in a university department. A hierarchy type definition for a hierarchy to model this organisation might contain the nodes, links, and link constraints, such as:

Node Types

  • Staff
  • Student
  • Research Assistant
  • Project
  • Tutors (links a Staff node to a Student node)
  • Employs (links a Staff node to a Research Assistant node)
  • Manages (links a Staff node to a Project node)
  • Works with (links a Staff node to another Staff node)

A member of staff can:

  • Tutor up to 10 students
  • Employ up to 5 research assistants
  • Manage only 2 projects

A hierarchy type definition system was developed to enable the general hierarchy editor tool to be configured to edit different types of hierarchy. A hierarchy type definition provides the nodes that may be added to a hierarchy and the links that may connect them together. A hierarchy type definition also specifies the constraints that control how the nodes may be connected to the links.

An initial design proposed that hierarchy type definitions would be textual descriptions that are parsed by the editor. The requirements of this language were that it must enable users to specify the name and attributes of the nodes, the names of the links and the type of nodes they connect, and the constraints on those links. Although the users of a hierarchy type definition language would be DOCKET tool developers rather than end users, several characteristics were important: ease of use, expressiveness, and compactness. Two initial designs for such a type definition language are shown below. The first is a COBOL-like type definition language that is highly structured but verbose.

TITLE Example.

AUTHOR Jeffrey Morgan.

REMARKS This is an example of a hierarchy type definition language.

NODE-DEFINITION.
    NODE staff CONTAINS name, room.
    NODE student CONTAINS name, address, number, course.
    NODE research_assistant CONTAINS name, room, project.
    NODE project CONTAINS name, supervisor.
    NODE staff IS ROOT.
END-NODES.

LINK-DEFINITION.
    LINK tutor FROM staff TO student WITH MAXIMUM 10 IS OPTIONAL.
    LINK manages FROM staff TO project WITH MAXIMUM 2.
    LINK employs FROM staff TO research_assistant ONLY-IF TO project WITH MAXIMUM 5.
    LINK works_with FROM staff TO staff.
LINK-COMPATABILITY.
    LINK manages, tutors NOT ALLOWED-TOGETHER.
END-LINKS.

END-HIERARCHY.

The second is a Prolog-like language that defines nodes and links as predicates. Although more concise than the COBOL-like language, the Prolog-like language is harder to read and write.

% This is an example of a hierarchy type definition language
% by Jeffrey Morgan.

% node definitions
staff(name, room).
student(name, address, number, course).
research_assistant(name, room, project).
project(name, supervisor).

% link definitions
link(optional(tutor), staff, property(student, maximum(10)).
link(works_with, staff, staff, _ ).
link(manages, staff, [property(research_assistant, maximum(5), property(project, maximum(2)]).
precondition(manages(research_assistant), manages(project)). incompatible([manages, tutors]).

The solution that was actually implemented was to enable users to design new hierarchy type definitions with the hierarchy editor tool itself. This seemed a more natural tasks for tool developers than writing a textual description in a hierarchy type definition language. The editor was able to be used to design hierarchy type definitions because of the characteristic that a node or link instance in one context can be a corresponding type in another context.

The hierarchy editor tool has two modes: hierarchy type definition design mode and hierarchy design mode. The hierarchy design mode uses a hierarchy type definition created in the hierarchy type definition mode.

The hierarchy type definition design mode provides a set of base types that are used to design hierarchy type definitions: a node type called box and a link type called line. A new node type is created by adding a node of the base type box. The name given to this new node is the name of the new node type. A new link type is created by adding a link of the base type line. The name given to this new link is the name of the new link type.

The hierarchy type definition design mode provides an extended notation for designing hierarchy type definitions. The following is an example of the hierarchy type definition design notation.

Example of the hierarchy type definition design notation

The supervises and tutors link types connect staff and student nodes. A link that connects nodes of the same type, called a self link, is denoted by a short line next to the node with the name of the link at the end. In the example above, the self link works_with connects a staff node to another staff node.

A hierarchy type definition is regarded as a normal hierarchy model that was designed with the base types, box and line. A hierarchy model becomes a hierarchy type definition when it is loaded into the editor as a type definition. The hierarchy instance model is transformed into a type. The following diagram shows the design of a hierarchy type definition that is then used to configure the editor to design a hierarchy of that type.

Design of a hierarchy type definition for configuring the hierarch type editor

Part (a) shows the first stage, designing the type. The hierarchy editor tool is first configured with the base types, box and line. A new hierarchy is then designed with these types using the notation described above and saved as a normal hierarchy model. Part (b) shows the second stage in which the newly designed hierarchy is used as a hierarchy type definition to configure the editor. A new hierarchy is designed with the new type and saved.

The next section describes the user interface of the hierarchy editor tool.

3. The Hierarchy Editor Tool

The following screenshot shows the user interface of the hierarchy editor tool. The majority of the interface is taken up with the hierarchy display and editing area. Operations for loading and saving hierarchies, configuring the editor with a hierarchy type definition, etc. are accessed from pull down menus at the top of the window. Short cuts to the most common operations, adding nodes and links, are provided by the buttons to the left of the drawing area. The top button adds a new node to the hierarchy and the bottom button adds a new link.

Screenshot of the hierarchy editor tool's user interface

To add a node, the user presses the Add New Node button and a dialog box is displayed that enables the user to select from a list of the available node types. When the user is designing a hierarchy type definition, this dialog is not displayed because the base type box is the only node type available. After a node type has been selected, the cursor changes to crosshairs to enable the user to position the node in the drawing area. Clicking the mouse button adds the node. The name of the type is displayed in the top left hand corner in lower case and the name of the instance is displayed in the lower half of the node in upper case. In the following new instance of a staff node, the name of the instance is UNDEFINED, which is the default name for all new node instances.

The name of a new instance is UNDEFINED

To add a link, the user first selects the from and to nodes by clicking on them. The from node is selected first, followed by the to node. When two nodes have been selected, the user clicks on the Add New Link button and a dialog box is displayed that enables the user to select from a list of the available link types. When the user is designing a hierarchy type definition, this dialog is not displayed because the base type link is the only link type available. An option is available for validating links when they are added which, if selected, does not allow links to be added that invalidate their constraints. A facility is also provided to validate a hierarchy which involves checking the constraint of each link in the model. Constraints can be added to a link via an option in the Tools menu. A dialog box is displayed that enables the type of constraint to be specified along with its parameters, such as minimum and maximum in the case of a mandatory constraint.

Nodes can be repositioned by dragging them around the drawing area. If a child node is dragged above its parent node, the link is displayed as shown in (a) below. The start and end points are not reversed to the bottom of the child node and the top of the parent node as shown in (b) because that would change the semantics and may also invalidate a link constraint.

Nodes can be repositioned by dragging
(a)
Nodes can be repositioned by dragging
(b)

4. Implementation

The following diagram illustrates the architecture of the hierarchy editor tool. The user interface is implemented with the OSF/Motif user interface toolkit. The hierarchies are drawn with the X-Lib graphics routines using graphical and semantic hierarchy information. The graphical information describes the co-ordinates of the nodes and links on the screen and is stored in a separate data file for each hierarchy.

Architecture of the hierarchy editor tool

The semantic information is stored in a BIM Prolog database that is accessed with a knowledge base manager. The semantic information about hierarchy models, represented by the nodes and links, and hierarchy type definitions are stored as Prolog predicates.

4.1 Hierarchy Instances

Node instances are stored in a node_instance predicate:

node_instance(node_id, node_type, node_name, node_attributes_list)

Link instances are stored in a link_instance predicate:

link_instance(link_id, link_type, link_name, from_node_id, to_node_id,
    minimum_allowed, maximum_allowed, mandatory_links_list, exclusive_links_list)

4.2 Hierarchy Type Definitions

Node types are stored in a node_type predicate:

node_type(node_type_name)

Link types are stored in a link_type predicate:

link_type(link_type_name, from_node_type, to_node_type,
    minimum_allowed, maximum_allowed, mandatory_links_list, exclusive_links_list)

4.3 Access Predicates

The semantic information represented by each hierarchy must be available for use by other DOCKET tools. A set of Prolog predicates provide a well defined interface to this information. Access and modifier predicates such as GetNodeName and ChangeLinkName encapsulate the information and protect it from corruption by the other DOCKET tools.

The interface to the Prolog database provides predicates to ensure that the link constraints are met. Validation involves checking that the from and to nodes of a link are of the correct type with the CheckLinkNodeTypes predicate. If the link has a cardinality constraint, validation involves checking that the minimum and maximum constraints have been met with the CheckLinkMin and CheckLinkMax predicates. If the link has a mandatory or exclusive constraint then the number of links connecting the from and to nodes are checked to ensure the relationships described in section 1.2 are upheld with the CheckLinkMandatory and CheckLinkExclusive predicates, respectively.

4.5 Instance to Type Conversion

All hierarchy models, including hierarchy type definitions, are stored as instances. When a hierarchy model is used as a hierarchy type definition it is converted from instance form to type form. Converting a node from an instance into a type involves taking the name of the instance and adding, or asserting, a node_type predicate into the database using the name as its argument. Node instances such as

node_instance(0, box, staff, []).
node_instance(2, box, student, []).

are converted into the following node types

node_type(staff).
node_type(student).

The node instances are then retracted from the database. Note that the type of the node instances is box, the base type for a node.

Converting a link from an instance into a type requires several steps. The types of the from and to nodes must be retrieved from the database because only their unique identifiers are stored in the link instance. Using the node instances above as an example, the type of the from node (with unique identifier 0) is staff, and the type of the to node (with unique identifier 2) is student. The link instance

link_instance(2, line, tutors, 0, 2, 0, 10, none, none).

is converted into the following link type

link_type(tutors, staff, student, 0, 10, node, none).

The link instance is then retracted from the database. Again, note that the type of the link instance is line, the base type for a link.

References

  • The Document and Code Knowledge Elicitation Toolset (DOCKET), ESPRIT Project 5111.