The goal of the Starburst project at IBM Almaden (1984-1992) was to build
a complete, operational prototype of an extensible
relational database management system. The extensibility built into
every aspect of Starburst made it easier for the user to customize
the system for the user's special needs, to experiment with new
database technologies, and to rapidly incorporate new features that
better support new application areas (such as CAD/CAM, geographic,
text, and expert systems) as well as traditional business
applications. Starburst allowed the user to add new storage methods
for tables, new types of access methods, user-defined operations on
tables or columns of those tables, new query optimization strategies,
and user-defined actions in response to changes in the database, among
Making Starburst Extensible
Different kinds of internal mechanisms were used to make Starburst
To make the Starburst language extensible, an open-ended syntax was
created that allowed additions to existing commands without requiring
modification of the underlying command processor, through the addition of
To add a user-defined function, e.g., "boundary overlap",
an extender would insert the function
name and parameter types in the FUNCTIONS catalog, along with the C
code implementing it.
Extensions deeper in Starburst, such as adding storage methods or access
methods, were made by registering with Starburst the new code to do certain
standard operations -- such as update, insert, and delete. This was done
simply by initializing an entry in an internal vector for each operation.
Starburst's authorization mechanism made it easy to add
user-specific extensions. Access privileges were granted or
revoked on types of database objects for individual users or groups of
users. The authorization algorithm allowed arbitrary, acyclic nesting of
user groups. Regardless of the complexity of the user group nesting,
testing authorizations took constant time.
Access privileges for database objects could be hierarchical and could reflect
the wide diversity in requirements and semantics allowed by Starburst's
extensions. It wass possible to restrict access to objects in a variety
of ways, including recursively revokable granting of privileges and transfer
of object ownership.
Most current systems give a single way of storing data (e.g., a
B-tree) and a single way of reaching the data (e.g., B-tree indices).
Starburst allowed the user to choose a storage method and then
to define multiple ways of accessing that data. These
multiple access paths, the attachments, had redundent information
that is associated with the data (B-tree indices, signature files,
hash tables, join indices, single record integrity constraints and
referential integrity constraints). When the user updated the data,
Starburst automatically updated the attachments.
Cataloging objects (How does Starburst find things?)
Descriptive information, or descriptors, for all objects in the system
were kept in system catalogs. Descriptors contained information
about queries or about objects needed by the query execution routines,
such as a table's storage method and all of its attachments. Since
object descriptors were packaged as records, objects associated with
the standard Starburst queries could be handled with the same facility
as objects associated with extensions.
Performance and Query Optimization
A query is parsed, semantically checked, and rewritten into a form
that is easier to optimize. In Starburst, this form was known as
the query graph model. Starburst provided powerful and extensible tools
for improving query performance that used this model. The query rewrite
engine allowed an extender to define query transformations (for example,
subquery to join transformations) that could improve performance. The query
optimizer determined an execution strategy using macro-like processing, which
recognized operators in the query graph and expanded them using named rules.
An expansion might be expanded, itself, and each expansion could have
alternatives. Each branch of this resulting decision tree was
evaluated for its estimated
cost of execution, and the lowest-cost branch was chosen.
Although rules were provided with the system, if the user added a new
way of accessing the data, the rules could be modified to reflect this
We made many extensions to Starburst. Through extensions
to Starburst, we incorporated the advanced structuring and data
behavior features offered by object-oriented database management
systems, while retaining the significant gains in data independence
and data integrity of the relational model and upward compatibility
with its standard access language, SQL. Some of the advanced features
supported by Starburst extensions include hierarchies of user-defined
types and functions, large unstructured and structured complex
objects, and user-defined rules (triggers) to respond to changes in the database.
IBM Almaden Computer Science |
IBM Almaden |
IBM home page |
Contact IBM |