Module 02

The CODASYL network model

A set here is not a collection and not a maths set. It is a named parent-child link, stored as a physical chain of addresses running from a parent record, through each of its children, and back to the parent again. Almost everything else in this database follows from that one sentence.

~45 min1 simulator10-question checkpoint
What this module is really about

How this database stores relationships. In a normal database you link two rows by putting the same value in both, and the database matches them up when you ask. Here the link is a physical address, written invisibly onto each record, so nothing is ever matched — the database just follows the trail.

That has consequences all the way through the course. Relationships take up real storage. They come with rules about who may join and who may leave. They have an order. And a child can be firmly attached to its parent while containing nothing anywhere in its data that says so — which is the single biggest obstacle when you copy this data into a normal database.

New words on this page, one line each
record type / occurrence
The definition of a kind of record, and one actual stored instance. Roughly: table and row.
set
A named parent-child relationship, stored as a chain of physical addresses.
owner / member
The parent record, and a child record, in that relationship.
membership option
Two rules per relationship: can a child be detached, and is it attached automatically.
set order
The order children sit in on the chain. Sometimes decoration, sometimes real information.
chain
The usual way the link is built: a ring of addresses. The alternatives are a tree-shaped index or an array of addresses.
singular set
A relationship with no parent record at all, used to build a plain index over every record of one type.
junction record
A small record sitting between two parents so a many-to-many relationship can exist. A join table.
prefix
Hidden addresses stored in front of every record’s real data. This is where relationship links physically live.

Records: the rows, and the three ways they are not rows

If you know PostgreSQL

Record type is a table, record occurrence is a row, element is a column. That mapping gets you a long way and then stops abruptly, for three reasons: a record has a physical address that other records store; a record can contain nested structures and arrays, so it is not flat; and a record type is not required to have a unique key at all.

A record type is a named structure with a numeric record ID, a length, a list of elements (fields) and a physical placement rule. A record occurrence is one stored instance. In relational terms: record type ≈ table, record occurrence ≈ row. The analogy stops being safe almost immediately, for three reasons.

  • A record occurrence has a physical address — the db-key — which is part of its identity from the DBMS's point of view, and which every pointer in the database uses to reach it.
  • Elements can be structured. COBOL group items, OCCURS arrays and REDEFINES overlays are all legal inside a record. A record is not flat.
  • A record type need not have a unique key at all. Nothing forces one. Records reached only through a set frequently have nothing unique in them.
a record definition in schema DDL, with a group item
RECORD NAME IS EMPLOYEE
    RECORD ID IS 415
    LOCATION MODE IS CALC USING ( EMP-ID-0415 )
        DUPLICATES ARE NOT ALLOWED
    WITHIN EMP-DEMO-REGION AREA.
    02  EMP-ID-0415             PIC 9(4).
    02  EMP-NAME-0415.
        03  EMP-FIRST-NAME-0415 PIC X(10).
        03  EMP-LAST-NAME-0415  PIC X(15).
    02  EMP-ADDRESS-0415.
        03  EMP-STREET-0415     PIC X(20).
        03  EMP-CITY-0415       PIC X(15).
        03  EMP-STATE-0415      PIC X(2).
        03  EMP-ZIP-0415        PIC X(9).
    02  STATUS-0415             PIC X(2).
    02  SS-NUMBER-0415          PIC 9(9).
    02  START-DATE-0415         PIC 9(8).
    02  TERMINATION-DATE-0415   PIC 9(8).

The -0415 suffix is a naming convention, not a requirement: element names must be unique across the whole dictionary, so shops append the record ID. You will see this everywhere in real schemas.

Sets: a relationship you could physically point at

Picture it

A labelled loop of string. It starts at the parent card, threads through each child card in turn, and comes back round to the parent.

Two things follow immediately. Reaching the end of the string and arriving back at the parent are the same event, which is why the database reports “end of set” rather than “nothing found”. And the string is physically stored on the cards, so adding or removing a child means rewriting the cards on either side of it.

A set type declares: one owner record type, one or more member record types, an order, a mode, and per-member rules. A set occurrence is one owner occurrence together with the member occurrences currently connected to it. If there are 40 departments, the DEPT-EMPLOYEE set type has 40 occurrences — one per department, several of which may be empty.

DEPARTMENT 3200 owner · 75020:1 EMPLOYEE 0028 member · 71003:1 EMPLOYEE 0031 member · 71006:1 EMPLOYEE 0033 member · 71009:1 NEXT NEXT NEXT NEXT wraps to owner PRIOR PRIOR OWNER
One set occurrence of DEPT-EMPLOYEE. NEXT forms a ring back to the owner — which is why "end of set" and "back at the owner" are the same event, and why the status code is 0307 rather than a null.

Those pointers are stored in the record prefix: a block of db-keys sitting in front of the user data in every occurrence. A record that participates in four sets as a member and owns two more carries a prefix with a db-key slot for each pointer of each set. Prefixes are why an IDMS record on disk is bigger than its PIC clauses suggest, and why adding a set to an existing database is a physical change requiring unload and reload.

