Skip to main content

Full text of "A Graphical Database Interface for a Mulitmedia [i.e. Multimedia] DBMS"

See other formats


NPSCS-91-013 



NAVAL POSTGRADUATE SCHOOL 

Monterey, California 




A Graphical Database Interface 
for a Mulitmedia DBMS 

Daniel A. Keim 
Vincent Y. Lum 

June 1991 

Approved for public release; distribution is unlimited. 
Prepared for; 

Naval Ocean Systems Center 
San Diego, CA 92152 



FedDocs 
D 208.14/2 
NPS-CS-91-013 




NAVAL POSTGRADUATE SCHOOL 
Monterey, California 



Rear Admiral R. W. West, Jr. 
Superintendent 



Harrison Shull 
Provost 



This report was prepared for the Naval Ocean Systems Center and funded by the Naval Post- 
graduate School. 

Reproduction of all or part of this report is authorized. 



UNCLASSIFffiD 



ISECURITY CLASSIFICATION OF THIS PAGE 



pUDLEY KNOX LIBRAPV 



REPORT DOCUMENTATION PAGE 



'7 CA P:-^ 



4 ^ ^", 0 ^ 



la. REPORT SECURITY CLASSIFICATION UNCLASSIFIED 



1b. RESTRICTIVE MARKINGS 



i 2a SECURITY CLASSIFICATION AUTHORITY 



I 2b. DECLASSIFICATION/DOWNGRADING SCHEDULE 



3. DISTRIBUTION/AVAILABILITY OF REPORT 
Approved for public release; 
distribution is unlimited 



4. PERFORMING ORGANIZATION REPORT NUMBER(S) 

NPSCS-91 -013 



5. MONITORING ORGANIZATION REPORT NUMBER(S) 



6a. NAME OF PERFORMING ORGANIZATION 
Computer Science Deptariment 
Naval Postgraduate School 



6b. OFFICE SYMBOL 
(if applicable) 

cs 



7a. NAME OF MONITORING ORGANIZATION 

Naval Ocean Systems Center 



6c. ADDRESS (City, State, and ZIP Code) 

Monterey, CA 93943 



7b. ADDRESS (City, State, and ZIP Code) 

San Diego, CA 92152 



8a. NAME OF FUNDING/SPONSORING 
ORGANIZATION 

Naval Postgraduate School 



8b. OFFICE SYMBOL 
(if applicable) 



9. PROCUREMENT INSTRUMENT IDENTIFICATION NUMBER 

OM&N Direct Funding 



8c. ADDRESS (City, State, and ZIP Code) 



Monterey, CA 93943 



10. SOURCE OF FUNDING NUMBERS 



PROGRAM 
ELEMENT NO. 



PROJECT 

NO. 



TASK 

NO. 



WORK UNIT 
ACCESSION NO. 



1 1 . TITLE (Include Security Classification) 

A Graphical Database Interface for a Multimedia DBMS 



12. PERSONAL AUTHOR(S) 



Daniel A. Keim, Vincent Y. Lum 



13a. TYPE OF REPORT 
Progress 



13b. TIME COVERED 
from Feb. 91 TO Mai 91 



14. DATE OF REPORT (Year, Month, Day) 
June 1991 



15. PAGE COUNT 
26 



16. SUPPLEMENTARY NOTATION 



17. COSATI CODES 


FIELD 


GROUP 


SUB-GROUP 















1 8. SUBJECT TERMS (Continue on reverse if necessary and identify by block number) 

Multimedia Database Systems, Information Retrieval, 

Graphical User Interface, Natural Language Interfaces 



19. ABSTRACT (Continue on reverse if necessary and identify by block number) 

In this paper we describe the GRAphical Database Interface (GRADI) of a Multimedia Database Manage- 
ment System. As generally true, the user interface is an important part of a system which strongly determines 
the effectiveness of using it. In order to find a natural way of interacting with the MDBMS system we ex- 
amined the query specification process used by humans. We found that incremental query specification, nat- 
ural ways of expressing joins and an additional ‘all ’-operator are important to improve the query 
specification process making it considerably easier to use in comparison with query languages like SQL. The 
Graphical Database Interface described in this paper incorporates the mentioned capabilities as part of the 
MDBMS system. We think that the principles are of general use not only for multimedia systems but for any 
database query interface. 



20. DISTRIBUTION/AVAILABILITY OF ABSTRACT 
[x] UNCUSSIFIED/UNLIMITED □ SAME AS RPT. □ OTIC USERS 


21. ABSTRACT SECURITY CLASSIFICATION 
UNCLASSIFIED 


22a. NAME OF RESPONSIBLE INDIVIDUAL 
Vincent Y. Lum 


22b. TELEPHONE //nc/ude Area Code; 1 
(408)646-26« | 


1 22c. OFFICE SYMBOL 
1 CS/Lum 



3D FORM 1473, 84 MAR 



83 APR edition may be used until exhausted 
All other editions are obsolete 



SECURITY CLASSIFICATION OF THIS PAGE 



UNCLASSIFIED 



A Graphical Database Interface 
for a Multimedia DBMS 



Daniel A. Keim^ Vincent Lum 

Computer Science Department ^ 

Naval Postgraduate School 
Monterey, CA 93943 

e-mail: keim, lum@cs.nps.navy.mil 

Abstract 

In this paper we describe the GRAphical Database Interface (GRADI) of a 
Multimedia Database Management System. As generally true, the user inter- 
face is an important part of a system which strongly determines the effective- 
ness of using it. In order to find a natural way of interacting with the MDBMS 
system we examined the query specification process used by humans. We 
found that incremental query specification, natural ways of expressing joins 
and an additional ‘all’-operator are important to improve the query specifica- 
tion process making it considerably easier to use in comparison with query 
languages like SQL. The Graphical Database Interface described in this paper 
incorporates the mentioned capabilities as part of the MDBMS system. We 
think that the principles are of general use not only for multimedia systems but 
for any database query interface. 

