Close
Home
Collections
Login
USC Login
Register
0
Selected
Invert selection
Deselect all
Deselect all
Click here to refresh results
Click here to refresh results
USC
/
Digital Library
/
University of Southern California Dissertations and Theses
/
SNAP: A graphics-based schema management system
(USC Thesis Other)
SNAP: A graphics-based schema management system
PDF
Download
Share
Open document
Flip pages
Contact Us
Contact Us
Copy asset link
Request this asset
Transcript (if available)
Content
SNAP: A GRAPHICS-BASED SCHEM A
M ANAG EM ENT SYSTEM
by
Daniel J. Bryce
A Dissertation Presented to the
FACULTY O F THE GRADUATE SCHOO L
UNIVERSITY O F SOUTHERN CALIFORNIA
In Partial Fulfillment of the
Requirements for the Degree
DOCTO R O F PHILOSOPHY
V
(Computer Science)
May 1987
UMI Number: DP22762
All rights reserved
INFORMATION TO ALL USERS
The quality of this reproduction is dependent upon the quality of the copy submitted.
In the unlikely event that the author did not send a complete manuscript
and there are missing pages, these will be noted. Also, if material had to be removed,
a note will indicate the deletion.
Dissertation Publishing
UMI DP22762
Published by ProQuest LLC (2014). Copyright in the Dissertation held by the Author.
Microform Edition © ProQuest LLC.
All rights reserved. This work is protected against
unauthorized copying under Title 17, United States Code
ProQuest LLC.
789 East Eisenhower Parkway
P.O. Box 1346
Ann Arbor, Ml 4 8 1 0 6 -1 3 4 6
UNIVERSITY OF SOUTHERN CAUFORNIA
THE GRADUATE SCHOOL
UNIVERSITY PARK
LOS ANGELES, CAUFORNIA 90089
Y h D .
Cp S
B9/6
3 *■ ^ 7 8 I ' t f
This dissertation, written by
O a a .\c \ T ............
under the direction of h.X.% ....... Dissertation
Committee, and approved by all its members,
has been presented to and accepted by The
Graduate School, in partial fulfillment of re
quirements for the degree of
DO CTO R OF PH ILO SO PH Y
Dean of Graduate Studies
March 4 , 1987
DISSERTATION COMMITTEE
.........
TABLE OF CONTENTS
1 .
Introduction ....................................................................
... 1
1.1. General Considerations of SNAP .............................. ... 3
1.2. Overview of SNAP . . . ............................................... . . . 7
1.3. Lessons Learned and Perspectives ...................... .
2. User Interface Design C riteria .............................. . . . 23
2.1. General User Interface Considerations ................. . . . 27
2.2. Graphics Based Considerations for SNAP . . . . . . . 32
3. Graphic Based Schema Manipulation .......................... . . . 38
3.1. Schema Design .................................................................... . . . 40
3.2. Schema Browsing ................................................................ . . . 59
3.2.1. Hiding and Redisplaying Portions of the Schema . . . 64
3.2.2. Viewing Different Areas of the Schema ................. . . . 70
3.2.3. Locating Schema Components ...................................... . . . 74
3.2.4. Modifying the Schema Layout ....................................... . . . 76
3.2.5. Advanced Browsing Features ...................................... . . . 79
3.3. Query Specification ....................................................... . . . 81
3.4. Results Formatting .......................................................
4. Survey of Related Systems ........................................... , , . 101
5. Concluding Remarks ....................................................... . . . 108
REFERENCES.................................................................... ......................... . . . 120
A. Appendix ............................................................................ . . . 127
A .I. Basic Model ........................................................................ . . . 127
A.1.1. IFO Data Model ................................................................ . . . 128
A.1.2. Additional Concepts ....................................................... . . . 138
A.1.3. Query Component ................................................................ . . . 141
A.1.4 Data formatting ................................................................
A.2. Summary of Objects in the System .......................... . . . 149
A.2.1. Operations on the General System .......................... . . . 149
A.2.2. Operations on Windows ................................................... . . . 150
A.2.3. Operations on Nodes . . . ........................................... . . . 154
A.2.4 Operations on Edges .......................... .......................... . . . 157
GLOSSARY..................................................................................................................159
LIST OF FIGURES
1-1 Sample SNAP Screen Layout .................................. 9
1-2 Portion of Tourist Agency Schema .................. 10
1-3 Schema with a Sample Query .............................. • 11
1-4 Alternate Formats for Query Results . . . . •
18
3-la Primary Creation Menu........................................... • 44
3-lb Prompt for Nam e of a Type ..................................
44
3-lc Abstract Type Representing a set of People 45
3-ld Addition of Printable Type for the Names 45
3-le Select Link Options for an Abstract Person Node . . . • 46
3 - lf Link Person to Pname with Surrogate Arc . . • • • • • •
46
3-2a Person Fragment with Attributes for Nam e and Address • 49
3-2b Trip Fragment ............................................................ 49
3-3 Person-Guide-Tourist ISA Structure . . . . 54
3-4 Complete Tourist Agency Schema ...................... • • • • » • 55
3-5 Complete Schema with Range-restricting ISA Arcs
Removed ......................................................................................... 56
3-6a Primary Nodes of the Schema .............................. 66
3-6b First Level Attributes of Primary Trip Node 66
3-6c Information About Participants of a Trip .
■
67
3-6d Relationships Between Person and Trip . . . 67
3-7a Focus on Trip Fragment ....................................... 71
3-7b Panning the Portal Over the Display . . . . 72
3-7c Result of Pan Operation ....................................... • 72
3-7d Resizing Portal on the Entire Enterprise 73
3-8a Request to Reposition Schema Window . . . . 84
3-8b A Schema and Query Window .................................. 85
3-9a Basic Hotel Query Fragment .............................. 86
3-9b Request to Add a Restriction to Capacity of Hotel . . • 87
3-9c Inherited Fragment of City of Hotel . . . . • 89
3-9d Output Hotel Nam e and Capacity for Hotels in
with Capacity of at Least 250 ......................
Beijing
• 90
3-10 Tourist-City Pairs for Cities which can Accommodate
Tourists ..................................................................................... 92
3 -lla Configuration for Creating a Format . . . . 99
3— 11 b Answer with Three Different Formats . . . . • • • • • • 100
3-12 First Normal Form Representation and a More
Representation ...................................................
Natural
100
A-l Guide-Language-Proficiency ..............................
134
A-2 Class Structure for Windows ..............................
150
A-3 Class Structure for Notes .................................. 154
A-4 Class Structure for Edges ..................................
158
ABSTRACT
SNAP is an integrated system which provides a graphics-based
interface to support the varied database a c tiv itie s of schema
design, schema browsing, data inquiry, and query results
formatting. The SNAP components introduced to support these
a c tiv itie s provide a solid foundation upon which a complete
graphics-based database management system may be constructed.
SNAP marries the concepts of graphics-based interfaces, object-
oriented programming, and object-oriented data models to create a
simple, natural, and consistent interface. At a ll levels the system
is comprised of objects corresponding to natural entities in the
application domain. The user performs a c tiv itie s by identifying an
object of interest and sending i t a request to perform one of its
operations. For example, in the graphics-based interface SNAP
displays a graphics representation of objects and allows the user to
roll a mouse across a table to select an object of in terest. The
identified object responds by presenting the user with a pop-up m enu
lis tin g its operations and asks the user to select one of them. At
the database lev el, the user is encouraged to create, organize, and
manipulate information by identifying natural object classes
corresponding to categories of entities in the application domain.
The object-oriented programming approach creates a natural connec
i v
tion between the graphics-based interface and the object-oriented
database.
SNAP uses the novel representation of IFO schemas and includes
a variety of abstraction mechanisms which encourage users to design
and view these schemas in a modular fashion. Not only can these
schemas describe the basic structure of the underlying information
but they can be extended to directly show derived data such as
inverse functions and composed functions. This capability allows
users to view relationships between data objects in a variety of
manners. The graphics-based paradigm used for defining the
structure of information is extended to allow the user to specify
restrictions or queries in a sim ilar fashion. SNAP supports several
capabilities for simultaneous display of large amounts of
information about the underlying schema, queries being specified,
and answers to those queries. A prototype of the system which
demonstrates the basic features of the user interface has been
implemented.
1. INTRODUCTION
The primary objective of database management systems is to
provide users with fast, easy access to an information base.
General purpose database management systems (DBMSs) evolved from
basic f i l e manipulations to provide higher level constructs, thus
freeing the application specialist from concentrating on the low
level data storage and retrieval details. Since the introduction of
DBM Ss much progress has been made, especially in the area of
providing mechanisms for e ffic ie n t storage and fast access to the
information in the database. Unfortunately, much less progress has
been made in the area of general-purpose user interfaces. A large
portion of the early database management system application domain
consisted of the banking and accounting industries processing and
collating large amounts of data in a rather specialized manner.
Database experts and application experts worked together to create
specialized user interfaces which invoked predefined transactions or
generated specialized output reports. Gradually, DBMSs found th eir
way into many other applications and, in so doing, a need for
different and more general interfaces has arisen. Today, database
management systems have been integrated into a wide variety of
environments, but they s t i l l require substantial training and effort
on the part of the user in order to effectively exercise them.
1
Special-purpose interfaces are s t ill required for many classes of
database access a c tiv itie s .
Most of the advances in providing experts in an application
domain with convenient access mechanisms to database schemas have
come from the object-oriented semantic data models. An early
example of a semantic data model is the Entity-Relationship (ER)
model [Ch 76], which is widely used as a conceptual aid to organize
information. Several systems have been developed to help the user
more easily design, browse, and query E R schemas [C 80, CL 79, F 84,
W K 82], More dramatically, two distinctive systems [GGKZ 85, K M 84]
have been recently introduced which are based on the more expressive
Semantic Data Model [HMc 81]. This paper presents the SNAP
paradigm, which represents the next step in the evolution of schema
access support systems. Most notably, the SNAP paradigm provides a
coherent integrated environment which allows the user to design
schemas, browse schemas, and specify queries, a ll in an essentially
graphics-based fashion. Furthermore, SNAP introduces a number of
novel concepts which can be incorporated into existing or future
database schema access packages.
The purpose of this document is to describe the research
surrounding the SNAP paradigm. The focus of the research was to
propose and experiment with a general paradigm for schema
management. The research consisted of determining c rite ria for
effective user interface design, developing a prototype based on
2
these c r ite ria , and experimenting with the prototype. The three
subsections of this introduction discuss the considerations guiding
the design of SNAP, overview the system features, and present som e
lessons learned and perspectives. The intoduction is a synopsis of
the contents of the entire document. Many of the ideas introduced
here in a simplified form shall be presented in more detail in later
sections of this document.
1.1. General Consideration of SNAP
Before demonstrating the actual interworkings of the system we
discuss some general characteristics of SNAP. A fundamental goal of
SNAP is to provide convenient support for selected database
a c tiv itie s . This platform could then be used to create a more
complete environment encompassing a wider range of database
acti v itie s .
Two important considerations of SNAP is the visual
representation and the set of operators needed to manipulate that
representation. In particu lar, SNAP has the following seven general
characteristics.
1. Even though the schema (the visual representation of the
database structure) may be too large to be displayed in its
entirety at one time, the schema representation fa c ilita te s
3
simultaneous, coherent display of large portions of the
schema. Furthermore, the representation displays the structure
and relationships between the various entity sets of the
underlying database. In particular, the representation
exhibits simultaneous portrayal of a ll types of object and
functional relationships.
2. Natural clustering mechanisms allow the schema to be viewed in
a modular fashion. The modular components help the user view
the schema at several levels of abstraction, and allow the user
to view complex models as a collection of related smaller
logical components.
3. SNAP permits fle xib le rearrangement of the schema, and i t also
provides mechanisms to return to fam iliar visual representa
tions. By allowing the user to return to essentially static
visual representations, the user maintains a feeling of
continuity and s ta b ility .
4. Simple queries are expressed in a simple way. Complex queries
may be b u ilt up in a piecemeal fashion. These queries are
expressed as graphs in much the same manner as the schemas, and
. t
it is possible to simultaneously view large portions ( i f not
a ll) of these complex queries.
5. The interface permits fle xib le viewing of query results. For
example, the user may view some information as a collection of
fla t tables and other information in a more appropriate
hierarchical representation.
6. SNAP maintains a close coupling between the various system
components and presents this relationship to the user in a
coherent fashion. In particular, consistency is maintained
between the components for defining the schema, issuing
requests on that schema to retrieve objects from the database,
and viewing the results of inquiries.
7. The user interface is consistent. The operations and the style
of interaction is sim ilar across a ll components, thus allowing
the user to apply knowledge gained in one area to other areas.
The above seven characteristics of SNAP may also be viewed as a
set of design goals of SNAP. The manner in which these goals were
achieved was to incorporate IFO (the underlying database model) as
the visual representation, extend the IFO representation to allow
the user to express data requests in a query-by-example fashion,
display the results in a non-first normal form relation, and to
fashion user access after an object-oriented programming language
paradi gm.
5
W e now b rie fly overview how these seven characteristics relate
to the SNAP components. The IFO schema representation [AH 84,
A H 85, A H 87] supports the fir s t three characteristics mainly due to
the principles in IFO of "distinct representations for distinct
rules" and of using "fragments as the basic building blocks of a
schema". Characteristic four is created by extending the schema
representation and allowing the user to express what is wanted by
directly manipulating schema components without having to resort to
a second syntax, or to compute the answer. This is sim ilar to the
e a rlie r approaches taken in Q B E [Z 77] and CUPID [McS 75] for the
relational model. SNAP also allows the user to express queries in a
piecemeal fashion sim ilar to the approach of GUIDE [W K 82], The
fle x ib le arrangement and presentation of information referred to in
characteristic five is achieved by using a format notation most
closely related to [AB 84] and more remotely influenced by [HY 84,
JS 82, RKS 84], Finally, characteristics six and seven are achieved
by using an object-oriented programming language paradigm and by
supporting a graphical style of user interaction.
The above seven points refer to specific goals or
characteristics of SNAP. Section 2 discusses user interface design
c rite ria in a more general sense. In particular, this section lis ts
a number of specific design goals and introduces a more general
design philosophy which promotes the idea that the "User is King"
[BWZ 86].
6
1.2. Overview of SNAP
The preceding section overviewed some characteristics of
SNAP. The following discussion b rie fly introduces the SNAP
environment, the graphical object-oriented style of user
interaction, and the basic components of SNAP.
SNAP u tiliz e s a high-resolution bit-mapped display screen, a
keyboard, and a pointing device. The display screen is used to
present both graphical and textual information to the user. The
keyboard is used to enter textual information or to invoke special
functions such as "abort" or "help". The mouse pointing device
controls the movement of a cursor on the screen. The user positions
the cursor over an object on the screen and presses a mouse button
to instruct that object to carry out some operation. In response to
a selection, the object typically displays a pop-up menu with the
applicable options and allows the user to select an option or to
abort the request.
SNAP introduces three basic types of windows through which the
user performs the primary database a c tiv itie s of schema design,
query specification, and results viewing. Figure 1-1 displays a
sample screen layout which contains six windows: one schema window
(located in the upper left-hand corner), one query window (located
in the upper right-hand corner), three answer windows (across the
i
central band on the display), and one system command window
7
(stretching across the bottom of the display). The user may freely
create, size, and position windows anywhere on the screen by using
the sophisticated window management capabilities. As shown in this
figure, the windows may possibly overlap, in which case the user
specifies which windows lie on top of other windows.
The following discussion and the more detailed presentation in
Section 3 demonstrate the basic ideas of SNAP by showing how a user
can design, browse, and query a database. In particular, a tourist
agency is chosen as a sample application in which the agency wishes
to maintain and correlate information about trip s , c itie s , hotels,
tourist traps, tour guides, and clien ts. For example, Figure 1-1
displays portions of a SNAP schema and query, and alternate formats
for the answer to an inquiry on the tourist agency database. The
sample query matches a city with a person as long as a hotel exists
in that city which is rated at least as well as the comfort
requirements of the person. Three different answer formats for the
query are shown in the three answer windows.
The leftmost answer window lis ts the person-city pairs sorted
on the persorV name. The middle answer window nests the set of
c itie s under each person, and the rightmost answer window displays
the people grouped under the c itie s which can accommodate them.
8
Figure 1-1. Sample S N A P Screen Layout.
| w n -tn |
l/ie w In fo rm a tio n
1 pnane cnane i
M ar* ttbov*
Joe R lln a n M a drid
Joa R lln a n P a ris
C a ro ly n B rig h t Be1J1ng
C a ro lyn B rig h t M adrid
C a ro lyn B r ig h t P a ris
C a ro ly n B r ig h t Tokyo
C a ro ly n B r ig h t LR
Doug Datey M a drid
Lo ren Denno M adrid
R ich Dubln B e ijin g
R ich Dubln M a drid
R ich Dubln P a ris
R ich Dubln Tokyo
R ich Dubln LR
R ian Eng B e ijin g
R ia n Eng M adrid
M ar* btlew
mmm
•apM H y
KcuMnforrnation
View Information
pnanc
□none
Joe R11nan
B e ijin g
M o t aiav*
I B e ijin g |
I M adrid j
I Par1a |
C a ro lyn B rig h t
Doug Dacey
t B e ijin g
I M adrid
I P a ris
I Tokyo
I LR
I Madrid I
Lo ren Denno I M adrid I
M art H lo w
mm
s s iia n
M a r* atav*
Joe R 1lnan |
C a ro ly n B r ig h t |
I
M a drid
R ich Dubln
fila n Eng
Bon E p s te in
Rob E rh a rt
Don O lsen
Joe ftlln a n
C a ro ly n B r ig h t
Doug Dazey
Lo ren Denno
R ic h Dubln
R ia n Eng
Don E p s te in I
Afar* In law
Connand:
Connand:
L iv e Window 1
s jD
_ j J city J
"*1” c«P*city"
Tourist Ageney
Figure 1-2. Portion of Tourist Agency Schema.
Figures 1-2 and 1-3, which w ill be discussed shortly, display
portions of the schema and the complete query specification for this
example. B rie fly , the schema describes three entity sets, namely
hotels, c itie s , and persons; where persons has two subtypes.
in
- - - o| city
Figure 1-3. Schema with a Sample Query.
The visual representation of schemas in SNAP is based on a
subset of the IFO database model [AH 84, A H 85, A H 87], an object-
oriented model which provides features for representation of simple
and complex objects, functional relationships, and ISA
relationships. A (restricted) IFO schema is represented as a
directed graph with up to five different types of nodes used to
represent sets of abstract, printable, free, or complex objects,
where a complex object is formed by using grouping and cartesian
product operation on the three basic types. The three types of
edges available in an IFO schema are used to define the structural,
11
functional, and inclusion dependency relationships between the
information represented by the nodes. (The complete IFO model
actually has two types of ISA edges representing specialization and
generalization.)
The IFO schema representation forms the basis for providing the
graph-based interface. In particu lar, the IFO schemas have two
characteristics which help provide the foundation for building and
viewing schemas in a modular fashion. F irs t, IFO schemas use
fragments as the basic building blocks. Each fragment represents an
entity set along with its attributes. Large complex schemas may be
b u ilt up from the smaller simple fragments in such a way that the
user may separately focus on each fragment in order to break the
complex entity relationships into small manageable chunks. Second,
to help support the fragment breakdown IFO schemas use distinct
representations for distinct roles of the entity sets. For example,
consider the simple portion of the schema shown in Figure 1-2. One
component of this schema denotes that a hotel has printable
attributes for its name, capacity, and comfort rating. Also, a
hotel has a free attrib u te called city whose attributes are defined
on the primary city node. Each city in the database has attributes
representing the city name, the language spoken there, and the
climate. (The climate is represented as a tuple with two components
representing average temperature and r a in f a ll.) Note that IFO uses
two distinct representations for c itie s : one for the cities
12
associated with hotels and one defining the actual set of cities in
the database.
The structure shown on the left-hand side of the schema in
Figure 1-2 demonstrates an ISA la ttic e . This ISA la ttic e contains
three major components, connected by double arrow ISA edges,
representing a set of people and two special subsets of people
corresponding to tr ip guides and tourists. Associated with each
person is that person's name. Associated with a tourist is the
comfort-quotient which specifies the minimum accommodations rating
required. Associated with each guide is the set of languages that
guide speaks and for each language the proficiency with which the
guide speaks that language. Also, note that since a guide or a
to urist is a person, a guide or tourist has the inherited attribute
representing the person's name.
The SNAP schema creation and browsing fa c ilit ie s provide many
tools to support the user in these a c tiv itie s . For example, to
create the schema components shown in Figure 1-2, the user simply
points at the schema window and asks i t to create a schema node, and
then points at the schema node and asks i t to define the various
edges. In more d e ta il, to create a schema node the user positions
the cursor to the location at which the new node shall be placed and
presses the rightmost mouse button. The schema window responds by
lis tin g the types of nodes ( i . e . , abstract, free , printable, cross,
and star) in a pop-up selection menu and asks the user to select one
13
of them. After the user selects the type of node, the schema window
prompts the user for the label of the node and then adds the node to
the display. To define an edge, the user points at one of the
candidate endpoint nodes and presses the rightmost mouse button.
The node responds by presenting a pop-up selection menu with the
available options, one of which is lin k . Assuming the user selected
the link option the node redisplays it s e lf in reverse video and asks
the user to identify the connecting node. I f more than one type of
edge is valid between the two selected nodes, a pop-up selection
menu appears which lis ts applicable edge types (possibly including
fragment, surrogate, object, and ISA). F in ally, the edge displays
its e lf between the two schema nodes.
The SNAP user may invoke several options to redefine the
current view of the schema. Since the entire schema may not always
f i t on the screen, SNAP presents the user with a portal (a
rectangular aperture through which the user views a portion of
graph). The user may freely reposition or resize the portal in
order to examine various areas of the schema in more or less
d e ta il. SNAP also provides a variety of tools for modifying the
schema layout. For example, schema nodes respond to a family of
hide/redisplay requests which allow the user to hide or redisplay a
node, a node and a ll its dependents, or simply a node's
dependents. Likewise, the user may freely reposition nodes,
dependents, fragments, ISA la ttic e s , or arbitrary groups of nodes in
14
order to achieve the desired layout. At the global level, SNAP
provides several operations to remove or redisplay schema components
based on display attributes such as node or edge types. SNAP also
provides mechanisms to help the user locate specific areas of the
schema by finding specific nodes or by following ISA
relationships. A more complete set of schema design and browsing
capabilities are presented in Section 3.
In addition to the novel representation and manipulation of
schemas, SNAP advances the state of graph-based query formulation by
allowing the user to specify or formulate queries by directly
manipulating (a copy of) the schema. W hen specifying queries in
SNAP, the user interacts with the query and schema windows to derive
from the schema a graph which represents what information the user
wishes to see. Instead of specifying how to retrieve information
from the database or dropping into a text-based predicate calculus
language such as [MacG 85, Sh 81, TsZa 84, Z 831 to express
requests, the SNAP user creates a diagram which presents the
structure and restrictions of the desired information set. In some
sense, this approach is analogous to Q B E [Z 77] on a graph where
fragments in SNAP correspond to relations in QBE.
The method for query specification follows the style of schema
design and browsing. F irs t, the user instructs SNAP to copy a
desired fragment from the schema to the query window. For example,
the f ir s t step in generating the query shown in Figure 1-3 was to
15
copy the hotel fragment. Next, the user may add the inherited
fragments associated with free or primary nodes. As shown in
Figure 1-3 for the free hotel city node, inherited fragment edges
are distinguished from regular fragment edges by using dashed lines
to represent inherited fragment edges. Third, the user m ay add
local or cross fragment restrictions. For example, the user may
re s tric t the hotel set to be large hotels by adding a local
restriction directly to the hotel capacity node that i t he at least
250. The query shown in Figure 1-3 shows the second type of
restriction with a comparator edge. This comparator edge represents
the restriction that the hotel comfort-rating be greater than the
comfort quotient demanded by a to u ris t. The final step of query
specification is to state what information shall be available for
formatting and printing in an answer window. The candidate active
nodes are shown with a shaded in te rio r.
The fin al SNAP component incorporates a particular class of
non-first normal form relations, called V-relations [AB 84], to
display information in a variety of representations. The SNAP user
can interact with the answer formatting system to quickly and easily
define a template which defines groupings of attributes. These
templates are used to format the information in a fle x ib le compact
form. For example, Figure 1-4 demonstrates how these formats can be
used to present the set of phone numbers, the set of languages
spoken, and the set of tours a guide is responsible fo r. Also, note
16
that the printable attrib ute guide associated with the primary free
guide node is in fact the pname attribute which was inherited from
the primary abstract person node. SNAP maintains the close
coupling between the query and schema components but allows the
user to relabel nodes in order to generate unique or more meaningful
headers. The two answer windows shown in Figure 1-4 show the
information as the trad itio n al f ir s t normal form relation and as the
more natural non-first-normal-form relation. In p articu lar, notice
that the complete information set for Gail does not even f i t in the
larger answer window on the le f t , whereas the small information
window on the right clearly shows the information for both Gail and
Jim.
SNAP features a consistent user interface in which a tight
binding is maintained across the answer, query, and schema
components. For example, the user may point at the guide
attribute shown in one of the answer windows of Figure 1-4 and
inquire where i t came from. The guide a ttrib u te w ill respond by
asking the printable guide node in the query window to highlight
it s e lf . Likewise, the user may inquire where the printable query
guide node came from to which i t responds by requesting the schema
pname attribute of person to highlight it s e lf . I f a node which is
attempting to highlight its e lf is not currently visible in the query
or schema portal then that node instructs the portal to reposition
17
tQ
c
3
rt>
I
■p*
0 >
-5
3
r t
a >
~n
o
“ * 5
3
o >
rt’
< />
o
3
o
c
f l>
Q
7 0
(D
l/>
C
rt-
< />
a
view Information
I guide 1anguage to u r nane phone nunber I
Top
G ail E n g lis h O rie n t Express 612-125?
G ail E n g lis h O rie n t Express 376-9844
G ail E n g lis h A sian Adventure 612-125?
G ail E n g lis h A sian Adventure 376-9844
Gai 1 E n g lis h European Getaway 612-125?
G ail E n g lis h European Getaway 376-9844
G ail E n g lis h G reat H a ll Tour 612-1257
G ail E n g lis h G reat H a ll Tour 376-9844
G ail Chinese O rie n t Express 612-125?
G a il Chinese O rie n t Express 376-9844
G ail Chinese A slan Adventure 612-125?
G ail Chinese Asian Adventure 376-9844
G ail Chinese European Getaway 612-125?
G ail Chinese European Getaway 376-9844
G ail Chinese G reat H a ll Tour 612-1257
G ail Chinese G reat H a ll Tour 376-9844
G all Japanese O rie n t Express 612-125?
G ail Japanese O rie n t Express 376-9844
G ail Japanese A sian Rdventure 612-125?
G ail Japanese Asian Adventure 376-9844
G ail Japanese European Getaway 612-1257
G ail Japanese European Getaway 376-9844
G ail Japanese G reat H a ll Tour 612-1257
G all Japanese Great H a ll Tour 376-9844
G ail French O rie n t Express 612-1237
G ail French O rie n t Express 376-9844
G ail French A sian Adventure 612-125?
G ail French A sian Adventure 376-9844
G ail French European Getaway
Afore to low
612-1257
0
W W W
SS5W
“ ““n
1 guide 1 language II to u r nane II phone nunber II
G ail 1 E n g lish
j Chinese
j Japanese
1 French
Top
| O rie n t Express |
j A slan A dventure j
j European Getaway |
I G reat H a ll Tour j
612-1257 |
376-9844 |
J in 1 E n g lish
I French
I Gernan
1 Spanish
j I t a lia n
1 Russian
1 Budget Europe I
j French Wine Tour j
j floor 1 sh Ruins I
j B r it is h Is le s j
j Russian R o u le tte j
Bottom
612-1258 |
372-4418 |
542-8355 I
00
its e lf so that the requested node is v is ib le . Another example of
how SNAP maintains a consistent user interface involves shared
operations in the various components. All of the schema browsing
commands including repositioning, hiding, redisplaying, and locating
schema objects (nodes, nodes and dependents, fragments, la ttic e s , or
arbitrary groups of nodes), operate in the same manner in the
query subsystem as they do in the schema component. Therefore, the
user may rely on past experiences and previously mastered operations
to venture forward in other areas.
1.3. Lessons Learned and Perspectives
The primary purpose of the prototype was to demonstrate the
basic concepts of the SNAP paradigm. The focus was on the graphics-
based interface to the various components and not on the
implementation of the underlying tools. For instance, the prototype
was not connected to a database system and therefore the user could
not actually create database instances or view the results of a
query. However, throughout the various prototype components,
structural in teg rity was maintained. For instance, the user of the
schema creation options was aided and constrained in such a way that
only valid IFO graphs could be created. (The final step of
verifying that the ISA constraints were satisfied and therefore the
IFO graph was a valid IFO schema was not actually implemented.)
19
Also, the query graph generation system allowed the user to create
only valid query graphs given a valid schema, but i t did not enforce
the va lid ity of certain types of comparisons. For example, the user
could create a comparator edge (with an equality operator) between a
scalar and a set. Relative to the data formatting system, the user
could build any valid format in an answer window associated with a
query window, but since no data was available the formatting was not
actually performed.
The SNAP prototype demonstrated many ideas in general and we
now discuss four lessons learned from interacting with the
prototype. F irs t, the SNAP graph layout capabilities represent a
middle ground between the approaches of dynamic graph layout found
in systems such as LID [F 84] and SKI [KM 84], and the fixed graph
layout found in a system such as GUIDE [W K 82]. The SNAP user m ay
freely reposition nodes, fragments, lattices or general groups to
easily define any desired layout. The incorporation of a simple
automatic tree layout capability demonstrated the power and
potential benefits of a good localized graph formatting to o l.
Second, in order to effective ly locate the desired components
of larger schemas and to explore various aspects of the schema some
meta-browsing commands are necessary. Meta-browsing commands range
from basic options such as "finding a node" or "finding a ll subtypes
(supertypes)" to sophisticated graph partitioning tools such as a
hierarchical subject directory concept of GUIDE. Also, the use of
20
display f il t e r s , such as those described in PHIGS [BHM 85], provides
a simple, powerful mechanism to control the display.
Third, because of fast response time, graphical operations are
effective; and they are usually very d irec t. Originally we thought
i t m ay be necessary to introduce a command language to allow the
user to quickly generate fragments. However, because of the
excellent response time of current bit-mapped workstations with
sophisticated windowing packages i t is direct and fast to create
fragments graphically. Along the same lin e , the simple mechanism
for creating data formats works very w ell. The simple tool we
implemented is easy to explain, easy to use, and very fa st. More
sophisticated tools which try to anticipate user desires may well
introduce unnecessary complexity.
Fourth, the object-oriented approach was convenient. Using an
object-oriented paradigm from the user interface to the lowest level
implementation helped produce a clean, easy-to-understand, and well
organized system.
This paper presents various aspects of the SNAP paradigm.
Section 2 synthesizes a wide body of lite ra tu re and experience to
present a number of c rite ria for user interface design. Section 3
forms a comprehensive discussion of the features of SNAP. Section 4
b rie fly discusses related systems described in the lite ra tu re ,
paying particular attention on how they accomplish sim ilar
objectives as SNAP. Comments on SNAP, the status of the implemented
21
prototype, and future directions are given in Section 5. The
Appendix consists of two major sections. The f ir s t section of the
appendix presents the formal definitions of the SNAP components
including the definitions of IFO schemas, query graphs, and data
formatting templates. The second section of the appendix lis ts the
SNAP user options. The document concludes with a glossary of terms
and a bibliography of related documents.
2. USER INTERFACE DESIGN CRITERIA
The process of designing a good user interface can be likened
to the w riting of a good novel. One cannot simply follow a set of
rules to achieve success. The creator must have a f l a i r for style,
drawing from experience and personal judgment to fashion a pleasing
product. In this sense, designing a good user interface is more of
an art form than a science. Many excellent tools exist for
computer-user interactions, but the real challenge is combining or
incorporating these methods to create an appealing environment.
Two fundamental considerations of user interface design are:
who are the targeted users, and how w ill they use i t . One user
interface may be perfect for one group of people but to ta lly
inappropriate for another. For example, a novice or infrequent user
may enjoy, and in fact somewhat rely on, a menu driven system in
which the computer in itia te s all requests, leading the user, step by
step, through every specification phase. O n the other hand, an
expert or frequent user may find this methodology cumbersome. A
command-driven system which allows the user to in itia te requests and
to state desires succinctly may be much more appropriate for the
advanced user.
The user interface designer must strive to strike a balance
between sim plicity and complexity. Imposing a simple re s tric tiv e
style may make a system easy to design, build, document, and perhaps
23
even easy to use i f used exactly as intended. Special purpose
interfaces, such as a computerized checkout at a supermarket,
provide ease in use and satisfy a ll th e ir objectives. A workstation
with more options or capabilities may only introduce unneeded
complexity and increase the probability of error. O n the other
hand, an overly sim plistic system which is easy to learn may be too
cumbersome. Imagine trying to use a calculator which has only
operations for addition, subtraction, logarithms, and
exponentiation. Obviously one could s t i l l perform m ultiplication
and division, but directly incorporating these frequently-used
operations greatly increases ease of use. The designer must arrive
at some compromise between the minimal or simplest approach and the
overly powerful or complex approach.
Many computer interfaces are designed in such a way that the
user must be trained and must adapt to a program. In contrast, the
conceptual approach taken by the User Derived Interface [G W W J 84]
emphasizes understanding the user's behavior. Following this
approach the user's input not only drives the design, but the user's
actions actually reshape the interface during usage. The basis of
the experiment was to have subject users type in requests (which
they thought would be processed by a computer) to try to accomplish
some objective. Actually a ll requests were not handled by a
computer but the human researchers examined the user input and
responded appropriately. In doing so the researchers trie d to make
24
the system look lik e i t was conforming to the user instead of
forcing the user to conform to the system. A to ta lly automated
process which molds the user interface around the user's
interactions is currently beyond the scope of any expert system.
Such a system may even produce a flawed interface because of
inherent user weaknesses. Many times the user requires some
guidance, or a more rigid framework in which the system imposes some
\
restriction s. For example, forcing the user to specify requests
mathematically may help the user arrange ideas and formulate the
proper problem statement.
There is no single best interface style for a ll users and
applications. There is not even a single set of rules one m ay
follow to ensure that the resulting interface w ill be a good user
interface. Many sources must be tapped, many factors considered,
and many goals examined when designing a broad-based, general user
interface. Even then, many groups w ill disagree on the best way to
do the job. This does not imply that judging user interfaces is
completely subjective. There are some general guidelines one may
consider when designing or evaluating a user interface.
Many authors have discussed various aspects of good
computer/user interface design [D 84, FVD 82, F W C 84, G W W J 84,
M a 84, S 80, W H 80]. In one presentation [RWZ 8fi] the authors
begin by trying to identify what factors are involved in the
building of a "world-beater engineering graphics system". The
25
resulting lis t contains 44 distinct concerns the designers must try
to simultaneously satisfy. At fir s t glance the task seems grim
since no one could remember a ll these points, some points seem to be
diam etrically opposed to others, and certainly there exist
additional considerations not included in the big l is t of 44. After
organizing these 44 points into 10 categories the task seems to be a
b it more manageable, though certainly not crystal clear. The
authors then suggest that we step back and instead of looking at
specific points try to grasp the general philosophy which envelops
the 10 categories of 44 points. The four general philosophical
principles that emerge are: maintain an open architecture,
encourage a bias for action at a ll levels, remember that simple is
powerful, and always maintain uncompromising qu ality. Now, instead
of remembering specific points, the software designers need only
remember the basic 4 philosophic guidelines and apply them to
individual circumstances. However, the authors do not stop here.
They go on to conclude that the only principle the designers must
unwaveringly follow is to remember that "the User is King".
Everything must be done in such a way that the user's job is as
simple as possible. Unfortunately, this seemingly obvious
fundamental philosophical point is far too often forgotten in many
system designs and evolutions.
Keeping in mind the general goal of catering to the user, the
next two sections present some specific c rite ria used in the design
26
of SNAP. This exposition is a synthesis of lite ra tu re in the area
[BWZ 86, D 84, FVD 84, F W C 84, G W W J 84, M a 84, S 80, W H 80] and of
original c rite ria especially applicable to graphics-based
interfaces. The f ir s t section discusses some general user interface
considerations; the second section presents specific c rite ria used
in the development of the SNAP graphics-based methodology.
2.1. General User Interface Considerations
It is very d iffic u lt to judge i f a user interface is good
without actually exploring i t under various circumstances. Many
ideas which look good on paper just don't work out when put to
actual use. Perhaps prototyping, developing a simple scaled down
version which demonstrates the basic features of a component of the
system, is the most effective method to prove which ideas are really
solvent, and to help determine what modifications would improve the
overall system.
Prototyping represents one way in which system designers m ay
have a bias for action. Instead of over in te lle c tu a lizin g and
debating every point, the designers can simply try out various
alternatives. But, even before development of a prototype, the
designer has some in tu ition about what the user interface should
look lik e . Many of these ideas come from experience; looking at
other systems and imagining how those ideas w ill work in the new
27
application. The designer must weigh several factors and make
tradeoffs in an attempt to find a well-balanced system. The
following lis t includes several general considerations which are
closely related and yet are subtly disparate in different
ci rcumstances.
1. Natural - The user interface should re fle c t the user's, not
the system's, point of view. Large tasks should be logically
subdivided into smaller tasks which the user performs in a
natural sequence. Decisions on how the system performs tasks
should not be based on ease in programming, but rather the
designer must always place the user's convenience as the
highest concern. Optimally, the system should disappear from
the user consciousness, as i t forms a natural medium between
the two parties.
2. Consistency - The system should be consistent at a ll levels.
Knowledge acquired in one part of the system should apply to
other parts of the system. Operations which are com m on to
many areas should be accessible in the same manner and should
perform the same functions throughout the entire system. All
syntactic and semantic constructs should have the same meaning
everywhere. Also, the style in which the user interacts with
28
the system should be consistent. For example, system status,
warning, and error messages should be displayed in the same
logical location. This does not mean that these prompts or
cues should be displayed in the same physical location, but
rather that the user should always know where to look for
assistance. Consistency of displays and command usage w ill
help the user gain an in tu itiv e knowledge of the function of
new displays and options.
3. C larity / Coherence / Conciseness - System components should
be cleanly separated and yet they should be coherently
integrated. The entire complexity of the system should be
encapsulated into logical subcomponents. A well designed
system w ill modularize the system at many levels, a ll the way
from the user interface to the lowest, level implementation.
Also, inappropriate or non-applicable options should be
separated from active options. For example, i f some option is
not applicable i t should not appear on pop-up menus.
S im ilarly, active and inactive global commands should be
distinguished.
4. Simple Yet Extensible - The system should be easy to use. The
number of concepts should be small, and should be used to
build up other operations. The starting set of operations
29
should not necessarily be the minimal set, but frequently used
operations should be readily accessible. Som e method of
combining operations to create new operations should be
provided where applicable. For example, many operating
systems allow users to create th e ir own command file s , and
many editors are extensible through edit macros.
5. System Feedback - The system must provide cues to help the
users recall where they are, what they are doing, and where
they are going. An appropriate prompt or cue must be
displayed to acknowledge that a user's request has been
accepted and is being processed. Multistage operations must
clearly show the current stage and must provide some mechanism
for aborting the sequence. Operations which require a long
compute time should interm ittently notify the user of the
progress or estimated time until completion. A graphical cue
such as a gas gauge proceeding from fu ll to empty provides
useful feedback to the user in two ways. The position of the
gauge indicates how much of the operation has been completed,
while the rate at which the gauge is moving helps the user
estimate how much time w ill be required to complete the
operation.
30
6. Help - Help information should be available at various
levels. Depending on the type of user (novice, intermediate,
or experienced) differen t levels of help may be offered. More
importantly, help should be context sensitive. The system
should consider what the user is doing in order to predict
what type of assistance the user may require.
7. Abort / Escape Function - The user should be able to back out
of any situation. Before completing the specification of a
multistage operation, the user should be able to easily abort
the request. Particularly dangerous operations with far
reaching consequences should require double confirmation.
8. Scaffolding - The system should allow the user to build up
from previous states. A user should be able to checkpoint the
system at any time, and to resume from that point at some
la te r time. This is p a rticu larly useful when attempting a
global modification in which the user is unsure of the
consequences. I t is reassuring to know that i f the results
are undesirable, then the user can easily fa ll back to the
previous checkpointed state.
9. Fam iliarity - The user should always be allowed to return to a
fam iliar configuration. No matter how well a system is
31
designed, users w ill inevitably become lo s t, suddenly realize
they are in the wrong part of the system, or simply change
th e ir minds about the task at hand. In any case, the system
should allow the user an easy mechanism to return to a
fam iliar state.
10. Responsive - A system must be responsive lest the user become
bored. Dramatic increases in productivity can be achieved i f
the system is able to respond very quickly to most
operations. For example, in a study by IBM [DTI about the
economic value of rapid response time, system response times
of less than one second produce exponential growth in the
number of user transactions per hour.
2.2. Graphics-Based Considerations for SNAP
[D 84] pointed out that database languages are special-purpose
programming languages and thus should follow c rite ria for general
computer languages. S im ilarly, graphics based interfaces to
database management systems are special-purpose user interfaces and
must follow principles of good user interface design. However,
there are additional factors which must be taken into account when
evaluating graphics-based interfaces.
32
Probably the key to a successful graphics-based database
interface is finding an effective visual representation and
providing the appropriate operations for manipulating i t . Many
factors determine whether a representation is appropriate or not.
The basic goal is to easily convey information to the user, and to
e ffec tive ly s o lic it browsing and query commands from the user. The
remainder of this section discusses some issues for good graphics
database interfaces in the context of SNAP, especially for schema
design, schema browsing and query specification.
1. High Information Content - The system should display a lot of
information in a clear and concise manner. The visual
representation, the tools for partitioning the information,
reformatting aids, and the manner in which relationships
between information are shown a ll play an important role in
achieving a dense information map which is s t i l l easy to
comprehend.
2. Perception aids - The perception of information can be greatly
enhanced by differen t types of encoding such as color, line
s tyle, and shape. Encodings can highlight
s im ila ritie s and differences between objects, or can aid in
the id en tificatio n of object roles. However, too many
encodings detract from the display and make the diagram
33
confusing. [FW C 84] lis ts the maximum number of codes for
nearly erro r-free recognition for various coding methods as
follows: 6 colors, 10 geometric shapes, 5 line types, 2 line
widths, and 2 in ten sities.
3. Object-oriented Approach - The object-oriented methodology
provides an excellent framework to organize the internal
representation and to present i t to the user. For example, in
this framework each object in the display (be i t a window,
menu, node, or an edge) knows how to respond to a collection
of messages representing requests to carry out one of its
operations. The user may d ire c tly manipulate the
representation by pointing at the desired object and by
identifying an operation that the object should perform.
4. Correlation - Convenient mechanisms must be available to help
the user understand the relationships between the various
entity sets. The more closely two entity sets are related, the
easier the relationship must be to uncover. The relationships
between two objects (sets) may be shown by using similar
graphical representations or by including some connecting Tine
type.
34
5. Flexible Visual Rearrangement - The user must be able to
freely exclude information from the display and to reposition
objects in order to take advantage of spatial perceptions. In
this way the user may focus on particular areas of interest.
The system must not only provide the minimum operations to
allow the user to scroll over the objects, zoom in on objects,
and reposition objects, but must supply a rich family of
operations which make browsing easy and natural. Automatic
screen layout tools provide powerful assistance to the user.
6. Viewing at Several Levels / Support for Meta Browsing - The
user should be able to partitio n the diagram based on a
variety to contexts. Object sets should be grouped by
fu nction ality, and the user should be able to browse through
the data structure by examining the various levels in this
breakdown. For example, the user may request to display or
erase objects from the diagram based on object type. Or the
user may wish to include or exclude objects on the basis of
th e ir relationship to a focal object.
7. Return to Familiar Visual Representation - Information and
relationships should always be displayed in the same manner
unless the user e x p lic itly asks for some change. Once the
user is fam iliar with a component in a large diagram, the user
35
can then quickly locate and identify the component again. I f
the spatial relationships between objects is altered the
observer must exert some e ffo rt to comprehend the new
arrangement.
8. Query Feedback - User must be able to build up queries in a
piecemeal fashion. In this manner, the user may examine
subqueries in order to verify that the query component is
expressed correctly. The results from these smaller queries
can also be used to explain or help understand the result of a
more complex query which can be viewed as a collection of
simpler queries.
9. E xtensibility through Derived Data - The user must be able to
include various types of derived information. Many times a
particular subset of an en tity set may be used in a number of
queries. Therefore, the user should be able to identify the
object set and treat i t as any regular en tity set. S im ilarly,
the user should be able to add computed attributes and
composed functions. SKI [KM 84] is an example of a system
which works almost en tirely by ite ra tiv e ly incorporating
derived information into the schema.
36
10. Fun to Use - F in ally , the interface must be powerful, natural,
entertaining, easy to use, and responsive. I f the user
interface is well done, then i t w ill also be pleasurable to
use and w ill enhance the creative process. The user interface
should never stand in the way of progress, but should always
foster and encourage exploration.
This section discussed several factors to consider in the
design of user interfaces and specifically of graphical interfaces
to database management systems. These points w ill help the
designers raise questions about proposed interfaces, but they w ill
not replace the creative process involved in the in it ia l design.
Developments in user interface tools have lagged behind the rapid
advancements in computer hardware. Now, with the a v a ila b ility of
more powerful and advanced equipment, more attention is being
focused on creating effective user/computer interfaces.
37
_____
3* GRAPHICS-BASED schema management
Database management systems (DBMS) emerged as a simpler and
more convenient interface to f i l e systems. An advantage of the D B M S
is that i t shelters the user from many of the details of how to
store and retrieve information in these f i l e systems. Typically, a
D B M S encapsulates many lower level operations into a few convenient
higher level constructs. The goal is to create an environment which
allows the user to express requests in a more natural fashion. The
user is allowed to interact at a higher le v e l, and thus may ignore
many of the detailed instructions which the system must carry out.
The information management a c tiv itie s can be roughly divided
into five phases: 1) definition of the structure and in terre latio n
ships between data (schema creation), 2) exploration (browsing) of
the structure, 3) entering or updating information, 4) issuing
queries or examining the information, and 5) viewing the results of
queries (report generation). These fiv e phases do not represent
to ta lly d isjoin t components, but rather they should be coherently
integrated in a complete information management environment.
A well designed user interface w ill present the capabilities of
the system to the user in a comprehensible and easily accessible
manner. Just as early DBM Ss provided simpler access to the basic
f i l e system, modern interfaces attempt to provide simpler access to
the DBM S a c tiv itie s . A concerted e ffo rt is being made on many
38
fronts to generate more natural computer/user communication
techniques. Most notably, the enhancement in computer hardware and
graphics devices has opened the door to a flood of graphics-based
interfaces. These interfaces present information to the user
graphically, and allow the user to express requests by manipulating
the display in an essentially non-text-based mode.
The body of this section describes how SNAP exercises graphics
to provide support for four of the primary DBM S a c tiv itie s . The
general tone of the discussion is to give examples of the kinds of
capabilities a user may wish to access, and then to show how the
user may express these requests in SNAP. The discussion is fa irly
high level and only attempts to give the reader a general
introduction to the various underlying tools used in SNAP. Formal
definitions of (relevant parts of) the IFO data model, query graphs,
and format templates are given in the f ir s t appendix section. An
object decomposition and general capabilities l i s t of the SNAP
implementation objects is given in the second appendix section. The
reader may wish to refer to these sections to examine the details of
the SNAP system.
Recall that the general SNAP user interface includes a high
resolution display screen, a keyboard, and a pointing device called
a mouse. The display screen is used to present graphical and
textual information to the user. The pointing device is used to
id entify objects oh the screen and to request operations on these
39
objects. The system prompts the user for additional information by
presenting a pop-up box for text entry or for option selection.
This section now demonstrates how SNAP uses these tools to create an
effective graphics-based environment fo r schema design, schema
browsing, query specification, and results examination.
3.1. Schema Design
Two of the f ir s t decisions a user must make is what information
shall reside in the database, and how shall the information be
structured. A database schema serves as the tool for expressing the
structure of information in typical database systems. For highly
structured database models i t is assumed that the structure of the
information is small relative to the amount of information
maintained. Other information management schemes, such as semantic
networks, arise for loosely structured data management in which
there exist re la tiv e ly few objects as compared to the many types of
relationships between them. SNAP was designed to provide support to
a highly structured database model.
A primary objective of the SNAP schema manager is to maximize
sim plicity and power simultaneously. Although these two goals may
seem to be diam etrically opposed, they can both be achieved by using
an effective visual representation and providing appropriate
operations to manipulate that representation. As w ill be demon
4D
strated below, the SNAP schema representation incorporates various
modularity and abstraction techniques.
The following paragraphs discuss several aspects of schema
design, and how graphics is employed in SNAP to aid the process.
During the schema design phase, all schema browsing capabilities
(discussed in the next section) are also available to aid the user
in locating or rearranging schema components during the schema
defin ition phase.
The f ir s t task of the SNAP user involves id en tifica tio n of the
primary object sets, d efin ition of the attributes of objects
residing in those sets, and determination of the structure of the
objects and a ttrib u te s . For example, consider the following scenario
in which a database user wishes to maintain information for a
to urist agency. The user f ir s t establishes that two fundamental
object sets are people and trip s . The attributes for people include
the person's name and address, where the name shall be represented
as a printable character string and the address shall be decomposed
into street name, c ity , state, and zip code. Each tr ip shall have a
tr ip id , a group of participants, a guide, and an itin e ra ry . The
itin erary lis ts a number of stops, where each stop is defined by a
c ity , arrival date, and departure date. Also associated with each
stop w ill be a hotel the participants w ill stay at, and a set of
places (to u rist traps) they may wish to v is it.
41
SNAP, using the IFO data model, provides natural constructs and
a convenient interface to build the in itia l schema components. In
order to build the fragments which represent the structure of the
information described above, the user proceeds as follows. The
f ir s t step is to create a schema node by a simple four-step process.
1. Use the mouse to position the cursor to the location on the
screen at which the schema node is to be created and press the
rightmost mouse button.
2. The system responds by presenting a menu of available object
types (see Figure 3 - la ). By moving the mouse up or down to
change the selection and by pressing a mouse button, the user
may choose the type of schema node to create. The user may
abort the request by either pressing the abort function key or
by moving the cursor o ff the pop-up menu. In this example the
user created an abstract node to represent people.
3. The system now prompts the user for the name, or token, to be
associated with the node (see Figure 3 -lb ). In this example
the user typed in "person". I f the user changes one's mind,
the sequence can be terminated with the abort function key.
42
4. Having acquired a ll the necessary information about the schema
node, the system displays the abstract type (depicted as a
diamond) as shown in Figure 3 -lc .
Using the same type of interaction, the user may create a
printable attrib u te (depicted as a rectangle with label pname) for
the person's name. The two schema nodes are shown in Figure 3 -ld .
Now the user wishes to express that the pname is an a ttrib u te
of person. To accomplish this the user follows a simple four-step
process for defining an association between schema nodes.
1. Identify one node of in terest. The user moves the cursor over
either the person or pname node and presses the rightmost mouse
button. In this example the person node was selected.
2. The system responds by presenting a menu of options for that
node (see Figure 3 -le ). The user selected the link option.
3. To provide feedback to the user and to help the user recall
which node was selected, the system displays the node in
reverse video. The user then chooses the node to which the
reverse video node is to be connected. I f the user wishes to
abort the sequence by pressing the abort abort function key.
In this example the user selected the node labeled pname.
43
T o u r iit A gency S ch em a
A b s tra c t) > <
c ro s s
d e r t ved
p rim a ry d e riv e d
p r in t a b le
s ta r
a d ju s t s c re e n
s t r e t c h p ic t u r e
r e fr e s h s cre e n
T o u ris t Rqencv Schema
Figure 3 -la . Primary Creation Menu.
t y p e I n « l a b e l f a r , t h l e a b s t r a c t ofa l . e t r a n l e n d Ml t h r e t u r n )
persona
K
T o u ris t FgencyScSVre
Figure 3 -lb . Prompt for Nam e of a Type.
44
- '™1 T Y ourlst ft9«r*cy 6ch««« ^ ’’....... ..................................
Figure 3 -lc . Abstract Type Representing a Set of People
Figure 3 -ld . Addition of Printable Type for a Person's Name.
45
a d i t la b # 1
d a l a t #
T o u r is t Hg«ncy Schema"
Figure 3 -le . Select Link Option for an Abstract Person Node.
( f u n c t io n a re I I
S u rr o g a te a r a l___ |
_ _
T o u ris t Rjjeney Schana
Figure 3 - l f . Link Person to Nam e with Surrogate Edge.
46
4. The system now presents the user with a selection menu of the
types of edges valid for the two selected nodes for IFO schemas
(see Figure 3 - l f ) . In this case the user selected surrogate
edge which denotes that the pname attribute serves as a unique
id e n tifie r for person.
SNAP knows about the structure of IFO schemas and therefore
many of the graph constraints of IFO schemas can be enforced. For
example, SNAP does not allow the user to create invalid fragments,
or to connect pairs of nodes with invalid types of edges. I f no
type of association is applicable between the reverse video node and
a given node, SNAP does not allow the user to select that node. I f
only one type of link is applicable SNAP w ill immediately produce
the link rather than present a selection menu with only one option.
The user repeats the node creation and linking process to
define the object set person and its two attributes: name and
address (see Figure 3-2a. One may recall from the introduction that
a cluster of this type is called an IFO fragment. Basically, a
fragment is a primary node together with its attributes. In the
fragment of Figure 3-2a, one type of abstraction, called
aggregation, is shown. A cross node (such as address) is used to
47
represent that an object is a tuple whose component domains are
defined by the children nodes (s tre et, c ity , state, and zip code).
A cross node must always be connected to one or more child node via
an object edge.
The fragment shown in Figure 3-2a shows three types of edges
relating nodes. A fragment edge, depicted as a line with an
arrowhead and a small square icon, represents a functional
relationship. For example, a person has an address or more
s p e c ific a lly , address(Jack) = ("1609 10th Street" "El Segundo" "CA"
"90250"). A surrogate edge, such as the one connecting person and
pname, represents a one-to-one, total function. In the running
example, this means every person has a name and that no two people
have the same name. A surrogate edge is depicted as a line with an
arrowhead and a two-way arrowhead icon.
F in a lly , an object edge, shown as a simple straight line with a
small fille d box icon, is used to represent structure within an
object. For example, an address has four components, one of which
is the c ity . For the above example we know that Jack lives in El
Segundo, denoted as address.city(Jack) = "El Segundo".
The s lig h tly larger tr ip fragment shown in Figure 3-2b
demonstrates additional features of IFO. These features are now
described by referring back to the running example. Recall that
each tr ip has a unique id e n tifie r, a guide, a set of
participants, and an itin e ra ry .
4R
city zip cod*
Tourist Racncy Sehsns
Figure 3-2a.
Person Fragment with Attributes for Name and Address.
trip
stoj
city
trip-id
trap
^ Tourlae Rpsncy^ s ^ 5 ^ ~
Figure 3-2b. Trip Fragment.
49
The itinerary is a set of stops where each stop is defined by the
c ity , and arrival and departure dates. Also, associated with each
stop is the hotel at which the participants w ill stay, and the set
of traps they may v is it.
The set of trip s is represented as an abstract type. The
surrogate edge between the tr ip node and the printable tr ip -id node
captures the constraint that trips are uniquely id entified by the
t r ip - id . Each tr ip also has a guide who is a person. This
relationship is captured by the fragment edge between abstract trip
node and the free guide node. A free node, shown as a c irc le ,
denotes that elements of that set form a subset of some primary
object set. Therefore, the structure, characteristics, and
attributes of objects residing at a free node are inherited from
some other s e t(s ). This inheritance w ill be discussed la te r when
describing the ISA edges.
The fin al type, called a star node, represents a grouping
abstraction and can be used to define multivalued functions. Recall
that each tr ip has a group of participants. This is shown in
Figure 3-2b by a fragment edge between the abstract tr ip node and
the group star node. Group is connected to the free node
participant by an object edge. As with guides, each participant is
a person and therefore a free node is used. Since the star node
represents a set or grouping operation, i t must be connected to
exactly one child node via an object edge. The type of objects
50
residing in the set associated with the star node is defined by the
child subtree; in this case each object associated with the star
node is a set of persons.
Star nodes and cross nodes can be intermixed to create complex
types. An example of a small complex type is shown in Figure 3-2b,
namely the object subtree with root labeled itin e ra ry . Reading from
top to bottom, the notion expressed in this example is as follows.
A tr ip has an itin e ra ry , which is a set of stops. A stop may be
viewed as a tuple consisting of city (whose structure and attributes
w ill be defined la te r) and printable attributes for the arrival and
departure, dates. In general, a complex type is a tree of star,
cross, free, and printable nodes connected by object edges. The
internal nodes of the tree are star or cross nodes (where a star
node has exactly one child and a cross node has one or more
children). The leaf nodes are free or printable nodes.
The fin al notion introduced by the trip fragment is nested
fragments. Up to this point a ll fragment edges mentioned emanated
from a primary node. In this example, two fragment edges emanate
from the stop node. They capture the notion that each stop on the
itin erary of a tr ip has a hotel and a set of possible traps to
v is it . In general, a nested fragment edge can only emanate from a
node, which is the child via object edge of a star node which is the
terminus of a fragment edge. (Formal definitions can be found in
Appendix A.1 .1 .) .
51
The two components described above, namely person and tr ip , are
examples of basic building blocks called fragments. An IFO fragment
consists of a primary node (usually an abstract node) and a number
of fragment components (usually types) connected to the primary node
via fragment or surrogate edges. (Formal defin ition of types and
fragments can be found in Appendix A.1 .1 .) . This concludes the
discussion of fragments. W e return now to the scenario in which the
to u rist agency database schema designer w ill refine the schema and
add additional structures.
A fter building the tr ip fragment, the user realizes that
additional object sets must be defined. These include hotels,
(to u ris t) traps, and c itie s . Also, the user begins to think more
in tently on what additional attributes are needed for the
participants and guides. For this example, the user wants to keep
track of a comfort quotient for people who participate in trip s , and
the user wishes to maintain the set of languages a guide speaks and
the proficiency of a guide in each language. Although these
attributes could be added to the abstract node person, the user
feels i t is much more natural to define two special subsets of
people.
SNAP uses a primary free node, depicted as a large c irc le , to
represent specialized subsets. These nodes are connected to other
primary nodes via ISA edges, depicted as a double arrow with a small
diamond-shaped icon. Figure 3-3 shows the person-guide-tourist
52
component for the running example which was created by using the
node creation and linking capabilities discussed above. The
semantics of this construct is that every guide speaks a set of
languages, each at a perhaps differen t proficiency, and every guide
is a person, thus inheriting a ll attributes of people.
S p ec ific ally , a guide has a name and an address. Sim ilarly, a
to urist has a comfort-quotient and every to u rist is a person.
The ISA edge presents the final construct in the (restricted)
IFO data model. (The complete IFO data model as detailed in [AH 84,
A H 85, A H 87] describes two types of ISA edges: namely generaliza
tion and sp ecialization .) One way to view the ISA edge is that i t
captures an inclusion dependency. That is , each object residing in
the object set associated with the node at the origin of an ISA edge
is an element of the object set at the terminus of the ISA edge.
The SNAP user u tiliz e s the ISA edge in two s lig h tly different
contexts. F irs t, as was shown above, ISA edges connect primary
nodes to build specialization structures. Second, a (range
restric tin g ) ISA edge joins a non-primary free node (usually in the
range of some function) to a primary node. For the tourist agency
schema, this second use of ISA edges represents that each
participant for some tr ip is a to u rist and each guide of a trip is a
special type of person called a guide. The complete schema for the
to urist agency is shown in Figure 3-4.
53
T >
a .
F ig u r e 3 - 3 . P e r s o n - G u i d e - T o u r i s t ISA S t r u c t u r e .
54
- r
F ig u r e 3 - 4 . Com plete T o u r i s t Agency Schema.
55
Figure 3-5.
Complete Schema with Range-restricting ISA Arcs Removed.
To conclude the discussion of schema design we highlight the
advantages of the SNAP approach to visual user interaction and the
IFO schema visual representation.
SNAP creates a very simple and natural user environment by
using a workstation with a high-resolution graphics display and a
mouse pointing device. The user expresses requests by pointing at
some object on the screen and pressing a mouse button. SNAP
responds by presenting a pop-up section menu of operations which are
valid for the chosen object. In contrast to a more trad itio nal menu
driven or command-driven system, this style of intention allows the
user to focus on the object or area of the screen of in terest. All
pop-up menus appear near the cursor, which is usually the user's
current focal point. Therefore, the user is not strained by having
to watch special portions of the display for status or error
messages, and to return to fixed areas to interact with the menu or
command in terp rete r.
The method of schema creation in SNAP reflects this simple
style of operation. The user points to the location on the display
at which a new node is to be created. SNAP displays a menu
selection of object types. The user may select a type or abort the
sequence. S im ilarly, the user creates edges by selecting the link
option for one node, pointing at the other node, and selecting the
type of edge. SNAP enforces many of the local restrictions to guide
the user in creation of valid IFO schemas.
57
The manner in which SNAP builds and displays schemas brings out
several attra ctive features of the IFO data model.
1. Every basic object type has a differen t graphical
representation. Also, since there are only five different
icons, the user can quickly and easily determine the type of a
schema node.
2. The relationships between nodes are clearly shown by four
differen t types of edges. Since the surrogate and fragment
edges are very sim ilar, the basic representation is the same,
only the small icons used for these edges are d iffe re n t.
3. The user can build up small fragments ignoring many of the
d e tails. Each of these building blocks can be created
separately and associations between them defined as needed.
4. D istinct nodes represent distinct roles of an object set. This
also makes i t easy for the user to focus on the fragments and
ignore the confusing crisscross of ISA edges inescapable in
large schemas. The range-restricting ISA edges can be easily
hidden to produce an easily comprehensible display (compare
Figures 3-4 and 3 -5 ).
58
5. The size and shape of icon cue the user to the role of the
component. For example, fragment and surrogate edges look very
sim ilar because surrogate edges simply represent a special type
of function. Also, free nodes and primary free nodes are both
depicted as circles. The user is immediately aware that the
structure and additional attributes of objects associated with
these types can be found at the other end(s) of an outgoing ISA
edge(s). The larger size of the primary free node reflects its
increased importance in an IFO schema.
The conjunction of a highly in teractive, easy to use graphics-
driven interface and the effective visual representation of the IFO
schema provides the basis for a useful schema design to o l. However,
the capab ilities discussed in this section are by no means
complete. The user requires additional operations to delete
components, rename nodes, to browse the structure, to move around
the display, to reposition nodes and to hide or redisplay portions
of the schema. These capabilities w ill be discussed below.
3.2. Schema Browsing
At the heart of the SNAP graphics-based schema manager lies the
browsing component. This component provides many capabilities which
are integrated into other components such as the schema design and
59
the query specification subsystems. Graphics-based schema browsing
of SNAP represents one type of database browsing. I t does not
include data browsing capabilities such as those in [H 80, M o 84, S K
82], The primary objective of this component is to present the user
with a coherent, easy to use set of operations to view the schema,
to hide portions of the schema, to locate fragments of in terest, and
to modify the graph layout. This section begins by discussing
several motivating factors in the design of SNAP and then details
how SNAP presents the schema browsing capabilities to the user.
The visual representation and the operations on that
representation were primary concerns of SNAP since any system for
schema browsing is fundamentally linked to the visual schema
representation used. Section 2 discussed several factors for good
user interface design and some graphics-based user interface design
c r ite ria . The following l i s t represents a more specific set of
goals or considerations of the SNAP schema browsing component.
1. The user must be able to easily view the primary object sets,
the a ttrib u te s , and the type and role(s) of these items.
2. The user must be able to request a simultaneous, coherent
display of a ll types of relationships arising in the underlying
data model.
60
3. The user cannot be confined to a small peephole into the data
structure, but must be allowed to view large portions of the
schema.
4. In order to contain the overwhelming complexities of very large
schemas, the user must be able to explore the structure in a
modular fashion.
5. Mechanisms supporting differen t levels of abstraction should be
used to aid the user in focusing attention on subcomponents and
interconnections of current interest.
6. The user must have control over the structure layout in order
to take fu ll advantage of spatial perceptions. The system must
support fle x ib le arrangements of the diagram.
7. Inevitably the user w ill become lost or confused. The visual
representation must fa c ilita te some mechanism for returning to
fa m iliar representations.
W e now introduce the general capabilities of SNAP which help
achieve these goals. These capabilities w ill be exhibited in more
detail in the tr a ilin g subsections.
61
SNAP provides the user with tools for fle x ib le schema layout.
For example, the user may position two nodes in close proximity to
re fle c t the close relationship between them. W hen viewing the
schema from another point of view, the user may reposition one of
the nodes closer to some th ird node. Also, when changing one's
view, the user may hide or redisplay some components. To aid in the
arrangement of the current active schema, SNAP offers powerful
operations at several levels to hide or redisplay components, to
reposition components, and to perform some automated layout of
components.
While the user examines differen t portions of the schema, the
user w ill require operations to modify the current portal into the
entire schema. SNAP provides a pan operation to allow the user to
scroll around the diagram, and a zoom operator to allow the user to
enlarge or shrink the diagram to focus on a smaller or larger
portion of the schema. SNAP also shows the user the location of the
current portal within the entire diagram.
Several methods may be employed in SNAP to help the user
segment the schema and recall i t la te r. At one level the user may
checkpoint the current system configuration, and resume from that
point la te r. On a s lig h tly differen t le v e l, SNAP browsing
capabilities p a rtitio n the schema into lo gically related components
to aid the user in locating areas of interest for differen t
functions. This includes layering and level of detail operations
62
through the use of f il t e r s . Also, the user may focus on a specific
component and re s tric t the display to only these components which
are closely related to i t .
The database schema should be able to allow users to view the
information structure from differen t points of view. For example,
one user at the to urist agency may view the relationship between
trip s and guides as each tr ip having a guide. However, another
possible viewpoint is that every guide is in charge of a set of
trip s . SNAP provides fle x ib le alternatives in viewing of
information structure by supporting options for creating views
including display of inherited fragments, derived data or derived
en tity subsets, inverse functions, or more general composed
attributes.
This concludes the general overview of the SNAP schema browsing
characteristics. W e turn now to a more detailed presentation of how
SNAP supports the user in these a c tiv itie s . This discussion only
includes those features which were actually implemented in the
prototype. Some of the more advanced capabilities such as meta
browsing and incorporation of derived data w ill be discussed in
Chapter 5.
3 .2 .1 . Hiding and Redisplaying Portions of the Schema
Assume the user wishes to examine the tourist agency schema,
and that the in it ia l status of the display is as shown in
Figure 3-6a. All nodes other than the ones representing the major
entity sets have been hidden. W e now show how the user interacts
with SNAP to unhide or hide various components.
Assume the user f ir s t wishes to uncover more information about
the tr ip component. Therefore, the user selects the tr ip node and
SNAP responds with a set of options. For this circumstance, SNAP
provides a number of options to display attrib u tes. For example,
the user may wish to view a l i s t of attributes and select some of
them for display. O n the other hand, the user may wish to show a ll
of them immediately. I f the user decides to display a ll of them,
the system adds the items to the active schema as shown in
Figure 3-6b.
The user may now proceed in the same manner to uncover
additional information about the attrib u te group. Since group is
represented by a star node i t must have one child. W hen the user
selects the group node, SNAP w ill respond with a number of options
(one of which is to display the hidden child node). The user wishes
to examine the group structure in more detail and therefore chooses
to display the child node. SNAP responds by adding the free node
labeled participant to the display. The user now knows that a trip
64
has a group of participants, and, since the participants are
represented as a derived node, the user also knows that the
structure and attributes are defined elsewhere in the schema.
To discover additional information about the participants, the
user may choose to unhide the supertype(s) (the node(s) connected to
i t via an outgoing ISA edge). When the system displays the tourist
node, the user may add the attributes for to u ris t and for person.
The resulting diagram is shown in Figure 3-6c. At this point the
entire set of attributes of a participant are really not displayed;
only the most relevant ones are shown. W e know that a participant
is a person and therefore shall in herit a ll attributes of a
person. Not only are attributes inherited from supertypes but they
are also inherited from subtypes. For example, the person entity
set inherits attributes from a ll subtypes since i t is possible for a
to u rist to also be a guide.
Given a node in an ISA la ttic e , the user may request that the
system display subtypes or supertypes. In the running example, when
the user requests the display of subnodes of person, the system
responds by adding guide to the display. As above, the user may
then request that the attributes be added. The resulting display is
shown in Figure 3-6d. The user now clearly sees the relationship
between the participants and the guide of a tr ip ; namely, they are
people (indeed a desirable characteristic given the amount of time
they must spend together).
65
trip
tra p
city
ro u '"‘ a t "9 **e y Seh**a
Figure 3-6a. Primary Nodes of the Schema
trip
tra p
c ity
f o u r fa t" ftpaney"'ScK«««‘
F ig u r e 3 - 6 b . F i r s t L evel A t t r i b u t e s o f Primary T rip Node
trip -ld
trip
to u rist
- T o u rist H a.rcv 5 c h ... ;
-------------- I
Figure 3-6c. Information About Participants of a Trip.
trip-id
trip
Ian
T o u rist Hgtncy Sehana _ ~ . . .. .
- —
F ig u r e 3 - 6 d . R e l a t i o n s h i p s Between P erson and T r ip .
The above session introduced some of the display control
c a p ab ilities. This f ir s t family of tools operates at a variety of
levels to hide and redisplay connected components. Associated with
any request is a range factor which is e x p lic itly or im p lic itly
set. This range may be used in three ways.
1. All or selected dependent nodes within the given range may be
hidden or redisplayed. (The set of dependent nodes of a given
node is defined as a ll nodes connected to i t via a path of
outgoing function, surrogate, or object edges.) I f the range
factor is set to n, candidate nodes for redisplay include a ll
hidden nodes whose path length is less than n. For a hide
request, a ll nodes of path length greater than or equal to n
are candidate nodes. The two extremes of 1 and a ll denote
immediate dependents and the closure of all dependents.
2. Also, a ll or selected subnodes in an ISA or object la ttic e
within the range may be hidden or redisplayed in a sim ilar
manner.
3. F in a lly , all or selected supernodes in an ISA la ttic e may be
hidden or redisplayed.
68
W hen objects are hidden or redisplayed, SNAP automatically
erases or redisplays ( i f both endpoints are visible) the edges. The
user may not e x p lic itly hide fragment or object edges since they
represent a unique binding between pairs of nodes. The node at the
terminus of one of these edges is dependent on the node at the
origin and therefore cannot stand alone. O n the other hand, the ISA
edge conveys a differen t sense and can be freely manipulated in
three ways.
1. At a local le v e l, the user may point at a specific ISA edge and
hide i t . The user may redisplay the edge by choosing the free
node at the origin of an ISA edge and selecting the redisplay
ISA option.
2. At a global le v e l, the user may elect to hide/redisplay all ISA
edges connecting a non-primary free node to a primary node.
These range-restricting edges represent restrictions on
function ranges and object subcomponents.
3. At a global le v e l, the user may hide/redisplay all ISA edges
between primary nodes. These edges connect primary nodes in an
ISA specialization structure.
69
3 .2 .2 . Viewing D ifferent Areas of the Schema
During any session the user may wish to focus on different
areas in more or less d e ta il. The previous section demonstrated how
users may focus on various components by hiding and redisplaying
schema elements. Although this may provide su fficien t support for
very small schemas, additional operations are required for any
re a lis tic application. This section discusses a family of commands
for modifying the viewers portal into a large schema. In SNAP, this
portal defines the area into the entire schema which is currently
displayed in the schema window.
W e return now to the to u rist agency example to demonstrate
various mechanisms to id entify the schema po rtal. Assume the user
wishes to focus on the tr ip fragment. I f this fragment is located
in the center of the screen, a simple zoom operation may be used to
decrease or increase the portal size (maintaining the same center or
focal point) thus zooming in or out of the displayed schema. For
example, with the zoom factor set to 2, a zooming operation w ill
double the size of the schema components. Applying the zoom-out
operation once w ill shrink the nodes by 1/2, thus allowing more of
the schema to be displayed. In general, the user may set the scale
facto r, which is defaulted to 2, and zoom in or out to achieve the
desired sizing.
70
Since the entire schema may not f i t into the current portal,
the user may pan this portal to reach other areas. For example,
consider the to u ris t agency user who is currently focusing on the
trip fragment as shown in Figure 3-7a. Since the user is interested
in the characteristics of participants of the trip s , the user wishes
to display the components connected (via the ISA edge) to the
participant node. W hen the SNAP user selects the adjust screen
option, a rectangle representing the portal is displayed (see Figure
3-7b). The user may then move this portal by pushing the mouse
across the table. The user may fin a lly accept the new portal
location, or abort the command to leave the portal unchanged. For
this example, the user selected the new location to focus on the
person fragment as shown in Figure 3-7c.
tourist
city
city
t our1 Nfltncy 8ch«««
F ig u r e 3 - 7 a . Focus on T rip Fragment
71
trlp-U
trip
trap
city
city
Figure 3-7b. Panning the Portal Over the Display
itinara]
T o u rist flgency 5ch«n«
Figure 3-7c. Result of Pan Operation.
72
The simple zoom and pan operations discussed above provide
useful support for local or minor portal alteratio ns. However, more
convenient mechanisms are required for moving to distant schema
locations or to reposition the portal over a specific area. For
example, suppose the user who is currently viewing the person
fragment wishes to move to the city fragment, or wishes to view the
three fragments on the right-hand side of the global schema
layout. In order to accomplish either of those objectives, the user
may need to invoke several adjust screen or zoom operations to
achieve the desired result since the simple adjust screen option
only allows the user to move the portal one h alf of the portal's
width in any direction.
T our1st ~Ngcncy 5eh«n«
Figure 3-7d. Resizing Portal on the Entire Enterprise.
73
SNAP provides a convenient mechanism for easily viewing any
area by displaying the entire schema and by allowing the user to
either move the po rtal, maintaining the same size, or to create a
new portal of any size. For example, i f the to u rist agency user
selects to view the entire schema, SNAP w ill display the image as
shown in Figure 3-7d. In this display, the shaded area represents
the location of the current po rtal. The user may pick up this
portal and move i t over any area to select another area, or the user
may select a new po rtal, possibly of a differen t size, by selecting
the upper left-hand and lower right-hand corners of the new
portal. For the second option, SNAP w ill create a portal which
includes the largest dimension but maintains the same aspect ratio
in order to prevent distortion.
3 .2 .3 . Locating Schema Components
The user now has at hand tools to freely view any part of the
schema. However, additional location operations would greatly
increase ease of use. For example, the user often wishes to move
the portal over a specific component, or to easily locate subtypes
and supertypes. This section describes these two options for
automatically repositioning the portal.
Assume the to u rist agency user is viewing the person component
and now wishes to view the city component as discussed above.
74
Instead of scrolling the portal across the schema to the opposite
corner, the user would obviously prefer to simply instruct the
system to move to the specified component. SNAP provides two
closely related commands to support this interaction. F irs t, the
user may ask SNAP to reposition the portal over a primary node. In
response, SNAP displays a pop-up menu of the hidden primary nodes
and asks the user to select one of them. SNAP then repositions the
portal such that the selected node is located in the center of the
po rtal. Second, a closely related option allows the user to type in
the name of the desired node. This d iffers from the previous
command in that the user may specify any primary or non-primary
node. I f more than one node exists with the given name, SNAP
displays a pop-up menu describing the unique context of each node
and asks the user to select one of them. As before, SNAP then
centers the portal over the selected node.
W hen viewing a schema the user may wish to view the structure
and attributes of a free node. The hide and redisplay option
presented above demonstrated one way to view this information.
However, the simple redisplay mechanisms do not provide sufficient
support for locating components which are not within the current
po rtal. For example, assume the tourist agency user is studying the
tr ip component in detail as shown in Figure 3-2b, and the user
wishes to examine the structure of the free node participant. SNAP
provides an easy method for locating supertypes with the "flash
75
super node" option. W hen the user selects this option, SNAP blinks
the supernode ( f ir s t redisplaying i t i f hidden) for a few seconds.
I f the supernode does not lie within the current portal, SNAP
automatically shifts the portal over the supernode. The user may use
this option to easily follow the ISA la ttic e to the root. In the
same manner a user may ask SNAP to display any subnodes.
3 .2 .4 . Modifying the Schema Layout
A (completely) fixed schema layout cannot possibly satisfy all
of the user's desires since users may view the information in many
d ifferen t ways. The best layout can only be determined by the user
performing a given task. Furthermore, since the user w ill carry out
several differen t tasks, i t is possible, and very lik e ly , that the
best layout for one task is not the best layout for another task.
In fa c t, a good layout in one case may be to ta lly inappropriate for
another. This section discusses various capabilities the user m ay
employ to modify the schema layout.
A coherent family of tools to reposition components within the
schema are supported at a variety of levels. For example, the SNAP
user may choose to reposition a node, a node and a ll dependent
nodes, a fragment, or an entire ISA la ttic e structure. Obviously
the user could achieve the desired layout with only the simple node
repositioning operation. However, this extremely simple approach
76
becomes very tedious and awkward. The integrated family of
reposition operators creates a much more natural, friendly
envi ronment.
While the user is browsing a portion of the schema, the desire
may arise to move a component to a specific area on the diagram. I f
the desired component is currently v is ib le , the operations discussed
above provide an easy mechanism to carry out the task. However, i f
the component is located outside of the current portal, the user
must go through a series of move and windowing operations to achieve
the desired layout. To resolve this awkward situation, SNAP
provides a family of mechanisms to allow the user to pick a location
and then to select which node, (root of a) fragment, or (root of a)
la ttic e to move to the specified location.
At a s lig h tly higher level the user may wish to move an
arbitrary group of objects. This option could be used to move
multiple fragments, maintaining the same re lativ e positioning. SNAP
provides this option by allowing the user to specify a rectangular
area surrounding the nodes of in terest, and the selec tivity
including or excluding specific nodes. The user then moves the
entire group by repositioning the box to another part of the schema.
Optimally, the user would prefer that the system automatically
lay out the schema in a nice manner. Such general graph layout
algorithms would be beneficial for a wide variety of applications,
but the development of such algorithms remains an open question.
77
However, some layout techniques can be u tilize d for specific
aspects. For example, SNAP w ill assist the user by automatically
laying out subtrees in an ISA or object la ttic e . The tree layout
algorithm used simply lays out children nodes centered under the
parent node. All children are laid out such that they lie at the
same la titu d e . Since only the visible nodes are candidates for
repositioning, this option is ideal for laying out a structure after
i t has been sim plified or enhanced.
Whenever the user moves a node, SNAP automatically repositions
the fragment, surrogate, and object edges. Each of these types of
edges is displayed as a straight line between the node centers.
Since the two nodes are closely related and ty p ica lly placed in
close proximity, the edges are usually rela tiv e ly short. O n the
other hand, ISA edges often connect fragments located farther
apart. SNAP represents an ISA edge as two straight components with
one bend in i t . Therefore, edges may be diverted around some
components, producing a cleaner, simpler diagram.
SNAP supports a few options for manipulating ISA edges. F irs t,
i f the user turns on the automatic ISA placement option, then
whenever a node at the end of an ISA edge is moved, SNAP w ill
reposition the ISA icon roughly halfway between the two nodes. In
this node, ISA edges act much lik e the other types of edges.
Second, the user may pick up the ISA icon and reposition i t to the
desired location. Third, the user may point out the derived node at
7 «
the origin of an ISA edge, and request that the system reposition
a ll ISA icons associated with ISA edges out of the selected node.
The repositioning w ill be done as described for the automatic
placement option.
3 .2 .5 . Advanced Browsing Features
The powerful set of operators discussed so fa r creates a fa irly
complete tool k it . Upon using the system i t becomes apparent that
additional advanced operations, possibly b u ilt up from the
previously defined set, w ill greatly assist the user. This section
presents one advanced browsing feature which allows the user to
easily add or remove ISA edges from the display. Chapter 4
discusses three other advanced browsing features which promise to be
quite useful but have not been tested in the prototype.
Due to the unique features of the IFO model, a SNAP schema can
easily be compartmentalized into a number of fragments. Also, since
IFO uses d istin ct representation for distin ct roles, each of these
fragments can be viewed independently. The criss-cross network of
inter-relationships between fragments has been relegated to the ISA
edges. Furthermore, because of the above mentioned features, the
ISA edges can be removed without great loss of information. As a
resu lt, SNAP can present the user with an easily digestible
representation of the structure of information. To accommodate
79
th is , SNAP provides global operators to allow the user to easily
hide or redisplay either a ll ISA edges between non-primary derived
nodes and primary nodes or a ll ISA edges within ISA lattice s of
primary nodes. (This is illu s tra te d in Figures 3.4 and 3 .5 ).
This concludes the introduction of the basic capabilities of
schema browsing. There are, of course, additional capabilities
which were only hinted at in this section, such as the a b ility to
rename components in the schema (a complete lis t of capabilities can
be found in the appendix). Also note that although these
capab ilities were presented as schema browsing ca p ab ilities, some of
them should be more aptly described as graph browsing
c a p a b ilities . For example, many of the hiding/redisplay, viewing,
locating, and repositioning operations discussed in the e a rlie r
subsections are also used for manipulating the query graphs.
All of the options described in this section have been verified
in the prototype. Interaction with the prototype also suggests
several areas for expansion, such as sophisticated display control
through f il t e r s , location of areas of interest through a
hierarchical subject directory, and extending the schema to include
derived data. These extensions shall be discussed in Chapter 5.
80
3 . 3 . Query S p e c i f i c a t i o n
Another major component of a D B M S is the query specification
subsystem. This component provides the agent through which the user
may inquire about information stored in the database. Because users
are often not database experts, the query specification component
must allow the user to state what information is desired in a
simple, natural manner. Encouraging the user to express what
information is desired rather than forcing the user to state how to
extract the desired information sim plifies many query requests. In
general, this type of interface is called non-procedural.
SNAP supports the underlying goal of coherence and sim plicity
by integrating the query specification component into the D B M S in a
coherent fashion. The commands, the style of interaction, and the
general user environment are consistent across all SNAP
components. Thus, users may rely on experience gained in one phase
of database a c tiv itie s to guide the user in another a c tiv ity . In
p a rticu lar, for the current context, SNAP carries through the
graphics-based paradigm. In the query specification mode, SNAP
provides a rich basis for specifying a wide range of queries in a
visual manner. SNAP also maintains the close coupling of informa
tion throughout the system. Therefore, the user may easily view the
relationship between query specification information and schema
information.
81
This section presents three aspects of the query specification
a c tiv ity : 1) the manner in which the user specifies which
components are of interest for a given question, 2) what constraints
or restrictions shall be placed on those components, and 3) what
information w ill actually be output. The method by which the user
specifies how the information shall be formatted shall be discussed
in the next section.
Specifying a query involves three d istin ct steps. These are,
id en tifica tio n of the objects of in terest, specification of
restrictions or constraints between these objects, and selection of
the information to be output. In many trad itio n al systems the user
performs these tasks by f ir s t exploring the schema, collecting the
needed knowledge about entity sets and a ttrib u te s . Then, armed with
this knowledge, the user sets out to state the request by using a
text-based language such as a predicate calculus derivative. In
contrast to the text-based approach, SNAP attempts to liberate the
user from this cumbersome style and to allow the user to express
requests in a natural visual graphics-based system. An important
point of the query component is that the query graphs mirror the
representation of the schema. Therefore, i f a user understands the
visual representation of schemas, then i t is easy to learn the query
specification system.
Queries in SNAP are expressed by using query graphs (see
Appendix A.1.3. for d e ta ils ). A query graph is formed by combining
82
one or more query fragments, each representing a primary entity set
and related information from schema fragments. Each node in the
query graph relates back to some node in the schema, and each edge
represents a relationship expressed in the schema. The user may
re s tric t information associated with a query graph in one of two
ways. F irs t, the user may add a local node restrictio n which
represents a restrictio n on the objects residing in the
corresponding fragment node. Second, the user may add comparator
edges to indicate that certain relationships must hold between
e n titie s within d ifferen t nodes. The manner in which the user
creates the query graphs shall be illu s tra te d in the following
examples.
W hen specifying queries the user prim arily interacts with the
schema, query, and answer windows. In order to fa c ilit a te multiple
simultaneous queries, many query windows may be associated with a
schema window. Likewise, multiple answer windows may be associated
with a query window in order to allow the user to view information
in d ifferen t manners. Each query window is closely coupled to its
schema window, and thus manipulations in one window are easily
translated into manipulations in the other. For example, the query
nodes within the query window maintain a close binding to the
associated schema node, and SNAP allows the user to freely view this
relationship. S im ilarly, the user may identify information in the
answer window and request to view where the information came from.
83
The f ir s t step in query formulation is to create a query
window. Assume the current screen layout is as shown in
Figure 3-8a, where the schema window occupies most of the screen,
and that the user wishes to shrink or relocate the schema window.
An easy method for doing this is to point at the schema window
border and press the rightmost mouse button. The system displays a
menu of options for windows including one to set the edges. Using
this option the user may identify the upper left-hand corner and
lower right-hand corners of the window. Now, to create the query
window, the user may point at the schema window, press the middle
mouse button, and select the create query window option. The
location of the query window is specified by identifying the two
corners as described above. The resulting display is shown in
Figure 3-8b.
TgiHH AWBCT.gtJlCBI
bury this window
hi do this window
kill this window
l i Z m O S
Figure 3-8a. Request the Reposition Schema Window.
84
*. .= . + — ■ ■ '--.-----------------------------------------
Figure 3-8b. A Schema and Query Window.
For the f ir s t query example, assume the to u rist agency user
wishes to locate hotels in Beijing with at least 250 rooms. To
create the query fragment the user positions the cursor to the
desired location in the query window, presses the rightmost mouse
button, and chooses the include fragment option. The system
displays the l i s t of primary nodes and asks the user to select
one. Figure 3-9a shows the display after the hotel node was chosen.
Now the user wishes to re s tric t the hotels to those with a
capacity of at least 250. To accomplish th is , the user points at
the capacity node and selects the change restrictio n option (see
Figure 3-9b). The system displays the current re s tric tio n , which is
85
empty for this case, and allows the user to modify i t . For this
example the user enters the string "> 250".
In order to re s tric t the city node to B eijing, the user must
access the c ity name a ttrib u te associated with the city attrib u te of
hotel. The user instructs SNAP to d ire c tly display inherited
fragment edges of the free (or primary) node by selecting the add
inherited fragment edges option for that node. For the free hotel
city node, the system responds by incorporating the cname, language,
and climate fragments to the display (see Figure 3-9c). Now, the
user may re s tric t the cname node to be equal to Beijing in the same
manner as capacity was restricted.
T ©
j UniMimJ
, y v • . . , , , j
\ m m |
r * — i
T o u r is t H forw y Scbana
^ ~ ~ v ~ ~- n v j-* r ^ i"" " **1 r ~ ^ ^
Figure 3-9a. Basic Hotel Query Fragment.
86
B m h m restrict! qy
scneiM nod*
a c tiv a t*
h id *
Figure 3-9b.
Request to Add a Restriction to Capacity of Hotel.
The final step in creating a query graph is to id entify which
attributes shall be output. When the user chooses the activate
option of a query node, the system shades in the node to signify
that that node is a candidate for output. The completed query
graph, together with a simple answer window, is shown in
Figure 3-9d.
The preceding example introduced many of the features of the
query specification component. As was shown in this simple example,
the style of interaction in the query window was exactly the same as
i t was in the schema window and the options correspond to the kinds
of things.a user wishes to perform in order to build a query graph.
87
B rie fly , the capabilities the user invokes for query
specification are as follows. The user builds query fragments by
incorporating schema components into the query window. The user may
freely use any of the graph browsing tools discussed relative to
schema browsing to hide/redisplay, reposition, or locate
components. Inherited fragments may be direc tly displayed and
manipulated for primary or free query nodes. The user may apply a
local restriction to any node by associating a formula with one free
variable with any selected nodes. F in ally , the user specifies what
information shall be printed by activating the desired nodes.
SNAP maintains a tig h t coupling between schema and query
components and presents this relationship to the user in a variety
of ways. For example, assume the user is working in a query window
whose corresponding schema window is currently hidden. The user may
ask the query window to display its parent schema window, to which
the system responds by bringing the schema window to the top of the
windowstack. Likewise, the user may ask the schema window to
display the current active query window. By default, the current
active query window is the last one created. The user may, however,
instruct another query window to become the active query window
associated with a schema window. As an aside, the current active
query window takes on added significance for creating query
fragments, because SNAP offers an alternate method for including
schema fragments into the query graph by direct id e n tific a tio n .
88
Using this method, the user may point direc tly at a primary node in
the schema window and ask that the corresponding query fragment be
created in the associated active query window.
SNAP also preserves the relationship between query and schema
nodes, and presents this information to the user. For example, the
user may ask a query node where i t came from in the schema. In
e ffe c t, the query node then issues a request to the corresponding
schema node to highlight it s e lf . The schema node responds by moving
the portal over it s e lf i f i t is currently outside the portal,
redisplaying it s e lf i f i t is not v is ib le , and flashing its e lf
(alternating between regular and reverse video) for a couple of
seconds.
Tom* < a t H aanov 5ch«w>
a - -P -L
1 1 1
Figure 3-9c. Inherited Fragment of City of Hotel.
89
G reat U e l!
Friend ship
H oliday In n
■
Figures 3-9d. Output Hotel Name and Capacity for Hotels
in Beijing with Capacity of at Least 250.
Given the tools discussed so fa r, the user may create simple
restriction queries. S p ec ific ally , the user may add restrictions
within a query fragment but may not compare components of one or
more fragments. The next example illu s tra te s how comparator edges
can be used to construct cross component comparisons.
Recall that as part of the original schema, each to u rist has an
associated comfort-quotient, which is a number (1-10) specifying how
luxurious the accommodations are required to be for that person.
Also, each hotel has an associated comfort-rating which reflects the
class of the hotel. The to u rist agency user wishes to generate a
l is t of to u ris t-c ity pairs such that a hotel exists in that city
90
with the required comfort-rating for the to u ris t. In order to
express this request, the user f ir s t creates the two query
fragments: one for to u ris t, and one for hotel. The user then links
the to u rist comfort-quotient node to the hotel comfort-rating node
with a comparator edge and f i l l s in the "<" comparator. Finally,
the user activates the components which are to be output. The
resulting query graph and answer window are shown in Figure 3-10.
In general, comparator edges may be linked between any two
compatible nodes (see Section A .1.3. for d e ta ils ). The types of
comparison may be the well known relational operators (=,<,>, e tc .),
set operations =<, >, e tc .), or set membership (e, i ) . The user may
freely change the comparator associated with an edge, or delete the
comparator edge e n tire ly .
Before concluding, le t us b rie fly describe the semantics
associated with a query graph by informally outlining a four step
procedure for arriving at an answer for a query. Basically, the
procedure generates a relation with all the information associated
with the query components and then applies the appropriate
restriction s. Section A.1.3. presents a more detailed account of
the meaning associated with a query graph.
1. Generate a relation (possibly with null values) for each query
fragment. Each node in the query fragment w ill be represented
as a column in the relation . (Since some of the nodes m ay
91
represent sets the relation is really not a f ir s t normal form
re la tio n .)
2. Take the cross product of a ll query fragment relations to
generate a large (wide) relation with a ll a ttrib u te s .
3. Remove tuples from the relation by applying the node
restrictions and the comparator edge restriction s.
4. Project out the fin al information corresponding to the active
(shaded) query nodes.
^ Town at ri|*ney Schana
View information
1 onana enano 1
Jtf»N ffbN
Jo* fill nan Paris
Carolyn Bright Be1jlng
Carolyn Bright Madrid
Carolyn Bright Parle
Carolyn Bright Tokyo
Carolyn Bright LB
Doug Daaay Madrid
Loren Senno Madrid
Rich Dubln 8*1J1ng
Rich Dubln Madrid
R'ch Dubln Parts
Rich Dubln T ekyo
M e t * b * f* »
___________________________
Buery Window 1
Figure 3-10. Tourist-City Pairs for Cities Which Can
Accommodate Tourists.
92
As was shown above, the user interacts with the query subsystem
prim arily through a graphics-based interface. The consistent user
interface across the schema and query components makes i t easy for a
user to learn how to effec tively exercise the query subsystem. Many
of the commands are identical and others are modified only slig htly
to reflect th e ir enhanced application. These query graphs clearly
represent the structure of the information the user wishes to
view. By manipulating these graphs, the user may express in a
simple fashion what information is required, rather than having to
state how to extract the information from the database. This
p icto ria l paradigm serves as a powerful tool to express a wide range
of database inquiries.
3.4. Results Formatting
After browsing the database structure and specifying a query,
the user w ill now wish to examine the results in differen t ways.
Many times this component is not discussed relative to graphics-
based interfaces, probably because viewing textual information
doesn't really f i t into the general flow of the system. I t is none-
the-less a very important component. For viewing results, three
d istin ct styles of presentation found in a wide variety of systems
may be distinguished. F irs t, information may be presented as a fla t
table of data. Second, a form may be created which displays each
93
en tity using a specific format. Third, a graphical icon m ay be
associated with the information.
A goal of the SNAP user interface is to present simultaneous
displays of large amounts of information in a compact, coherent,
easy to comprehend fashion. Furthermore, the manner in which the
user specifies how to format the information must be natural, easy
to use, and easily modified. A major problem with the simple
tabular approach is that the explosion of information makes i t
d iffic u lt for the user to absorb the data. Commands to sort the
data on columns a lle v ia te but fa il to eliminate this problem. The
form display of e n titie s may work for canned queries but these
templates are often cumbersome to create and modify. Also, a form
which displays one en tity at a time does not allow the user to
easily grasp the entire context of the information. F in ally, dis
playing icons for data, possibly modified to re fle c t differences,
turns out to be more entertaining than useful. Specification and
interpretation of icons is only feasible for small, essentially
s ta tic databases.
Another approach to data (object) browsing is interactive
access of individual objects as used in the inspector of the
Smalltalk environment [G 84] or as used in the ISIS [F 84] database
access systems. Using this approach, the user holds an object and
examines its a ttrib u te s . Since each of the attributes may also be
viewed as objects, the user may in turn inspect each of them. This
94
approach works well for examining a small number of objects but it
is d iffic u lt to view large or even moderate amounts of information
concurrently. I t is also d iffic u lt at times to uncover or identify
the relationships between objects quickly.
SNAP allows the user to view the information as a (special type
of) non-first-normal-form relatio n . The user may either view the
data in simple tabular form or may group information in a natural
fashion. The user simply creates a template which directly
corresponds to a bucket format header as introduced by [AB 84], The
manner in which the header is created is very simple. The user is
presented with a l is t of attributes corresponding to the active
nodes in the query graph. The user may include attributes into the
header along with (possibly nested) buckets. When the final bucket
is closed o ff, the user may browse the information formatted
according to that bucket d e fin itio n . The types of formats and
general style of interaction shall be demonstrated by a couple of
examples.
For the f ir s t example, recall the tourist-hotel-com fort
quotient query of the previous section (see Figure 3-10). For this
example, the user wishes to view the information in three differen t
manners; the to u ris t-c ity pairs, the data grouped by to u ris t, and
the data grouped by c ity .
In SNAP, a ll three of these formats may be viewed
simultaneously by using multiple answer windows. Just as many query
95
windows may be created relative to a schema window, many answer
windows may be created relative to a query window. W hen the user
requests a SNAP query window to process the query, the results are
sent to the current active answer window. By default the current
active window is the last one created; the user may, however, freely
select any window as the active window.
To create an answer window the user points at the query window
and chooses the create answer window operation. The user then
defines its position on the screen by choosing the upper le f t and
lower right-hand corners of the window border. Now, assuming the
appropriate nodes are activated, the user instructs the query window
to process the query. The database is then queried and the results,
along with a default format, are sent to the answer window for
additional processing. The simple table of to u ris t-c ity pairs is
shown in Figure 3-10.
An answer window takes on one of two formats: one for viewing
the information and one for editing the bucket format header. In
the view information mode, the answer window consists of three areas
separated by narrow lin es. The top area displays the t i t l e of the
window. The user may point at this area to request the system to
switch to the edit bucket format configuration. The second area
displays the current bucket format. The th ird area, taking up the
bulk of the answer window, displays the information. The f ir s t and
last lines of the information portion contain ita lic iz e d phrases
96
which indicate the current position in the table. For example, in
Figure 3-10 the phrase "top" indicates that the top of the
information table is currently v is ib le , and the phrase "more below"
on the bottom of the display indicates that additional information
is available.
The user may scroll through the information in several ways.
F irs t, the user may use the cursor to push up or pull down on the
words "more above" or "more below" to scroll one line up or down in
the table. Second, the user may select the words "more above" or
"more below" with a mouse button to scroll up or down by one page.
Third, the user may use the scroll bar to move around the tahle.
After bumping the scroll bar (the vertical line along the left-hand
border) the user may perform three types of scro lling . Pressing the
leftmost mouse button causes the current lin e (the one pointed at by
the cursor) to move to the top of the display. Pressing the
rightmost mouse button moves the top lin e of the display to the
current position of the cursor. Pressing the middle button causes
percentage scrolling. For example, with the cursor positioned at
the bottom of the information area, pressing the middle mouse button
displays the information at the bottom of the table. Likewise,
choosing the middle area displays the information in the middle of
the table.
Recall that for the to u rist comfort query the user also wished
to view the information grouped by to u ris t. To specify a new
97
format, the user selects the answer window t i t l e lin e , which causes
the system to enter the edit format configuration. The display for
this configuration (see Figure 3 -lla ) consists of four sections.
The f ir s t section is the window t i t l e lin e , which can be used to
return to the view information configuration. The second section
lis ts editing commands. The third section displays the lis t of
attributes which may be selected to be included in the format
specification. The fourth section shows the current display format.
The user now proceeds in the obvious manner to create a bucket
format. F irs t, the user may select the reset command to erase the
current format and begin the global bucket. The user next selects
the to u rist attrib u te with the include option. The system responds
by highlighting the a ttrib u te , thus indicating that i t has been
selected and is no longer a candidate for selection. The system
also adds the attrib u te to the bucket format lin e . Since for the
current request the user wishes to view the set of citie s associated
with each to u ris t, the user creates a bucket with city in i t by
invoking the begin-bucket command, by selecting the city attrib u te,
and by invoking the end-bucket command. F in a lly , to view the
results formatted according to the new bucket format, the user
selects the t i t l e portion.
I f the user makes a mistake or changes one's mind during bucket
format creation, the undo command may be used to strip off the
rightmost symbol. This symbol may be a close bucket, attrib u te , or a
98
begin bucket symbol. The final display of the three formats is shown
in Figure 3-11b.
W e conclude the discussion of answer reformatting by showing
how i t can be used to greatly compact the information display.
Assume that a guide speaks several languages, is in charge of a
number of trip s and phone numbers. Consider the average guide has
three phone numbers (work, home, and car), speaks fiv e languages,
and is in charge of five trip s . I f the simple tabular format were
used 75 lines ( 3 x 5 x 5 ) would be taken up in order to display the
information about the average guide. O n the other hand, a bucket
format with guide, bucket of languages, bucket of trip s , and bucket
of phone numbers w ill only require 5 lines (maximum of 3, 5, and
5 ). The results of such a query are demonstrated in Figure 3-12.
^ \ "** I
> 3 < 3 ^ 0
3 333333333T.9y?^.s$..?!3W8tt..?is^ff!£........................
nr n i r n
Reset Start Bucket End Bucket Undo
cname
pname
L
Figure 3 - lla . Configuration for Creating a Format.
99
Query Window 1
View Inform ation
i pnans crane !
M o r * akN
Joa fllIran Madrid
Joa B1Iran Paris
Carolyn Bright Be1J f ng
Carolyn Bright Madrid
Carolyn Bright Paris
Carolyn Bright Tokyo
Carolyn Bright LB
Doug Daxey Madrid
Loren Oenno Madrid
R1 eh Dub 1n BelJfng
Rich Dubfn Madrid
Rich Dubfn Paris
Rich Dubfn Tokyo
Rich Dubfn LB
Rian Eng Befjfng
Rian Eng Madrid
M c ra batow
,.JL
n e w T n f o r m o f i o f T
1 cnwe 1 1
Joe flllMn
M o * * a boa*
I 8e1J1ng |
I Madrid i
I Pari* |
Carolyn Bright
Doug Dasey
Loren Denno
Baf J1ng
Madrid
Paris
Tokyo
LB
I Madrid I
I Madrid
M o r a ba low
----------- cr
ew In/ormation
Mst-a j cnane j pnane | j
Ba1Jlng
M o ra abov*
1 Joe Rllnar |
j Carolyn Bright j
I Rich Dubfn j
I B1an Eng |
1 Don Eestafn |
I Rob Erhart j
| Don Qlaan {
Madrid
Quer 1 Carolyn Bright |
j Doug Dazey |
I Loren Oenno |
1 Rich Dubfn |
1 filan Eng J
1 Con Epstein |
M o r a b *lo w
Figure 3 -llb . Answer with Three D ifferent Formats.
„ y
£
V ew Inform ation
1 qufde 1anouaoe tour nane phene nunber 1
T o p
Gall Eng!1ah Orient Express El2-125?
Gaf 1 Englfsh Orient Express 376-9944
Gall English Bsfan Adventure 612-1257
Gaf 1 English Asian Rdventure 376-9844
Gall Englfsh European Getaway 612-1257
Gall Englfsh European Getaway 376-9844
Gall Eng!fsh Great Uell Tour 612-1257
Gall Eng!fsh Greet Hall Tour 376-9B44
Gall Chinese Orient Express 612-1257
Gaf 1 Chinese Orient Express 376-9844
Gall Chinese fisfan Adventure 612-1257
Gall Chinese Asian Adventure 376-9844
Gaf 1 Chinese European Getaway 612-12S7
Gall Chinese European Getaway 376*9844
Gall Chinese Great Kell Tour 612-1257
Gaf 1 Chinese Great Hall Tour 376-9844
Gaf 1 Japanese Orient Express 612-1257
Gal 1 Japanese Orient Express 376-9844
Gaf 1 Japanese Aslan Rdventure 612-1257
Ga11 Japanese Asian Rdventure 376-9844
Gall Japanese European Getaway 612-1257
Gall Japanese European Getaway 376-9844
Gaf 1 Japanese Great Uell Tour 612-1257
' Gall Japanese Great Uell Tour 376-9844
Gall French Orient Express 612*1257
Gail French Orient Express 376-9044
GaH French Aslan Adventure 612-1257
Gail French Aslan Adventure 376*9844
Gail French European Getaway 612-1257
M o r a bahna
u utaui
JSRSBS'I
jTtimtiiitiuuas
Ouery uindou 1“
Giew information
t guide ilenoueee I I tour nane i i phone nunber | j
T o *
Gall English
Chinese
Jeoeneea
French
) Orient Express |
j Aslan Adventure |
1 European Getaway j
I Great UaU Tour |
\ 612-1257 |
I 376-9844 |
Jin English
French
Gernsn
Spanish
Italian
Russian
| Budget Europe |
1 French U1ne Tour j
( Moorish Ruins j
j British Isles j
| Russian Roulette j
| 612-1258 |
I 572-4418 |
1 542*8355 I
Memem
Figure 3-12, First Normal
More Natural
Form Representation
Representation.
and a
100
4 . SURVEY OF RELATED SYSTEMS
In this section a b rie f survey of interactive systems for
database access is given. All of these systems satisfy most of the
c rite ra for good design discussed in Section 2 to varying degrees.
Therefore, this section focuses on the outstanding characteristics
of these systems. Proceeding from the most sim ilar data model to
the least sim ilar, the following presentation w ill overview two
systems based on the Semantic Data Model [HMc 81], four systems
based on the Entity Relationship model [Oh 76], and fiv e systems
based on the relational model.
The two systems most closely related to SNAP are SKI [K 84,
K M 84] and ISIS [GGKZ 85]. Both of these are based on an object-
oriented data model called the Semantic Data Model (SDM) [HMc 81].
Both systems support the various database a c tiv itie s of schema
design, schema browsing, and query formulation. Additionally, ISIS
supports data browsing. The following presentation shall f ir s t
cover the schema representation of both systems and then the query
specification and data display for these systems.
In SKI the graphical representation is created dynamically as
the user browses and enhances the database structure. The user
interacts with a display which separates the subschema into
horizontal stripes, where a ll nodes in a stripe serve the same
purpose. For example, the top band displays primary entity sets,
101
the second displays functions, and the th ird displays the range of
the functions. One goal of the SKI approach was to achieve an
appropriate balance between the complexity and unpredictability of a
to ta lly dynamic layout approach and the re s tric tiv e static layout
approach. Also, this approach attempts to eliminate the confusing
criss-cross network of relationship edges.
A weakness of this approach is that the user is not free to
view the information in the most natural manner. The user is
constrained to repositioning the nodes only within the horizontal
stripes. The user cannot freely arrange the schema to take
advantage of spatial perceptions. Another weakness of this approach
is that the user may not simultaneously display large amounts of
information because the display of any band is limited by the size
of the graphical icon. For example, assume the user wished to
display the 20 en tity sets of a database. Furthermore, because of
the size of the icons and the size of the screen, only 10 icons w ill
f i t across the screen. The user would be confined to browse through
10 at a time displayed on the top horizontal s trip , even though the
rest of the display screen was unused. The approach achieves a fa ir
degree of sim plicity by sacrificing power and generality.
In the ISIS system users are provided with more permanent
visual representations of portions of the schema. Each entity set,
a ttrib u te , or subset is represented by a rectangular box with a
unique f i l l pattern for each entity type. Object subtype
102
relationships between them are shown by connecting them with a
simple straight lin e , and range-restricting ISA relationships may be
derived by matching f i l l patterns. This visual representation fa lls
short in the area of perception aids. F irs t, each node is displayed
as a simple rectangle, thus giving no immediate clue as to its
role. Second, the f i l l pattern does nothing to aid in
distinguishing the various types of nodes. Since each node has a
unique f i l l pattern, the number of patterns quickly exceeds the
maximum number advised by [FW C 84] for error free recognition.
Furthermore, this f i l l pattern is used in an attempt to show the
range types of functions listed in an entity set node. Again, this
approach makes i t d iffic u lt to quickly identify the ISA relationship
because of the large number of patterns required for even small
schemas. F in ally , the type of relationship represented by an edge
between nodes is not readily apparent. The user must deduce its
type by examining the role of the two nodes connected by the edge.
The query f a c ilit ie s of SKI and ISIS u tiliz e an aspect of S O M
in a novel fashion. That is , queries are specified by in teractively
extending the schema to include derived data. For example,
available guides may be defined as a subset of the guides who are
not currently assigned to any t r ip . Both SKI and ISIS provide
various constructs for defining d ifferen t types of derived data.
ISIS allows the user to build up the entire query graphically by
selecting menu items with the mouse. Although this creates a very
1H3
consistent style of user interaction, i t is not clear that i t is
really advantageous over the text-based constraint method of SKI.
Fin ally , both systems provide some support for displaying query
results. SKI display answers by either using a fir s t normal form
relation or by using predefined en tity forms. ISIS provides richer
data browsing ca p ab ilities, but in essence displays only one small
piece of information at a time. Both systems fa il to display large
amounts of information grouped in an easily comprehensible manner.
Turning to systems based on the Entity-Relationship (ER) model
[Ch 76], the Database Design and Evaluation Workbench (DDEW) [R 84]
is a graphics-oriented decision support system for database
design. D D EW provides a coherent environment that allows a designer
to use fam iliar representations to progress from one design phase to
the next, and to ite ra te over previous design phases. A primary
benefit in using this tool is that i t encourages stepwise, ite ra tiv e
database design by a structured refinement methodology. As the user
describes requirements for en tities and the relationships between
them, the system aids in the organization of this information into
an E R schema. The resulting E R schema can then be translated into
re la tio n a l, network, or hierarchical schemas i f desired. The strong
point of D D EW is the coherent interface for schema design; D D E W does
not support query specifications.
The GUIDE system [W K 82] represents one of the f ir s t graphical
schema browsing systems. The GUIDE user traverses paths on a fixed
104
ER schema to express queries. Partial queries may be created,
independently examined, and combined to create more complex
queries. A primary contribution of GUIDE is the introduction of
several meta browsing f a c ilit ie s for locating schema components and
for focusing on specific components of the schema. Indeed, the
hierarchical subject directory and radius restriction operations of
SNAP evolved from e a rlie r capabilities in GUIDE. While GUIDE
provides a fu ll complement of fa c ilit ie s for panning, zooming, and
hiding or redisplaying schema components, i t lacks any capability
for users to rearrange the schema layout. Because of this fixed
schema layout, the user cannot reposition nodes in order to take
advantage of spatial perceptions. Also, the user who views the
relationships in a d iffe re n t manner from the DBA who created the
layout may find the diagram to be very confusing. Nodes which are
considered closely related from one point of view may seem
re la tiv e ly unrelated from another. Thus the nodes may not be placed
in close proximity of one another.
All the above mentioned systems focused on the structure of the
database. That is , the user browses around the schema in order to
specify queries. An alternate approach which involves browsing the
data in the database was introduced by two closely related
systems. The PDB system [C 80] is a sematic network database
browser. The data, is viewed as a graph whose nodes are individual
data items and whose edges represent a type of relationship between
105
the entities. The user navigates through the database by following
these edges between database residents. While PDB provides these
capabilities in a text-based fashion, the Living in a Database (LID)
system [F 84] supports them in a graphical manner. The LID user
lives in an instance of an ER schema, residing at a particular tuple
and viewing data and associated schema components. The entity-
relationship graphical representation is dynamically generated
during data graph-traversal. LID designers state that an important
factor for users is having a pleasing display and interaction
format, thus LID has obvious benefit over PDB. However, they also
acknowledge that dynamic creation of graphs is very d iffic u lt. As a
result, the user may have d iffic u lty discovering the database
structure since relationships may be shown in different orientations
for like entities.
Finally, this section concludes with a brief presentation of
five systems based on the less expressive relational data model.
The well known QBE [Z 77] is often called the firs t graphical
interface, though i t scarcely utilizes graphics. In Q BE the user
expresses queries by creating skeleton tables which correspond to
relations, and by using variables as entries in the tables to
indicate relationships between various attributes. The CUPID system
[McS 75] generalizes QBE in that the relational skeletons are
replaced by graphs with icons to represent relations, attributes,
and comparisons. The TIMBER system [SK 82] provides a powerful
106
relation editor. Users may browse and update the data in much the
same manner as with text editors. The Spatial Data Management
System [H 80] uses graphical icons to represent entities in the
database. The user browses the two dimensional layout to examine
various aspects of the underlying database. The RABBIT system
[W 84] is based on a notion of retrieval by reformulation which was
derived from the psychological theory of human recall. RABBIT aids
people who have only a vague idea of what they want or who are
casual users with limited knowledge of a given database.
107
5- CONCLUDING REMARKS
This section concludes the discussion of graphics-based
database management by reviewing the SNAP components, overviewing
the SNAP prototype status, and outlining some logical extensions and
additional areas of research directions motivated by SNAP.
SNAP makes extensive use of a large high-resolution bit mapped
screen and a pointing device called a mouse. The display consists
of one or more windows which are used to display portions of the
schema, queries and answers, or for status information and general
user interaction. By pointing at an object of interest with the
mouse and responding to the pop-up menu, the user states requests.
SNAP uses a system of pre-highlighting (drawing a flashing box
around the object currently pointed at) to provide feedback to the
user about what actions may take place by pressing one of the mouse
buttons.
SNAP is consistent at all levels. For example, knowledge of
browsing commands associated with the schema window can be directly
applied to browsing commands in the query components. Also, the
consistent style of user interaction allows the user to comfortably
move between the various components. General selection menus or
data entry panels always appear at the current focal point, thus
freeing the user from constantly changing one's focus to respond to
a request in some fixed area of the display. Because these pop-up
108
menus are dynamically created rather than being fixed, SNAP always
eliminates non-applicable options from the menu before presenting it
to the user.
The SNAP user primarily interacts with three types of windows,
these being schema, query, and answer windows. These windows
correspond to the varied database activities of schema design and
browsing, query specification, and data evaluation. By splitting
these activities across three types of closely related windows, SNAP
cleanly separates the components and yet encourages interaction
between them. This approach also allows the user to simultaneously
work with many schema windows representing views into the same or
different databases. By allowing the user to create any number of
query windows relative to a schema window, SNAP encourages the user
to explore variations on queries in order to better understand the
database. Likewise, multiple answer windows associated with a query
window allow the user to study the information more intently by
simultaneously displaying the data with different formats.
The general design of SNAP creates effective visual represen
tation. The high-resolution display, coupled with a window manager,
provides the basis for simultaneous presentation of large amounts of
information in a clear and coherent fashion. On top of this, the
graphics-based representation employs a small number of node and
edge types to clearly present the structure of the database to the
user. The fragments, which serve as the basic building blocks,
109
provide a substantial modularity ingredient. The distinct
representation for distinct roles concept which was introduced by
IFO also makes i t much easier for the user to focus attention on
small manageable chunks.
SNAP provides several fa c ilitie s for allowing the user to view
the schema. Browsing capabilities help the user locate subschemas
of interest. Additionally, the user may freely hide or position
schema components in order to clearly view the schema in the most
natural intuitive manner. Several commands assist the user in
determining the relationship between nodes and fragments in the
schema. Some of these commands automatically invoke portal
modification requests. The user may also freely modify the portal
to view any portion of the database schema enterprise at an
appropriate level of detail.
The SNAP query component encourages the user to try out various
options. The user may easily and quickly add constraints, specify
which attributes are to be printed out, and request partial
queries. By using these commands a user may build up complex
queries in a piecemeal fashion. The user may scrutinize various
components of a large query in order to better understand the query
results. Finally, the user may freely reformat query results to
view them in the most natural concise fashion.
As was mentioned ea rlier, the SNAP prototype is implemented in
Zetalisp on a Symbolics 3600. This implementation takes full
110
advantage of the sophisticated windowing capabilities of the
Symbolics and of an object-oriented graphics-based package called
BOOGIE (Bell's Object-Oriented Graphics Interactive Executive,
developed by Brigham Bell at the Information Sciences Institute,
Marina del Rey, California). The primary focus of this prototype is
demonstrating the major features of the graphical user interface;
efficiency and completeness are not emphasized in the
implementation.
W e turn now to examine some areas of interest highlighted by
using the SNAP prototype and discuss some logical extensions to the
currently implemented system.
The method for creating edges between nodes worked well for
defining fragment and object edges but i t has a drawback for
specifying ISA edges. Typically, the user will place nodes in a
fragment in close proximity and therefore the lengths of fragment
and object edges are short. The same cannot be said, in general,
about ISA edges. An ISA edge may possibly define a relationship
between one fragment at one side of the schema and another at the
opposite side of the schema. This does not present a problem for
small schemas in which the entire schema is usable but it does
present a problem for large schemas.
The current method of defining an edge is to instruct one node
that it is a target (either origin or terminus) of an edge and then
to instruct the other node to create an edge between its e lf and the
111
target node. In order to complete such a sequence both nodes must
be visible in the schema window because the only operation allowed
after the sequence is initiated to abort the request or to complete
i t . One way to solve this problem would be to allow windowing and
find object operations at any time. A drawback of this solution is
that it detracts from the simplicity of the system. The user must
now be concerned about the present state (or mode) of the system and
how to express desires. For example, the user would have to think
about whether an abort request would abort the window/find operation
or the link sequence.
A simpler and more natural solution may be to add another
option which free nodes may respond to. With this option the user
may ask a free node to define an ISA edge between its e lf and a
primary node. In response to such a request, the free node displays
the lis t of primary nodes and asks the user to select one of them.
A general area in which SNAP can extend the graphics-based
paradigm of schema design is to incorporate various aspects of
derived data into the schema. Derived data, which is viewed as a
fundamental contribution of semantic data modeling, includes derived
functions (including inverse and composed functions) and derived
subsets. Derived functions can be incorporated into SNAP by
allowing the user to define a path from a primary node to a target
node and to request that the system extend the schema to include the
appropriate fragment component. The path could be built by
112
identifying all nodes along the path or by using the "show
relationships" option discussed shortly. The other type of derived
data, namely derived subsets, can be defined by interacting with the
schema and query windows. For example, the user might copy the
hotel fragment to a query window and add a restriction that the
capacity be greater than 250. The user could then extend the schema
to create a subset of hotels, called large-hotels, which is derived
or computed based on the definition shown in the query window.
The browsing capabilities of SNAP represent a class of basic
operation which could be extended to support ideas found in other
systems. The following discussion presents three advanced browsing
tools which could be incorporated into the prototype to increase the
power and fle x ib ility of SNAP. The f ir s t feature allows the user
great fle x ib ility in controlling the display through the use of
filte r s similar to those found in PHIGS [BHM 85]. The second
feature helps the user locate areas of interest through the use of a
hierarchical subject directory similar to a capability in GUIDE
[W K 82]. The third feature allows the user to examine the
relationship between schema nodes through a path finding capability
similar to those found in SKI [KM 84] and GUIDE C W K 82].
The use of filte rs for controlling the current display of
schema (query) components represents the fir s t advanced browing
feature. Given a schema, a f i l t e r describes a set of display
constraints on that schema such that only those nodes which are
113
allowed to pass through the f i l t e r may be included in the display.
The way in which this works is described as follows.
Associated with every node is a set of display attributes. The
schema display system then uses an inclusion and exclusion f i l t e r
system to determine which nodes will be displayed. All nodes which
contain at least one display attribute in the inclusion f i l t e r set,
and which contain no display attributes in the exclusion f i l t e r set
shall be displayed. (Additional parent nodes of candidate nodes
will also be displayed.) The following definition describes this
concept in more detail.
P efinition: Let S=(V,E) be a schema where V is the set of nodes and
let da(v), v e V, represent the set of display attributes of
node v. Furthermore, let IF and XF represent subsets of
display attributes representing the inclusion and exclusion
f ilte r s . Then, when applying the filte rs to a display, the set
of visible nodes (VN) will be defined recursively as follows.
For v e V, v e VN i f
1. either d a (v)n lF * $ and du(v)HXF = < )> ,
2. or v is the parent via object or fragment edge of u e VN.
This display attribute f i l t e r mechanism provides a powerful,
flexible basis upon which several schema control operations may be
114
b u ilt. For example, assume that the display attributes assigned to
nodes include the type of the node ( i . e . , primary, non-primary,
abstract, free, cross, star, and printable). The system can then
easily display all primary nodes by setting the inclusion f i l t e r to
"primary". Likewise, the user may restrict the view to primary nodes
which are not abstract nodes by setting the inclusion f i l t e r to
"primary" and the exclusion f i l t e r to "abstract". In general, SNAP
allows the user to specify any attributes and to control the display
by using the system and user defined attribute sets.
The second advanced feature extends the hierarchical subject
directory concept of GUIDE [WK 82], This directory helps the user
locate the schema components of interest by allowing the user to
browse a tree structure. In this tree structure, nodes closer to
the root represent more general concepts and the user can easily
browse from the top downward (following the parent/child edges) to
successively refine the scope to the area of interest.
The manner in which SNAP uses the hierarchical subject
directory (HSD) differs substantially from the GUIDE approach. In
SNAP, the user fir s t requests to use the HSD associated with a
schema. SNAP responds by bringing up a window with the HSD display
structure. The HSD is displayed and manipulated in the same manner
as the nodes in the schema. All nodes in the graph are simply
displayed as rectangular boxes connected by straight lines. All of
the hide, redisplay, reposition, automatic layout, and find
115
operations function exactly as they do for browsing a complex types
in the IFO schema. Therefore, no new commands or style of
interaction need be learned. Associated with each node in the graph
are inclusion and exclusion filte r s , position information for all
nodes in the schema, and a portal definition. Therefore, when a
user selects to view the schema based on some node in the HSD* SNAP
lays out the schema nodes according to the position information,
displays the valid nodes, and positions the portal to the desired
area. The user may resume schema browsing or examine other layouts.
The third advanced feature assists the user in discovering
relationships between entity sets. This concept is closely related
to the “show relationships" option of SKI [KM 841. The user
specifies two or more objects and request the system to display
possible ways in which they are related. SNAP responds by finding
paths connecting the fragments. Each of the paths is then displayed
sequentially based on the closeness of the relationships.
The algorithm for determining the order in which to display the
various paths uses weighted edges. Each edge type (fragment,
surrogate, object, and ISA) has a weight factor. For example, the
weight of an ISA edge may be much less than that of a fragment edge
since it represents a very close relationship. The sum of the
weights of the edges in a path connecting the nodes determines the
closeness of the relationship. SNAP displays the path with the
lowest weight fir s t and then proceeds to display paths with
increasing weight.
116
Relative to the query subsystem of SNAP, i t may be interesting
to explore and extend the class of queries which may be expressed in
SNAP. One way to measure the expressive capability is to compare it
to other query languages. Obviously, the language is not as
powerful as firs t order predicate logic. I t would be interesting to
consider enhancements which could be integrated in a coherent
fashion to cover a wider range of queries. For example, the system
could be extended to include disjunction by introducing condition
boxes as in QBE. A major emphasis of this future work would be to
stick to the pictorial paradigm as much as possible instead of
falling back to a simple graphics-based realization of a traditional
text-based approach.
The final area of concern in SNAP involves viewing of
results. The use of the bucket notation for specifying formats
allows the user to view the data in a variety of ways. One
extension we considered was to develop a format editing assistant.
This component could possibly take advantage of information in the
schema to help guide and restrict the creation of meaningful
formats. For example, there may often be one obvious format which
may be associated with any fragment assuming the user wishes to view
the results in the same way in which the schema is arranged. Also,
it probably doesn't make sense to create a format with a key such as
person and a bucket for name(s) i f the schema has not defined name
as a multivalued function.
117
A more general approach to extending SNAP is based on
incorporating alternate structurings of data by using various IFO
representations. Simple mechanisms are already provided to create
composed or inverse functions through the derived data operations.
An example of a simple type of restructuring was given above for the
trip-guide relationship. This relationship may be viewed as the set
of trips a guide is responsible for or the guide assigned to each
tr ip . It is easy to imagine much more involved data restruc
turings. This raises some basic questions: what is an appropriate
general framework within which to understand this kind of data
restructuring, and is there a natural visual representation for
it? In itia l work in this area [AH 84] indicate that an algebra of
simple, local restructuring generalizations of these of [HY 84] may
provide the desired framework.
Another general issue which can be investigated involves the
use of IFO as an integration center for heterogeneous databases.
The structural aspects of IFO subsume many of the capabilities of
the relational, functional, Entity-Relationship, and Semantic Data
Models as well as the most frequently used features of the network
and hierarchical model. (IFO as such does not however address many
of the constraint mechanisms of some implementation.) An essential
ingredient is the understanding of the various ways data may be
restructured without loss of information content. Some in itia l
progress has been made in this area by [OH 84, MaPi 83].
118
A final related issue involves the relationship between IFO and
the relational model. The SNAP system may well serve as an
effective front end to a relational database management system.
Specifically, there is a straightforward translation of a natural
subset of the IFO data model into third normal relations (in much
the same way that ER schemas can be translated into the relational
model [Ch 76]). Thus, SNAP could be used to design and maintain
information which is stored in a relational database. Theoretical
results concerning update propagation in the IFO model CA H 85] could
be applied to ensure that certain types of functional and inclusion
dependencies are not violated.
REFERENCES
[AB 84] Abiteboul, S. and N. Bidoit. Non-First Normal Form
Relations to Represent Hierarchically Organized Data. In Proc. A C M
SIGACT-SIGMOD Symp. on Principles of Database Systems, 1984.
[AH 84] Abiteboul, S. and R. Hull. IFO: A Formal Semantic
Database Model. Technical Report TR-84-304, Department of Computer
Science, Univ. of Southern C a lif., April 1984. Preliminary version
appears in Proc. ACM SIGACT-SIGMOD Symp. on Principles of Database
Systems, April 1984, pages 119-132.
[AH 85] Abiteboul, S. and R. Hull. Update Propogation in the IFO
Database Model. In Proc. Int. Conf. on Foundations of Data
Organization, pages 243-251, Kyoto, Japan, May 22-24 1985.
[AH 86] Abiteboul, S. and R. Hull. Restructuring of Semantic
Database Objects and Office Forms. In t. Conf. on Database Theory,
Rome, Ita ly , Sept, 1986.
[AH 87] Abiteboul, S. and R. Hull. IFO: A Formal Semantic
Database Model. To appear in ACM Trans, on Database Systems, 1987.
[Br 83] Brachman, R.J. What IS-A is and isn 't: An Analysis of
Taxonomic Links in Semantic Networks. Computer 16(10):30-36, 1983.
[B 86] Bryce, D. Functional Description of SNAP. Unpublished.
[BH 85] Bryce, D. and R. Hull. A Conceptual Basis for Graphics-
Based Engineering Data Management. Technical Report TR-84-316,
Department of Computer Science, Univ. of Southern C a lif., October,
1984.
[BH 86] Bryce, 0. and R. Hull. SNAP: A Graphics-based Schema
Manager. Proc. In t. Conf. on Data Engineering, pages 151-164. Los
Angeles, CA, February 5-7, 1986.
[BHM 85] Brown, M. and M. Heck. Understanding PHIGS. Published by
TEMPLATE, The Software Division of the Megatek Corporation, 9645
Scranton Rd., SanDiego, CA 92121, 1985.
[BWZ 86] Bryce, D., J. Walker, and P. Zelenski. The Shape of
Things to Come. Presentation at National Computer Graphics
Association Conference, Anaheim, California, May 1986. Paper to be
published.
120
[BF 79] Buneman, P. and R.E. Frankel. FQL - A Functional Query
Language (A preliminary report). In Proc. ACM SIGMOO In t. Conf. on
the Management of Data, pages 53-58, 1979.
[BFN 82] Buneman, P., R.E. Frankel, and R. Nikhil. An
Implementation Technique for Database Query Languages. ACM Trans,
on Database Systems 7 (2 ):164-186, 1982.
[C 80] C attell, R. An Entity-Based Database User Interface. In
Proc. ACM SIGMOD In t. Conf. on the Management of Data, pages ,
Santa Monica, 1980.
[CL 79] Chan, E.P.R. and F. H. Lochovsky. A Graphical Data Base
Aid Using the Entity;-Relationship Model. In Proc. of the In tl.
Conf. on the Entity-Relationship Approach to Systems Analysis and
Design, pages 303-318, 1979.
[Ch 76] Chen, P.P. The Entity-Relationship Model - Toward a
Unified View of Data. ACM Trans, on Database Systems l(l):9 -3 6 ,
1976.
[CM 84] Copeland, G. and D. Maier. Making Smalltalk a Database
System. In Proc. ACM SIGMOD In t. Conf. on the Management of Data,
pages 316-325, June 1984.
[D 81] Date, C.J. An Introduction to Database Systems, Vol. I,
Addison-Wesley, Reading, MA, 1981.
[D 83] Date, C.J. An Introduction to Database Systems, Vol. I I ,
Addison-Wesley, Reading, MA, 1983.
[D 84] Date, C.J. Some Principles of Good Language Design. SIGMOD
Record 14(3):1-7, November 1984.
[DH 84] Dayal, U. and H. Hwang. View Definition and Generalization
for Database Integration in a Multidatabase System. 'IEEE Trans, on
Software Engineering 6:628-644, 1984.
[DT] Doherty, W . and A. Thadhani. The Economic Value of Rapid
Response Time. IBM productivity seminars.
[DJ 83] Dube, R. and H. Johnson. Computer-Assisted Engineering
Data Base. In The American Society of Mechanical Engineers, 1983.
ASM E 83-WA/Aero-ll.
121
CDS 83] Dube, R. and M. Rivers Smith. Managing Geometric with a
Database Management System. In IEEE Computer Graphics and
Applications, pages 57-62, October 1983.
[ELNW 82] Evans, S., D. Lipkie, .1. Newlin, and R. Weissman. Star
Graphics: An Object-Oriented Implementation. Computer Graphics
16(3):115-124, July 1982.
[F 84] Fogg, D. Lessons from a "Living in a Database" Graphical
Query Interface. In Proc. A C M SIGMOD In t. Conf. on the Management
of Data, pages 100-106, 1984.
[FVD 82] Foley, J. and A. Van Dam. Fundamentals of Interactive
Computer Graphics. Addison-Wesley, Reading, MA, 1982.
[FWC 84] Foley, J ., V. Wallace, and P. Chan. The Human Factors of
Computer Graphics Interaction Techniques. IEEE Computer Graphics
and Applications. Volume 4, Number 11, pages 13-48, November, 1984.
[G 84] Goldberg, A. Smalltalk-80, The Interactive Programming
Environment. Addison-Wesley, Menlo Park, CA, 1984.
[GGKZ 85] Goldman, K.J., S.A. Goldman, P.C. Kanellakis and S.8.
Zdonik. ISIS: Interface for a Semantic Information System. In
Proc. ACM SIGMOD In t. Conf. on the Management of Data, pages 328-
342, May 1985.
[GW W J 84] Good, M., J. Whiteside, D. Wixon, and S. Jones. Building
a User-Derived Interface. Communications of the ACM, Volume 27,
Number 10, pages 1032-1043, October 1984.
[HMc 79] Hammer, M. and D. McLeod, O n the Architecture of Database
Management Systems. In Infotech State-of-the-Art Report on Data
Design, 1979.
[HMc 81] Hammer, M. and D. McLeod. Database Description with
SDM: A Semantic Database Model. ACM Trans, on Database Systems
6(3):351-386, 1981.
[H 80] Herot, C.F. Spatial Management of Data. ACM Trans, on
Database Systems 5 (4 ):493-514, 1980.
[HY 84] Hull, R. and C.K. Yap. The Format Model: A Theory of
Database Organization. Journal of ACM 31(3):518-537, July 1984.
122
[JS 82] Jaeschke, B. and H.J. Schek. Remarks on the Algebra of
Non-First Normal Form Relations. Proc. ACM SIGACT-SIGMOD Symposium
on Principles of Database Systems, 1982.
[JSW 83] Johnson, H.R., J.E. Schweitzer and E.R. Warktine. A DBM S
Facility for Handling Structured Engineering Entities. In SIGMOD
'83 Engineering Applications, pages 3-11, May 1983.
[K 79] Kent, W . Limitations of Record-Based Information Models.
ACM Trans, on Database Systems 4 (1 }:107-131, 1979.
[KP 76] Kerschberg, L. and J.E.S. Pacheco. A Functional Data Base
Model. Technical Report, Pontificia Universidade Catolica do Rio de
Janeiro, Rio de Janeiro, Brazil, February 1976.
[K 84] King, R. Sembase: A Semantic DBMS. In Proc. of the First
In tl. Workshop on Expert Database Systems, pages 151-171, October
1984.
[KMc 82] King, R. and D. McLeod. The Event Database Specification
Model. In Proc. of the 2nd In tl. Conf. on Databases: Improving
Usability and Responsiveness, pages 299-321. Jerusalem, Israel,
June 1982.
[KMc 84] King, R. and D. McLeod. Semantic Database Models.
Database Design, Springer-Veriag, New York, 1984.
[KM 84] King, R. and S. Melville. The Semantics-Knowledge
Interface. In Proc. 10th In t. Conf. Very Large Data Bases, pages
30-37, 1984.
[K 83] Koriba, M. Database Systems: Their Applications to CAD
Software Design. Computer Aided Design 15(5):277-287, September
1983.
[LiPo 83] Linton, M. and M. Powell. Visual Abstractions in and
Interactive Programming Environment. In ACM 0-89791-108-
3/83/006/0014, pages 14-21, 1983.
[LoPl 83] Lorie, R. and W . Plouffe. Complex Objects and Their Use
in Design Transactions. In SIGMOD '83 Engineering Applications,
pages 115-121, May 1983.
[MacG 85] MacGregor, R.M. ARIEL - A Semantic Front-End to
Relational DBMSs. In Proc. 11th Int. Conf. Very Large Data Bases,
pages 305-315, 1985.
123
[MNG 86] Maier, D., P. Nordquist, and M. Grossman. Displaying
Database Objects. Technical Report No. CSE-86-001, Oregon Graduate
Center, January 1986.
[MMP 83] Malhortra, A., H.M. Markowitz, D.P. Pazel. EAS-E: An
Application Development System: Principles and Language Summary.
Communications of the ACM 27(8):785-799, August 1984.
[MaPi 83] Manola, F. and A. Pirotte. An Approach to Multi-Model
Database Systems. In S.M. Deen and P. Hammersley (editor), IC0D-?
Second International Conference on Databases, pages 53-75. The
British Computer Society, Churchill College, Cambridge, September
1983.
[Ma 84] Marcus, A. Icon Design Requires Clarity, Consistency.
Computer Graphics Today, page 7, November 1984.
[McS 75] McDonald, N. and M. Stonebraker. CUPID: A User Friendly
Graphics Query Language. In Proc. ACM-Pacific Conference, pages
127-131, San Francisco, CA, April 1975.
[MS 80] McLeod, D. and J.M. Smith. Abstraction in Databases. In
Workshop on Data Abstraction, Databases, and Conceptual Modelling,
pages 19-25, Pingree Park, Colorado, 1980.
[Me 81] Mehlmann, M. When People Use Computers - An Approach to
Developing an Interface. Prentice-Hall, Inc. Englewood C liffs , NJ,
1981.
[Mo 84] Motro, A. BAROQUE: A Browsing Interface to Relational
Databases. Technical Report TR-84-310, University of Southern
California, August 1984.
[My 83] Myers, B. INCENSE: A System for Displaying Data
Structures. Computer Graphics 17(3):115-125, July 1983.
[OD 83] Olsen, D. and E. Dempsey. SYNGRAPH: A Graphical User
Interface Generator. Computer Graphics 17(3):43-50, July 1983.
[PW 82] Peters, T. and R. Waterman, Jr. In Search of Excellence -
Lessons from Americas Best-Run Companies. Warner Books, New York,
NY, 1982.
[R 84] Reiner, D., et. a l . The Database Design and Evaluation
Workbench (DDEW) Project at CCA. IEEE Database Engineering 7(4),
1984.
124
[RKS 84] Roth, M.A., H.F. Korth, and A. Si 1berschatz. Theory of
Non First Normal Form Relational Databases. Technical Report TR-84-
36, University of Texas at Austin, December 1984.
[S 80] Schneiderman, B. Software Psychology: Human Factors in
Computer and Information Systems. Prentice-Hal1, Inc., Englewood
C liffs , NJ, 1980.
[Sh 81] Shipman, D. The Functional Data Model and the Data
Language DAPLEX. ACM Trans, on Database Systems 6(1) :140-173, 1981.
[SmSm 77] Smith, J.M. and D.C.P. Smith. Database Abstractions:
Aggregation and Generalization. ACM Trans, on Database Systems
2 (2 ):105-133, 1977.
[Sp 84] Spooner, D. Database Support for Interactive Computer
Graphics. In Proc. ACM SIGMOD Int. Conf. on the Management of Data,
pages 90-99, June 1984.
[SK 82] Stonebraker, M. and J. Kalash. TIMBER: A Sophisticated
Relation Browser. In Proc. 8th Int. Conf. Very Large Data Bases,
pages 1-10, 1982.
[SR 82] Stonebraker, M. and L. Rowe. Database Portals: A New
Application Program Interface. Memorandum M82/80, UCB/ERL, November
1982.
[TL 82] Tsichritzis, D.C. and F.H. Lochovsky. Data Models,
Prentice-Hall, Englewood C liffs , NJ, 1982.
[TsZa 84] Tsar, S. and C. Zaniolo. An Implementation of G EM -
Supporting a Semantic Data Model on a Relational Back-End. In Proc.
ACM SIGMOD Int. Conf. on the Management of Data, pages 286-295,
1984.
[UNO 81] Uffsby, S., S. Meen and J. Oian. TORNADO: A DBM S for
CAD/CAM Systems. Computer Aided Design 13(4):193— 197, July 1981.
[U 82] Ullman, J.D. Principles of Database Systems, 2nd Ed.
Computer Science Press, Potomac, MD, 1982.
[W 84] Williams, M.D. What Makes RABBIT Run? Int. J. Man-Machine
Studies 21:333-352, 1984.
125
[W DDD 83] Wilson, G., E. Domeshek, E. Drascher and J. Dean. The
Multipurpose Presentation System, In VLDB, pages 56-69, November
1983.
[W H 80] Wilson, G., and C. Herot. Semantics VS Graphics -- To Show
or Not to Show. In VLDB, pages 183-196, 1980.
[W K 82] Wong, H.K.T. and I . Kuo. GUIDE: A Graphical User
Interface for Database Exploration. In Proc. 8th Int. Conf. V e ry
Large Databases, pages 22-32, 1982.
[Z 83] Zaniolo, C. The Database Language GEM. Proc. SIGMOD, pages
207-217, 1983.
[Z 77] Zloof, M. Query-by-example: A Database Language. IBM
Systems Journal 16:324-343, 1977.
A. APPENDIX
This appendix contains two sections. The firs t section
presents the formal definitions of the basic model, including the
(restricted) IFO data model used in SNAP, the query specification
components, and the data formatting component. The second section
outlines the major operations of the SNAP sysatem, windows, nodes,
and edges.
The primary intent of this appendix is to serve as a reference
and to give definitive answers to questions about SNAP components.
This section does not contain expository remarks about the
motivation or possible use of these components.
A .I. Basic Model
This section presents formal definitions for the three primary
SNAP components which are used for database structure
representation, query specification, and results examination.
F irst, relevant definitions of various components of the IFO data
model are given. In particular, the firs t subsection defines the
basic building blocks of IFO schemas called fragments, and then
defines how these fragments can be assembled to create valid IFO
schemas. IFO schemas are used in SNAP to represent the database
structure. Second, the definitions of the constituents of the SNAP
127
query specification component are given. The SNAP user requests
information from the database by manipulating the schema to create
query graphs. Basically, a query graph includes one or more query
fragments where each query fragment represents a schema fragment
extended to include inherited attributes. The user may restrict the
information by applying local node restrictions or by including more
general comparator edges. Finally, the user may view the query
results in a variety of ways by creating object templates. This
appendix section concludes by describing the semantics of SNAP
queries and of these templates.
A.1.1. IFO Data Model
This subsection highlights major definitions of the IFO data
model by describing aspects of IFO components pertinent to this
work. Specifically, the structural aspects and the semantics of a
restricted IFO model are given. A complete presentation of IFO can
be found in [AH 84, A H 87]. The model used here differs only
slightly from the complete model in that generalization ISA edges
are not permitted. Therefore, some of the definitions are
simplifications of those given in [AH 87].
IFO is a model for database schemas and instances. An IFO
schema represents the structure of a database by using a directed
graph notation with certain kinds of nodes and edges. Types, the
128
most basic component of an IFO schema, are simple graphs used to
represent simple or complex object types. Simple functional
relationships between objects are represented in the basic building
blocks of an IFO schema called fragments (which are built out of
types). Fragments may be combined together by including ISA edges,
which represent inclusion dependencies, to create IFO graphs. IFO
graphs which satisfy the IFO ISA constraints are called IFO schemas.
Types form the most basic schema component by providing the
mechanism to represent simple or complex database objects. Simple
atomic types are used to represent printable, abstract, or free
information. These atomic types may be combined with star or cross
nodes, which correspond to grouping or cartesian product operations,
to create complex object types. Basically, a type is a directed
tree with printable, abstract, and free leaf nodes and internal star
and cross nodes.
Definition 1: A type is a directed tree R =(V,E) such that
1. V is the disjoint set of Vp(printable nodes), VA(abstract
nodes), Vp(free nodes), V*(star nodes), and Vx(cross
nodes),
2. each printable, abstract, or free node has no children,
3. each star node has exactly one child, and
4. each cross node has one or more children (which are viewed
as ordered).
129
Instances of a type R have the natural hierarchical structuring
as described by R. The atomic types ( i . e . , those consisting of a
single node) represent printable information, abstract objects, or
subsets of another object set. The star and cross nodes represent
grouping and cartesian product operations. Printable information
may be represented by character strings, integers, real numbers, or
any other types which have natural representations. Examples of
printable information include a person's name and age. Abstract
object sets represent things which may be described by but not fully
defined by printable attributes. For example, a person may be
partially identified by a name or id, but these attributes, do not
really capture the essence of the person.
The domain of a printable or abstract type v, denoted as dom(v)
is the collection of all objects of the given type. The other
atomic type, called a free type, represents some subset of objects,
and therefore the structure and characteristics of the objects
residing at a free node are inherited from somewhere else within the
larger context. This prompts the following definition of an object
i nstance.
Definition 2: Let R=(V,E) be a type. An object of type R is
1. an element of dom(v) i f V = {v} is the singleton printable
or abstract node,
130
2. a fin ite set of objects of R' i f the root of R is a star
node with child subtree R',
3. an ordered n-tuple (0^, 02, . . . , 0n), where 0^ is an object
of R^ i f the root of R is a cross node with ordered
subtrees R^, R2 , . . . , Rn, or
4. an element of some other type R‘ i f V is a singleton free
node.
The domain of a type R, denoted dom(R), is the set of all
objects of R. An object instance of a type R is a fin ite subset of
dom(R).
Given an object instance (defined relative to some type) one
may break down the structure into its constituents. The active
domain of a node in a type is defined as the collection of all
objects residing at that node within the given object instance.
Definition 3 : Let R=(V,E) be a type, and let I be an object
instance of R. For each node q of R the active domain of q in
I, denoted ac tq (I), is the set of objects of the subtree of R
with root q.
act (o) | oel}, i f the root of R is a star node
actq(I) " not equal to q.
a ^ th e ro o t ^ 1S 9 cross norl
” I n ic in tho kth cnhfrroo
i f the root of R is a cross node
and q is in the kth subtree.
not equal to q.
i f q is the root of R.
131
Fragments and fragment instances form the basic building blocks
for creating IFO schemas. Basically, a fragment represents an
object set along with a number of associated attributes. The
fragment instances provide the vehicle to incorporate functional
relationships between object sets.
Definition 4 : A fragment is a directed tree R=(V,E) such that
1. E is the disjoint union of Eq (object edges) and Ep
(fragment edges),
2. (V,Eq) is a forest of types,
3. the origin of each fragment edge is the root of R or it is
the child via an object edge of a star node which is the
terminus of a fragment edge, and
4. th e te rm in u s o f each fragm ent edge i s th e ro o t of a type
in th e f o r e s t (V,Eq ) .
An instance of a fragment is defined as a collection of objects
and a function describing attributes of those objects.
Definition 5 : Let R be a fragment with root r. Also, let Rq be the
type in R with root r, let fj , f 2 , . . . , f n be the fragment edges
out of root r, let pj, p2 , . . . , p n be the termini i of
f ^ ,f ?............ f n, and let R^ denote the subtree of R with root
p^. A fragment instance of R is an ordered pair T=(J,F) where
132
J is an object instance of Rq, and F is a function with domain
*f? » ...» fn such that F (fk), also denoted I / f k or simply f k i f
I is understood, is a partial function with domain J such that
for each o in J either
1. I / f k(o) is an object of Rk i f Rk is a type, or
1 I
2. I / f k(o) is an instance of Rk, i f Rk is not a type and R^
is the fragment obtained from Rk by removing its star root
node.
IFO fragments allow the user to nest fragment edges to
arbitrary depths. For example, consider the fragment shown in
Figure A-l for representing the proficiency guides speak various
languages. I f Gail is a guide who speaks French well and German at
a basic level then we write (G ail)/proficiency(French) = "well" and
language(Gail)/proficiency(German) = "basic". This prompts the
following definition and notation.
Definition 6 : Let R be a fragment with root r. A nested fragment
edge chain is a sequence of fragment edges g^, . . . , gn
where the origin of g^ is r and for each i (1 < i < n) the
origin of gn * is the child (via an object edge) of the terminus
of g-j_i (which is a star node).
133
[addre:
tourist
langua
pname
proficiency
Figure A-l. Guide-Language-Proficiency Fragment.
Notation: Let R be a fragment with root r, let g^, g^,, . . . , gn be
an instance of R. I f o1 e 0^ and I/g ^ O j) = (0,,, F^) we
sometimes use I/g j(O j) to denote C^. More generally, i f o^,
. . . , o^ satisfy o^+j e i / g ^ ( O j ) / . . . / g . ( o ^ ) for 1 < i < k then
depending on the context, I/g 1(o1) / . . . / g k( 0|(;) will denote either the
fragment or the object portion of that fragment instance.
134
As in types, the active domain of a node in a fragment
corresponds to the objects residing at that node for a given
i nstance.
Definition 7 : Let R be a fragment with root r. Also, let Rq be the
type in R with root r, let f j , f ? f n be the fragment edges
of R with origin r, let Pi,P 2 »...»Pn be the termini of
f j , f ? , . . . , f n, and let Rk be the subtree of R with root p^.
Finally, let I=(J,F) be an instance of R. For each node q of R
the active domain of q in I, denoted actq( I ) , is the set of
objects as follows,
1. actq(J ), i f q is in Rg.
2. actq ( { I / f K(o) | O e J } ) , i f q is a descendent of Pk and
Rk is a type.
3. {L | I / f k(o) = (L,G) for some OeJ}, i f q = Pk and Rk is
not a type.
4. y a c tq( { I/f j<(o) | O eJ}), i f q is a proper descendant of
and Rk is not a type.
Fragments form the basis out of which the user may create IFO
schemas. A schema consists of one or more fragments which may be
connected via ISA edges. Recall that a free node in a fragment
represents objects whose structure and attributes are defined
elsewhere. In an IFO schema every free node has at least one ISA
135
edge connecting it to a fragment root which define the
characteristics of the objects residing in that set. The active
domain of a free node can thus be viewed as a subset of the active
domain of each of the primary node(s) at the terminus (termini) of
the connecting ISA edge(s).
To define IFO, schemas, the following discussion firs t
introduces the notion of an IFO graph. As will be shown, each valid
IFO schema is an IFO graph which satisfies specific constraints. An
IFO instance is then defined as a collection of fragment instances
which satisfy the inclusion dependencies implied by the ISA edges.
Definition 8 : An IFO graph is a directed graph S=(V,E) such that:
1. V is the disjoint union of Vp (printable nodes),
(abstract nodes), Vp (free nodes), V* (star nodes),
and Vx (cross nodes),
2. E is the disjoint union of Eq (object edges), EF
(fragment edges), and E$ (specialization ISA edges),
and
3. (V,Eq u Ep) is a forest of fragments.
Definition 9: In an IFO graph, a node is primary i f i t is the root
of some fragment in the forest of fragments (V, Eq u Ep).
136
Definition 10; An IFO schema is an IFO graph which satifies the
following constraints.
1. All directed paths of specialization edges (ISA edges)
originating at a node can be extended with
specialization edges to a common node.
2. (V.EgU Es) has no directed cycles.
3. The origin of each specialization edge is a free node.
4. The terminus of each specialization edge is a primary
node.
5. Each free node is the origin of at least one
specialization edge.
An instance of an IFO schema is a collection of database
objects together with a set of functions and dependencies.
Specifically, an instance is a collection of fragment instances such
that the inclusion dependencies are satisfied.
Definition 11: Let S be an IFO schema with fragments R^,R2 ...,R n.
Then a database instance of S is a function J from
• • »Rn suctl an i nstance of Rk, and
actq (J (Rk)) is a subset of actp(J(Rj)) for each edge
(q,p) e Es where q is in fragment Rk and p is in fragment
137
A . 1 . 2 . A d d it io n a l IFO C on cepts
Some additional concepts must be defined relative to the IFO
model in order to describe the family of query graphs. In
particular, the following discussion shall distinguish three
distinct types of fragment edges. These are local fragment edges,
nested fragment edges, and inherited fragment edges. A local
fragment edge is a fragment edge which originates at a primary
node. A nested fragment edge is one which originates at a non-
primary node. An inherited fragment edge is a virtual edge in an
IFO schema that does not explicitly exist but it is implied by the
ISA relationship. For example, consider a simple database for
maintaining a set of people, a subset of which will be distinguished
as guides. Each person will have a name and each guide w ill speak a
set of languages. The IFO schema component capturing this structure
is shown in Figure A-l. Since a guide is a person each guide will
have a name. Therefore we say there exists an inherited fragment
edge from the guide node to the (person) name node. Also, since
some people are guides the speaks-language attribute may be
inherited up the ISA edge to the person node. W e emphasize that
these inherited fragment edges are not actually part of the fragment
edge set of a schema but they will actually exist in query graphs.
138
Definition 12: Let S = (V,E) be a schema and let ueV. If u is a
primary node then the local fragment edges of u,
denoted E^p(u), is defined as the set of fragment edges
originating at u. I f u is a non-primary node then the
nested fragment edges of u, denoted ENp(u), is defined as
the set of fragment edges originating at u. Furthermore,
for an IFO schema eLF is the subset of fragment edges for
which the originating node is primary and ENp is the
subset of fragment edges for which the originating node is
non-primary.
Before defining the inherited fragment edges of a node, we
define the set of nodes from which that node may inherit fragment
edges as the ISA class.
Definition 13: Let S = (V,E) be an IFO schema. Then the ISA class
of a primary or free node u is the set of primary of free
nodes in the connected component of u in (V,ES).
Given an ISA class, a node is said to be in the range set of
that class i f it is connected to a node in the ISA class by means of
a local fragment edge. Therefore, i f the ISA class is viewed as a
single unit then the range set defines all nodes associated with the
ISA class via outgoing fragment edges.
139
Definition 14: Let S = (V,E) be a schema, and let IC be an ISA
class. Then the range set of IC is
{v | u e IC and (u,v) e E^p}.
Now, an inherited fragment edge is a virtual edge connecting a
given node to another node in the ISA range set class of that node.
Definition 15: Let S = (V,E) be a schema and let u he a primary or
free node. Then the inherited fragment edges of u,
denoted Ejp(u), is {(u,v)|v e range set of the ISA class
of u} - E^p. Relative to an IFO schema, Ejp denotes the
set of all inherited fragment edges in the schema.
The results of applying an inherited function (represented as
an inherited fragment edge) to an object is defined by applying the
corresponding local function. Of course, some of the functions will
result in null values. For example, i f one were to ask for the
1 anguages-spoken of a person who is not a guide, then the results
will be null (an undefined value).
Definition 16: Let I be a database instance of schema S = (V,E),
let(u, v) e Ejp, and let o e actu ( I ) . Then (u,v)(o)
is defined as (w,v)(o) where (w,v) e E^p.
140
A .1 . 3 . Query Component
The previous two sections described the IFO model which forms
the basis for representing the structural aspects of information in
a database. This section describes the query graph which is used
for extracting information from that database. The user creates
query graphs from IFO schemas by including fragments (possibly
including duplicates) and by adding inherited fragment components to
free or primary nodes.
The following exposition on query graphs will begin by
describing simple building blocks of query graphs and will proceed
through the description of the semantics of the query graphs. Query
fragments, the basic components of query graphs, closely correspond
to fragments in IFO schemas. Each query fragment is created by
copying a fragment and possibly adding inherited attributes with the
associated subcomponents. The ab ility to directly show (copies of)
inherited subcomponents represents a major distinction between
schema and query components. Also, the feature of allowing multiple
query fragments (all copied from the same fragment) captures the
notion that an object set may take on different roles in a query. A
forest of query fragments is called a (unrestricted) query graph. A
query graph describes the entire structure of the information the
user may wish to view. The user may also restrict the information
141
set by adding local node restrictions and by adding comparator edges
to a query graph.
A query fragment is created by copying (part of) a schema
fragment and extending it to directly show inherited structure and
attributes. An important observation about the relationship between
a schema and a query fragment is that inherited fragment edges which
are a virtual part of the schema become an explicit part of a query
fragment. In the formal definition below, the function QtoS records
the correspondence between the query fragment and its underlying
schema. Also, in this definition kind is used as a shorthand
notation for the type of a node or edge. For example,
i f v e V* then kind(v) = "star". Similarly i f (u,v) e Ejp then
kind((u,v)) = "inherited fragment".
Definition 17: A query fragment is a trip le (Q,S, QtoS) where
Q = (V^,E^) is a directed tree, S = (V^,E^) is an IFO
schema, and QtoS is a mapping from to V^. Furthermore the
trip le must satisfy the following conditions.
1. is the disjoint union of (abstract), vj? (free),
Vp (printable), (star), and (cross) nodes.
2. E^ is the disjoint union of Eq (object) and
Ep (fragment) edges where Ep is the disjoint union
of E^p (local fragment), E^F (nested fragment) and
Ejp (inherited fragment) edges.
142
3. Each node in Q corresponds (via QtoS) to a node in S such
that
a. either they are the same kinds of nodes or
b. the query node represents structure inheritance.
(v e kind (v) - kind (QtoS (v)) or
( i f v e VQ - Vp but Q to S(v) e Vp then
kind (v) = kind ( root-via-ISA (QtoS(v))))
4. Each edge in Q corresponds (via QtoS) to an edge in S such
that
a. either they are the same kinds of edges or
b. the object edge represents structure inheritance.
((u,v) e -» • kind ((u ,v )) = kind ((QtoS(u),
QtoS(u)))) or ( if(u ,v ) e Eq where u e vj U V^
but QtoS (u) e Vp then (root-via-ISA (OtoS(u)),
QtoS(v)) e Eg).
An instance of a query fragment is a relation whose columns
contain either atomic or complex objects. The domain of each column
is the domain of the corresponding object type in the underlying
schema.
Definition 18: Let (Q, S, QtoS) be a query fragment where
Q=(VQ, E°), S = (US, ES) , and QtoS: VQ -> VS.
143
Furthermore, let a^,a 2 * . . . , a n be variables correspond!’ng to
the nodes vi»v2 >***>vn 1n and let u^ =
QtoS ( Vi) (1 < i < n). Finally, let I be an instance of
S. Then the instance of the query fragment corresponding to
I (assuming an ordering v j , v2, . . . , vn) is a set of tuples
(a1, a2, an) such that
1. a. e act ( I)
2. functional relationships hold for non-nested fragment
edges (( v ^ V j) e E ^ eJf , = (v ., Vj) ( a . ) ) .
3. nested functional relationships hold for nested fragment
edges (for K - vj) e ENF* let 9i» 99* •••* 9k = ( vi * vj)
be the nested fragment edge chain of S which ends with
(v ., v .) . Also, for each p (1 < p < k) let v. be the
J P
origin of g^. Then a^ = 9 i(a.. / ^ ( a ^ ) / . . .
/ 9 k - i ( a1k_l V a k Ca1) .
4. object structures maintain tuple relationships ( if
( v . , v.) e e9, where v. is the kth child of a
* * J J
cross node v ., then a. = n^fa.))
I J K 1
5. object structures maintain set relationships
( i f (vi , Vj) e Eq, where Vj is the child of star node
vi# 3j e a .).
144
Just as fragments serve as the basic building blocks of an IFO
schema, query fragments represent the basic component of a query
graph. Each query fragment describes a request for a set of
entities of one type and associated information. A number of these
query fragments may be combined to create a query graph. A query
graph also incorporates into the graphics-based paradigm a
constraint mechanism for expressing basic types of restrictions.
Definition 19: A query graph is a tuple (0, S, QtoS, A, R, E }
where Q = (V, E) is a directed graph, S in an IFO schema,
QtoS is a mapping from the nodes in Q to the nodes in S, A is
a subset of the nodes of 0 called the active nodes, R is a
set of local restrictions, and Ec is a set of comparator
edge. Furthermore, the query graph must satisfy the
following constraints.
1. V is the disjoint union of Vp (printable), Vp(free),
(abstract), V* (s ta r), and Vx (cross) nodes.
2. E is the disjoint union of Eg (object) and Ep (fragment),
where Ep has a partition of Ejp, ENp, and E^F.
3. ((V, Eg U E p), S, QtoS) is a forest of query fragments.
4. Each comparator edge ((u , v) e Ec where u, v e V) has an
associated operator of type =, * , <, <, >, >, e or i .
5. R is a set of pairs (v,F) where v e V and F is a formula
with one free variable.
145
The query graph represents a request for some information. The
semantics of a query graph is defined as the cartesian product of
the query fragment instances and applying the nodal and comparator
edge restrictions.
Definition 20: Let (0, S, QtoS, A, R, E ) be a query graph with
query fragments QF^ QF2 , QFm. Let v l , v?, . . . , v'j1 be
an enumeration of the vertices of QF^ and let , v2, ...» vn
1 kl 1 k7 1 km
be the sequence v. . . . v ; vi . . . vi . . . v„ . . . v* . Also,
1 1 z Z m m
let a^ be a variable corresponding to v-j (1 < i < n).
Finally, let I be an instance of S and let QF.(I) denote the
J
instance of query fragment j (1 < j < m). Then the complete
table of the query graph on instance I is the set of
tuples (a^, a2» . . . a ) such that
1. (a1# a2, . . . , an) e QF^I) X QF2( I) X . . . X QFm ( I ) ,
2. the nodal restrictions are satisfied (F(a^), for
each (v ., F) e R), and
3. the comparator arc restrictions hold ( i f (v ., v.) e Fp
I J t
with associated operator op then a^ op a^).
The complete table described above typically includes
nonrelevant and/or redundant information. The active table (the
146
table corresponding to the active nodes in a query graph) is simply
a projection of the complete table.
Definition 21: Let I be a complete table of a query graph and let A
be the attributes of the complete table corresponding to the
set of active vertices. Then the active table is nA( I ) .
A.1.4. Data Formatting
Formats provide the basis for viewing the active table in a
number of ways. Basically, a format can be viewed as a grouping
mechanism on a relation. Formats and their instances correspond
closely to the V-Relations of [AB 84].
Definition 22: Let A = {Aj, A2, . . . , An} be a set of attributes. A
format F over A is defined as a pair (T ,f), where T = (V,E)
is a directed tree and f is a function which maps each
node in V to a set of attributes of A. Furthermore,
{ f ( v-j) I 1 £ i < n} is a partition of the attributes. That
is:
1. The attributes associated with nodes in the tree are
disjoint (for u,v e V, u * v -*• f(u) flf(v ) = <)>), and
147
2. The attributes associated with nodes in the tree cover the
set of attributes {let V = {vp v^, . . . , vm } ,
then f(v x) u f(v 2) u . . . u f ( v j = A), and
3. Every node has at least one attribute associated with
it (u e V + f(u) * $)
An instance of a format is a complex object. The root of the
tree represents the set of attributes which identify unique
entities. Each branch represents a set of attributes of the
*
entity. These attributes may in turn be recursively defined as any
format. Given an active table and a format over a set of
attributes, the instance of the format is defined as follows.
Definition 23: Let F = (T = (V,E)» f) be a format over attributes
Aj, and let I be an active table over A. Then the
corresponding instance of F is defined as Group ( I , F) where
Group ( I , F) =
1. I i f V is a singleton vertex, or
2. Group ^ATj af(r)=h Fl)»
Group (l)» Fj>)» •••
Group (wAT of ( r) =h ( I ) . Fn)) such that
h e 1If ( r ) where r is the root of T with child subtrees
Tj, T2, . . . , Tn, AT .j is the set of attributes over T^,
and Fi = (T ., f)}
Note that in this case, f ( r) is a key of Group ( I , F).
148
A.2. Summary of Objects in the System
The SNAP prototype was developed using the object-oriented
programming features of Zetalisp. Each object in the system has
some internal memory and i t responds to a set of messages. In
response to a message, an object may manipulate its internal memory
or invoke other objects. This section presents a very high level
abstraction of the major objects in the system representing windows,
nodes, or edges.
A.2.1. Operations on the General System
General system operations include those options that allow the
user to invoke SNAP and control the database to which SNAP will
communicate. The lis t of operations is as follows:
1. Open an existing database or create a new database.
2. Checkpoint the system (save the current configuration) or
resume from a previously checkpointed state.
3. Open a new schema window on the current database.
A .2 . 2 . O p e r a tio n s on Windows
The three basic types of SNAP windows correspond to the
activities of schema creation and browsing, query specification, and
results viewing. Figure A-2 displays the class structure repre
senting these three fundamental windows. In this structure lowest
level classes inherit operations from higher level classes. For
example, the entire interface for a schema window will include not
only the operations defined locally for the schema window class, but
will also include all operations defined for the graphics window and
SNAP window classes. The following discussion describes the
various classes starting from the most general class proceeding to
the more specific classes.
Window
Graphics
Answer
Schema Query
Figure A-2. Class Structure for Windows.
150
1. Operation on SNAP Windows
a. Collapse the window and make i t become a small icon
representati on.
b. Reposition and resize the window by specifying the upper
left-hand and lower right-hand corners of the new window
borders.
c. Move the window (maintaining the same size) to another
area on the screen.
d. Pop the window to the top of the stack of windows.
e. Push the window to the bottom of the stack of windows.
f. Repaint the window thus cleaning up any stray lines.
2. Operations on a Graphics Window
a. Move the portal to the le ft or right, or move it up or
down in order to focus on another area of the graphics
enterprise.
b. Resize the portal by zooming in or zoom out in order to
view components of the graph in more or less detail.
c. Show the entire enterprise with the area covered by the
current portal shaded in. Allow the user to specify the
new location of the portal by specifying uppoer left-hand
and lower right-hand corners of the portal.
151
d. Find a primary node by picking it from a pop-up menu, and
center the portal over the selected node.
e. Find a node (not necessarily a primary node) by typing in
the label of the node. After identifying the unique node
center the portal over i t .
f . Move a group of nodes by selection all nodes with regions
and by explicitly including or excluding specific nodes.
g. Move a named node (and all dependents) to a given
location.
h. Modify the inclusion and exclusion filte r s , or apply these
filte rs to produce a new display.
3. Operations on a Schema Window
a. Create an abstract, cross, star, printable, or free node
at a specified screen location.
b. Create a query window relative to the schema window and
make i t the current active query window.
c. Redisplay or highlight the current active query window.
d. Hide or redisplay all ISA edges between primary nodes (ISA
lattice ISA edges).
e. Hide or redisplay all ISA edges between non-primary and
primary nodes (range definition ISA edges).
152
f. Select a group of nodes (two or more) and display the
various ways in which the set of nodes are interconnected.
4. Operations on a Query Window
a. Create an answer window relative to the query window and
make it the current active answer window.
b. Redisplay or highlight the current active answer window.
c. Make the query window the current active query window of
the associated schema window.
d. Redisplay or highlight the associated schema window.
e. Process the entire query; send the answer and a default
format to the current answer window.
f. Process the current visible query; send the answer and a
default format to the current answer window.
5. Operations on an Answer Window
a. Make the answer window the current answer window of the
associated query window.
b. Redisplay or highlight the associated query window.
153
A .2 . 3 . O p e ra tio n on Nodes
The basic types of nodes, as shown in Figure A-3, are divided
into two classes; one for schema and one for query components.
Also, note that the primary free nodes inherit operations from both
the free and the primary classes.
Node
Schema
Query
Printable Cross Star Free Primary Printable Cross Star Free Primary
Primary Free Abstract
Primary Free Abstract
Figure A-3. Class Structure for Nodes.
154
1. Operations on SNAP Nodes
a. Delete the node.
b. Delete the node and all dependents.
c. Hide the node and all dependents.
d. Hide/Redisplay all dependent nodes within a given range.
e. Hide/Redisplay subnodes in a complex type within a given
range.
f. Hide/Redisplay subnodes/supernodes in an ISA lattice
within a given range.
g. Move the node to another location.
h. Move the node and all dependents to another location.
i . Relabel the node.
2. Operations on Schema Nodes
a. Link the node to another node. There are really two
options for this operation. Either the user is specifying
the fir s t node and entering the link phase, or the user is
specifying the second node and completing the link phase.
3. Operations on Primary Nodes
a. Find and flash all nodes representing subtypes.
155
b. Layout visible subnodes/supernodes in the primary ISA
la ttic e .
c. Include the fragment whose root is the given node into the
current active query window.
d. Move the entire primary ISA lattice containing the given
node to another location.
4. Operations on Free Nodes
a. Find and flash all nodes representing supertypes of the
given node.
b. Redisplay all out ISA edges. Add the supernodes to the
current active view i f they are not currently visible.
c. Reposition (reformat) visible out ISA edges so that the
ISA icon is close to halfway between the two connecting
nodes.
5. Operations on Query Nodes
a. Find and flash the associated schema node.
b. Add inherited attributes to the given free or abstract
node.
c. Add inherited structure to the given free node.
156
d. Activate or deactivate the node. Information associated
with the active nodes (shown with shaded icons) shall he
included in the answer when a query is processed.
e. Process the partial query in the query component which
contains the node.
f. Add or modify the constraint formula associated with the
node.
g. Link the node to another query node with a comparator
edge.
h. Reposition the comparator edge(s) connected to the node.
A.2.4. Operations on Edges
Edges are used to represent the relationships betwen schema
nodes or between query nodes. The basic edge class breakdown is
shown in Figure A-4.
1. Operations on Schema Edges
a. Delete the edge.
b. Delete the edge and the associated dependent subgraph.
157
2. Operations on ISA Edges
a. Hide the ISA edge.
b. Reposition the ISA edge by using the automatic formatter
which attempts to place the ISA icon roughly halway
between the connecting nodes.
3. Operations on Comparator Edges
a. Delete the comparator edge.
b. Modify the operator associated with the comparator edge.
c. Reposition the edge by using the same method as the
automatic ISA edge reformatter.
Edge
Schema
Fragment Surrogate Object ISA
Query
Fragment Surrogate Object Comparator Fragment Surrogate Object ISA Fragment Surrogate Object Comparator
Figure A-3. Class Structure for Edges.
158
GLOSSARY
active domain - The active domain of a node in a schema or query
graph refers to the set of objects residing within the node
in the current context.
active table - The active table is a subset of the query table. The
active table displays specified information to the user
relative to a given query.
DBA - The database administrator (DBA) is the person responsible for
general matters of the database. These responsibilities are
analogous to those of a system manager of a computer system.
DBM S - A database management system (DRMS) is the software which
allows users to access or modify an organized information
bank.
domain - A domain is a collection of objects.
edge - An edge (also called an arc) connects two nodes together. An
edge conveys a close relationship between two nodes. The
various types of edges in SNAP include object, fragment
(functional or surrogate), ISA, and comparator. In SNAP an
edge is displayed as two line segments connecting two nodes
with an icon between them.
format - A format is a specification of the shape of an information
set. In SNAP formats may be represented as complex IFO
types. Typically a format is shown using a bucket notation
in SNAP answer windows.
fragment - Fragments are the tool used to represent object sets and
functional relationships between the object sets. Fragments
serve as the basic building blocks of an IFO schema.
fragment instance - A fragment instance is a primary object set
together with a number of functions which map those objects
to other objects in the system.
graph - A graph is a collection of nodes and edges. In SNAP graphs
are used to represent structural information and to represent
queries on a database.
159
IFO - IFO is an object-oriented data model introduced by S.
Abiteboul and R. Hull [AH 86j . IFO has several features
which make i t especially well suited for a graphics-based
interfaces such as SNAP.
inclusion dependency - An inclusion dependency between one object
set and another simply states that all elements of the firs t
set must be included in the second. In IFO an ISA edge
represents an inclusion dependency between the associated
active domains of the schema nodes.
ISA - An ISA edge is the IFO components which conveys the meaning
that an object associated with a free node is an object of
the type implied by the adjoining node. For example, a
student is a person. In IFO an ISA edge always originates at
a free node and terminates at a primary node.
object instance - An object (instance) is an instance of some
type. (An object is an element of the domain associated with
a type.)
query fragment - A query fragment is a component of a query graph.
A query fragment is derived from an IFO fragment in a
schema. However, in a query fragment inherited fragment,
components and structures may be directly displayed.
query graph - A query graph is the tool used to specify a request
for information from a database. A query graph is formed by
including a number of query fragments and possibly connecting
them with comparator edges.
schema - A schema is the component of a database system which
describes the structure of the information. In IFO a schema
is a graph which satisfies certain constraints.
type - A type is a directed tree which describes the structure of an
object. An atomic type may be printable, abstract, or
free. A complex type is built up from atomic types by using
cross and star nodes which correspond to cartesian product
and grouping operations.
160
Abstract (if available)
Linked assets
University of Southern California Dissertations and Theses
Conceptually similar
PDF
A system for object-based conceptual schema evolution
PDF
Language features for a static data flow environment
PDF
A hierarchical knowledge based system for airplane recognition
PDF
Properties of functional dependency data bases
PDF
An integrated systems approach for software project management
PDF
A learning-based object-oriented framework for conceptual database evolution
PDF
A federated architecture for database systems
PDF
Dynamic load balancing for concurrent Lisp execution on a multicomputer system
PDF
Optimal testing algorithms for symmetric coherent systems
PDF
Softman: An environment supporting the engineering and reverse engineering of large scale software systems
PDF
Occamflow: Programming a multiprocessor system in a high-level data-flow language
PDF
Management of interface design activities
PDF
A distributed access control mechanism for managing intellectual property rights in large-scale information systems
PDF
Unambiguity and subset-strict interpretations
PDF
User-assisted design and evolution of physical databases
PDF
An investigation of the effects of output variability and output bandwidth on user performance in an interactive computer system
PDF
Machine skill acquisiton based on self-discovery
PDF
Detecting architectural mismatches during systems composition
PDF
Reliability analysis and optimization in the design of distributed systems
PDF
Software object management in heterogeneous, autonomous environments: A hypertext approach
Asset Metadata
Creator
Bryce, Daniel J.
(author)
Core Title
SNAP: A graphics-based schema management system
Degree
Doctor of Philosophy
Degree Program
Computer Science
Publisher
University of Southern California
(original),
University of Southern California. Libraries
(digital)
Tag
Computer Science,OAI-PMH Harvest
Language
English
Contributor
Digitized by ProQuest
(provenance)
Permanent Link (DOI)
https://doi.org/10.25549/usctheses-c17-71192
Unique identifier
UC11348764
Identifier
DP22762.pdf (filename),usctheses-c17-71192 (legacy record id)
Legacy Identifier
DP22762.pdf
Dmrecord
71192
Document Type
Dissertation
Rights
Bryce, Daniel J.
Type
texts
Source
University of Southern California
(contributing entity),
University of Southern California Dissertations and Theses
(collection)
Access Conditions
The author retains rights to his/her dissertation, thesis or other graduate work according to U.S. copyright law. Electronic access is being provided by the USC Libraries in agreement with the au...
Repository Name
University of Southern California Digital Library
Repository Location
USC Digital Library, University of Southern California, University Park Campus, Los Angeles, California 90089, USA