Starburst

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 many others.

Making Starburst Extensible

Different kinds of internal mechanisms were used to make Starburst extensible.

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 user-defined functions. 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.

Specialized Indices

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 new attachment.

Extensions

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.

References