Keywords: Graphical User Interfaces, Multimedia Database Systems, 

Natural -Language Interfaces, Information Retrieval 



1. This work was performed while the author was with the Multimedia Database Project at the Naval Postgraduate 
School. The stay was sponsored by the German Scholarship Foundation. The author’s permanent address is Institut 
fiir Informatik, Universitat Milnchen, Theresienstr. 39, 8000 Miinchen 2, West Germany. 

2. This research was supported in part by NOSC, Direct Funding and the German Scholarship Foundation. 



- 2 - 



1. Introduction 

The GRAphical Database Interface (GRADI) is designed as an integral part of the Multimedia 
Database Management System (MDBMS). It is designed to support a natural retrieval process of 
conventional and media data. The MDBMS system controls the management of multimedia data, 
which include image and sound among others, in addition to supporting conventional databases. 
The manipulation of multimedia data is not straightforward as in conventional databases. One main 
problem is the retrieval of multimedia data from the database with the need to match the contents 
of multimedia data to a user query. In order to achieve a content based retrieval in our approach, 
we use natural language captions allowing the user to describe the contents of multimedia data. In 
a similar manner, users will specify their queries on multimedia data contents in natural language 
form. One major problem with this approach is that it is generally the case that the description of 
a multimedia data does not exactly match the description of a user query. The reason is that it is 
difficult for different users or even the same user at different times to describe the same thing iden- 
tically because they can use synonyms or generalize/specialize categories belonging to the domain 
of interest and so on. Hence, in an earlier paper we proposed an intelligent approach to approximate 
matching by integrating object-oriented and natural language understanding techniques 
[KEIM91]. In the algorithms used for the intelligent matching only the retrieval of multimedia data 
by queries on the media part are considered. However as generally true, a query involves not only 
the media part but also the related formatted data. Queries may be composed of arbitrary combina- 
tions of conditions on the media and formatted data. 

It is important to achieve an easy specification of complex queries composed of many condi- 
tions. The procedure for the specification strongly determines the effectiveness in using the system. 
Our goal in developing GRADI was to provide a natural way of interacting with the MDBMS sys- 
tem. We examined the query specification process used by humans and found that in order to for- 
mulate complex queries a user partitions it into smaller pieces and put them together in a later stage. 
This behavior is reflected in the principle of incremental query specification which is supported by 
GRADI. In addition, we observed that, for a given database, the joins necessary to specify most of 
the queries correspond directly to natural language expressions. This leads to the principle of nat- 
ural expression of joins, also supported by GRADI. Furthermore, we introduce an ‘all’-operator 
making the query specification in many cases considerably easier. 

Over the last two decades several research projects have been conducted in the area of user in- 
terfaces for (multimedia) database systems. The first approach for a graphical database interface is 
the well-known OBE interface [ZL0077]. Most recent research in the area of user interfaces fo- 
cuses on the entity-relationship [WONG82, FOGG84, ROGE88] or the more complex semantic 
and object-oriented data model [KING84, GOLD85, BRYC86, AGRA90], allowing queries to be 
directly specified within the schema. In contrast, we use an extension of the relational model to 



-3- 



handle and manipulate the media data. In order to allow an easy query specification we provide a 
graphical user interface which incorporates the capabilities as mentioned above, dififering in many 
ways from OBE. 

Another approach to achieve a natural query specification was chosen by researchers in the ar- 
tificial intelligence area. Much effort went in building natural language understanding systems ca- 
pable of understanding queries expressed in natural language. An overview over the research in 
this area can be found in [ALLE87] and a good example for the current state of the art is the TEAM 
system [GROZ87]. Because of the problems related to natural language understanding hardly any 
of the systems is actually used for retrieval in databases. In GRADl we are not trying to understand 
natural language. We argue that in order to express a query on formatted data in most cases natural 
language understanding is not necessary. The user can easily choose the necessary tables and at- 
tributes from lists, type the desired values and combine simple conditions into more complex ones. 
To our knowledge, none of the natural language interfaces to database systems can handle complex 
combinations of conditions because of the semantic problems related to multiple sentences. Fur- 
thermore, a graphical user interface like GRADl is generally applicable and less complicated and 
time-consuming than natural language understanding. 

The paper is organized as follows: Section 2 gives a short overview of the Multimedia Database 
Management System (MDBMS). Section 3 outlines important features of GRADl and gives exam- 
ples for query specifications. Section 4 describes the other database operations (schema definition, 
insert, update and delete) and Section 5 gives concluding remarks and a summary. 

2. Overview of the Multimedia DBMS Prototype 

As mentioned before, multimedia data, in the broadest sense, consists of unformatted data such 
as text, image, voice, signals, etc. in addition to alphanumeric data. A multimedia database man- 
agement system is a system that manages all multimedia data and provide mechanisms to handle 
concurrency, consistency, and recovery in addition to providing a query language and query pro- 
cessing. In the following, we outline object model, architecture and main components of our Mul- 
timedia Database Management System (MDBMS). 

2.1 Object Model 

Despite differences in data model and implementation, all research projects on MDBMS have 
decided to organize multimedia data using the abstract data type (ADT) concept. This is generally 
accepted as the adequate approach. However, none of the projects have addressed the problem of 
content retrieval of multimedia data. 

The fundamental difficulty in handling multimedia data is intrinsically tied to a very rich se- 
mantics. To answer queries posed on media objects a person must draw from a very rich experience 



- 4 - 



IMAGE 



c 

c 

c 



