Efficiently querying forests (multiple trees)

[Kurtis Mullins]

Hello,

I am looking for advice on efficiently constructing a forest of tree-structures where each object/row has the following format:

class Node(Base):
    id = Column(Integer, primary_key=True)
    parent_id = Column(Integer, ForeignKey('parent.id'))
    parent = relationship('Node', back_populates='children')
    children = relationship('Node')

The primary database target is Postgres but I would also like to stay compatible with sqlite if feasible.

At the moment, my sample table is relatively small (less than 500 rows) so I experimented with the following approach:

• Fetch all rows
• Create a list of all root nodes (those without a parent_id)
• Recursively attempt to insert all rows into the forest/trees

I foresee the following issues:

1. It is an expensive query.
2. It will not scale well.
   
3. I don't foresee any easy way to fetch multiple trees, or multiple sub-trees, without running this entire query+algorithm.
4. I have to convert from SQL Alchemy objects to dictionaries, in order to manually populate the "children" lists.

Here are the types of queries I hope to more efficiently perform:

• Select the entire "forest". Basically, `select all` with preloading.
• Select a whole tree based on a child node multiple levels deep. 
• Select a sub-tree where a given node will become the root.
• Select multiple trees based on multiple child odes.

I am trying to avoid double-linked or other complex data-structures where managing the state becomes more complicated and error-prone.

If anyone can give me pointers or recommendations, I would appreciate it.

Thanks!

[Benoit Barthelet]

I'd use ltree postgresql extension, but I have no idea if there is an option for sqlite, 

--
SQLAlchemy -
The Python SQL Toolkit and Object Relational Mapper
 
http://www.sqlalchemy.org/
 
To post example code, please provide an MCVE: Minimal, Complete, and Verifiable Example. See http://stackoverflow.com/help/mcve for a full description.
---
You received this message because you are subscribed to the Google Groups "sqlalchemy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sqlalchemy+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sqlalchemy/e8900b03-e918-4a26-a352-2c4ef0ded07b%40googlegroups.com.