Modeling Networks and Graph-Like Relationships

Learning outcomes

A hierarchy is a constrained graph: each node usually has one parent and cycles are forbidden. Many real domains are more general. Roads connect locations, Parts depend on other Parts, users follow users, technicians have skill dependencies, and assets can participate in network topologies. Relational databases can model these graphs, but the right design depends on traversal depth and query patterns.

Node-edge model

Node(  node_id,  node_type,  ...)Edge(  edge_id,  from_node_id,  to_node_id,  edge_type,  ...)

This generic pattern is flexible but sacrifices some semantic typing.

Domain-specific edge tables

Often clearer:

PartDependency(  part_id,  depends_on_part_id,  dependency_type)

Both columns reference Part.

Directed relationships

A depends on B is directional:

Reversing the edge changes meaning.

Undirected relationships

For “locations are connected,” A-B may be equivalent to B-A. Store one canonical orientation:

CHECK (location_a_id < location_b_id)

when IDs are comparable and this canonicalization suits the domain.

Weighted edges

RoadEdge(  from_location_id,  to_location_id,  distance_km,  travel_minutes,  toll_cost)

Different weights support different path algorithms.

Typed edges

A single pair of nodes may have multiple relationship meanings. Avoid collapsing semantically distinct relationships into an ambiguous generic link if domain-specific constraints matter.

Multiple edges

Two locations may have several roads. A composite uniqueness rule on endpoints alone would be wrong if parallel edges are meaningful.

Self-edges

Decide whether:

from_node_id = to_node_id

is legal. Many dependency graphs should forbid self-dependency.

Cycles

Some graphs allow cycles:

Others, such as prerequisite/dependency DAGs, must forbid them.

DAGs

A directed acyclic graph can represent:

• build dependencies;
• course prerequisites;
• manufacturing dependencies;
• approval dependencies.

Cycle detection becomes a business invariant.

Recursive traversal

WITH RECURSIVE reachable AS (  SELECT to_node_id  FROM edge  WHERE from_node_id = :start  UNION  SELECT e.to_node_id  FROM edge e  JOIN reachable r    ON e.from_node_id = r.to_node_id)SELECT * FROM reachable;

Use cycle guards and depth limits where appropriate.

Shortest path

Relational SQL can express some path logic, but weighted shortest-path algorithms are often cumbersome and engine-specific. If graph traversal dominates the workload, specialized graph capabilities may be justified.

Graph versus hierarchy

WorkshopHub graph-like examples

• Part substitutes and compatible alternatives;
• Part dependency graph for assemblies;
• service-center routing network;
• technician mentorship network;
• asset component connectivity.

Use domain-specific schemas when possible

Instead of one universal Edge table, these may be clearer:

PartSubstitute(part_id, substitute_part_id)PartDependency(part_id, depends_on_part_id)LocationRoute(from_location_id, to_location_id, distance_km)

Each table can enforce domain-specific constraints and attributes.

When relational is enough

Relational modeling is often sufficient when:

• traversal depth is small;
• graph queries are occasional;
• transactional integrity with other relational data dominates;
• recursive CTEs meet performance needs.

When graph tooling may help

Consider graph-specific systems when:

• multi-hop traversal is the dominant workload;
• path algorithms are frequent;
• relationship patterns change dynamically;
• graph centrality/community queries matter;
• relational recursive queries become operationally awkward.

Practice: tree or graph?

Chapter 14 synthesis

time:events + effective intervals + historytrees:adjacency listnested setsmaterialized pathclosure tablegraphs:nodes + typed edges + traversal rules

Summary and next chapter

Chapter 14 extended database design across time and recursive structure. You can now model effective dates and event history, preserve slowly changing operational data, represent hierarchies with several relational patterns, and model graph-like networks when trees are insufficient. Chapter 15 moves into semi-structured and polymorphic data: JSON, flexible attributes, polymorphic associations, EAV models, and hybrid relational/document designs.

References

• Joe Celko, Trees and Hierarchies in SQL for Smarties.
• Richard T. Snodgrass, temporal database literature.
• Martin Kleppmann, Designing Data-Intensive Applications.
• Database vendor documentation on recursive SQL and graph extensions.