Registration Data (Height, Width, Depth, Colormap 



Raw Data (Matrix of Pixels in Raster/Bitmap Format) 



Description Data (abstracted content of image using text) 



ifiJ 

3 



Figure 1; Example for the Multimedia Data Format 



encountered in life to derive a good answer. One must have a sophisticated technique to analyze 
the contents of the images to get the semantics of different things in the images. Technology today 
is not advanced enough to expect systems to have this kind of capability to answer multimedia que- 
ries. However, we can abstract the contents of multimedia data into text and use the text description 
equivalent of the original multimedia data to match the user request or query. This is the principle 
we used in designing a MDBMS to handle multimedia data for different applications. Figure 1 
shows the format of a multimedia data which consists of the registration, raw and description data. 

Raw data is the bit string representation of the image, sound, signal, etc. obtained from scan- 
ning or digitizing the original multimedia data. Registration data generally enhances the informa- 
tion about raw data and is not redundant. The contents of a multimedia data is described by 
description data. We assume that users will supply the description data for multimedia data in nat- 
ural language form. In future systems however, the description could be automatically derived by 
the computer. 



2.2 Architecture 

The overall architecture of the MDBMS system is shown in figure 2. The components break 
down into GRAphical Database Interface (GRADI), query processor, data access and intelligent 
retrieval subsystem. The query processor accepts queries from GRADI and executes them by call- 
ing the other components. When a new description for a multimedia data is entered, for example, 
the query processor calls the parser. The parser uses the dictionary to produce first-order predicates 
and return them to the query processor. The query processor then hands the predicates over to the 
description manager which then links the description to its multimedia data. 

When the query processor receives a query the first task is to decompose the query into sub- 
queries affecting only conventional or media part. The conventional subquery is passed directly to 
the conventional data manager without modifications. For the text description, the query processor 
calls the natural language parser to obtain the equivalent query predicates. The predicates are then 
handed to the matcher. The matcher tries to match the query with the qualified multimedia data by 



- 5 - 



fielatbns 

DBMS 



Graphical Database^ 
Interface ) 




(^gsr) 




^ ^ Sound ^ tnij^e^ 
y y^Managary y^Managay 











Domain 

Knowledge 




Dictionary 



Data Access Subsystem Intelligent Retrieval Subsystem 

Figure 2: Architecture of the MDBMS System 



comparing the predicates of the query with that of the stored multimedia data. The matcher does 
this by calling the description manager and using domain knowledge. As the solution to the natural 
language part of a query, the query processor receives links to the qualified multimedia data. After 
combining them with the results of the conventional subquery the final results are retrieved by the 
Data Access Subsystem. 



2.3 Parser 

In order to accomplish the goal of content retrieval of multimedia data, full understanding of 
natural language is not necessary. However, a restricted interpretation is necessary which is done 
by the parser component using the application dependent dictionary as a semantic basis. The dic- 
tionary or lexicon is necessary for parsing and gives each possible natural language word its se- 
mantic: its part of speech, its grammatical form and the form of literals needed to represent it. 

The parser automatically partitions the text description into subject, verb and object compo- 
nents and translates them into a set of predicates called meaning list. The imprecision and ambigu- 
ity of the natural language descriptions is reduced considerably by transforming them into a set of 
predicates in first-order predicate calculus. These predicates state facts about the real world entities 
involved with multimedia data like their properties and relationships. Important features of the 
parser are supercaptions, a generalization of captions, and frames for stereotypical actions, allow- 
ing a set of predicates to be derived from terms in the description. 

Our current implementation of the parser uses augmented-transition network parsing and inter- 
pretation routines. It is implemented in Quintus Prolog and running on a SUN SPARC workstation. 
The details of the parser are beyond the scope of this paper and are given in [DULL90, ROWE91]. 



- 6 - 



2.4 Matcher 

The major problem with content retrieval by natural language descriptions is that generally the 
description of a multimedia data does not exactly match the description of a user query since the 
same media object may be described differently. To solve the problem the matcher provides an ap- 
proximate matching algorithm using domain knowledge organized as object hierarchies. The 
matcher searches in the noun and verb generalization hierarchies of the object classes and assigns 
weights depending on the distance in the object hierarchy. Then the weights for single component 
groups (subject noun, verb and object noun phrases) are combined using appropriate weighting fac- 
tors as received from the user. Finally, the multimedia data with combined weight exceeding a 
threshold value set by the user will be retrieved. 

A prototype of MDBMS has been implemented at the Naval Postgraduate School [MEYE88, 
LUM89, HOLT90, PEI90]. In this paper, we focus on the interaction technique used in GRADI. 

3. Query Specification in GRADI 

The goal of a graphical user interface is to support the query specification process allowing the 
user to efficiently use the database system. It should allow inexperienced users to retrieve data from 
the database without having to know a specific query language. In today’s database management 
systems the user is forced to think in terms of data model and query language, differing a lot from 
his way of thinking. Often a user can express a query easily in natural language, but has difficulties 
to express it in some given query language. 

Most queries involve both media and formatted data. For the media part of the query we use 
our intelligent matching algorithm which is directly processing natural language captions. For con- 
ditions on formatted data, natural language expressions are mostly too imprecise to be directly pro- 
cessed. We try to overcome this problem by providing a graphical user interface supporting natural 
query specification. 

The data model adopted in our system is an extended relational model. Despite some draw- 
backs the relational model has great advantages; It is well known, widely used and has a firm the- 
oretical basis. For our purpose, we extend the relational model to capture media datatypes and, as 
shown below, we also extend the query language to allow the manipulation of media data and fa- 
cilitate the query specification process. 

Before describing GRADI in more detail, we first outline ways to achieve a natural query spec- 
ification process. 

3.1 Towards a Natural Query Specification 

Usually, every user can describe a query (or at least the desired result) easily in natural lan- 
guage. Unfortunately, natural language expressions representing a query are imprecise and difficult 



- 7 - 



to automatically translate into a formal query language to be understood by a database management 
system. We argue that the gap between the user’s way of expressing a query in natural language 
and database manipulation languages like SQL can be improved considerably. 

