Figure 1: Multi-user canvas editing application and its PAC* model.
Parlevink group,
Faculty of Computer Science
University of Twente,
Enschede,
P.O. Box 217, 7500 AE, Netherlands
schooten@cs.utwente.nl
Boris van Schooten
This paper discusses a specification technique that is based on a traditional (entity-relationship) database model to model the architecture of complex interactive systems, in particular multimodal and multi-user user interfaces.
User interface components and other software components are modelled as agents, each of which communicates with the others through a shared database. The database may be structured in terms of the agents, that is, each agent corresponds to an entity in the database.
The technique consists of several executable languages, providing two levels of detail: the configuration level, describing the system structure, and the component level, describing the behaviour of an individual agent.
The technique may be combined with well-established non-executable specifications, such as entity-relationship diagrams and screen layouts. Its application in a development cycle is discussed, and a small example application is given that illustrates its usage.
This paper proposes a specification technique for specifying multi user and multimodal virtual environments. A specification technique (or specification method) is defined here as a suite of specification languages. It facilitates development in the following ways [5, 3, 25]:
Here, we consider execution of the full system to be part of the execution capabilities that a specification technique should have. This means that programming (or implementation) languages are considered an integral part of a specification technique. Specification techniques often have more than one language, in order to cover the three aspects more satisfactorily, and to enable specifications with different viewpoints and different levels of abstraction.
Using multiple languages, however, has the problem of making sure the specifications match. This is particularly cumbersome in highly iterative development such as prototyping and user-centred development, and has led to techniques such as prescribed in extreme programming [3]. In extreme programming, the programming language is viewed as the only specification language. Alternative ways to deal with this matching problem are a separation into multiple programming languages, each describing one aspect of the system [16], and specifying a well-defined match between the more abstract or non-executable languages and the executable or programming languages. Both approaches will be used in the technique described here.
The technique is being developed as part of the VETk (Virtual Environment Toolkit) system [26]. VETk should eventually provide a suite of specification languages, standard components, and software tools for development of virtual environments (VEs). In particular, we consider VEs with the following properties:
An example of such a system is our in-house project, the Virtual Music Centre (VMC) [22]. There are specific problems related to this type of system, which will be discussed in more detail below. Multi-agent and multimodal imply a complex architecture. In particular, some parts of the system have to gather and interpret information from various sources. Distributed implies increased technical constraints. While such technical constraints are sometimes considered non-functional and therefore not important for initial system specifications, in practice they often turn out to have an impact on the functional design of a system [4]. So, a specification technique for such systems should preferably deal with such technical issues in an integrated way.
Various models exist that provide a means for structuring single-user or multi-user interfaces in an understandable way. In order to explain the rationale behind the technique proposed here, we discuss some of the most common classes of models.
Architectural models are software component models that are meant both to provide a structural framework for user interface design and to provide a separation between the user interface and the application domain (which we will call the domain model here). The essential aspects of these models, which are abstract and non-executable, are also called architectural styles [14]. Some of these models do have explicit implementation support in the form of programming languages or software libraries, filling in the details not specified by the architectural styles themselves.
The domain model is typically modelled as a separate software component or set of components, and user activities may be specified as access operations on these components. Clear examples of this are the Seeheim and Arch [11] models. However, there is more data in the system than just the state of the domain model: there is also the state of user interface itself. We will specifically focus on how different models represent this state.
Some models, such as PAC [15], PAC-Amodeus [21], and MVC [15] encapsulate the user interface state in specific types of software component (called the Abstraction component in PAC, or the Model component in MVC), while other types of component represent display to and manipulation by the user (the Presentation components in PAC, and the View and Control components in MVC).
MVC enforces little structuring except for the separation into its three types of component, with the Model component the only one that models shared state. PAC enforces the strictest structuring scheme, namely, Presentation and Abstraction components are always local to a single Control component, which serves as `glue' component for interacting with other Control components. A Control component together with its local Presentation and Abstraction components is also called a PAC agent. In this manner, the application-specific `glue' code may remain mostly localised in the Control components. The dependency structure between the Control components is always a tree. In other words, a Control component may encapsulate a number of other PAC agents. These general ideas of separation into `glue' and hierarchical encapsulation are commonly found in other user interface models and toolkits as well [14, 18].
There are some models that provide means for structuring inter-user communication. One example is the PAC* model [6, 9], which is a descendant of PAC-Amodeus. In the PAC* model, each user is represented by a PAC tree. Agents which are in the same position in the different users' trees are able to communicate directly. These agents are called peer agents. This communication scheme may be considered similar to replication schemes found in multi-user models [14]. As an example, consider a multi-user scrollbar which shows one regular scrollbar, and a view upon the positions of the other users' scrollbars [6], see figure 1. The PAC* solution is that peer scrollbars communicate their positions directly.
Figure 1: Multi-user canvas editing application and its PAC* model.
In fact, the PAC* architecture assumes that the user interface state required for inter-user awareness is typically found inside peer agents. This works well for simple cases such as the multi-user scrollbar. However, a more complex architecture would be needed if, for example, one had chosen to model the regular scrollbar and the view bar showing other users' scrollbars as separate agents that may be used in separate parts of the user interface. In those cases, the scrollbar position would have to be communicated up the tree to the appropriate parent and its peers, and from there, back down to the users' view bars. Adding such a feature to an existing user interface is likely to require modifications to be made in each of these control components.
This is, for instance, the case in applications in which the user interface for each user contains different windows with various content. In this case, the concept of peer communication is not really of much use. For example, if the canvas application would include a general overview window showing the activities of all users, only the root agent would allow the window's components to get at this information, because the information resides in different subtrees. See figure 1. Another example is in fact given by the very example communication illustrated in [9]. In such cases, the root agent needs to handle all peer communication, and effectively becomes a central access point for much of the user interface state.
This small example indicates that in some user interfaces, user interface state information is inherently non-localised, and is difficult to encapsulate meaningfully. This particularly goes for multimodal and multi-user systems, in which one party needs to keep track of the various activities of another in an integrated manner. Other examples are: a `radar' view showing an overview of users' activities, as is found in GroupKit, and context-sensitive assistance, in which an assistant agent keeps track of a user's various activities in various parts of the user interface and offers help when appropriate. In fact, some multi-user toolkits, such as GroupKit [23], maintain a separate distributed shared dataspace to model parts of the user interface state that should be shared between users. In the case of GroupKit, the structure of this dataspace actually bears no relation to the structure of the user interface. In fact, the dataspace simply bypasses the architectural model used by the user interface.
A second problem of architectural styles is that few of them provide proper notations or guidelines for modelling constraints and interrelations between dynamically-created components, such as multiple windows in a single-user application or multiple users.
A third problem is the difficulty of matching the style's essential features with its implementation model(s). Usually, no abstract or high-level specification is defined for a given style, and instead, one has to encode the constructs which are inherent to the style using specifications in a regular programming language. Some styles do suggest some form of diagrammatic notation, which is however limited to relatively informal sketches [6, 9]. While such notations are apparently useful, the role that they might play in the specification of such systems is usually not discussed. There are some architectural styles that do use a special-purpose programming language to concisely describe the architecture. An example of this is Chiron-2 [14].
Another kind of model that can be used to structure user interfaces are conceptual models, in particular entity-relationship (E/R) models. The best-known E/R specification language is the entity-relationship diagram (ERD) with its many variants and extensions [13, 24]. Relational database implementations may also be considered E/R models, providing suitably high-level executable specifications closely matching the more abstract ERDs [24].
E/R models have been used extensively to model the domain models of various types of application. This includes relational database models, in which the interaction between user interface components and the domain model proceeds through database views and database update operations.
Additionally, the structure and state of the user interface itself can be modelled using E/R models. One example is the ERMIA (Entity Relationship Modelling of Information Artifacts) technique [13]. ERMIA uses ERDs to model the information structure of various artifacts, including user interfaces. It is meant for addressing usability issues, rather than implementation issues, and is suitable for non-programmers. It does, however, not prescribe an executable implementation model, nor does it discuss the mapping from an ERMIA ERD to an implementation.
ERDs may also be used to specify the architecture of user interfaces, as specified according to a specific architectural style. This provides an abstract graphical notation of an application's architecture. Even using plain ERD specifications in this manner already provides some added value.
Typical PAC tree diagrams only sketch the structure of a user interface at a specific moment in time. If we simply represent tree nodes by entities and arcs by relationships, we get an ERD representation. The relationships need not even be given names, since they are all of the same kind. With this representation, we are already able to specify the general pattern that the tree should conform to at any moment in time, by using relational multiplicities. This kind of diagram concisely specifies the structural correspondence of the agents in the system. In fact, such a representation is similar to one that might have been produced by an ERMIA specification.
As an example, consider the PAC-style model for our multi-user editor. An ERD specifying the general structure of the system is specified in figure 2. It specifies that there are only two kinds of windows, editor windows and overview windows. At any moment in time, a user may have zero or more editor windows open, and may or may not be viewing the overview window. The overview window contains zero or more file views.
Figure 2: ERD of abstract PAC architecture of multi-user editor.
Additionally, we can specify user interface state in E/R models by means of entity attributes. There are some user interface toolkits that use such an approach: the component structure is a graph, and each component can define variables within its own node within the graph. Component interaction may be achieved by traversing the graph structure and reading nodes' variables as needed. One of the nicest examples is Amulet [20], which structures its components in a tree, and specifies interdependencies between them by means of queries specified in terms of this tree structure. A similar scheme is also supported by VRML [7], which also uses a tree, and enables components to traverse the tree structure and read variables from the different nodes at will. These trees are not encapsulation trees. Rather, they specify visual embedding in some cases, and conceptual grouping in other cases.
In fact, there is no fundamental reason why other structures, such as directed labelled graphs, might not be used instead of trees. The component structure is in effect a relational database, with each component representing an entity in the database. So, such toolkits may effectively be modelled using a relational database approach. In terms of the PAC model, the Abstraction part of the user interface is now entirely modelled within the database, while the Control part operates by means of accesses to this database.
For example, the files being edited and the corresponding scrollbar positions may be effectively modelled using attributes, as given in figure 2. The file views may conveniently obtain their information by means of database views.
A new specification technique is proposed here, which uses E/R modelling to model the architecture of a user interface. Unlike architectural models, no encapsulation is used, but all information is shared through entity attributes. A special-purpose database engine was developed to enable executable specifications using a relational database approach. As compared to the discussed models, this approach provides the following things:
The proposed technique integrates several executable and non-executable languages, each playing a specific role in the specification of a system. While some of the languages are still subject to improvement, the technique as a whole should serve well as a proof of concept of such an approach.
Executable systems are built using separate specifications for the architectural level of the system. The role these specifications play is comparable to that of PAC's Control components, and to architectural description languages and configuration languages [1, 14]. This part of the specification will be called the configuration level. The specifications of the individual components will be called component level specifications.
Different languages may be used for each level. Currently, two configuration languages are supported: a simple scripting language called VETkScript, and HTML using embedded agents. Using HTML in this way enables specification of a set of components corresponding to a user interface element (in particular, a window) by combining the element's component configuration with its screen layout within a single specification [2]. Of course, a visual tool that generates HTML might be used instead [2].
A component (also called agent) is specified by its interface to the outside world (its instantiation parameters, its inputs, and its outputs), and its behaviour. This is done in a separate language called VETk Component Language. It is, as yet, just a thin layer on top of Java, and its main purpose is to integrate component interfaces with regular Java code.
The technique's executable languages can effectively be combined with E/R diagrams (ERDs). Figure 3 gives a rough idea of how the technique may be used in a development process. One starts development with some informal specifications. Typically, this includes screen layouts [17], models of the user interface (or Web site) structure [24], and models of the system's concepts and behaviour [17]. The first step from here is to identify the different types of agents that are used in the system. This may mean adopting existing agents from an agent library, or defining custom agents and specifying their interfaces. Using these agent interface specifications, an ERD may be specified, globally describing the user interface state model.
The screen layouts and user interface structure should be directly translatable to a set of VETkScript and HTML files. This results in a first prototype that shows the system's appearance and some simple behaviour. The system may be filled in and refined further by specifying the internals of the custom agents, and, if necessary, modifying parts of the configuration to fit them in. The high degree of configurability and the well-defined user interface state model should minimise change impact. The intermediate systems may be further refined by means of incremental changes. Ideally, this goes all the way to the final system.
Figure 3: Example development cycle.
In configuration language approaches, a system is specified by instantiating a number of components and defining how they should be `plugged' together [1, 2, 7]. In the most basic case, a component specifies an interface, consisting of a set of input and output points. A system configuration is defined by plugging output points to input points in some manner. In our model, we use an alternative approach to input. Instead of having regular input points, a component maintains views upon the outside world. The views represent sets of data objects, which are updated by input from the outside world, consisting of additions to and deletions from these sets. The views are automatically updated when new information is available. The output points output regular data objects that may be translated to database update actions by VETkScript scripts. A component is configured by coupling database queries to views, and outputs to database write actions.
The components in our model will be called agents. The precise needs for satisfactorily specifying agent control flow fall outside the scope of this paper. In the current version of the model, agent behaviour is specified mostly using Java statements. The agent's interface may be specified like this:
Name: <agentname>
Arguments: List of ( <argument-java-type> <argument-id> )
Views: Set of ( <view-id>
( List of ( <field-java-type> <argument-id> ) )
)
Updates: Set of ( <output-script-id>
( List of ( <argument-java-type> <argument-id> ) )
)
In other words, the agent has a number of initialisation parameters, which are regular Java objects, and a number of views and updates. A view is specified by a name and a list of Java types which stand for its required fields. An update is specified by a name and a set of parameters, which are again regular Java objects.
The VETkScript language is basically a regular procedural language with built-in database query facilities. While it is obviously subject to improvement, it should illustrate the role of such a language in the technique well enough. Scripts serve three purposes:
Each agent corresponds to an entity in the database, distinguished by means of a unique ID. The agent's ID is always accessible from within a script through the variable %self, enabling any database queries or operations to be specified in terms of this ID. In case the script is an output script, the agent also passes its output variables to the script.
The language has functions for creating new agents (new), coupling database queries to the views of the agent in which the script runs ( adq), and doing database updates (upd). The format used for both query specification and update operations are basically Prolog [27] specifications, including Prolog-style pattern matching. A tuple is specified as a Prolog-style predicate
<tuple-name> `(' <field> <field> ... `)'
A field (or attribute in E/R terminology) may be a value, which indicates that specific value at that position, or a variable, which indicates that any field in the database matches the variable at that position. A query is specified as
<variable> <variable> ... `:' <tuple> <tuple> ...
This selects a number of variables from the list of matches specified by the list of tuples.
An update is specified as the set of tuples that should be added or deleted:
<tuple> <tuple> ...
Optionally, it may be followed by a query which specifies the values of any variables used in these tuples:
<tuple> <tuple> ... `:' <tuple> <tuple> ...
The regular notation used in VETk applications maps to E/R diagrams in the following way. A field of an entity with ID A is represented by the tuple field-name(A field-value). A relation between entities with ID A and B is represented by the tuple relation-name(A B). This means that an entity does not really have a type associated with it (though this may be added easily by means of an extra type field), and fields may be added to and deleted from an entity at will during its lifetime.
For example, if we assume that the relations in figure 2 are named contains in our database, the file views of our multi-user editor may obtain their scrollbar positions using the following query:
1 POSITION : contains(OVERVIEW %self) file_viewed(OVERVIEW FILENAME) 2 filename(EDITOR FILENAME) 3 contains(EDITOR SCROLLBAR) position(SCROLLBAR POSITION)
Line 1 specifies the filename of the file that the file view belongs to. Line 2 specifies the editors editing that file. Line 3 specifies the scrollbar positions of these editors.
Specifications may be executed with help of a publisher-subscriber [12] database engine. The engine is based on the SWI-Prolog engine [27], with a C layer that handles publisher-subscriber functionality and a Java layer that handles Java objects and integration with other Java code.
The engine may be run as a separate process, which is accessed using an object request broker running on top of Java object streams and TCP sockets. This setup enables applets from remote sites to connect to the system and communicate through the database. While this `central server' approach is not very scalable, it is reasonably efficient for small-scale network applications, and serves well as a proof-of-concept implementation. A more distributed approach is left as a subject of future research.
Both the database update actions and the query result updates are transmitted asynchronously [19], that is, they do not block the agents or the engine, but are queued. While asynchronous message passing is more difficult to understand than regular synchronous message passing, some degree of asynchrony is essential for obtaining a fast response in distributed environments.
In this section, we illustrate the technique further by means of a larger example: the specification of a simple multi-user VE. This VE is inspired by the 3-dimensional Virtual Musinc Centre (VMC) [22] system, but represents the environment using static displays of the different VE locations. A dialogue agent is present in one of the locations, answering users' inquiries. Meanwhile, the users may browse through regular Web pages containing related information. While its graphical representation is much more primitive than the `real' VMC, it can do some things that the VMC cannot. In particular, the dialogue agent is able to process multimodal input: it is aware of the users' pointing and browsing activities.
An example screen layout of the application is given in figure 4. The most essential window is that of the VE interface. Basically, there is a canvas displaying the VE action, some means for specifying user name and avatar appearance, and text chat facilities. Other windows include regular Web pages and table views.
Figure 4: Prototype window layouts of the VE interface, specified using HTML.
The GUI components may be modelled using standard agents. The VE can be specified as a discrete set of rooms, each containing a number of objects. Some of the objects may be exits to other rooms. Some of the objects may be avatars, which are able to walk around the building, speak, and point at things. There is one dialogue agent in the system, called Karin. Karin is multimodal, that is, it is able to keep track of a user's pointing and viewing behaviour, listen to user's utterances, do its own utterances, and show tables with information:
Name: KarinAgent /* the VMC dialogue agent */
Arguments: /*none*/
Views: user_pointing(Agent user, String topic)
user_viewing(Agent user, String topic)
user_utterance(Agent user, String utterance)
Updates: utter(String utterance)
new_table(Agent user)
table_item(Agent user, String item)
An ERD specifying this general setup is shown in figure 5. Each user is specified as possibly viewing one or more Web pages, each with a number of web page components. Some of the components may be hyperlinks, which indicate whether they are being pointed at or clicked.
Figure 5: ERD of the user interface state model of the VE.
The complete executable code for the system consists of the HTML code for the windows, the code specifying KarinAgent's behaviour, and the initialisation script that sets up the VE locations. Here, we will only look in detail at a part of the initialisation script, namely, the part that initialises Karin:
1 new karin KarinAgent {init_s =
2 adq user_pointing USER TOPIC :
3 pointing_at(USER OBJ) topic(OBJ TOPIC);
4 adq user_viewing USER TOPIC : views(USER PAGE) topic(PAGE TOPIC);
5 adq user_utterance USER UTT : contains(ROOM %%self)
6 contains(ROOM USER) speak_event(USER UTT); },
7 {new_table_s =
8 upd -showing_table_item(%%self %%user _);
9 upd .show_document(PAGE "table_view.html") : views(%%user PAGE); },
10 {table_item_s = upd showing_table_item(%%self %%user %%item); },
11 {utter_s = upd .speak_event(%%self %%utterance); };
12 upd object_app(%karin "karin_avatar.gif") object_pos(%karin 306 74);
Lines 1-11 create a new instance of KarinAgent, assigning its ID to the variable %karin. KarinAgent takes four parameters, as specified between braces. init_s (line 1-6) is the initialisation script, which couples queries to its three views using the adq <view> <query> command. new_table_s (line 7-9) is the output script for creating a new table. In line 8, all old showing_table_item relations for the corresponding user are removed. Line 9 requests a new document table_view.html to be shown by the corresponding user's browser. table_item_s (line 10) adds a table item to be shown by creating a showing_table_item relation. utter_s (line 11) issues a speak_event. Line 12 sets some fixed attributes in the karin entity, namely, its avatar's appearance and position.
While the current technique is still in a proof-of-concept stage, we have illustrated here how multi-user and multimodal VEs may be structured using E/R modelling techniques. The proposed separation into configuration level and component level works at least reasonably well: it was found that components could be re-used in various configurations without modification, and without needing excessive amounts of configuration-level code.
In general, the executable specifications were found to be compact. If we do not count the regular Web pages, the code for our VMC example totals less than 190 lines. Other small prototype applications, such as a multi-user canvas editor and a chat room, could be built using less than 100 lines of code. In order to test the scalability of the approach to large systems, more complex example systems should be built.
While plain ERDs have been shown to be useful as specifications, there is a wide range of semantics that they cannot specify. A more advanced variant of ERDs could be used, or a less abstract language, such as Object Constraint Language (OCL) [8], could be used to specify structural constraints. In fact, OCL specifications could be used to verify the correctness of a system's behaviour.
The technique's suitability for multi-user applications requiring more complex coordination should be tested. For instance, even while basic concurrent multi-user write access can be modelled simply by means of concurrent database updates, no applications have been built that require a complex arbitration protocol [16].
In order to test the suitability of the technique for driving more complex graphical representations, it should be applied to VRML or some other 3D or animation system. The role of VRML may be analogous to that of HTML, specifying detailed graphical representations that may be driven by agents embedded in the VRML code. A first VRML prototype has been built, using translation and rotation commands to move VRML objects. A similar scheme could be used for animations, with abstract commands triggering or driving arbitrary VRML animations.
The centralised nature of the current database engine is obviously not suitable for larger-scale distributed applications. The possibilities of improving efficiency by means of a more distributed implementation of the database engine should be explored.
Structuring distributed virtual environments using a relational database model
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -show_section_numbers -split 0 dsvis-schooten-final.
The translation was initiated by Boris van Schooten on Sun Jan 13 13:25:40 MET 2002