Who may join, and who may leave

The two questions, in plain terms

Every relationship answers two independent yes-or-no questions about its children.

Can this child ever be detached and still exist? No means MANDATORY, yes means OPTIONAL. That is exactly a NOT NULL foreign key versus a nullable one.

Does the database attach it for me when I store it? Yes means AUTOMATIC, no means MANUAL and the program must issue a separate command. Get this one wrong and you create records that no navigation path ever reaches.

Every member record type in every set declares two independent properties. They are the closest thing IDMS has to declarative referential integrity, and they are enforced by the DBMS, not by application code.

MANDATORY/OPTIONAL controls leaving; AUTOMATIC/MANUAL controls joining
CombinationOn STORECan it be DISCONNECTed?Relational analogue
MANDATORY AUTOMATIC (MA) Connected automatically to the current owner Never. Only ERASE removes it. NOT NULL foreign key, set at insert, immutable relationship
OPTIONAL AUTOMATIC (OA) Connected automatically to the current owner Yes — the record survives as an orphan in that set Nullable foreign key, defaulted at insert
MANDATORY MANUAL (MM) Not connected. Program must issue CONNECT. Never, once connected Deferred but permanent assignment. Rare, and a common source of bugs.
OPTIONAL MANUAL (OM) Not connected Yes, freely Nullable foreign key, fully application-managed
The orphan trap An OPTIONAL member that has been disconnected still exists on disk and is still reachable by CALC or by an area sweep — but it appears in no set occurrence. If your extract navigates from owners downward, you will silently miss every orphan. If your extract sweeps the area, you will pick them up and then have nothing to attach them to. Both are wrong answers to a question you must ask the business: what does a disconnected record mean?

The order children sit in, and when that order is information

Why order is not a cosmetic detail

Rows in a normal table have no inherent order. Children on a chain do, and applications rely on it: “the current salary” is very often just “the first child on this string”.

So if you copy this data to a normal database and lose the order, you lose that meaning. It has to become an actual column — a sequence number, a valid-from date, or a current flag.

ORDER ISNew member is insertedTypical use
FIRSTAt the head of the chain, immediately after the owner"Most recent first" — LIFO history
LASTAt the tail, immediately before the ownerChronological append — FIFO
NEXTImmediately after the current member of setProgram-controlled ordering
PRIORImmediately before the current member of setProgram-controlled ordering
SORTEDBy declared key values, ascending or descendingOrdered retrieval without an index; enables key-based positioning within the set

SORTED sets additionally declare DUPLICATES ARE FIRST | LAST | NOT ALLOWED. NOT ALLOWED makes the sort key a uniqueness constraint within that set occurrence — a genuinely useful piece of declarative integrity, and one of the few places an IDMS schema hands you a natural key you can use downstream.

ORDER IS NEXT and ORDER IS PRIOR depend on where currency happens to be when the STORE executes. That makes physical order a function of program flow. If a downstream consumer depends on set order carrying meaning, verify it against the code, not the schema.

Three ways the link is physically built

One line each

Chain — a ring of addresses. Cheap to store, cheap to add to, slow to search because you walk it one link at a time.

Index — a tree of sorted key values. Fast to search, extra work on every change.

Pointer array — the parent holds a list of all its children’s addresses. Instant access by position, awkward when the list grows. You will meet it in older designs.

CHAIN

Ring of db-key pointers. Always has NEXT; optionally PRIOR and OWNER. Cheap to store, cheap to insert, linear to search.

Without PRIOR, OBTAIN LAST walks the entire chain. Without OWNER, OBTAIN OWNER walks forward until it finds the owner. Both are common performance surprises.

INDEX

A B-tree-shaped structure of index records (SR8 blocks under an SR7 owner) holding sorted key values and pointers. Logarithmic search, ordered retrieval, extra maintenance on update.

Covered fully in Module 06. An indexed set can be a normal owner-member set or a singular set owned by SYSTEM — the latter is IDMS's standalone index.

POINTER ARRAY

The owner holds an array of member db-keys. Direct positional access, no walking — but the array must be maintained and can outgrow its page.

Historically used for small, stable, frequently-random-accessed sets. You will meet it in older schemas.

Relationships with no parent, and how they become an index

A set can declare OWNER IS SYSTEM. There is then exactly one set occurrence in the whole database, and every occurrence of the member record type belongs to it. This is how IDMS provides:

  • A standalone index — ORDER IS SORTED, MODE IS INDEX, owned by SYSTEM, giving keyed access to a record type independent of any owner.
  • A sequential access path across all occurrences of a record type without an area sweep.
  • A "root" for a hierarchy, so top-level records still hang off something navigable.
a system-owned index
SET NAME IS EMP-NAME-NDX
    ORDER IS SORTED
    MODE IS INDEX
        BLOCK CONTAINS 30 KEYS
        DISPLACEMENT IS 0 PAGES
    OWNER IS SYSTEM
    MEMBER IS EMPLOYEE
        MANDATORY AUTOMATIC
        INDEX DBKEY POSITION IS 4
        ASCENDING KEY IS ( EMP-LAST-NAME-0415 )
        DUPLICATES ARE LAST.