When comparing the user’s natural language (NL) expression for a query with corresponding 
SQL statements the first difficulty is that the table and attribute names do not exactly match. In a 
graphical user interface this problem is easy to overcome. All table and attribute names can be pre- 
sented to the user who simply selects the desired ones using a pointing device (e.g. mouse). 

Another difficulty is related to joins between tables. Mostly the join condition is hidden in the 
user’s NL expression. In examining a large number of queries expressed in natural language as well 
as SQL we found that, in most cases, the join condition directly corresponds to some specific NL 
expressions. Additionally, the number of joins used in most of the queries was small compared to 
the number of possible joins. This can be explained by two facts. First, the number of semantically 
meaningful joins is restricted and second, some of the most frequently used joins are already in- 
tended at the design time of the database. In order to provide a natural way of expressing joins, in 
our system we allow database designer and user to define and name joins prior to its actual use. A 
predefined join can involve more than two tables (e.g. two tables are joined by means of a third 
table) thereby providing a simple way of expressing m:n relationships. Once defined and named, 
all predefined joins can be used to specify a query. Predefined joins differ from views: First, the 
result of a predefined join is not a table as in the case of a view but a specific connection between 
tables. Second, predefined joins allow connections between different levels in nested queries and 
even recursive joins can be expressed. Examples are given in the next section. 

Another thing we learned in examining the process of query specification is the handling of 
complex queries. Given a complex data retrieval task the user partitions it into smaller subtasks 
which are easier to handle. Starting with the clear parts of the query the user deals with all parts 
and combines the results into the final solution. In our system we support this way of handling com- 
plex queries by an incremental query specification to be described in the next section. 

Finally, we observed that a special category of queries is easy to express in NL but rather com- 
plicated in a formal query language. Additional operators, closely related to corresponding NL ex- 
pressions, allow an easier and clearer query specification. Considering for example a query like 
‘Select the name of ships which carry all weapons of the category surface-to-air!’ , we found that 
a special ‘all’ operator would greatly enhance the readability and understandability of the SQL-like 
query making it similar to the user’s NL expression. For the example, we presume to have the ta- 
bles ship, weapon, shipjveapon and a predefined join named carries expressing the m:n relation- 
ship between ships and weapons. 



- 8 - 



Example 1: select s_name from ship 

where ship carries weapon 

and w_nr = all (select w_nr from weapon 

where category = ‘surface-to-air’) 



A SQL statement expressing the same query without the ‘all’-operator is rather complicated. 
Two possibilities are: 



3.2 Description of the Query Specification 

In this section, we will describe GRADI in more detail by presenting several examples. We will 
show the main features of GRADI especially those which are different from other graphical data- 
base interfaces. We start with a general description of the steps used in the retrieval process. 

When starting the MDBMS system the user will be automatically connected to GRADI and the 
first step is to select the desired database. Then the user gets the system menu providing the main 
database manipulation functions: insert, delete, update or retrieve. When selecting retrieval, the 
user gets the query specification window and his first step is to select the tables to be used in the 
query. For each selected table a list with all attributes will be displayed in a separate window and 
all predefined connections involving at least one of the selected tables will appear in the Connec- 
tions window. To specify the result list (projection) the user has to move the desired attributes to 
the Result List. Now only the conditions need to be specified. Using connections, attributes of the 
selected tables and operators provided by the Tool Box, the query can easily be built using the 
mouse. In the Query Representation window the query is displayed graphically. Each part of the 
query is represented by a small box, simple conditions by a single, subqueries by a double box, and 
the connection lines are labeled with the kind of connection used. An advantage is that every part 
of the query can be addressed for edit or delete at any time during the query specification process. 

Predefined Joins 

A special feature of GRADI are predefined joins. Predefined joins can be defined at design time 
of the database by the database designer. Having the necessary connections between tables in mind, 
the database designer tunes the database that joins can be executed efficiently. All semantically 
meaningful joins can already be defined at design time. However, if other joins are needed later, 
the user can define them at any time. 



select s_name from ship 

where ((select w_nr from ship_weapon A 



where ship.w_nr = A.w_nr) 
contains 

(select w_nr from weapon 
where category = ‘surface-to-air’) ) 



select s_name from ship 
where not exists 

(select * from ship_weapon B 

where B.w_nr in (select w_iu from weapon 

where category = ‘surface-to-air’)) 
and not exists 

(select * from ship_weapon C 
where C. s_nr = B.s_nr 

and C.w_nr = B.W_m) ) 



-9- 



Let us consider a sample database with the following tables: 
mission (m_id, mjiame, direction, goal, task) 
navyjbase (basejd, location, size) 

officer (ojd, ojiame, address, salary, commander Jd, shipjir, ojmage) 
ship (s_nr, sjiame, class, yrjjuilt, capjd, missionjd, basejd, sjmage) 
ship_weapon (s_nr, w_nr, quantity) 
weapon (w_nr, wjiame, category, type, range, wjmage) 

Only few of the possible joins between these tables are semantically meaningful; e.g. the only 
meaningful equijoin between ship and officer is ship. capjd = offcer.ojd. Most other equijoins 
like ship.s_name = officer.address or ship.sjir = officer.ojd are senseless and will never be 
used. 

P*redefined joins allow an easier specification of complex queries. The user does not need to 
think about the attributes and conditions necessary to join tables, he simply chooses the desired one 
out of the predefined joins in the Connections window. Predefined joins can involve more than two 
tables, e.g. the following SQL statement expresses a three way join between ship and weapon: 

Example 2: select s_name, w_name from ship, ship_weapon, weapon 

where ship.s_nr = ship_weapon.s_nr 

and ship_weapon.w_nr = weapon.w_nr 

To expressed the join conditions of the same query in GRADI, only one step is necessary. After 
selecting tables and attributes the predefined join ship carries weapon has to be selected. The re- 
sult as displayed in the Query Representation window is shown in figure 3. 




