Loading learning content...
Read aloud is unavailable in this browser.
By the late 1960s, the hierarchical model had proven its worth in production database systems, most notably through IBM's Information Management System (IMS). Organizations could faithfully represent tree-structured data—organizational charts, product catalogs, and bill-of-materials hierarchies. But as applications grew more sophisticated, a fundamental limitation became painfully apparent: the real world doesn't always organize itself into neat trees.
Consider a student enrolled in multiple courses. In a pure hierarchical model, where does this student belong? Under the Computer Science course? Under the Mathematics course? If we duplicate the student record under each course, we face data redundancy and consistency nightmares. If we choose only one parent, we lose critical relationship information. The rigid parent-child constraint of the hierarchical model—where every child has exactly one parent—simply couldn't accommodate the many-to-many relationships pervasive in real-world domains.
The network model emerged as a direct response to these limitations, offering a fundamentally different organizing principle based on graph structures rather than tree structures.
By the end of this page, you will understand: (1) How graph structures overcome the limitations of hierarchical trees, (2) The fundamental components of the network model—nodes, edges, and their semantics, (3) How multiple parentage enables many-to-many relationship modeling, (4) The formal mathematical definition of network structures, and (5) Why this architectural shift represented a significant leap in data modeling capability.
To understand why the network model represented a fundamental advancement, we must first establish the mathematical distinction between trees and graphs.
Tree Structure (Hierarchical Model):
A tree is a connected, acyclic graph in which:
Formally, for a tree with n nodes, there are exactly n-1 edges. The constraint of single parentage means that if we visualize relationships as arrows pointing from parent to child, each child has exactly one incoming arrow.
Graph Structure (Network Model):
A graph relaxes the tree constraints:
Formally, a directed graph G = (V, E) consists of a set of vertices V and a set of directed edges E ⊆ V × V. For n vertices, the number of edges can range from 0 to n² (including self-loops) or n(n-1) (excluding self-loops), vastly exceeding the n-1 edges of a tree.
| Property | Tree (Hierarchical) | Graph (Network) |
|---|---|---|
| Parent count per node | Exactly 1 (except root) | 0, 1, or many |
| Cycles | Not allowed | Permitted |
| Paths between nodes | Exactly 1 | Potentially many |
| Edge count for n nodes | Exactly n-1 | 0 to n² (directed) |
| Root requirement | Exactly one required | Not required |
| Relationship expressiveness | Limited (1:N only) | Full (M:N supported) |
| Navigation complexity | Simple—follow parent/child | Complex—multiple paths possible |
The Modeling Implications:
This seemingly simple mathematical relaxation—allowing multiple parents—has profound implications for data modeling:
Many-to-Many Relationships: A student can be linked to multiple courses while each course remains linked to multiple students. Neither entity must be designated as the "owner."
Shared Subordinates: A component that appears in multiple products need not be duplicated. A single part record can be referenced by multiple parent assemblies.
Network Semantics: Real-world networks—social connections, transportation routes, supply chains—can be modeled naturally without artificial decomposition.
Reference vs. Containment: Rather than physically nesting data (containment), the network model allows referencing the same data from multiple contexts.
The single most important difference between hierarchical and network models is multiple parentage. This one change transforms the data model from representing trees to representing arbitrary directed graphs, enabling a leap in expressiveness that unlocks domains previously inaccessible to database management.
The network model introduces specific terminology for its graph-based structure. Understanding this vocabulary is essential for comprehending network database systems and the CODASYL standard that formalized them.
Record Types (Nodes):
A record type in the network model is analogous to an entity type in the ER model or a table in the relational model. It defines a template for storing related data items.
Key characteristics:
12345678910111213141516171819202122
RECORD TYPE: STUDENTDATA ITEMS: StudentID : INTEGER Name : CHARACTER(50) DateOfBirth : DATE Major : CHARACTER(30) GPA : DECIMAL(3,2) RECORD TYPE: COURSEDATA ITEMS: CourseCode : CHARACTER(10) Title : CHARACTER(100) Credits : INTEGER Department : CHARACTER(30) MaxEnrollment : INTEGER RECORD TYPE: INSTRUCTORDATA ITEMS: InstructorID : INTEGER Name : CHARACTER(50) Department : CHARACTER(30) OfficeLocation : CHARACTER(20)Set Types (Edges):
A set type defines a named one-to-many (1:N) relationship between two record types. Despite the network model supporting many-to-many relationships conceptually, each individual set is a 1:N link. Many-to-many relationships are constructed by chaining multiple set types through an intermediate record type.
Set type components:
The term "set" is somewhat misleading mathematically—it's really an ordered collection (potentially with insertion order semantics) rather than an unordered mathematical set.
1234567891011121314151617181920212223
SET TYPE: DEPT_INSTRUCTOR OWNER: DEPARTMENT MEMBER: INSTRUCTOR ORDER: SORTED BY Instructor.Name -- Links each department to its instructors SET TYPE: DEPT_COURSE OWNER: DEPARTMENT MEMBER: COURSE ORDER: FIRST (insert at beginning) -- Links each department to its courses SET TYPE: COURSE_ENROLLMENT OWNER: COURSE MEMBER: ENROLLMENT ORDER: LAST (insert at end) -- Links each course to enrollment records SET TYPE: STUDENT_ENROLLMENT OWNER: STUDENT MEMBER: ENROLLMENT ORDER: SORTED BY Enrollment.EnrollmentDate -- Links each student to enrollment recordsThe key insight is that a single member record can belong to multiple sets of different types. The ENROLLMENT record above is a member of both COURSE_ENROLLMENT and STUDENT_ENROLLMENT sets. This dual membership is what creates the many-to-many relationship between STUDENT and COURSE—the graph structure emerges from overlapping set memberships.
Abstract graph theory becomes tangible when we visualize network structures. Let's examine how the network model represents a university domain, contrasting it with how the same domain would be constrained in a hierarchical model.
The University Domain:
Consider these real-world facts:
Key Observations in the Diagram:
ENROLLMENT as an Intersection Record: The ENROLLMENT record type has two owners—it belongs to both the COURSE_ENROLLMENT set and the STUDENT_ENROLLMENT set. This is the network model's technique for representing M:N relationships.
Multiple Set Memberships: Notice how COURSE is both a member (of DEPT_COURSE and TEACHES) and an owner (of COURSE_ENROLLMENT). Records can simultaneously play both roles.
No Single Root: Unlike hierarchical structures, there's no designated root. The structure forms a directed graph that can be navigated from any entry point.
Cycle Potential: If instructors could also be students (e.g., graduate teaching assistants), we could create a cycle: STUDENT → ENROLLMENT → COURSE → TEACHES → INSTRUCTOR → (back to STUDENT if instructor-student link existed).
Graph structures in network databases aren't merely conceptual—they're implemented through physical pointer chains stored directly in the database. Understanding this implementation illuminates both the power and the challenges of the network model.
Set Implementation via Linked Lists:
Each set occurrence (an owner with its members) is typically implemented as a circular linked list:
12345678910111213141516171819202122232425262728293031323334353637383940414243
SET OCCURRENCE EXAMPLE: DEPT_INSTRUCTOR set for "Computer Science" department ┌─────────────────────────────────────────────────────────────────────┐│ OWNER RECORD: DEPARTMENT "Computer Science" ││ ┌───────────────────────────────────────────────────────────────┐ ││ │ DeptID: "CS" │ ││ │ Name: "Computer Science" │ ││ │ Building: "Engineering Hall" │ ││ │ FIRST_MEMBER_PTR: ──────────────────────────────────────────┐ │ ││ └───────────────────────────────────────────────────────────┐ │ │ │└──────────────────────────────────────────────────────────────┼─┼─┘ │ │ │ ┌──────────────────────────────────────────────────────────┘ │ │ │ ▼ │┌─────────────────────────────────────────────────────────────┐ ││ MEMBER 1: INSTRUCTOR "Dr. Alice Chen" │ ││ ┌───────────────────────────────────────────────────────┐ │ ││ │ InstID: 101 │ │ ││ │ Name: "Dr. Alice Chen" │ │ ││ │ Office: "EH-301" │ │ ││ │ OWNER_PTR: ──────────────────────────────────────────────────┘│ │ NEXT_MEMBER_PTR: ─────────────────────────────────────────┐│ └───────────────────────────────────────────────────────┘ │└──────────────────────────────────────────────────────────────┘ │ ┌──────────────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────────────────┐│ MEMBER 2: INSTRUCTOR "Dr. Bob Martinez" ││ ┌───────────────────────────────────────────────────────┐ ││ │ InstID: 102 │ ││ │ Name: "Dr. Bob Martinez" │ ││ │ Office: "EH-305" │ ││ │ OWNER_PTR: → (points back to DEPARTMENT "CS") │ ││ │ NEXT_MEMBER_PTR: → (points to next member or owner) │ ││ └───────────────────────────────────────────────────────┘ │└──────────────────────────────────────────────────────────────┘ │ │ ... more members ... │ └──→ (circular: last member's NEXT_PTR → back to owner)Dual Set Membership Illustrated:
When a record belongs to multiple sets, it participates in multiple pointer chains simultaneously. The ENROLLMENT record demonstrates this complexity—it contains pointers for both the COURSE_ENROLLMENT set and the STUDENT_ENROLLMENT set:
12345678910111213141516171819202122232425262728293031
ENROLLMENT RECORD with DUAL SET MEMBERSHIP: ┌──────────────────────────────────────────────────────────────────────┐│ ENROLLMENT RECORD ││ ┌────────────────────────────────────────────────────────────────┐ ││ │ EnrollmentID: 50001 │ ││ │ Grade: "A" │ ││ │ Semester: "Fall 2024" │ ││ │ EnrollmentDate: 2024-08-15 │ ││ │ │ ││ │ // COURSE_ENROLLMENT set pointers │ ││ │ COURSE_OWNER_PTR: → COURSE "CS101" │ ││ │ COURSE_NEXT_PTR: → next ENROLLMENT in CS101 │ ││ │ COURSE_PREV_PTR: → prev ENROLLMENT in CS101 (if doubly-linked)│ ││ │ │ ││ │ // STUDENT_ENROLLMENT set pointers │ ││ │ STUDENT_OWNER_PTR: → STUDENT "John Smith" │ ││ │ STUDENT_NEXT_PTR: → next ENROLLMENT for John │ ││ │ STUDENT_PREV_PTR: → prev ENROLLMENT for John (if doubly-linked)│ ││ └────────────────────────────────────────────────────────────────┘ │└──────────────────────────────────────────────────────────────────────┘ This single ENROLLMENT record is simultaneously: - A member of the CS101 course's enrollment set (linked with other CS101 enrollments) - A member of John Smith's enrollment set (linked with John's other course enrollments) Traversal from COURSE "CS101": CS101 → FIRST_MEMBER → ENROLL_50001 → NEXT → ENROLL_50002 → ... → (back to CS101) Traversal from STUDENT "John Smith": John → FIRST_MEMBER → ENROLL_50001 → NEXT → ENROLL_50007 → ... → (back to John)Each set membership requires additional pointer storage in the member record. A record belonging to N sets contains roughly 2N to 3N extra pointer fields (owner pointer plus chain pointers). This overhead is significant—it's one reason relational databases, which avoid explicit pointers, eventually dominated the market.
The network database schema formally defines the complete graph structure—all record types, their fields, and all set relationships between them. This schema is typically defined using a Data Definition Language (DDL) that became standardized through CODASYL.
Schema Components:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
SCHEMA NAME IS UNIVERSITY_DB RECORD NAME IS DEPARTMENT LOCATION MODE IS CALC USING DeptID DUPLICATES ARE NOT ALLOWED 02 DeptID TYPE IS CHARACTER 10 02 DeptName TYPE IS CHARACTER 50 02 Building TYPE IS CHARACTER 30 02 Budget TYPE IS DECIMAL 12 RECORD NAME IS INSTRUCTOR LOCATION MODE IS VIA DEPT_INSTRUCTOR SET 02 InstructorID TYPE IS DECIMAL 8 02 Name TYPE IS CHARACTER 50 02 HireDate TYPE IS DATE 02 Salary TYPE IS DECIMAL 10 02 Office TYPE IS CHARACTER 20 RECORD NAME IS COURSE LOCATION MODE IS CALC USING CourseCode 02 CourseCode TYPE IS CHARACTER 10 02 Title TYPE IS CHARACTER 100 02 Credits TYPE IS DECIMAL 2 02 Description TYPE IS CHARACTER 500 RECORD NAME IS STUDENT LOCATION MODE IS CALC USING StudentID 02 StudentID TYPE IS DECIMAL 10 02 Name TYPE IS CHARACTER 50 02 DateOfBirth TYPE IS DATE 02 Major TYPE IS CHARACTER 30 02 GPA TYPE IS DECIMAL 3 RECORD NAME IS ENROLLMENT LOCATION MODE IS VIA COURSE_ENROLLMENT SET 02 EnrollmentDate TYPE IS DATE 02 Grade TYPE IS CHARACTER 2 02 Semester TYPE IS CHARACTER 20 SET NAME IS DEPT_INSTRUCTOR OWNER IS DEPARTMENT ORDER IS SORTED BY DEFINED KEYS MEMBER IS INSTRUCTOR KEY IS Name ASCENDING INSERTION IS AUTOMATIC RETENTION IS MANDATORY SET SELECTION IS THRU CURRENT OF DEPT_INSTRUCTOR SET NAME IS DEPT_COURSE OWNER IS DEPARTMENT ORDER IS SORTED BY DEFINED KEYS MEMBER IS COURSE KEY IS CourseCode ASCENDING INSERTION IS MANUAL RETENTION IS OPTIONAL SET SELECTION IS BY APPLICATION SET NAME IS COURSE_ENROLLMENT OWNER IS COURSE ORDER IS LAST MEMBER IS ENROLLMENT INSERTION IS AUTOMATIC RETENTION IS FIXED SET SELECTION IS STRUCTURAL SET NAME IS STUDENT_ENROLLMENT OWNER IS STUDENT ORDER IS SORTED BY DEFINED KEYS MEMBER IS ENROLLMENT KEY IS EnrollmentDate ASCENDING INSERTION IS AUTOMATIC RETENTION IS FIXED SET SELECTION IS STRUCTURALUnderstanding the network model deeply requires connecting it to fundamental graph theory concepts. These formal foundations explain both the power and the computational characteristics of network databases.
Directed Graphs (Digraphs):
Network database structures form directed graphs—graphs where edges have direction (from owner to member). Key properties:
| Graph Theory Term | Network Database Equivalent | Example |
|---|---|---|
| Vertex/Node | Record occurrence | A specific STUDENT record |
| Directed Edge | Set membership (owner→member) | DEPT→INSTRUCTOR link |
| Path | Navigation sequence through sets | DEPT→COURSE→ENROLLMENT→STUDENT |
| Cycle | Circular navigation possible | STUDENT→ENROLLMENT→COURSE→TA→STUDENT |
| Degree | Set participations (owner+member) | ENROLLMENT: in-degree=2, out-degree=0 |
| Connected Component | All reachable records from a starting point | All data linked to a DEPARTMENT |
| DAG (Directed Acyclic) | Network without cycles | Typical organizational hierarchies |
Connectivity and Reachability:
One of the most significant graph properties for databases is reachability—which records can be accessed from a given starting point by following set links?
Definition: Record B is reachable from Record A if there exists a path:
A → X₁ → X₂ → ... → Xₙ → B
where each arrow represents traversing a set (in either direction: owner→member or member→owner)
In a well-designed network database:
Path Length and Access Efficiency:
The shortest path length between two records directly impacts query performance:
Network database designers optimize the schema to minimize path lengths for common query patterns while maintaining semantic accuracy.
Network database schema design is fundamentally graph structure design. The goal is to create a graph where frequently-needed navigation paths are short and efficient, while accurately representing real-world entity relationships. This dual optimization—performance and correctness—defines the network database design challenge.
The graph structure of the network model provided substantial advantages over hierarchical systems, addressing many real-world modeling challenges:
1. Natural Many-to-Many Representation:
The most significant advantage is native support for M:N relationships through intersection records with multiple set memberships. This maps naturally to:
2. Elimination of Data Redundancy:
By allowing multiple parents (owner records), shared entities need only be stored once. A supplier used by multiple purchasing departments exists as a single record, linked via sets to each department—not copied into each.
Network structures shine in domains with: (1) Complex many-to-many relationships, (2) Frequent traversal-based queries following relationships, (3) Stable schema that won't require frequent restructuring, (4) High-volume transaction processing needing predictable performance.
However, graph structures introduce: (1) Schema rigidity—changing relationships means restructuring pointers, (2) Navigation complexity—programmers must understand the full graph, (3) Pointer overhead—storage cost for link maintenance, (4) System dependency—pointer values are internal identifiers.
We've explored the fundamental architectural decision that distinguishes network databases from their hierarchical predecessors: the shift from tree structures to graph structures.
What's Next:
Understanding the graph structure provides the foundation. Next, we'll explore CODASYL—the committee that standardized the network model, creating the specifications that governed commercial network database systems like IDMS, IDS II, and DMS-1100. We'll see how they formalized set operations, navigation primitives, and data manipulation in a comprehensive standard that shaped database technology for decades.
You now understand the graph-based architecture that defines the network data model. The ability to model many-to-many relationships through multiple set memberships was revolutionary, enabling database systems to faithfully represent complex real-world domains that hierarchies could not capture. Next, we'll examine how CODASYL standardized these concepts.