Many-to-many: the record in the middle

If you know join tables

This is exactly a join table, and spotting it in a design is most of the work of modelling your target database. The tell is simple: a record type that is a child in two relationships and a parent in none. It becomes a table keyed on both foreign keys, with its own remaining fields as payload.

CODASYL sets are strictly one-owner-to-many-members. Many-to-many is expressed by inserting a third record type that is a member of two sets at once. Recognising this pattern is the single most valuable schema-reading skill for anyone building a target model.

EMPLOYEE owner SKILL owner EXPERTISE SKILL-LEVEL, DATE EMP-EXPERTISE SKILL-EXPERTISE member of both sets · owns none · has no CALC key
The CODASYL many-to-many idiom. In the target model this is a junction table keyed on both foreign keys.

The same trick handles recursive relationships. An employee who manages other employees cannot be both owner and member of the same set occurrence, so schemas use a STRUCTURE record that is a member of a MANAGES set (owned by the manager) and of a REPORTS-TO set (owned by the subordinate). Bills of materials use exactly this shape.

Lab — walk a real set

Pick a set, pick an owner occurrence, and navigate. Watch what NEXT does at the end of the chain, and note that OBTAIN LAST is one hop when the set is LINKED TO PRIOR.

Reading a Bachman diagram

The standard notation for a network schema: boxes are record types, arrows point from owner to member, and the arrow is labelled with the set name. Here is the sample database used throughout this course.

DEPARTMENT OFFICE JOB SKILL EMPLOYEECALC EMP-ID EMPOSITIONVIA EMP-EMPOSITION EXPERTISEVIA EMP-EXPERTISE COVERAGEVIA EMP-COVERAGE INSURANCE-PLANCALC PLAN-CODE DEPT-EMPLOYEE OFFICE-EMPLOYEE EMP-EMPOSITION JOB-EMPOSITION EMP-EXPERTISE SKILL-EXPERTISE EMP-COVERAGE INS-PLAN-COVERAGE Solid box = CALC or owner record · arrow points owner → member · label = set name
Two things to read off immediately: EMPLOYEE is a member of two sets with different owners (a network, not a tree), and EXPERTISE has two owners of different types (a junction record).

Side by side with the relational model

Network (IDMS)RelationalWhere the analogy breaks
Record typeTableRecords may contain nested groups, arrays and overlays
Record occurrenceRowHas a physical address that other records store
Set typeForeign-key relationshipMaterialised as pointers; traversal is explicit and directional
Set occurrenceThe rows sharing one FK valueOrdered, and the order can carry meaning
MANDATORY membershipNOT NULL FKEnforced on DISCONNECT, not only on INSERT
AUTOMATIC membershipFK populated by the INSERT statementValue comes from currency, not from the record's own data
Junction recordAssociative tableFrequently has no key of its own
AreaTablespaceAlso the unit of READY, locking and recovery
SubschemaSchema/view + permissionsAlso restricts which navigation paths exist for a program
The deepest difference In a relational database the relationship is a value that happens to be indexed. In a network database the relationship is a structure and the value may not exist at all. That is why you can have an EMPOSITION that belongs to employee 0028 while containing nothing anywhere in its bytes that says "0028". The linkage is in the prefix, and the prefix is not user data.

What this means for replication

  • Set membership is data you must reconstruct. A change record for an EMPOSITION may carry no owner identifier. Either the capture layer resolves the owner via the prefix pointers, or your apply logic must obtain it another way. Confirm which, before design freeze.
  • Membership options become your NOT NULL decisions. Map MANDATORY to NOT NULL and OPTIONAL to nullable, and you inherit the source's integrity rules instead of inventing new ones that production data will violate.
  • Junction records map cleanly; find them first. Any record type that is a member of two sets and owns none is almost certainly an associative table in disguise.
  • Set order may be meaning, not decoration. An ORDER IS FIRST history set where the application always reads the first member is encoding "current version". If your target loses order, you lose that semantic — so materialise it as a column (a sequence, a valid-from date, a flag).
  • Orphans exist. Decide deliberately whether to carry them, drop them, or attach them to a synthetic parent. Do not let the extract method decide by accident.
Exercise 2.1 — Model the sample database relationally, then check yourself

Using only the Bachman diagram above, write the CREATE TABLE statements you would target, including nullability. Then answer:

  1. Which table has no natural primary key, and what will you use instead?
  2. Which relationship needs a junction table, and what is its key?
  3. COVERAGE is a member of two sets. Does it need one foreign key or two? Why?
  4. If DEPT-EMPLOYEE is OPTIONAL AUTOMATIC, can EMPLOYEE.DEPT_ID be NOT NULL?

Answers: (1) EMPOSITION — use a composite of employee plus start date, or a generated sequence. (2) EXPERTISE, keyed on employee plus skill. (3) Two — one to the employee who holds the coverage, one to the insurance plan it selects; losing either loses information. (4) No. An employee can legally be disconnected from every department.

Checkpoint