Place several rods down on the table, and hinge
them
together to make a chain. Is it always
possible to
rotate the hinges and move the links, in such
a way
that the links are straightened into a line? The links
are not allowed to change length or cross each other.
At first glance, it seems intuitive that any chain can
be ``unraveled'' into a
straight line, but
experimentation reveals that this is
a nontrivial
problem.
This question has been open for many years, posed
by
several researchers including Joseph Mitchell, William
Lenhart, and Sue Whitesides. A related question is, if
we connect the rods in a cycle, can we move the links
to make a convex polygon? This question
seems even
harder than straightening chains. This talk
surveys
the work done on both of these problems, and presents
some new results.
Facilitator: Kerry Mahoney, Co-operative Education & Career Services
Are you interested in a career in academia or research? If so,
this
workshop on preparing a cover letter and curriculum vitae (C.V.) is
for
you! Its never too soon to start thinking about your career plans.
And a
crucial part of your planning should include learning how to represent
your experience and your skills in writing. In this workshop,
you will
learn how to analyze job advertisements and prepare a cover letter.
Please pre-register for this workshop by sending an email to
trace@watserv1 by Wednesday, April 14, 1999, or by sending the form
below
to TRACE, MC 4055. Enrolment is limited, so sign up early!
If you have
any questions, please contact TRACE at ext. 3132
Attendence Manditory
- Friday, April 16, 1999
Arunprasad P. Marathe, graduate student, Dept. Comp.
Sci., Univ. of Waterloo, will
speak on ``Query
Processing Techniques for Arrays''.
TIME: 2:00-3:00 p.m.
ROOM: DC 1331
ABSTRACT
Arrays are an appropriate data model
for images,
gridded output from computational models, and
other
types of data. In this talk,
I shall describe an
approach to array query processing.
Queries are
expressed in the Array Manipulation Language (AML), a
logical algebra that is easily extended
with user-
defined functions to support a wide variety of array
operations. For example, compression, filtering,
and
algebraic operations on images can be described.
AML
expressions involving such operations can be treated
declaratively and subjected to
useful rewrite
optimizations. I shall describe a plan generator that
produces efficient iterator-based plans from rewritten
AML expressions.
This is joint work with my advisor, Dr. Ken Salem.
A
paper based on ideas in this talk shall appear in the
SIGMOD 99 conference.
- Monday, April 19, 1999
Koji Ueda, graduate student, Dept. Comp. Sci., Univ.
Waterloo, will speak on ``Efficient
Query Result
Retrieval in a Distributed Object Environment.''
TIME: 1:00-2:00 p.m.
ROOM: DC 1304
ABSTRACT
Most database server products offer an iterator-based
programming interface like the following:
Result result = database.query( condition );
while( result.more() )
{
doSomething( result.get() );
}
This interface is easy to use for
the client-side
programmers and has been quite popular up to this day.
Usually, database products provide a stub library with
which client programs should be linked. This portion of
the program deals with the communication details with
the database server and performs caching for the client
application. However, the situation is different in a
distributed object environment such as
Java RMI or
CORBA. Every function call is not a local procedure
call to the client stub, but essentially
a remote
method call to the server object, which can lead to a
bad query performance. This is a
serious problem,
especially for applications such
as geographic
information systems since their result sets are usually
huge and real-time user interaction is required.
We contrive two ideas to avoid this bottleneck, without
changing the same programming interface.
1. Dynamically download a caching program
to the
client side using Java RMI.
2. Insert caching codes into ORB
using the CORBA
object wrapper mechanism.
In this thesis, each solution is examined under various
conditions from diverse points of view: the
time to
retrieve a result set, the size of transferred data,
and the amount of required programming. The multiple
retrieval interface (i.e., the interface with Data[]
getn(int n) instead of Data get()) is also evaluated
for comparison.