Database systems · Chapter 2 · Data models

Hierarchical and network models

Before the relational model, two designs dominated. One is shaped like a tree, the other like a graph, and the difference between them comes down to a single rule: how many parents a record is allowed to have.

Tree versus graph, side by side On the left, a root record with two children, each child having exactly one parent. On the right, two parent records both pointing to one shared child record, which therefore has two parents at once. HIERARCHICAL · one parent per record A B C NETWORK · a record may have several parents X Y Z
Record Z belongs to two parents at once. In a tree that is not allowed; Z would have to be copied once for X and again for Y.

Two answers to the same problem

Both models came before SQL and both are navigational: the program walks from record to record along stored links, and it has to know the structure to find anything.

IBM built the hierarchical model first, in the mid 1960s, to manage the bill of materials for the Apollo program. The network model followed a few years later, designed in part to fix the hierarchical model's biggest limitation. Both ran production systems for decades, both are still running in some mainframe shops today, and both were eventually overtaken by the relational model for the same reason: a change to the structure meant rewriting the programs that navigated it.

What separates them is one rule. In a hierarchical database, a record has exactly one parent. In a network database, a record can have more than one. That single difference decides what each model can represent directly and what it has to fake.

The hierarchical model

A tree. Every record sits on exactly one path down from a single root, and that path is the only way to reach it.

IBM's Information Management System, first shipped in 1966, is the model most people mean when they say hierarchical. Data is organized into segments, and segments are joined by parent and child links. The topmost segment is the root. To read anything, a program starts at the root and walks down a branch, one segment at a time.

The rule that defines the model is simple: a child segment has one and only one parent. A parent segment may have many children, so one to many relationships are natural, and because the path to any record is fixed and short, retrieval along that path is fast.

Hierarchical model drawn as a tree A COLLEGE root segment above two DEPARTMENT segments, each above two COURSE segments. A professor who teaches in both departments appears twice, once under a course in each branch. same person, stored twice COLLEGE MATHEMATICS PHYSICS CALCULUS STATISTICS MECHANICS OPTICS PROF LEE PROF LEE
COLLEGE is the root. Each COURSE has exactly one DEPARTMENT above it, which is why the tree can show one to many relationships cleanly but breaks the moment a professor teaches across two departments.

What the tree cannot hold

Professor Lee teaches a statistics course in Mathematics and a mechanics course in Physics. Because a segment can have only one parent, there is no single place to store her record. She is written once under each department, and the two copies now have to be kept in agreement by hand. This is the redundancy problem the relational model exists to solve.

The network model

A graph. A record can belong to more than one owner, so the same record can sit on several paths at once.

The network model was formalized by the Conference on Data Systems Languages, through its Data Base Task Group, in a report published around 1971. It built on Charles Bachman's earlier Integrated Data Store, and it is also where the terms schema, subschema, and a separate data definition language and data manipulation language entered common use, terms the relational world later kept.

Data is still stored in records, but relationships are stored as sets. A set has one owner record type and one or more member record types, and one set occurrence is one owner together with all of the members that belong to it. The rule that defines the model is the opposite of the hierarchical one: a member record can take part in more than one set, so it can have more than one owner, and a record can be an owner in one set while being a member in another.

Network model drawn as a graph of sets DEPARTMENT owns a set of COURSE records. STUDENT owns a set of ENROLLMENT records, and COURSE also owns a set of ENROLLMENT records, so the ENROLLMENT record has two owners and links students to courses many to many. offers 1 M has 1 M takes 1 M DEPARTMENT owner COURSE member above, owner below STUDENT owner ENROLLMENT member of two sets Two one to many sets sharing one member record produce a many to many link.
ENROLLMENT is a member of the set owned by STUDENT and the set owned by COURSE at the same time. That double membership is how the network model represents many to many without duplicating any data.

What the graph can hold that the tree cannot

To connect students and courses many to many, the design adds one ENROLLMENT record for each registration and makes it a member of two sets: one owned by STUDENT, one owned by COURSE. No student record is copied, no course record is copied, and Professor Lee's earlier problem never comes up, because COURSE can be owned by more than one path into the graph as well.

The cost is complexity. A network schema can grow into a genuine web of sets, and a program still has to navigate it one pointer at a time, entering a set at its owner and stepping through its members. Changing the set structure usually means rewriting the code that walks it, which is the same structural dependence the hierarchical model has, just spread across a richer shape.

Side by side

Same questions, two different answers.

How each model answers the same design questions.
QuestionHierarchicalNetwork
Overall shapeAn inverted treeA graph, sometimes called a plex
Parents per recordExactly oneOne or many
Building blocksSegments joined by parent and child linksRecords joined by sets with one owner and one or more members
One to manyNativeNative
Many to manyOnly by duplicating data across two pathsNative, through a record that is a member of two sets
Best known systemIBM Information Management System, 1966The CODASYL Data Base Task Group standard, around 1971
How you read itStart at the root, walk down one branchStart at any owner, walk into its set

Why the relational model replaced both

Two ideas the earlier models shared turned out to be the ones worth giving up.

Both models are navigational. A query is a sequence of steps through stored pointers, and that sequence has to be written into the application. The relational model is declarative instead: a query states what result is wanted, and the system works out how to get it, which means the same request can be satisfied no matter how the data happens to be laid out underneath.

Both models also carry structural dependence. If a tree grows a new branch or a set gets a new member type, every program that walked the old structure may need to change. A relational query written against a primary key and a foreign key does not know or care how the rows are physically arranged, so the schema can grow without breaking the applications built on top of it.

Neither model disappeared without leaving something behind. The hierarchical model proved that a single database could enforce structure and serve many programs safely at once, and its tree shape came back decades later in XML and in document stores such as MongoDB. The network model gave the field the schema and subschema split, the separation of data definition from data manipulation, and the habit of describing a database through a formal standard, all of which carried straight into the relational systems that followed.