Adjacency List Relationships

Adjacency List Relationships

The adjacency list pattern is a common relational pattern whereby a tablecontains a foreign key reference to itself. This is the most commonway to represent hierarchical data in flat tables. Other methodsinclude nested sets, sometimes called “modified preorder”,as well as materialized path. Despite the appeal that modified preorderhas when evaluated for its fluency within SQL queries, the adjacency list model isprobably the most appropriate pattern for the large majority of hierarchicalstorage needs, for reasons of concurrency, reduced complexity, and thatmodified preorder has little advantage over an application which can fullyload subtrees into the application space.

In this example, we’ll work with a single mappedclass called Node, representing a tree structure:

class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)
    parent_id = Column(Integer, ForeignKey('node.id'))
    data = Column(String(50))
    children = relationship("Node")

With this structure, a graph such as the following:

root --+---> child1
       +---> child2 --+--> subchild1
       |              +--> subchild2
       +---> child3

Would be represented with data such as:

id       parent_id     data
---      -------       ----
1        NULL          root
2        1             child1
3        1             child2
4        3             subchild1
5        3             subchild2
6        1             child3

The relationship() configuration here works in thesame way as a “normal” one-to-many relationship, with theexception that the “direction”, i.e. whether the relationshipis one-to-many or many-to-one, is assumed by default tobe one-to-many. To establish the relationship as many-to-one,an extra directive is added known as remote_side, whichis a Column or collection of Column objectsthat indicate those which should be considered to be “remote”:

class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)
    parent_id = Column(Integer, ForeignKey('node.id'))
    data = Column(String(50))
    parent = relationship("Node", remote_side=[id])

Where above, the id column is applied as the remote_sideof the parent relationship(), thus establishingparent_id as the “local” side, and the relationshipthen behaves as a many-to-one.

As always, both directions can be combined into a bidirectionalrelationship using the backref() function:

class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)
    parent_id = Column(Integer, ForeignKey('node.id'))
    data = Column(String(50))
    children = relationship("Node",
                backref=backref('parent', remote_side=[id])
            )

There are several examples included with SQLAlchemy illustratingself-referential strategies; these include Adjacency List andXML Persistence.

Composite Adjacency Lists

A sub-category of the adjacency list relationship is the rarecase where a particular column is present on both the “local” and“remote” side of the join condition. An example is the Folderclass below; using a composite primary key, the account_idcolumn refers to itself, to indicate sub folders which are withinthe same account as that of the parent; while folder_id refersto a specific folder within that account:

class Folder(Base):
    __tablename__ = 'folder'
    __table_args__ = (
      ForeignKeyConstraint(
          ['account_id', 'parent_id'],
          ['folder.account_id', 'folder.folder_id']),
    )
 
    account_id = Column(Integer, primary_key=True)
    folder_id = Column(Integer, primary_key=True)
    parent_id = Column(Integer)
    name = Column(String)
 
    parent_folder = relationship("Folder",
                        backref="child_folders",
                        remote_side=[account_id, folder_id]
                  )

Above, we pass account_id into the remote_side list.relationship() recognizes that the account_id column hereis on both sides, and aligns the “remote” column along with thefolder_id column, which it recognizes as uniquely present onthe “remote” side.

Self-Referential Query Strategies

Querying of self-referential structures works like any other query:

# get all nodes named 'child2'
session.query(Node).filter(Node.data=='child2')

However extra care is needed when attempting to join alongthe foreign key from one level of the tree to the next. In SQL,a join from a table to itself requires that at least one side of theexpression be “aliased” so that it can be unambiguously referred to.

Recall from Using Aliases in the ORM tutorial that theorm.aliased() construct is normally used to provide an “alias” ofan ORM entity. Joining from Node to itself using this techniquelooks like:

from sqlalchemy.orm import aliased
 
nodealias = aliased(Node)
sqlsession.query(Node).filter(Node.data=='subchild1').\
                join(nodealias, Node.parent).\
                filter(nodealias.data=="child2").\
                all()
SELECT node.id AS node_id,
        node.parent_id AS node_parent_id,
        node.data AS node_data
FROM node JOIN node AS node_1
    ON node.parent_id = node_1.id
WHERE node.data = ?
    AND node_1.data = ?
['subchild1', 'child2']

Query.join() also includes a feature known asQuery.join.aliased that can shorten the verbosity self-referential joins, at the expense of query flexibility. This featureperforms a similar “aliasing” step to that above, without the need foran explicit entity. Calls to Query.filter() and similarsubsequent to the aliased join will adapt the Node entity tobe that of the alias:

sqlsession.query(Node).filter(Node.data=='subchild1').\
        join(Node.parent, aliased=True).\
        filter(Node.data=='child2').\
        all()
SELECT node.id AS node_id,
        node.parent_id AS node_parent_id,
        node.data AS node_data
FROM node
    JOIN node AS node_1 ON node_1.id = node.parent_id
WHERE node.data = ? AND node_1.data = ?
['subchild1', 'child2']

To add criterion to multiple points along a longer join, addQuery.join.from_joinpoint to the additionaljoin() calls:

# get all nodes named 'subchild1' with a
# parent named 'child2' and a grandparent 'root'
sqlsession.query(Node).\
        filter(Node.data=='subchild1').\
        join(Node.parent, aliased=True).\
        filter(Node.data=='child2').\
        join(Node.parent, aliased=True, from_joinpoint=True).\
        filter(Node.data=='root').\
        all()
SELECT node.id AS node_id,
        node.parent_id AS node_parent_id,
        node.data AS node_data
FROM node
    JOIN node AS node_1 ON node_1.id = node.parent_id
    JOIN node AS node_2 ON node_2.id = node_1.parent_id
WHERE node.data = ?
    AND node_1.data = ?
    AND node_2.data = ?
['subchild1', 'child2', 'root']

Query.reset_joinpoint() will also remove the “aliasing” from filteringcalls:

session.query(Node).\
        join(Node.children, aliased=True).\
        filter(Node.data == 'foo').\
        reset_joinpoint().\
        filter(Node.data == 'bar')

For an example of using Query.join.aliased toarbitrarily join along a chain of self-referential nodes, seeXML Persistence.

Configuring Self-Referential Eager Loading

Eager loading of relationships occurs using joins or outerjoins from parent tochild table during a normal query operation, such that the parent and itsimmediate child collection or reference can be populated from a single SQLstatement, or a second statement for all immediate child collections.SQLAlchemy’s joined and subquery eager loading use aliased tables in all caseswhen joining to related items, so are compatible with self-referentialjoining. However, to use eager loading with a self-referential relationship,SQLAlchemy needs to be told how many levels deep it should join and/or query;otherwise the eager load will not take place at all. This depth setting isconfigured via join_depth:

class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)
    parent_id = Column(Integer, ForeignKey('node.id'))
    data = Column(String(50))
    children = relationship("Node",
                    lazy="joined",
                    join_depth=2)
 
sqlsession.query(Node).all()
SELECT node_1.id AS node_1_id,
        node_1.parent_id AS node_1_parent_id,
        node_1.data AS node_1_data,
        node_2.id AS node_2_id,
        node_2.parent_id AS node_2_parent_id,
        node_2.data AS node_2_data,
        node.id AS node_id,
        node.parent_id AS node_parent_id,
        node.data AS node_data
FROM node
    LEFT OUTER JOIN node AS node_2
        ON node.id = node_2.parent_id
    LEFT OUTER JOIN node AS node_1
        ON node_2.id = node_1.parent_id
[]