Figure 3: Example for a predefined join 

Predefined joins can even be used to express recursive queries, e.g. the one-level recursive que- 
ry 'Select the name of each officer together with the name of his immediate commander!’ can be 
easily specified using a predefined join. The user could specify the query as follows: First he has 
to select the officer table. Since he deals with two instances of this table he has to select it twice 
resulting in the officerl and officer! window. The last step is to select the predefined join officer 
isjcommanderjof officer. The whole query is shown in figure 4. 



- 10 - 



Two more things about predefined joins need to be mentioned: First, any kind of join (not only 
equijoins) may be predefined and used in the same way as equijoins. Second, it is allowed to pre- 
define identical joins with different names. This is useful to allow an easy identification of the re- 
quired predefined join since the same query can be expressed differently. A simple example is 
ship carries weapon and weapon isjcarriedjby ship. 

‘All ’-Operator 

As mentioned before we introduced an additional ‘all’-operator to make the specification of a 
special class of queries easier. The use of the ‘all’ -operator in GRADI is similar to other relational 
operators, e.g ‘exists’ or ‘in’. The user specifies it by selecting an attribute, an operator (=, >, <, >, 
<) and a double box representing a (sub-)query or a table. The semantics of the ‘all’-operator will 
be given in section 3.5. 

Incremental Query Specification 

To support incremental query specification we allow the user to start with any part of the query; 
e.g. to specify the query example 1 (see page 7) the user can start with the subquery weapons of 
category ‘surface-to-air’ and then continue with the main part of the query without specifying the 
connection between these two parts. At a later stage, the user may combine the separate parts. 

As an additional feature, we provide an option to save and reload any part of a query for later 
use. If the user needs part of the query later for other queries he may save the desired parts by se- 
lecting the corresponding items in the Query Representation window and assigning a name to 
them. Later he can reload the desired parts when working on a different query and integrate it in 
there. Furthermore, to enhance the clarity of display parts of a query can be grouped together and 
displayed as one box (zoom in). If the user wants to see the query in full detail at a later stage he 
can use the zoom out option. 

Tool Box 

The Tool Box allows fast access to all functions supported by the system. The functions are 
divided in five groups: logical operators and basic elements (AND, OR, Condition, Subquery), 
comparison operators (=,>,<,>, <), nesting operators (Exists, not Exists, IN, not IN, ALL), set 
operators (U, O, C, 3) and aggregate operators (AVG, SUM, MAX, MIN, COUNT). The se- 
mantics of most operators is the same as in SQL. The additional 'a//’ -operator has already been 
introduced (see above). Condition and Subquery options are necessary for the incremental query 
specification process. Using these options the user is able to continue the query specification with 
a different part of the query. When selecting Condition the user gets a new condition box and in 
the case of selecting the Subquery option he gets a new double box for a new subquery. 



- 11 - 



Media Description Editor 

Another important part of our system is the way of specifying the natural language description 
part of a query necessary when media data are involved. If the user selects a media attribute in the 
specification of the condition, automatically a special Media Description Editor will be displayed 
in a separate window where the media description can be specified. The description editor has spe- 
cial features to support the intelligent matching process mentioned above. When selecting the 
'Check' button the entered description is instantly sent to the parser. The parser tries to check and 
interpret it and, in case of an error, gives back the error message. The 'Hierarchy' button supports 
the user in finding the right description. For a selected word or phrase (highlighted) it presents the 
corresponding part of the object-oriented domain knowledge base thereby providing hints for a bet- 
ter description. With the 'Weight' button the user is able to assign weighting factors to the different 
component groups of a query. As mentioned before, the weighting factors are used to combine the 
weights of single groups. If the user does not provide weighting factors, an equal factor is assigned 
to all component groups. When selecting the 'Done' button the description is automatically 
checked (like in case of the 'Check' button) and the Media Description Editor disappears. If the 
user want to edit the description at a later stage he has to select the corresponding box in the Query 
Representation window and push the 'Edit' button in there. 

An example for the description 'An aircraft carrier is operating in the Mediterranean. Planes 
are in operation over the ship.’ is shown in figure 5. 

A Larger Example 

To further explain the query specification process let us walk through a more complex example: 
'Select the name, basejd and image of ships which can carry all weapons of the 
category surface-to-air and where the image shows "An aircraft carrier is operating in the 
Mediterranean. Planes are in operation over the ship.” ’. 

If a user wants to specify the query he might want to start with an easy part, e.g. 'weapons of 
the category surface-to-air’ . To specify this part the user first selects Subquery in the Tool Box pro- 



Media Description Editor'! 

An aircraft carrier is operating in the 
Mediterranean. Planes are in operation 
over the ship. 






Figure 5: Media Description Editor 



- 12 - 



viding him a second double box for the subquery. Then he selects weapon in the Tables window. 
As a result he gets all attributes of the weapon’s table in a separate window and by clicking to w_nr 
he selects the desired attribute. The next step is to specify the condition. By clicking to Cond in the 
Tool Box he gets an empty condition box in the Query Representation window and by clicking to 
the attribute category in the weapon’s window, '=’ in the Tool Box and typing in surface-to-air he 
fills the box with the actual condition. 

As the next part the user might want to specify the image description condition ‘image shows 
“An aircraft carrier is operating in the Mediterranean. Planes are in operation over the ship.” ’. 
The specification process for this part is similar to the specification of the first part. The user selects 
the ship table and after getting a new condition box he selects the attribute sjmage from the ship 
window. Because sjmage is a media attribute, the system automatically provides the special Me- 
dia Description Editor window. In this window the user can type the natural language description 
for the image, in our example “An aircraft carrier is operating in the Mediterranean. Planes are 
in operation over the ship.” . When selecting the 'Done' button the description will directly be in- 
terpreted by the parser to get the equivalent predicates. 

