mercredi 8 avril 2015

Determine the children nodes from a DAG in a SQLite database

I have as input an SQLite database of a directed acyclic graph (not necessarily connected) where the nodes are stored as



node_id | name
1 | a
2 | b
3 | c
4 | d
5 | e
6 | f


and the edges are stored as:



edge_id | source | target
1 | 1 | 2
2 | 1 | 3
3 | 1 | 4
4 | 2 | 5


This is a toy example, my database has about 10^4 to 10^5 nodes (small but not trivially so). I need to query all of the "children" nodes from a given node. As an example:



input | expected output
1 | [2,3,4,5]
2 | [5]
3 | []
6 | []


I am using python's SQLite3 module to do this now, but I have to recursively make a select call for each node -- this can get prohibitively expensive. Is there a smart way to do this, perhaps with a single SQLite call?


Aucun commentaire:

Enregistrer un commentaire