| Partially Shared Views: A Scheme for Communicating among Groups that Use Different Type Hierarchies | | BIBAK | 1-26 | |
| Jintae Lee; Thomas W. Malone | |||
| Many computer systems are based on various types of messages, forms, or
other objects. When users of such systems need to communicate with people who
use different object types, some kind of translation is necessary. In this
paper, we explore the space of general solutions to this translation problem
and propose a scheme that synthesizes these solutions. After first
illustrating the problem in the Object Lens system, we identify two partly
conflicting objectives that any translation scheme should satisfy: preservation
of meaning and autonomous evolution of group languages. Then we partition the
space of possible solutions to this problem in terms of the set theoretic
relations between group languages and a common language. This leads to five
primary solution classes and we illustrate and evaluate each one. Finally, we
describe a composite scheme, called Partially Shared Views, that combines many
of the best features of the other schemes. A key insight of the analysis is
that partially shared type hierarchies allow "foreign" object types to be
automatically translated into their nearest common "ancestor" types. The
partial interoperability attained in this way makes possible flexible standards
from which people can benefit from whatever agreements they do have without
having to agree on everything. Even though our examples deal primarily with
extensions to the Object Lens system, the analysis also suggests how other
kinds of systems, such as EDI applications, might exploit specialization
hierarchies of object types to simplify the translation problem. Keywords: Software engineering, Tools and techniques, Modules and interfaces, Software
libraries, Software engineering, Management, Software configuration management,
Operating systems, Organization and design, Distributed systems, Hierarchical
systems, Data, Files, Organization and structure, Information systems, General,
Information systems applications, Communications applications, Electronic mail,
Artificial intelligence, Applications and expert systems, Office automation,
Management of computing and information systems, Software management,
Management of computing and information systems, System management, Design,
Languages, Management, Standardization, Communication, Computer supported
cooperative work, Information Lens, Object Lens, Partially shared views | |||
| Compression, Information Theory, and Grammars: A Unified Approach | | BIBAK | 27-49 | |
| Abraham Bookstein; Shmuel T. Klein | |||
| Text compression is of considerable theoretical and practical interest. It
is, for example, becoming increasingly important for satisfying the
requirements of fitting a large database onto a single CD-ROM. Many of the
compression techniques discussed in the literature are model based. We here
propose the notion of a formal grammar as a flexible model of text generation
that encompasses most of the models offered before as well as, in principle,
extending the possibility of compression to a much more general class of
languages. Assuming a general model of text generation, a derivation is given
of the well known Shannon entropy formula, making possible a theory of
information based upon test representation rather than on communication. The
ideas are shown to apply to a number of commonly used text models. Finally, we
focus on a Markov model of text generation, suggest an information theoretic
measure of similarity between two probability distributions, and develop a
clustering algorithm based on this measure. This algorithm allows us to
cluster Markov states, and thereby base our compression algorithm on a smaller
number of probability distributions than would otherwise have been required. A
number of theoretical consequences of this approach to compression are
explored, and a detailed example is given. Keywords: Data, Coding and information theory, Data compaction and compression, Models
and principles, Systems and information theory, Information theory, Information
storage and retrieval, Information storage, Artificial intelligence, Natural
language processing, Algorithms, Theory, Huffman coding, Markov model of
language generation | |||
| Distributed Form Management | | BIBAK | 50-76 | |
| Heikki Hammainen; Eero Eloranta; Jari Alasuvanto | |||
| An open architecture for distributed form management is described. The
model employs object-orientation in describing organizational units as well as
individual users as entities with uniform external interfaces. Each entity is
represented by an autonomous user agent which operates on local and migrating
forms. The form concept encapsulates data, layout, and rules into a unified
object which is the basic unit of presentation, processing, storage, and
communication. All functionality of the system appears in rules of form
classes and all data in instances of these form classes. This approach applies
the techniques of computer supported cooperative work to provide a flexible
mechanism for interpersonal, intraoffice, and interoffice procedures. The main
challenge is to organize the collaboration without affecting the autonomy of
individual user agents. In this respect, the contribution of the model is the
mechanism for form migration. The dynamic integration of forms into different
agents is solved with the coordinated interchange of form classes. A specific
inheritance scheme provides the desired flexibility by separating the
interrelated private and public form operations within each agent. The paper
first describes the architecture by starting from a single agent and moving
progressively towards a set of cooperating agents. Then an agent
implementation called PAGES is described, experiences reported, and the open
issues discussed. A typical distributed ordering procedure is used as an
example throughout the text. Keywords: Computer-communication networks, Distributed systems, Distributed
applications, Database management, Systems, Object-orientation, Information
systems applications, Office automation, Information systems applications,
Communications applications, Electronic mail, Human factors, Management,
Performance, Computer supported cooperative work, Form management, User agent | |||
| A Transient Hypergraph-Based Model for Data Access | | BIBAK | 77-102 | |
| Carolyn Watters; Michael A. Shepherd | |||
| Two major methods of accessing data in current database systems are querying
and browsing. The more traditional query method returns an answer set that may
consist of data values (DBMS), items containing the answer (full text), or
items referring the user to items containing the answer (bibliographic).
Browsing within a database, as best exemplified by hypertext systems, consists
of viewing a database item and linking to related items on the basis of some
attribute or attribute value.
A model of data access has been developed that supports both query and browse access methods. The model is based on hypergraph representation of data instances. The hyperedges and nodes are manipulated through a set of operators to compose new nodes and to instantiate new links dynamically, resulting in transient hypergraphs. These transient hypergraphs are virtual structures created in response to user queries, and lasting only as long as the query session. The model provides a framework for general data access that accommodates user-directed browsing and querying, as well as traditional models of information and data retrieval, such as the Boolean, vector space, and probabilistic models. Finally, the relational database model is shown to provide a reasonable platform for the implementation of this transient hypergraph-based model of data access. Keywords: Database management, Logic design, Data models, Information storage and
retrieval, Information storage, Design, Data access model, Data items, Data
manipulation, Data structures, Hypertext, Transient hypergraphs, Virtual
structures | |||
| Design of the Mneme Persistent Object Store | | BIBAK | 103-139 | |
| J. Eliot B. Moss | |||
| The Mneme project is an investigation of techniques for integrating
programming language and database features to provide better support for
cooperative, information-intensive tasks such as computer-aided software
engineering. The project strategy is to implement efficient, distributed,
persistent programming languages. We report here on the Mneme persistent
object store, a fundamental component of the project, discussing its design and
initial prototype. Mneme stores objects in a simple and general format,
preserving object identity and object interrelationships. Specific goals for
the store include portability, extensibility (especially with respect to object
management policies), and performance. The model of memory that the store aims
at is a single, cooperatively-shared heap, distributed across a collection of
networked computers. The initial prototype is intended mainly to explore
performance issues and to support object-oriented persistent programming
languages. We include performance measurements from the prototype as well as
more qualitative results. Keywords: Programming languages, Processors, Run-time environments, Operating systems,
Storage management, Distributed memories, Segmentation, Storage hierarchies,
Virtual memory, Operating systems, File systems management, Access methods,
Directory structures, File organization, Operating systems, Organization and
design, Operating systems, Performance, Measurements, Operating systems,
Systems programs and utilities, Database management, Physical design, Access
methods, Database management, Systems, Design, Languages, Performance, Database
programming languages, Object-based systems, Object management, Object-oriented
database systems, Object-oriented programming languages, Persistent object
stores, Persistent programming languages | |||
| New Techniques for Best-Match Retrieval | | BIBAK | 140-158 | |
| Dennis Shasha; Tsong-Li Wang | |||
| A scheme to answer best-match queries from a file containing a collection of
objects is described. A best-match query is to find the objects in the file
that are closest (according to some (dis)similarity measure) to a given target.
Previous work [5, 33] suggests that one can reduce the number of comparisons required to achieve the desired results using the triangle inequality, starting with a data structure for the file that reflects some precomputed intrafile distances. We generalize the technique to allow the optimum use of any given set of precomputed intrafile distances. Some empirical results are presented which illustrate the effectiveness of our scheme, and its performance relative to previous algorithms. Keywords: Analysis of algorithms and problem complexity, Nonnumerical algorithms and
problems, Sorting and searching, Database management, Systems, Query
processing, Information storage and retrieval, Information search and
retrieval, Search process, Artificial intelligence, Miscellaneous, Algorithms,
Performance, Theory, Best match, Distance metrics, File searching, Heuristics,
Lower bounds, Matching, Topology, Upper bounds | |||
| Imprecise Information and Uncertainty in Information Systems | | BIBAK | 159-180 | |
| J. M. Morrissey | |||
| Information systems exist to model, store, and retrieve all types of data.
Problems arise when some of the data are missing or imprecisely known or when
an attribute is not applicable to a particular object. A consistent and useful
treatment of such exceptions is necessary. The approach taken here is to allow
any attribute value to be a regular precise value, a string denoting that the
value is missing, a string denoting that the attribute is not applicable, or an
imprecise value. The imprecise values introduce uncertainty into query
evaluation, since it is no longer obvious which objects should be retrieved.
To handle the uncertainty, two set of objects are retrieved in response to
every query: the set of objects that are known to satisfy with complete
certainty and the set that possibly satisfies the query with various degrees of
uncertainty. Two methods of estimating this uncertainty, based on information
theory, are proposed. The measure of uncertainty is used to rank objects for
presentation to a user. Keywords: Models and principles, Systems and information theory, Information theory,
Database management, Systems, Query processing, Design, Management, Incomplete
information, Null values, Query evaluation, Uncertainty | |||
| The UAN: A User-Oriented Representation for Direct Manipulation Interface Designs | | BIBAK | 181-203 | |
| H. Rex Hartson; Antonio C. Siochi; Deborah Hix | |||
| Many existing interface representation techniques, especially those
associated with UIMS, are constructional and focused on interface
implementation, and therefore do not adequately support a user-centered focus.
But it is in the behavioral domain of the user that interface designers and
evaluators do their work. We are seeking to complement constructional methods
by providing a tool-supported technique capable of specifying the behavioral
aspects of an interactive system-the tasks and the actions a user performs to
accomplish those tasks. In particular, this paper is a practical introduction
to use of the User Action Notation (UAN), a task- and user-oriented notation
for behavioral representation of asynchronous, direct manipulation interface
designs. Interfaces are specified in UAN as a quasihierarchy of asynchronous
tasks. At the lower levels, user actions are associated with feedback and
system state changes. The notation makes use of visually onomatopoeic symbols
and is simple enough to read with little instruction. UAN is being used by
growing numbers of interface developers and researchers. In addition to its
design role, current research is investigating how UAN can support production
and maintenance of code and documentation. Keywords: Software engineering, Requirements/specifications, Languages, Software
engineering, Tools and techniques, User interfaces, Software engineering,
Design, Representation, Design, Human factors, Languages, Behavioral design,
Constructional design, Human-computer interface, Representation of interfaces,
Task analysis, User interface | |||
| ITS: A Tool for Rapidly Developing Interactive Applications | | BIBAK | 204-236 | |
| Charles Wiecha; William Bennett; Stephen Boies; John Gould; Sharon Greene | |||
| The ITS architecture separates applications into four layers. The action
layer implements back-end application functions. The dialog layer defines the
content of the user interface, independent of its style. Content specifies the
objects included in each frame of the interface, the flow of control among
frames, and what actions are associated with each object. The style rule layer
defines the presentation and behavior of a family of interaction techniques.
Finally, the style program layer implements primitive toolkit objects that are
composed by the rule layer into complete interaction techniques. This paper
describes the architecture in detail, compares it with previous User Interface
Management Systems and toolkits, and describes how ITS is being used to
implement the visitor information system for EXPO'92. Keywords: Software engineering, Tools and techniques, Software libraries, User
interfaces, Models and principles, User/machine systems, Human factors,
Information systems applications, General, Computer graphics, Methodology and
techniques, Device independence, Ergonomics, Interaction techniques, Languages,
Management of computing and information systems, Project and people management,
Systems analysis and design, Systems development, Management of computing and
information systems, Software management, Software development, Software
maintenance, Design, Human factors, Languages, Management, Standardization,
Management systems, User interface | |||
| Unidraw: A Framework for Building Domain-Specific Graphical Editors | | BIBAK | 237-268 | |
| John M. Vlissides; Mark A. Linton | |||
| Unidraw is a framework for creating graphical editors in domains such as
technical and artistic drawing, music composition, and circuit design. The
Unidraw architecture simplifies the construction of these editors by providing
programming abstractions that are common across domains. Unidraw defines four
basic abstractions: components encapsulate the appearance and behavior of
objects, tools support direct manipulation of components, commands define
operations on components, and external representations define the mapping
between components and the file format generated by the editor. Unidraw also
supports multiple views, graphical connectivity, and dataflow between
components. This paper describes the Unidraw design, implementation issues,
and three experimental domain-specific editors we have developed with Unidraw:
a drawing editor, a user interface builder, and a schematic capture system.
Our results indicate a substantial reduction in implementation time and effort
compared with existing tools. Keywords: Software engineering, Tools and techniques, Software libraries, User
interfaces, Computer graphics, Graphics utilities, Application packages,
Computer applications, Computer-aided engineering, Computer-aided design (CAD),
Design, Human factors, Direct manipulation user interfaces, Graphical
constraints, Object-oriented graphical editors | |||
| Interactive Specification of Flexible User Interface Displays | | BIBAK | 269-288 | |
| Scott E. Hudson; Shamim P. Mohamed | |||
| One of the problems with conventional UIMSs is that very often there is no
graphical way to specify interfaces. This paper describes OPUS, the user
interface editor of the Penguims UIMS. This system allows the presentation
component of graphical user interfaces to be specified interactively in a
graphical notation without explicit programming. The Penguims UIMS supports an
underlying model of computation based loosely on spreadsheets. In particular,
it supports incremental computations based on a system of equations (one-way
constraints) over a set of named values (spreadsheet cells). These equations
are used to provide immediate feedback at all levels of the interface. They
are used to incrementally determine the position and dynamic appearance of the
individual interactor objects that make up the interface. They are also used
to connect the presentation directly to underlying application data thereby
supporting semantic feedback. The OPUS user interface editor employs a special
graphical notation for specifying the presentation component of a user
interface. This notation allows the power of the underlying computational
model to be expressed simply and quickly. The resulting presentations are very
flexible in nature. They can automatically respond to changes in the size and
position of display objects and can directly support derivation of their
appearance from application data objects. Keywords: Software engineering, Tools and techniques, User interfaces, Software
engineering, Programming environments, Interactive, Software engineering,
Miscellaneous, Rapid prototyping, Computer graphics, Methodology and
techniques, Human factors, Languages, Constraint systems, Direct manipulation,
End-user programming, Interface builders, User interface management systems | |||
| A New Model for Handling Input | | BIBAK | 289-320 | |
| Brad A. Myers | |||
| Although there has been important progress in models and packages for the
output of graphics to computer screens, there has been little change in the way
that input from the mouse, keyboard, and other input devices is handled. New
graphics standards are still using a fifteen-year-old model even though it is
widely accepted as inadequate, and most modern window managers simply return a
stream of low-level, device-dependent input events. This paper presents a new
model that handles input devices for highly interactive, direct manipulation,
graphical user interfaces, which could be used in future toolkits, window
managers, and graphics standards. This model encapsulates interactive
behaviors into a few "Interactor" object types. Application programs can then
create instances of these Interactor objects which hide the details of the
underlying window manager events. In addition, Interactors allow a clean
separation between the input handling, the graphics, and the application
programs. This model has been extensively used as part of the Garnet system
and has proven to be convenient, efficient, and easy to learn. Keywords: Software engineering, Tools and techniques, User interfaces, Computer
graphics, Methodology and techniques, Human factors, Direct manipulation, Input
devices, Interaction, Interaction techniques, Model-view controller,
Object-oriented design, User interface management systems | |||
| Telos: Representing Knowledge About Information Systems | | BIBAK | 325-362 | |
| John Mylopoulos; Alex Borgida; Matthias Jarke; Manolis Koubarakis | |||
| We describe Telos, a language intended to support the development of
information systems. The design principles for the language are based on the
premise that information system development is knowledge intensive and that the
primary responsibility of any language intended for the task is to be able to
formally represent the relevant knowledge. Accordingly, the proposed language
is founded on concepts from knowledge representation. Indeed, the language is
appropriate for representing knowledge about a variety of worlds related to an
information system, such as the subject world (application domain), the usage
world (user models, environments), the system world (software requirements,
design), and the development world (teams, methodologies).
We introduce the features of the language through examples, focusing on those provided for describing metaconcepts that can then be used to describe knowledge relevant to a particular information system. Telos' features include an object-centered framework which supports aggregation, generalization, and classification; a novel treatment of attributes; an explicit representation of time; and facilities for specifying integrity constraints and deductive rules. We review actual applications of the language through further examples, and we sketch a formalization of the language. Keywords: Software engineering, Requirements/specifications, Languages, Methodologies,
Software engineering, Design, Methodologies, Representation, Models and
principles, General, Artificial intelligence, Knowledge representation
formalisms and methods, Representation languages, Semantic networks, Predicate
logic, Management of computing and information systems, Software management,
Software development, Design, Languages, Belief time, Class, Deductive rules,
History time, Instance, Integrity constraints, Knowledge base, Metaclass,
Proposition, Temporal knowledge | |||
| Experiments with a Component Theory of Probabilistic Information Retrieval Based on Single Terms as Document Components | | BIBAK | 363-386 | |
| K. L. Kwok | |||
| A component theory of information retrieval using single content terms as
component for queries and documents was reviewed and experimented with. The
theory has the advantages of being able to (1) bootstrap itself, that is,
define initial term weights naturally based on the fact that items are
self-relevant; (2) make use of within-item term frequencies; (3) account for
query-focused and document-focused indexing and retrieval strategies
cooperatively; and (4) allow for component-specific feedback if such
information is available. Retrieval results with four collections support the
effectiveness of all the first three aspects, except for predictive retrieval.
At the initial indexing stage, the retrieval theory performed much more
consistently across collections than Croft's model and provided results
comparable to Salton's tf*idf approach. An inverse collection term frequency
(ICTF) formula was also tested that performed much better than the inverse
document frequency (IDF). With full feedback retrospective retrieval, the
component theory performed substantially better than Croft's, because of the
highly specific nature of document-focused feedback. Repetitive retrieval
results with partial relevance feedback mirrored those for the retrospective.
However, for the important case of predictive retrieval using residual ranking,
results were not unequivocal. Keywords: Information storage and retrieval, Content analysis and indexing, Indexing
methods, Information storage and retrieval, Information search and retrieval,
Retrieval models, Experimentation, Theory, Document-focused and query-focused
relevance feedback, Indexing and retrieval, Inverse collection term frequency
weighting, Inverse document frequency weighting, Probabilistic indexing,
Probabilistic retrieval, Ranking and weighting of composite objects | |||
| Queries and Query Processing in Object-Oriented Database Systems | | BIBAK | 387-430 | |
| Dave D. Straube; M. Tamer Ozsu | |||
| Object-oriented database management systems (OODBMS) combine the data
abstraction and computational models of object-oriented programming languages
with the query and performance capabilities of database management systems. A
concise, formal data model for OODBMS has not been universally accepted,
preventing detailed investigation of various system issues such as query
processing. We define a data model that captures the essence of
classification-based object-oriented systems and formalize concepts such as
object identity, inheritance, and methods. The main topic of the paper is the
presentation of a query processing methodology complete with an object calculus
and a closed object algebra. Query processing issues such as query safety and
object calculus to object algebra translation are discussed in detail. The
paper concludes with a discussion of equivalence-preserving transformation
rules for object algebra expressions. Keywords: Programming languages, Language constructs, Abstract data types, Data types
and structures, Modules and packages, Database management, Logical design, Data
models, Database management, Languages, Query languages, Database management,
Systems, Query processing, Algorithms, Design, Languages, Object algebra,
Object calculus, Object-oriented databases, Query transformation rules | |||