The last step is to specify the main part of the query and to compose the parts into the final re- 
sult. Starting with the beginning of the query (‘Select name, basejd and image') the user moves 
the attributes sjiame, basejd and sjmage to the Result List window. By selecting Cond from 
Tool Box and ship carries weapon from the connections window the user specifies the join condi- 
tion. Now as the last part of the query the user has to specify the all condition. This can be accom- 
plished by getting a new condition box, clicking to w_nr in the weapons window, '=' and ‘alV in 
the Tool Box and the double box representing the subquery ‘weapons of the category surface-to- 
air’ in the Query Representation window. The last step is to combine the conditions into the final 
result. This is done by selecting the conditions and the logical operator AND from the Tool Box. 
In Figure 6 the final result of the query specification process is shown. 

3.3 Presentation of Results 

An important aspect of a graphical user interface for multimedia database systems is the pre- 
sentation of the results. The question is how to present a huge amount of multimedia objects. The 
problem is that, unlike conventional attributes, multimedia objects may have a time and space di- 
mension. 

To solve these problems we choose a combined form and list oriented approach. Generally, the 
results are presented as a list. In place of the media values only buttons are displayed which the 
user selects in order to see and/or hear the corresponding media object. Another way to see an ob- 
ject in more detail is to point to the line containing the desired tuple to get the tuple displayed in its 
form representation. Forms allow users to see more attributes (including media attributes) than 



- 13- 



available in a list; however in contrast to lists, only one tuple at a time is displayed. By using the 
list representation the user can easily scan a huge amount of data but at any step he has also the 
possibility to get the more detailed form version of a media object. When specifying a query auto- 
matically a new form is created including spaces for the values of all attributes involved. \V^th the 
help of a graphical design tool the user can rearrange the form according to this needs and store it 
under a different name. In future queries the user can choose an already defined form when dealing 
with a similar query. In figure 7 the results of our sample query are shown using the customized 
form withDescription. 

The combined list and form oriented approach only solves the space problem. It is highly de- 
sirable to have an influence on the time dimension of multimedia objects, too. Nobody wants to see 
a whole video in order to identify it as the desired one. Each time, a media object with time dimen- 
sion (e.g. video or sound) is played, the user should have the possibility to stop, skip a part, go back, 
etc. In a special window all possible options should be presented as buttons so that the user can 
choose one of them using the mouse. A precondition for this kind of handling of time dependant 
media objects is random access to their storage representation. In our prototype MDBMS system 
random access to media objects is not supported yet and therefore we do not provide the features 
for time dependant objects. Other desirable options for time dependant media objects are the pos- 
sibility to see a text version of a sound object (e.g. possible for speech or songs), the possibility to 
define index points which are directly accessible without linearly scanning the media object and 
the possibility to define synchronization points (for combined media objects). 

3.4 Predefined Joins and Query Optimization 

So far we introduced predefined joins only from the user’s point of view. In this section, howev- 
er, we will explain the internal handling of predefined joins and related query optimization issues. 

To process a predefined join the query is transformed substituting each occurrence of a pre- 
defined join by it’s definition. Additionally, missing tables are added to the ‘from’ part of the query. 
By this expansion some queries become more complex than necessary. The reason is that some- 
times a two way join is sufficient although a three or four way join is substituted for predefined 

Example 3: select s_no from ship 

where ship carries weapon (original query) 

and weapon.type = torpedo 

select s_no from ship, ship_weapon, weapon 

where ship.s_nr = ship_weapon.s_nr (expanded version) 

and ship_weapon.w_nr = weapon.w_nr 
and weapon.type = torpedo 

select s_nr from ship_weapon, weapon 

where ship_weapon.w_nr = weapon.w_nr (optimized version) 

and weapon.type = torpedo 



- 14- 



joins. In example 3 the predefined join ‘ship carries weapon’ is used. In the expanded version the 
predefined join is substituted by the three way join ‘ship.sjir - ship_weapon.s_nr and 
ship_weapon.w_nr = weapon.wjir’ . However, for the evaluation of the query only a two way join 
is necessary (see optimized version). 

In order to automatically generate a simplified version we developed an optimization algorithm 
to be applied recursively after substituting all predefined joins according to their definition. The 
first step of the optimization algorithm is to check whether a simplification is possible or not. A 
precondition for a simplification is that one of the join attributes must be the only attribute of that 
table used in the query. In this case table and join condition are omitted and each occurrence of the 
join attribute is substituted by the other attribute of the join condition. Formally, the optimization 
algorithm for a two way join can be described as follows: 



if e Attr [A] ) a e Attr [A] Ak^k') a g Attr [A] ) a (a,-^ = a^) 

sub 

by n 



then substitute n o, „ , , _ , (Apr? B) 

•••(<>/„«'«) “i-“r 



1 . ...a, Oi.a. ...a, ®(o, ec,)... (0, ©c_) 
‘1 ‘*-1 * ' J„ 



In more complex queries the optimization algorithm may be applied several times to achieve 
an even larger simplification. In example 4 a query is shown which can be simplified considerably 
(reduction from a four way to a two way join) using the optimization algorithm recursively. 



Example 4: select s_name, o_nr» m_nr from ship, officer, mission 

where officer is_captain_of ship 
and ship isj)n mission 
and ship.class = aircraft_carrier 

select s_name, o_nr, m_nr from ship, officer, mission 
where officer.ojd =ship.cap_id 

and ship.missionjd = mission.mjd 
and ship.class = aircraft-carrier 

select S-name, cap_nr, m_nr from ship, mission 
where ship.missionjd = mission.mjd 
and ship.class = aircraft-Carrier 

select s_name, cap_nr, mission_nr from ship 
where ship.class = aircraft_carrier 



(original query) 



(expanded version) 



(first optimization) 



(final version) 



3*5 Semantic of the ‘aH’-operator 

