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.

I'm building site with a very simple data structure: documents that are nodes that reference other nodes that each have arrays of parents, children and siblings, so the structure is:

Node:
uuid
name [string]
description [string]
children, parents, siblings [arrays of node uuids]

What is most important is making the following query fast and easy: all nodes with uuid x in their children/parents/siblings array.

I'm considering using Riak or possibly Postgres with hstore, but would like other suggestions as to a good database designed to easily and quickly store and retrieve data with this structure.

Persistence is important, scalability is a secondary concern right now.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

You may find the ARRAY column type and associated operators help out here: you can efficiently index and query on array content, including contains and contained by operations.

PostgreSQL also features Common Table Expressions, which are an efficient and reasonably portable way to express a recursive query in a single SQL statement.

Finally, PostgreSQL has a native UUID data type that is efficient to store, index, and operate on.

Given your specified query, you should have something as simple as:

select uuid from node where ANY(children) = X OR ANY(parents) = X

There are other ways to write that - array concatenation, or array containment operations, but that is probably the simples. CTEs will allow you to extend that recursively if your tree structure query, as I anticipate, ends up needing to collect multiple levels in one operation.

In my testing both features performed well for search across a 15GB data set without substantial tuning, on an 8GB Mac laptop with slow spinning disk storage. Given your statements, I would strongly advise PostgreSQL as the conservative choice.

Again, in our testing, Riak performs well and has solid tools, but you need a three physical machine cluster to really start to see basic performance. Since you need much more persistence robustness than scalability, I think that will much less well fit your needs right now.

share|improve this answer
    
+1 good answer. I would recommend PSQL too. I would however also question Marcus as to why use UUID in such a simple data structure? Perhaps use a SEQUENCE instead by creating the id with BIGSERIAL so the the value is also a bigint. This would also be faster and more efficient. –  Ross Feb 18 '12 at 14:28
    
@Ross - I'll be creating records not only on a web app, but also on offline devices that will be synced back to the main database. As far as I know the best way to make sure there are no collisions is to use UUID's, though this is outside my area of expertise. –  Marcus Feb 18 '12 at 17:28
    
@Daniel Pittman - Thanks for the answer! I was hoping for postgres since I'm much more familiar with relational databases. This gives me a lot to go on. –  Marcus Feb 18 '12 at 17:29
1  
Using a UUID, other than a version 3/5 (MD5 or SHA1), doesn't give you a one hundred percent assurance that you won't have collisions, just a probabilistic one. If the devices have poor PRNGs you might end up with more collisions than expected unless you can use, eg, the IMEI or some other more unique input. However, you are not wrong in your statement that a UUID is a good choice, and in most cases collision risk is simply enough handled by allowing server reassignment in the unlikely case of a collision during sync. –  Daniel Pittman Feb 18 '12 at 17:30
    
@Marcus - Ok, got it. I would agree UUID would be the way to go then. UUID is perfect when you don't have an underlying guaranteed unique number generator (such as a sequence in most normal cases) .. instead you are making do with a probabilistic one. –  Ross Feb 19 '12 at 23:46
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.