An associative backend machine for data base management

It has long been recognized that computer systems containing large data bases expend an inordinate amount of time managing the resources (viz. central processing time, memory, ... etc.) rather than performing useful computation in response to user I s query. This is due to the adaptation of the classical machine architecture, the so called von Neumann architecture, to a problem domain that needs radically different machine architecture for an efficient solution. The characteristics that distinguish the computation for data base management systems are: massive amount of data, simple repetitive non-numeric operations and the association of a name space with the information space at a high level. The current systems meet these requirements by memory management techniques, specially designed application programs and a sophisticated address mapping methods. This accounts for a large software overhead and the resulting semantic gap between the high level language and the underlying machine architecture. To overcome the difficulties of the von Neumann machines, Slotnick suggested the idea of the hardware backend processing by distributing the processing capabilities outside of CPU and among the read/write cells. These cells act as filters which imp rove the system performance by reducing the processing load on the CPU as well as the amount of data transported back and forth between secondary and main storage. The major contribution of this dissertation is the definition of a backend machine architecture ASLM (Associative Search Language Machine) and the development of a query language ASL (Associative Search Language) which is directly executed by the backend machine using built-in hardware algorithms for query processing and associative hardware for name-space resolution. The language ASL is a high level data base language using associative principles for basic operations. The language has been defined based on the relational data model. ASL is relationally complete, and provides complete data independence. ASL provides facilities for query, insertion, detection and update operations on tuples of variable sizes. Moreover, the structure of the statements in ASL are represented in arithmetic expressions like entities called set expressions. ASLM is designed based on cellular organization, a design similar to Slotnick\u27s idea with an important exception. In the design of ASLM, the processing units (cells) are moved into the backend machine. The general strategy in ASLM is based on the pre-search through the data file and then the execution of the operations on the explicit subfiles which are stored in the associative memory. The generation of the subrelations explicitly eliminates the existence of so-called mark bits in some of the previously designed data base machines. Moreover, it provides fast algorithms for international operations such as join. ASLM is also microprogrammable which gives more flexibility to the system. The design of the ASLM differs from the majority of the data base machines based on Slotnick\u27s idea: first, the separation of the cells from the secondary storage will result in a cost effective system in comparison to the other machines. This also eliminates any restriction on the secondary devices. Second, since cells are independent of each other there is no need for interconnection network between the cells. Third, ASLM is implemented by associative memory, the closeness between associative operations and data base operations reduces the existing semantic gap found in the conventional system, and fourth, ASLM is expandable to the MIMD class of machines