To make the query specification process easier we introduced an ‘all’-operator. The semantics 
of the ‘air -operator corresponds to the minus-operator in the relational algebra. In this section we 
will explain formally how the ‘all’-operator can be translated into the relational algebra. 

Let us consider a simple one table query with the ‘all ’-operator being used once. 

n a (A) 



- 15- 



To explain the semantic of the ‘all’-operator we use an extension of the relational algebra and 
show how it can be translated into the pure relational algebra. For our extension we allow a condi- 
tion Cj to be the ‘all’-operator Oj = all (B) with B being either an other table or a query 
^ ^ (A'). We define the semantic of the ‘all’-operator by a transformation rule to be 

applied to all occurrences of the ‘all’ -operator. 



7t a (A) 



a,...o_ C....C. 



(A-B). 



In the case of nesting of ‘all’ -operators the semantic of a complex query is defined recursively. 
Starting innermost, each occurrence of the ‘all’-operator is substituted till all occurrences are trans- 
formed into the minus-operator. 

For a better understanding we apply the transformation rule to query example 1 (see page 7). 
In our extended relational algebra the query would be expressed as 



^s.name'^w.nr =a// (VnrO»u,o>,. (weapon)) 



( (shipg_>< „,.ship_weapon) weapon ) . 



By applying the transformation rule defined above we get a version of the query being seman- 
tically identical but using only operators of the well defined relational algebra 

^_nrShip_weapon)^_„^_„^weapon) - = wace-u.ai,' (weapon))). 



