Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Environment

  • PostgreSQL 9.1
  • Java

Problem

I'll try to illustrate the problem here as simply as possible:

I'm trying to record the following relationship:

Node 1 => Node 2 => Node 3

Where Node 1 is the parent of Node 2, and Node 2 is the parent of Node 3. In the database table, the initial design is tracking this data in a linked list fashion. However, I am finding this extremely inefficient because each time I want to trace the lineage of say Node 1, I'd have to retrieve Node 2, then with Node 2, I'd retrieve Node 3. Since I would be displaying the lineage of Node 1 to the user, I'd have to make 3 separate calls to the database to display this information.

I'd also like to backtrack, but for the sake of simplicity I left that part out.

Alternatives

Some alternatives I have considered, but I can't go to at this time are Neo4j and other solutions like it. Unfortunately, at this time, I have to stay in Postgresql.

Question

Is there a design pattern such that I can retrieve all this information at once? If there is, how would you implement with the example above?

UPDATE

With @MichaelT's comment, and finding Common Table Expressions, I've been lead to this link, which seems to provide more information on this: http://stackoverflow.com/questions/53108/is-it-possible-to-make-a-recursive-sql-query

share|improve this question
1  
You are looking for something like connect by prior (another example)... –  MichaelT Apr 23 '13 at 19:42
    
@MichaelT, thanks! Would this be analogous to Common Table Expressions in PostgreSQL? –  hulkmeister Apr 23 '13 at 19:45
    
No idea really... I haven't delved too far into PostgreSQL. It looks like it might, but I'd check with a database type for that db to determine if it can do what you want. –  MichaelT Apr 23 '13 at 19:49
add comment

1 Answer

up vote 2 down vote accepted

While PostgreSQL's recursive query feature might be the way to go here, your relationship is also a special case of a directed acyclic graph (DAG). Take a look at http://stackoverflow.com/questions/4074794/simple-graph-search-algorithm-in-sql-postgresql and also consider switching from PostgreSQL to a graph database, like Neo4j.

Another possibility would be to add an additional ID to each record which associates parents, children, grandchildren, etc. into families. Parents and children could share a common family ID, which would be indexed, so retrieving all related records could be done in a single (fast) query. If you include backlinks, then it doesn't matter where you start from: you can work forward and backward through the result set to order the nodes. You could also bring the entire family into RAM for fast manipulation outside of PostgreSQL. Yes, there would be some additional overhead in maintaining consistent family IDs across CRUD operations, but you might realize a net win in performance.

share|improve this answer
    
+1 for all the references and putting a name to all the ideas involved! Would the linked list (doubly linked list) structure be a way of applying the family ID record strategy? If you don't think it's the best, could you give an example? –  hulkmeister Apr 24 '13 at 3:23
    
Making a list doubly linked would not in itself provide the family ID. That requires a separate field. To do both, you'd really need four IDs: the primary key ("ID"), the parent ID (null if no parent), the child ID (null if no child), and the family ID, plus whatever other data you want to store. –  Randall Cook Apr 24 '13 at 20:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.