O'Reilly logo

The Art of SQL by Peter Robson, Stephane Faroult

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Representing Trees in an SQL Database

Trees are generally represented in the SQL world by one of three models:

Adjacency model

The adjacency model is thus called because the identifier of the closest ancestor up in the hierarchy (the parent row) is given as an attribute of the child row. Two adjacent nodes in the tree are therefore clearly associated. The adjacency model is often illustrated by the employee number of the manager being specified as an attribute of each employee managed. (The direct association of the manager to the employee is in truth a poor design, because the manager identification should be an attribute of the structure that is managed. There is no reason that, when the head of a department is changed, one should update the records of all the people who work in the department to indicate the new manager). Some products implement special operators for dealing with this type of model, such as Oracle's connect by (introduced as early as Oracle version 4 around the mid 1980s) or the more recent recursive with statement of DB2 and SQL Server. Without any such operator, the adjacency model is very hard to manage.

Materialized path model

The idea here is to associate with each node in the tree a representation of its position within the tree. This representation takes the form of a concatenated list of the identifiers of all the node's ancestors, from the root of the tree down to its immediate parent, or as a list of numbers indicating the rank within siblings ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required