Graph representation in databases

i need to be able to represent an unidrected graph with an unlimited branching factor in a database. given two nodes I would need to find a path between them.

given this problem i could simply make an adjacency list and use any of those well known graph search algorithm, DFID, DFS with a cycle check, etc.

the problem is that i am doing this over teh web, and i plan to use php and mysql.
i could write an algorithm for bidirectional DFID, because i have one in lisp, but i heard that PHP cannot handle recursion that well, not to mention that it would take many queries

i learned about joe celko's nested sets, but that is for hierarchial data. i dont know how i would implement an undirected search with that.

Who says PHP cannot handle recursion well, and what was their reason?

I have never had any problem with recursion in PHP. In fact, (since you mention LISP) PHP even has the ability to do anonymous lambda-style functions. PHP also has array_walk() which recursively applies any callback function you define to every element in a nested array.

Now, I will mention that MySQL is probably not well-suited to a recursive data structure, given its limited logical capabilities, and lack of constraints or a procedural language. Have you considered PostgreSQL?

Also, you might want to search Google for references to "materialized path" and "semi-materialized path" and SQL. Again, this approach is used more for hierarchies, but it might be something you could apply to undirected graphs with a little thought.

hi rycamor,
i think i read it in an article about joe celko's nested sets on evolt.org.
http://www.sitepoint.com/print/1105
he wasn't specifying php specifically, he just said that most languages aren't suited for recursion like LISP.

i haven't considered PostgreSQL, but i think a problem would lie in any database. the basic idea is to use an adjacency list and to use php to traverse with whatever algorithm. every expansion of a node would require a mysql query. since my graphs have unlimited branching factors this cuold be costly.

thanks for the advice. im gonnare ad about it now =)

My point about PostgreSQL, or any DBMS that supports stored procedures is that the solution could be handled on the database side, rather than in the application layer.

For example, with PostgreSQL, there are several examples of stored procedures available that handle nested sets, adjacency lists, etc... This sort of thing is available to any of the "serious" SQL database systems out there, such as Oracle, MSSQL, etc... but is decidedly not available in MySQL.

PostgreSQL is especially interesting in this regard, though, because it allows for stored procedures (or functions) in several different languages, including Python and TCL, which I suspect might be nice for recursion.


That's why I mentioned "materialized path". Here is an article you might find interesting.

I know PHP (like most languages) is not as recursion-happy as LISP but still, have you tried recursion in PHP? It's not that big a problem, and as I mentioned, PHP has lambda-style anonymous functions, which are useful in recursion.

that's interesting. i never knew db's had the functionality you mentioned. so you're saying that its entriely possible to for postresql to handle this problem in the db itself with good efficiency?

im reading the article--it's great.

for my other graph, which is just a tree, i was thinking of using nested sets. after reading this article im gonna change my mind.

no i havent done recursion in php and im sure it would handle it just fine. that wasn't my main concern as much as the database problem.

im designing my site and unfortunately i signed up for a server thatu ses mysql.

would a postgresql server be very expensive?

This can be much more efficient than passing the whole dataset to the PHP application layer for processing. Keep it all in one environment, until you have the final result, which you pass out to another environment.



No, there are quite a few hosting companies that offer PostgreSQL as well as MySQL, along with PHP/Apache, etc...

See http://techdocs.postgresql.org/hosting.php

http://pghoster.com/ is probably one of the best, but also see:

http://hosting.verio.com/index.php/vps_vpscompare.html, one example of a very large hosting company that supports PostgreSQL.

Also, many PHP/MySQL hosting companies also support PostgreSQL, but just don't advertise it. (www.bodhost.com is one example, I believe)

rycamor,
i wouldn't be passing the whole dataset to php. im not sure if you are familiar with graph theory, but if you are this is what i plan to do.

basically i have two nodes and i want to find a path (if it exists) between them. the database is an adjacency list. originally i planned to use some sort of common search algorithm (DFID or BFS) with an heuristic to search. since each node has an unlimited branching factor there might be many seperate queries.

so i was basically looking at other options

1. i could think of better database schema
2. i could perform the whole search within a database.

I'm not too familiar with graph theory, but I understand that it wouldn't take the *whole* dataset to perform your search. But as you say, any method that doesn't solve it in the database would require a series of repeated queries, rather than just one query to a stored procedure.
The point is to handle the logic without repeatedly crossing the boundary between database and application layer. The simple fact of repeated queries will probably at least double the processing overheard, versus handling it inside the database.

ah i see your point, rycamor.
the thing is that even with a recursive function in sql or postresql, i dont see a way of doing it in one query--at least not with my current structure.

with my current approach, multiple queries, the WORST case scenario would be around 6,250,000 queries on an index retrieving only the ID. this scenario would rarely happen. this number depends on the user...i doubt most users will need to query this amount. best case scenario is 1

im thinking of caching the results in a cache table to reduce future repeated queries.

what do you think?

6,250,000 queries... that would take awhile...

I would be very curious to see your table structure, and some information about how you plan to implement the search algorithm.

In principle, there is nothing wrong with caching query results to a static table, as long as you have a logical method to keep your data fresh enough for your needs. Again, a DBMS which allows for triggers and stored procedures can automate this process inside the database, transparently to the application layer .

hi rycamor,
id be all for keeping it within the database but i just signed up for service that only has mysql.

the table structure is basically just an adjacncy list. so the table "node" has three int fields, nodeID, parent, and child.

the search algorithm is nothing new, it's called depth first iterative deepening.

http://www.comp.lancs.ac.uk/computi...ction3_6_4.html

it mgiht be hard to understand if you dont now about graphs, but since you know about db's and you know about nested sets, i cant try.

actually since you understand nested sets, it should be easy. you know the method that traverse the tree to get the left and right values? well that's depth first search!

it's called depth first because you go search down the tree...all the way until you hit the end and then go back up.

the other method is breadth first search where you go across the tree. think of it as iterating through each level.

both have advantages and disadvantages. depth first iterative deepening is an ingenius idea that combines the two, takign all their benefits and none of their disadvantages.

im not searching a tree, but the methods still apply

http://www.cs.sunysb.edu/~skiena/co...ons/search.html

ok rycamor,
from this discussion i have decidd to switch to a postgresql database.

quick question then since i a pgsql buddy.

if i have a statement like this

INSERT into table
SELECT ... FROM table, table 2 WHERE...

this statement is illegal in mysql since i have table in the FROM clause. i assume it is illegal in pgsql too.
with ur knowledge of functions, what wuold be a good way to accomplish this?

PostgreSQL allows the SELECT INTO TABLE syntax, which makes it even easier to move the results from any complex query into a static table. But, I believe even the syntax you asked about would be allowable in PostgreSQL too. PostgreSQL is vastly more capable of handling complex querying needs. For example, one major help in a recursive query might be the fact that SELECT statements can be nested (although, if you think about it, you can make a function that recursively calls itself, which might be even better).

Also, there are such things as constraints, views, cursors, set-returning functions, triggers, rules, domains, user-defined datatypes, all of which greatly expand your expressive power in your database.

Enjoy! And welcome to PostgreSQL .

P.S. are you familiar with the concept of triggers ( and also ) and RULEs? These can be a great help in providing automated methods to keep a caching table sychronized, for example.