(((shipg 



4. Other Database Operations: Schema Definition, Insert, Update and Delete 

In this section we will give an overview of the other database operations as they are supported 
by GRADI. The operations to be described are Schema Definition, Insert, Update and Delete. 

For the schema definition we choose a rather simple table-oriented approach. The system de- 
signer defines a new relation by identifying name, type, width and key of all the attributes. The pos- 
sible datatypes including the media datatypes are presented in a menu. More important at this stage, 
however, is the possibility to predefine joins allowing an easier query specification by the end user. 

Insert, Delete and Update are performed using a form-based approach. When creating a new 
table automatically a new form is created. The spaces for the attribute values reflect the possible 
length of values to be inserted or updated. As mentioned before, the user is able to rearrange the 
form according to his needs. 

The insert operation is performed by filling a form with data. After specifying the attribute val- 
ues for a tuple the user selects the ‘Insert’ button to trigger the actual insert. During the insertion 
process also an ‘Erase All’ button to erase all fields is available. After inserting a tuple the user 
remains in the form to insert other tuples. To quit the insertion mode the user has to use the ‘Quit’ 
button. An example for the insertion window is given in figure 8. 

The first step of the update operation is similar to the retrieval operation because it is necessary 
to identify the tuples desired for update by specifying a selection condition. The condition, a simple 



- 16 - 



or complex one, is specified using the query specification window as described in section 3.2. How- 
ever, only attributes from one table may be in the Result List. The result for the specified query is 
presented as a list and by clicking to one row of the list a tuple is caused to be displayed in a form. 
To change the tuple the user simply edits the values in the form and uses the 'Update’ button. Other 
buttons available in the form are the ‘Next Tuple’ , ‘Previous Tuple’, ‘Update All' and, of course, the 
‘Quit’ button. By using the ‘Next Tuple’ or ‘Previous Tuple’ button the user gets the next or previous 
tuple found by the user given selection condition letting the displayed tuple unchanged. When using 
the ‘Update All’ button an empty form is provided which the user fills to change all tuples found 
using the user given selection condition. Figure 9 shows an example for the update process. 

Like update, delete is a two step operation. First, tuples must be retrieved according to a spec- 
ified selection condition. In contrast to update, no Result List is necessary since tuples can not be 
deleted partially. The second step, the actual deletion, is performed using the resulting list or a 
form. Both list and form provide buttons for deleting the tuples one-by-one or all tuples at once. 

An other important issue is how the media datatypes are integrated into forms because e.g. a 
sound can not be displayed in a form and other difficulties arise for images. For the sound type two 
fields are necessary, one for the path of the sound file and one for the description. Furthermore a 
‘Play Sound’ button is available for each attribute of type sound to play the sound after inserting 
the path. For the attributes of type image a frame, two text fields for the path and the description 
and a ‘Display Image’ button to display the image after inserting or updating the path are provided 
(see figure 8). The frame for the image can be of an arbitrary size making it necessary to zoom the 
image in or out. 

5. Concluding Remarks and Summary 

A major problem faced in today’s database systems is the lack of a natural way to specify com- 
plex queries. It is caused by the gap between the user’s way of thinking and the query languages used 
in most systems. Although a lot of work has been done in the area of user interfaces for database 
systems no query language comes close to the natural query specification process used by humans. 

Our contribution exploited in this paper is a graphical database interface supporting a natural 
query specification process. It narrows the gap between the user’s way of thinking and formal query 
languages by using graphical user interaction. In our system, we support an incremental query spec- 
ification, predefined joins and the special ‘all’-operator to make the query specification process user 
friendly. The user is guided as much as possible allowing a quick and almost faultless query specifi- 
cation. Further research is necessary to come even closer to the user’s way of query specification e.g. 
by allowing the user to directly communicate with the system in natural language when appropriate. 

We believe that our system provides a simple and elegant approach to the retrieval of multime- 
dia data. The simplicity of our user interface lies in the natural way of query specification being 



- 17 - 



directly obtained from queries expressed in natural language. We also believe that our approach is 
a general one that can be readily applied to most database query interfaces (e.g. relational systems 
and extensions hereof). 

References 

[AGRA90] Agrawal, R. et al. “OdeView; The Graphical Interface to Ode”, Proc. ACM- 



[ALLE87] 


SIGMOD 1990 Int’l Conf. on Management of Data, Atlantic City, May 1990, 
pp. 34-43 

Allen, J., “ Natural Language Understanding,” Benjamin/Cummings Publishing 
Company, Inc., 1987 


[BRYC86] 


Bryce D. and Hull, R. “SNAP: A Graphics Based Schema Manager”, Proc. DEEE 
2nd Int’l Conf. on Data Engineering, Los Angeles, California, Feb. 1986, pp. 151- 
164 


[DULL90] 


Dulle, J. “The Scope of Descriptive Captions for Use in a Multimedia Database 
System,” M.S. Thesis, Computer Science Department, Naval Postgraduate School, 
Monterey, CA, June 1990 


[FOGG84] 


Fogg, D.”Leesons from a ‘Living in a Database’ Graphical User Interface”, Proc. 
ACM-SIGMOD 1984 Int’l Conf. on Management of Data, May 1984, pp. 100-106 


[GOLD85] 


Goldman, K. J. et al. “ISIS: Interface for a Semantic Information System”, Proc. 
ACM-SIGMOD 1985 Int’l Conf. on Management of Data, Austin, Texas, May 
1985, pp. 328-342 


[GROSZ87] 


Grosz, B.J. et. al., “TEAM: An experiment in the Design of Transportable Natural 
Language Interfaces,” Artificial Intelligence, 32 (1987), pp. 173-243 


[HOLT90] 


Holtkamp, B. et. al., “Demon - A media object model incorporating natural 
language descriptions for retrieval support,” Tech. Report NPS52-90-019, 
Computer Science Department, Naval Postgraduate School, Monterey, Feb. 1990 


[KEIM91] 


Keim, D.A., Kim, K.-C. and Lum, V., “A Friendly and Intelligent Approach to Data 
Retrieval in a Multimedia DBMS”, Int. Conf. on Database and Expert Systems 
(DEXA), Berlin, Germany, Aug. 1991 


[KING84] 


King, R. and Melville, S. “Ski: A Semantics-Knowledgeable Interface”, Proc. 10th 
Int’l Conf. on Very Large Data Bases, Singapore, Aug. 1984, pp. 115-123 


[LUM89] 


Lum, V. and K. Meyer-Wegener, “A Multimedia Database Management System 
Supporting Content Search in Media Data,” Tech. Report NPS52-89-020, 
Computer Science Department, Naval Postgraduate School, Monterey, CA, March 
1989 



- 18- 



[MEYE88] Meyer-Wegener, K. el. al., “Managing Multimedia Data,” Tech. Report NPS52-88- 
010, Computer Science Department, Naval Postgraduate School, Monterey, CA, 
March 1988 



[PEI90] Pei, Su-Cheng “Design and Implementation of a Multimedia DBMS : Catalog 
Management, Table Creation and Data Insertion,” M.S. Thesis, Computer Science 
Department, Naval Postgraduate School, Monterey, CA, December 1990 

[ROGE88] Rogers, T. R. and Cattell, R. G. G. “ Entity-Relationship Database User Interfaces” 
in Readings in Database Systems, edieted by M. Stonebraker, 1988 

[ROWE91] Rowe, N. and E. Guglielmo, “Exploiting Captions for Access to Multimedia 
Databases,” To appear in IEEE Computer , 1991 

[WONG82] Wong, H. K. T. and Kuo, I. “ GUIDE: Graphic User Interface for Database 
Exploration”, Proc. of the 8th Int’l Conference on Very Large Data Bases, Mexico 
City, Sept. 1982, pp. 22-32 

[ZL0077] Zloof, M. M. “Query-By-Example: A Data Base Language,” IBM Systems Journal, 
4, Dec. 1977, pp. 324-343 




Figure 4: Example for a Recursive Query 




- 19- 




Rgure 6: Query Specification 




Figure 7: Presentation of Results 






- 20 - 




Rgure 8: Insert Process 




Rgure 9: Update Process 






Distribution List 



SPAWAR-3242 
Attn: Phil Andrews 
Washington, DC 20363 

Defense Technical Information Center, 
Cameron Station, 

Alexandria, VA 22304-6145 

Library, Code 52 
Naval Postgraduate School, 

Monterey, CA 93943 

Center for Naval Analyses, 

4401 Ford Avenue 
Alexandria, VA 22302-0268 

Director of Research Administration, 
Code 08, 

Naval Postgraduate School, 

Monterey, CA 93943 

John Maynard 
Code 402 

Command and Control Departments 
Naval Ocean Systems Center 
San Diego, CA 92152 

Dr. Sherman Gee 
ONT-221 

Chief of Naval Research 
800 N. Quincy Street 
Arlington, VA 22217-5000 

Leah Wong 
Code 443 

Command and Control Departments 
Naval Ocean Systems Center 
San Diego, CA 92152 

Vincent Y. Lum 

Naval Postgraduate School, 

Code CS, Dept, of Computer Science 
Monterey, California 93943-5100 



1 copies 



2 copies 



2 copies 



1 copy 



1 copy 



1 copy 



1 copy 



1 copy 



25 copies 



Daniel A. Keim 

Comupter Science Department 

University of Munich 

Theresienstr. 39 

D-8000 Muenchen 2 

Germany 

Kyung-Chung Kim 
Computer Science Department 
Hong-Dc-University 
72-1 Shngsu - Dong, Mapo-Ko 
Seoul, Korea 

Neil C. Rowe 
Code CSRp 

Naval Postgraduate School 
Monterey, CA 93943 

Thomas C. Wu 
Code CSWu 

Naval Postgraduate School 
Monterey, CA 93943 

Bernhard Holtkamp 
University of Dortmund 
Software Technology Lab 
Postfach 500500 
D-4600 Dortmund 50 
Germany 

Klaus Meyer Wegener 

University of Erlangen 

Computer Science Department 

P.O. Box 

Erlangen 

Germany 



5 copies 



1 copy 



1 copy 



1 copy 



1 copy 



1 copy 



rmni CV KMDX LIBRARY