Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Representing a DAG (directed acyclic graph)

I need to store dependencies in a DAG. (We're mapping a new school curriculum at a very fine grained level)

We're using rails 3

Considerations

  • Wider than it is deep
  • Very large
  • I estimate 5-10 links per node. As the system grows this will increase.
  • Many reads, few writes
  • most common are lookups:
    • dependencies of first and second degree
    • searching/verifying dependencies

I know SQL, I'll consider NoSQL.

Looking for pointers to good comparisons of implementation options.

Also interested in what we can start with fast, but will be less painful to transition to something more robust/scalable later.

like image 737
Ben Sand Avatar asked Oct 10 '10 01:10

Ben Sand


2 Answers

I found this example of modeling a directed acyclic graph in SQL:

http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx?msg=3051183

like image 64
Matt Avatar answered Sep 23 '22 02:09

Matt


I think the upcoming version (beta at the moment) of the Ruby bindings for the graph database Neo4j should be a good fit. It's for use with Rails 3. The underlying data model uses nodes and directed relationships/edges with key/value style attributes on both. To scale read-mostly architectures Neo4j uses a master/slave replication setup.

like image 39
nawroth Avatar answered Sep 22 '22 02:09

nawroth