Citations for the publications referred to below can be
Table Grouping (2009-present)
Akiban Server is a database system designed to optimize complex
queries, characterized by many joins. The basic idea is to colocate
frequently joined rows in a single b-tree. When these joins are
specified in a query, the necessary rows can then be retrieved in a
way that makes effective use of caches at all levels. While there is
extensive research literature non-first normal form query processing,
and on hierarchical query languages, Akiban had a unique problem: how
to execute relational queries (SQL) over hierarchical structures. This
led to a number of research problems:
Scalable Data Structures (2003-2009)
- Storing a hierarchy in a b-tree: The basic storage scheme
is straightforward -- the b-tree key is formed by concatenating
primary keys from the root of the hierarchy (defined by grouping
foreign keys) to each table. Table identifiers separate the key
segments to allow for branching hierarchies, (as opposed to just
deep hierarchies). A number of research problems had to be solved to
make this hierarchical representation practical: how to maintain b-tree keys
across primary and foreign key updates; how to deal with "orphan"
rows, (which have no parent in the hierarchy); and how to do locking
to allow for good concurrency while maintaining correct operation.
- Algebra for query processing: We needed a set of query
processing operators for supporting SQL queries over hierarchically
structured data. "Flattening" operators have been used in other
non-first normal algebras. We also needed operators for navigating
the hierarchy, and we needed to generalize more conventional
operators (e.g. for selection) to accomodate hierarchically
structured data. Factors influencing the design of the algebra
included expressiveness, performance, and the needs of the query
- Indexing: Indexes over hierarchical data provide a number
of new optimization opportunities. I contributed to research on how
to implement indexes whose fields span the tables in a hierarchy.
At Archivas, I was responsible for the design and implementation of
the Metadata Manager, the component which maintained metadata
on archived files. This metadata includes POSIX metadata, and locations of
file copies within the archive. We initially considered one large
would scale up as needed. But this database would have been a single point
of failure. It would not scale as well as the rest of the system, and would
become a bottlneck. As nodes are added to the cluster, throughput
would increase, but
only up to a limit imposed by the database.
For these reasons, we decided to distribute the database, using
techniques from the field of scalable data structures. I conducted
original research in this area:
- How to avoid rehashing everything: When nodes fail and leave the cluster,
or when nodes are added to the cluster, data needs to be load-balanced across the
modified set of nodes. But rehashing everything is prohibitively expensive.
The traditional approach to this problem is to use consistent hashing.
We pursued an approach based on linear hashing instead.
- Maintaining synchronous replicas: Each linear hash bucket has multiple copies.
These copies have to be kept tightly synchronized so that, following a node failure, surviving copies
can be used to continue servicing request.
- Mapping hierarchical filesystem to hash-based data structure: POSIX semantics
require directory metadata to be updated each time a file is created or deleted.
There is no easy way to map a hierarchy to a set of hash buckets -- does a directory go to the same
bucket as the child or the parent? I designed a mapping that maintains POSIX semantics correctly
with correct transaction semantics and good performance. The implementation supports
up to 200,000 files per directory.
Object/Relational Mapping (1995-2000)
At Object Design, I became interested in the problems of
linking the object-oriented and relational data models,
based on some problems faced by one of our customers,
USWest. USWest liked the programming model supported by
Object Design's product, ObjectStore, but wanted to
be able to use that model in conjunction with
traditional relational database systems.
I wrote a series of internal papers describing technical
approaches to these problems.
This design work
led to the establishment of a group whose goal was to create
products mapping in both directions between object-oriented
and relational databases.
A customer application built on top of one of these tools
was described in a 1995 conference publication.
In late 1995 I decided to build an object/relational mapping
system for the Java language, which had just
been released by Sun. Object
Design was not interested in pursuing this work so I left
to build the product on my own.
A few other object/relational mapping systems existed, mostly
for C++. However, they all had serious performance problems.
An object-oriented application spends much of its time
navigating from one object to another. Turning each navigation
into a retrieval from a relational database is an easy
translation, but this is an inefficient way to access a
relational database. I defined and solved a number of
research problems in producing a system whose performance
was comparable to what could be achieved by hand-coded
relational database applications.
A paper describing some of this research
was published in 1999. Other original work
was not published.
I sold my company to Novera Software, Inc. in 1996.
My product became a central piece of the
Novera product line.
Object-Oriented Database Systems (1989-1996)
Traditional database systems are based on the
relational model of data. Virtually all relational
database systems use a server-centric architecture.
Many applications cannot use relational database systems
because the data model is not adequate for modeling
the concepts on which the application is based, and because
the performance characteristics of the application call for
a more client-centric architecture.
Object-oriented database systems offer an alternative.
The data model of an object-oriented database system is much
closer to that of a programming language, (an object-oriented one),
and most of the persistence mechanism is implemented on the
client side. These approaches combine to produce a database system
that is well-suited to applications involving detailed analysis
of complex data, e.g. geographic information systems, ECAD, MCAD
At CCA, on the DARPA-funded PROBE research project, I started working
on the problem of how to extend the capabilities of database systems
with object-oriented features.
My work on spatial data processing represented part of this work.
Papers describing the PROBE project were published in several
journals and conference proceedings.
PROBE was focused on adding
object-oriented capabilities to traditional database systems.
Another project I worked on, Persistent Ada,
dealt with a new approach to persistence, adding persistence
to a programming language. Persistent Ada was a brief,
DARPA-funded research project,
and produced no software.
I worked on ideas related to Persistent Ada
at Object Design. The company's
goal was to create
a commercial product based on C++, so in addition to producing a database
system based on an object-oriented model, we also had to
develop a client-centric architecture.
were in the area of data modeling, query languages and query
processing. I surveyed the relevant research literature in these
areas, selected a set of the more practical ideas,
and implemented them. In a number of instances,
the implementation work required solutions to new research
Conference and journal publications
on the novel aspects of the system appeared between 1991 and 1993.
Spatial Data Processing (1982-1991)
Traditional database systems are designed to handle alphanumeric
information, such as names and numbers. Many important applications
need both the data management capabilities of traditional
as well as the ability to handle spatial data, e.g. maps,
solid models, and
Three approaches have been used to build these applications: 1) Ad hoc
implementations; 2) Systems geared to applications within a domain, e.g.
Geographic Information Systems; 3) Hybrid systems built by combining
a traditional database system with extensions for geographic data
(as an example).
My research in this area has pursued a fourth possibility:
extending the capabilities of database systems to handle
arbitrary spatial data types. This work has been carried out
in the context of traditional relational database systems,
as well as extended-relational and object-oriented database
The results have been described in conference and journal
between 1983 and 1991.
The research has also led to the creation of
a software product, a spatial index library named
The product has been licensed
to two object database vendors (Object Design, Objectivity),
and is in use in deployed applications by their customers.
There are at least two other implementations of these
I consulted with IBMs Santa Teresa Labs on my research, and they
have used it in conjunction with a medical imaging application.
Microsoft has adopted my algorithms
for use in their
TerraServer application, which is a showcase
for their SQL Server database system.
- Member of the program committees for various database conferences, including SIGMOD and VLDB, (several times each).
- Reviewer for several journals.
- Reviewer for several M.Sc. dissertations.