The researchers propose using the Data Structure Machine, a massively parallel computer, for implementing a nested relational database system. Nested relational databases are formed by relaxing the First Normal Form (INF) requirement that was imposed on relational databases. As a result, values can be complex objects instead of atomic values we associate with the relational model. Object-oriented data-bases, engineering and graphics applications, and image analysis can all benefit from an efficient nested relational database implementation. The Data Structure Machine (DSM) is a particularly good candidate for a nested relational database computer.The scaling properties that the simple tree-base connection topology provide, will allow the DSM to grow to a massive degree of parallelism. Further, the DSM is optimized to exploit locality within data structures. A proposed serial nested relational database implementation by Deshpand and Van Gucht maintains the locality properties that the DSM exploits. With Deshpand, the researchers have mapped, as an abstract implementation, the serial model onto the parallel architecture of the DSM. They plan to transform this abstract implementation to a physical implementation on a prototype DSM. Transformation of the critical algorithms can be done during Phase I of this project.Commercial Applications:A separate project is underway to scale the DSM from a small-scale prototype to a real-world machine. The economies of scale that are a result of the simple connection topology will make the machine cost-effective when compared to a general connection topology, i.e.., the Connection Machine (CM). In this database application the DSM will outperform the CM.
