3.1. Main features of systems based on inverted lists

Among the most famous and typical representatives of such systems are Datacom / DB of Applied Data Research, Inc. (ADR), focused on use on IBM's main-class machines, and Software AG's Adabas.

The organization of access to data based on inverted lists is used in almost all modern relational DBMSs, but in these systems, users do not have direct access to inverted lists (indices). By the way, when we consider the internal interfaces of relational DBMSs, you will see that they are very close to the user interfaces of systems based on inverted lists.

3.1.1. Data structures

A database organized using inverted lists is similar to a relational database, but with the difference that the stored tables and access paths are visible to users. Wherein:

1. The rows of the tables are ordered by the system in some physical sequence.
2. The physical ordering of rows of all tables can be determined for the entire database (this is done, for example, in Datacom / DB).
3. For each table, you can define an arbitrary number of search keys for which indexes are built. These indexes are automatically maintained by the system, but are clearly visible to users.

3.1.2. Data manipulation

Two classes of operators are supported:

1. The operators that establish the address of the entry, among which are:

• direct search operators (for example, to find the first entry of the table by some access path);
• operators that find a record in terms of a relative position from a previous record along a certain access path.
• Operators on addressable entries

  Typical set of operators:

  • LOCATE FIRST — find the first record of table T in physical order; returns the address of the record;
  • LOCATE FIRST WITH SEARCH KEY EQUAL - find the first record of table T with the specified search key value K; returns the address of the record;
  • LOCATE NEXT - find the first entry following the entry with the specified address in the specified access path; returns the address of the record;
  • LOCATE NEXT WITH SEARCH KEY EQUAL - find the following entry in table T in the order of the search path with the specified value K; there must be a correspondence between the scanning method used and the key K; returns the address of the record;
  • LOCATE FIRST WITH SEARCH KEY GREATER — find the first record of table T in the order of the search key K with the key field value greater than the specified value K; returns the address of the record;
  • RETRIVE - select an entry with the specified address;
  • UPDATE - update the record with the specified address;
  • DELETE - delete the record with the specified address;
  • STORE - include an entry in the specified table; the operation generates the address of the entry.

  3.1.3. Integrity constraints

  There are no general rules for determining the integrity of the database. Some systems support the limitations of the uniqueness of the values ​​of some fields, but basically everything rests on the application program.