database model for acyclic directed graph

From: Andreas Schmidt <andreas.schmidt_at_team-konzept.de>
Date: 25 Apr 2002 05:49:53 -0700
Message-ID: <54522a18.0204250449.4117b35a_at_posting.google.com>

i'm developing an application which needs to hold several acyclic directed graphs in a database. the most needed function is: give me the path(es) between node a and b. so i'm looking for a representation that allows me to receive all nodes of all pathes with one query.

i'm quite familiar with the "nested set" database model for trees which would fit perfect, if i had just trees. so i wonder, whether there is equivalent to the nestes set-model for acyclic directed graphs.

i found myself one solution: instead of managing the directed graph in the database, i put the traversing-path of the directed graph (like in the nested set model) in the database. this path would be a tree, so i could nearly reuse the queries for "give me the path...". even if the table could get quite big (because it would hold each subgraph for each incoming edge of the starting node) this would be acceptable, because i would put the "node-data" in a second table, so it would be just a huge amount of integers.

unfortunately i cann't reuse the queries for adding new nodes or deleting or moving nodes/subtrees, and there was no need to add edges to existing nodes with trees. i started to write my own queries, but after a while i stopped because they got too complicated (for me).

so:
a) does anyone know a good and efficient solution for my purpose or
b) has anyone a set of queries for the basic tree-operations for my nested-set-based approach

the solutions should not use database specific extensions to sql 92 because my application should run in different environments. my development database is postgres, where it should run at least.

thanks for your help,
andi Received on Thu Apr 25 2002 - 14:49:53 CEST