RE: Question about SQL and Graph nodel trees

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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




[Index of Archives]     [PHP Home]     [Apache Users]     [PHP on Windows]     [Kernel Newbies]     [PHP Install]     [PHP Classes]     [Pear]     [Postgresql]     [Postgresql PHP]     [PHP on Windows]     [PHP Database Programming]     [PHP SOAP]

  Powered by Linux