Logical Data Model
The data model offered to users is the CODASYL network model. The main structuring concepts in this model are records and sets. Records essentially follow the COBOL pattern, consisting of fields of different types: this allows complex internal structure such as repeating items and repeating groups.
The most distinctive structuring concept in the Codasyl model is the set. Not to be confused with a mathematical set, a Codasyl set represents a one-to-many relationship between records: one owner, many members. The fact that a record can be a member in many different sets is the key factor that distinguishes the network model from the earlier hierarchical model. As with records, each set belongs to a named set type (different set types model different logical relationships). Sets are in fact ordered, and the sequence of records in a set can be used to convey information. A record can participate as an owner and member of any number of sets.
Records have identity, the identity being represented by a value known as a database key. In IDMS, as in most other Codasyl implementations, the database key is directly related to the physical address of the record on disk. Database keys are also used as pointers to implement sets in the form of linked lists and trees. This close correspondence between the logical model and the physical implementation (which is not a strictly necessary part of the Codasyl model, but was a characteristic of all successful implementations) is responsible for the efficiency of database retrieval, but also makes operations such as database loading and restructuring rather expensive.
Records can be accessed directly by database key, by following set relationships, or by direct access using key values. Initially the only direct access was through hashing, a mechanism known in the Codasyl model as CALC access. In IDMS, CALC access is implemented through an internal set, linking all records that share the same hash value to an owner record that occupies the first few bytes of every disk page.
In subsequent years, some versions of IDMS added the ability to access records using BTree-like indexes.
Storage
IDMS organizes its databases as a series of files. These files are mapped and pre-formatted into so-called areas. The areas are subdivided into pages which correspond to physical blocks on the disk. The database records are stored within these blocks.
The DBA allocates a fixed number of pages in a file for each area. The DBA then defines which records are to be stored in each area, and details of how they are to be stored.
IDMS intersperses special space-allocation pages throughout the database. These pages are used to keep track of the free space available in each page in the database. To reduce I/O requirements, the free space is only tracked for all pages when the free space for the area falls below 30%.
Four methods are available for storing records in an IDMS database: Direct, Sequential, CALC, and VIA. The Fujitsu/ICL IDMSX version extends this with two more methods, Page Direct, and Random.
In direct mode the target database key is specified by the user and is stored as close as possible to that DB key, with the actual DB key on which the record is stored being returned to the application program.
Sequential placement (not to be confused with indexed sequential), simply places each new record at the end of the area. This option is rarely used.
CALC uses a hashing algorithm to decide where to place the record; the hash key then provides efficient retrieval of the record. The entire CALC area is preformatted each with a header consisting of a special CALC "owner" record. The hashing algorithm determines a page number (from which the physical disk address can be determined), and the record is then stored on this page, or as near as possible to it, and is linked to the header record on that page using the CALC set. The CALC records are linked to the page's CALC Owner record using a single link-list (pointers). The CALC Owner located in the page header thus owns the set of all records which target to its particular page (whether the records are stored on that page or, in the case of an overflow, on another page ).
CALC provides extremely efficient storage and retrieval: IDMS can retrieve a CALC record in 1.1 I/O operations. However, the method does not cope well with changes to the value of the primary key, and expensive reorganization is needed if the number of pages needs to be expanded. A work-around is to expand the area, and then run an application program which scans the area sequentially for each CALC record, and then uses the MODIFY verb to update each record. This results in each CALC record being connected to the CALC Set for the correct target page as calculated for the Area's new page range. The downside to this method is that vanishingly few CALC records will now be on their target pages, and navigating each page's CALC set is likely to involve many IO operations. As a result, it is recommended only to use this work-around in extreme circumstances as performance will suffer.
VIA placement attempts to store a record near its owner in a particular set. Usually the records are clustered on the same physical page as the owner. This leads to efficient navigation when the record is accessed by following that set relationship. (VIA allows records to be stored in a different IDMS area so that they can be stored separately from the owner, yet remain clustered together for efficiency. Within IDMSX they may also be offset from the owner by a set number of pages).
Page Direct (IDMSX only) is similar to Direct mode, however a target Database page number is specified and the record is connected to the CALC chain for that page.
Random (IDMSX only) allocates a target page number to the record occurrence when it is stored using the CALC algorithm (this either uses a Key within the record or in the case of un-keyed random, uses the date & time of storage as a seed for the CALC algorithm).
Sets are generally maintained as linked lists, using the database key as a pointer. Every record includes a forward link to the next record; the database designer can choose whether to include owner pointers and prior pointers (if not provided, navigation in those directions will be slower).
Some versions of IDMS subsequently included the ability to define indexes: either record indexes, allowing records to be located from knowledge of a secondary key, or set indexes, allowing the members of a set to be retrieved by key value.
The IDMSX Page Direct and Random placement records are typically used in conjunction with Record Indexes as described above. The Indexes themselves are subject to placement rules, either Direct (which really means "CALC using the Index ID as the key") or CALC.
