PostgreSQL - tree organization

Question

I'm working on a project wich requires a tree of categories, organized as id, parent, title table. Which are the best ways to retrieve category and its subcategories(and a full tree, if root categories have parent=0) in Postgres? I'm looking for a pure database solution, but if there is a way for Ruby and PHP - it will be great too.

The main goal is speed of select clauses, 'cause data in this table is not critical for update/insert/delete speed.

UPD: there will be also path searching, i mean path from current vertex(category) to root category.

Answer 1

retrieve category and its subcategories

If you only have a limited depth of subitems, you can do this using a self-join, eg. two levels deep:

SELECT *
FROM categories AS child
LEFT JOIN categories AS parent ON parent.id=child.parent
LEFT JOIN categories AS grandparent ON grandparent.id=parent.parent
WHERE child.id=(id) OR parent.id=(id) OR grandparent.id=(id);

You can't do this for an arbitrary-depth hierarchy using standard SQL over a ‘parent-id-foreign-key’ type schema.

Some DBMSs provide non-standard hierarchical tools that allow something like this in various ways, but if you want to stick to cross-DBMS-compatible code you'll need to rejig your schema to one of the better models of representing hierarchies. The two popular ones are:

• Nested Set. Stores a linear ordering representing a depth-first search of the tree in two columns of the target table (one of which you'll already have if your target has explicit ordering).

• Adjacency Relation. Stores each ancestor/descendent pair in a separate join table.

There are advantages and disadvantages to each approach, and numerous variants (eg. sparse nested set numbering, ‘distance’ in AR) which can affect how expensive various types of add/delete/move-position operations are. Personally I tend to gravitate towards a simplified nested set model by default as it contains less redundancy than AR.

Answer 2

Take a look at the "ltree" contrib module.