# Transitive Closure in PostgreSQL

DevFeed: [Transitive Closure in PostgreSQL](<https://devfeed.tech/articles/transitive-closure-in-postgresql-31923.md>)

Original publisher: [Read original article](<http://engineering.remind.com/Transitive-Closure-In-PostgreSQL/>)

Author: Remind

Published: 2023-09-29T00:00:00Z

Content type: tutorial

Language: en

Sources: [Remind](<https://devfeed.tech/sources/remind.md>)

Topics: [PostgreSQL](<https://devfeed.tech/topics/postgresql.md>), [Database](<https://devfeed.tech/topics/database.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [database](<https://devfeed.tech/tags/database.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [postgresql](<https://devfeed.tech/tags/postgresql.md>), [query](<https://devfeed.tech/tags/query.md>), [scale](<https://devfeed.tech/tags/scale.md>)

## AI overview

This tutorial explains how Remind models hierarchical organization data as graphs in PostgreSQL. It compares recursive queries, nested sets, and materialized transitive closure, selecting transitive closure to support efficient queries while accommodating frequent leaf-node updates.

## Source excerpt

At Remind we operate one of the largest communication tools for education in the United States and Canada. We have millions of parents, students, teachers and administrators use our application each day to improve learning outcomes by sending 10s of millions of messages per day. With this large scale usage we've had many opportunities to innovate and some of our most recent work has been around using PostgreSQL to capture graph-based structure and efficiently query them. Graphs in a relational database Our particular dataset consists of multiple organization trees. In education, most classes belong to a school and most schools belong to a district. But some classes may belong to a department, which may belong to a school, which may belong to a college, which may belong to a campus, which may belong to a university. We wanted to build a system that could not only represent these hierarchies but do so in an efficient manner. As a concrete example, here's how a middle school mach class might be represented: In our database, we store these entities as an adjacency list. Note: We store these with UUIDs, but here we'll use the names to make it easier to follow. organization parent Algebra I Maple Middle School Maple Middle School Springfield District Springfield District NULL Common query patterns we have require finding all classes in a district, or finding the district a class belongs to. Naively, we need to traverse through Maple Middle School to determine that Algebra 1 is a descendent of Springfield District. Our goal was to make such queries fast and performant while maintaining accuracy. There are a few techniques for doing this inside a PostgreSQL database: We can traverse through the adjacency list using Recursive Queries. We can use Nested Sets We can materialize the Transitive Closure. We started with option 1 but performance wasn't quite where we wanted it to be. Option 2 was a viable path, but concerns around maintenance and our update pattern (where leaf nod