Thank you for the informaiton. I did see that code but it looks like it is formatted for MSSQL and was unable to get it to work for Mysql. Tim ________________________________________ From: Andrew Ballard [aballard@xxxxxxxxx] Sent: Wednesday, July 21, 2010 11:40 AM To: Tim Gallagher Cc: php-general@xxxxxxxxxxxxx Subject: Re: Question about SQL and Graph nodel trees On Wed, Jul 21, 2010 at 11:04 AM, Tim Gallagher <tgallagher@xxxxxxxxxx> wrote: > I cannot be the only one that is having this problem, what are you using for DAG (Direct Acrylic Graph)? I need to have a mesh node edge graph and am having trouble with this? I see that Neo4j has a rest server and I can do this in Java but I want to do it in PHP with a MYSQL or postgresql. If you are doing something like this, can you please tell me how you are doing this. I can do a relationship with a parent child or a nested tree, but I need to do a DAG. > > Thanks for the help, > timgerr > A basic approach would be to use two tables - one to store the nodes and second table to store the edges between the nodes. As far as traversing the graph, the best approach I have seen expands this a bit to store the full transitive closure of the graph, rather than just the direct edges: http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx It is written for SQL Server, but the idea works OK (and I successfully tested it once) in MySQL. (I imagine the same would be true for PostgreSQL.) The idea is to store the transitive closure (every possible path) of the entire graph. For instance, if you have a basic graph A -> B -> C -> D it stores these paths: A -> B B -> C C -> D A -> C B -> D A -> D The obvious downside is that edge table can get incredibly large depending on the nature of the graph you are modeling. (The article provides much more detail.) I did, however, import a good chunk of an Active Directory tree (just users and groups, not the full list of attributes) into this pattern just to test the concept, and I found that in that case the size of the transitive closure table did not get out of hand. Andrew -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
