Internal organization of relational DBMS Lecture 9. External memory structures, index organization methods

Relational DBMS have a number of features that affect the organization of external memory. The most important features include the following:

• The presence of two levels of the system: the level of direct data management in external memory (and usually the management of memory buffers, transaction management and logging database changes) and language level (for example, the level that implements the SQL language). With such an organization, the subsystem of the lower level must maintain in the external memory a set of basic structures, the specific interpretation of which is among the functions of the subsystem of the upper level.
• Maintaining a directory relationship. Information related to the naming of database objects and their specific properties (for example, the index key structure) is maintained by the language-level subsystem. From the point of view of the structures of external memory, the relation-directory is no different from the usual database relation.
• Regularity of data structures. Since the main object of the relational data model is a flat table, the main set of external memory objects can have a very simple regular structure.
• At the same time, it is necessary to ensure the possibility of effective execution of language level operators both over one relation (simple selection and projection) and over several relations (the most common and time-consuming connection of several relations). For this, additional "control" structures - indices should be supported in the external memory.
• Finally, in order to fulfill the requirement of reliable database storage, it is necessary to maintain data storage redundancy, which is usually implemented in the form of a database change log.

Accordingly, the following types of objects appear in the external memory of the database:

• relationship rows - the main part of the database, mostly directly visible to users;
• control structures — indices created at the initiative of the user (administrator) or the upper level of the system for reasons of improved query performance and usually automatically supported by the lower level of the system;
• journal information maintained to meet the need for reliable data storage;
• service information supported to meet the internal needs of the lower level of the system (for example, information about free memory).

Using the examples of System R and Ingres, we looked at two alternative approaches to the organization of a relational DBMS from the point of separation of functions between different components. Recall that in System RMS, there was an integrated data, transaction and logging management subsystem, while at Ingres data management was separated from transaction and log management.

Both of these approaches have their own advantages and disadvantages. The System R approach allows using more efficient methods by jointly solving the problems of physical and logical synchronization, using common protocols in buffer management and logging, etc. But at the same time, in a sense, the subsystem of the lower level becomes a monolith; with its most successful structuring, the components remain connected by common interaction protocols. Unreasonable local changes of one component can lead to fatal consequences for the entire system. Ingres's approach allows us to simplify the structure of the system and make it more flexible, but this is possible only through the coarsening of algorithms: the use of coarser transaction management methods; hard logging protocols, etc.

Ultimately, any particular system is based on a specific integrated solution. We consider here fragments of such decisions (sketches).