Hacker News Reader

Comment by lijogdfljk | Hacker News Reader

Anyone have a recommended resource for understanding the practical application of recursive CTEs / Graph DBs?

Look for a good reference about handling trees in SQL. There are a number of books on the whole area, and many smaller more focused articles online.

The most common place I've encountered recursive CTEs being massively useful in real world work is working with company responsibility & reporting hierarchies (line management, regulatory supervision, "spans of control" reporting, ...) where there is not a fixed number of levels.

When there are a small and fixed number of levels (for instance every drone has a supervisor and senior supervisor and you don't monitor connections above that) there are often other solutions that people find easier to understand and/or perform faster but for deeper trees or those where the level structure is any less static, recursive CTEs are a godsend.

Other examples include nested taxonomies (nature, book or other publication filing, nested tags for categorisation), properly threaded discussion records, family trees (though these are graphs rather than trees unless you impose some strict limits on what you count), representing file-system like structures in the DB, ...

Graphs get tricker (trees are a subset of graphs) as you may need to consider multiple paths to the same node, infinite loops, and other complications, so I suggest looking into trees first then expending your research.

Going out on a limb here because your question can be interpreted in multiple ways and I only feel qualified to answer one of them:

The most common example for graphs in DBs would be a graph representing the friends/contacts of users. It's one of these "you'll know when you need it" solutions.

Sometimes your data structure is a graph, and sometimes you want that graph to live in a database.

And in even rarer cases you want to search that graph in your database in some recursive manner.

What about representing states? Not sure about how graph dbs could perform on that scenario. There is a recent post talking about the topic and I'm still thinking about the best solution to store flows or similar. https://news.ycombinator.com/item?id=24764303

Recursive Common Table Expressions (CTE) are hard to understand until you've worked through at least one real-world example. The SQLite documentation on the WITH Clause has a couple of simple examples [1] for an Org Chart and a Family; both represent hierarchical data structures.

The Fossil discussion involves the SCM's representation of a File System, probably the most common hierarchical data structure we regularly encounter. Hierarchical data structures are notoriously hard in SQL. Recursive CTEs are not easy but they are useful and efficient for hierarchical data.

[1] https://www.sqlite.org/draft/lang_with.html#hierarchical_que...

Another good writeup is included in the SQL Anywhere documentation [1] which has a good example of a parts explosion problem [2]. I don't know if the syntax works in SQLite but it might be a good exercise to get it to work.

[1] http://dcx.sap.com/1200/en/dbusage/ug-commontblexpr.html

[2] http://dcx.sap.com/1200/en/dbusage/parts-explosion-cte-sqlug...

I've used them (in postgresql) to evaluate the merging of "parent" and "child" values - e.g. one row can be parent, and if the child has NULL for value it takes it from the parent (though do not remember much of the details). This can go to deeper just first parent, but parent of parent too.

I was able to make a query like this in PostgreSQL, but forgot the details of how I did it (though once you sit down, you get it eventually).

In the past I used recursive CTEs in Postgres to calculate the BOM of a product. Products consisted of "parts", and each "part" had a cost and could consist of any number of other "parts" (subassemblies). This was for a homemade ERP resembling software.

While the end result looks like a graph, I think that still qualifies as a standard relational DB use case though?

A graph database usually means you’re storing the graph nodes and edges as entities, so you can traverse the graph easily from any direction, and express different kinds of relationships.

Yeah, wasn't trying to say this was an example of graph. Maybe it is slightly outside what would be considered "standard" relational DB use case? My impression of recursive CTE's in RDBMS is that if you need speed or any more advanced graph-like features, you should move to an actual graph db. So far I haven't taken on any projects that warranted that, though it does interest me.

Either way my intention here was to simply provide an example of a real-world recursive CTE use case.

One application not mention in this thread is to traverse trees, like in the old forums where you had many levels of categories/subcategories. AKA hierarchical query. SQLite already has support for this[0]. It seems they are supporting multiple selects now.

[0] https://sqlite.org/lang_with.html

Yes, chapter 2 in Martin Kleppmann's Designing Data-Intensive Applications.

Reply on news.ycombinator.com