Thread: Implementing hierarchy

I am trying to write code to access a product catalog (more as a learning
exercise than anything else) and need to implement some sort of searchable
hierarcy.  For example:

Computer Hardware (toplevel)
   Hard Drives
      Internal
         SCSI
            Fast SCSI
            Wide SCSI
            SCA

Assuming these 'categories' are all in the same table as follows:

prkey    (primary key)
descr    varchar
parent    (for subcategories, toplevel parent is 0)

Is it possible to formulate an SQL query to give me the hierarchy for SCA
hard drives?  (with "Computer Hardware", "Hard Drives", "SCSI", "SCA" in
the result set)  I've been experimenting with self-joins, but cannot see
how to extend it for an arbitrary number of subcategories.  If I have the
primary key for an item listed as being an "SCA hard drive", how do I get
it's parents (subcategories and toplevel parent)?

Pointers to documentation/books/web sites with this sort of information
are greatly appreciated.

Much thanks in advance.

Mike.


======================================================================
  Mike Frisch                         Email: mfrisch@saturn.tlug.org
  Northstar Technologies        WWW: http://saturn.tlug.org/~mfrisch
  Newmarket, Ontario, CANADA
======================================================================

I have a similar problem. I can tell you how to get subcategories and
sub-sub categories with unions and self-joins, but it sounds like you've
already worked that out. I don't know how to get sub-categories down to
an arbitrary depth (I think this is the crux of your question), so I
have joins that go down several levels, as many as I need.


Mike Frisch wrote:
>
> I am trying to write code to access a product catalog (more as a learning
> exercise than anything else) and need to implement some sort of searchable
> hierarcy.  For example:
>
> Computer Hardware (toplevel)
>    Hard Drives
>       Internal
>          SCSI
>             Fast SCSI
>             Wide SCSI
>             SCA
>
> Assuming these 'categories' are all in the same table as follows:
>
> prkey   (primary key)
> descr   varchar
> parent  (for subcategories, toplevel parent is 0)
>
> Is it possible to formulate an SQL query to give me the hierarchy for SCA
> hard drives?  (with "Computer Hardware", "Hard Drives", "SCSI", "SCA" in
> the result set)  I've been experimenting with self-joins, but cannot see
> how to extend it for an arbitrary number of subcategories.  If I have the
> primary key for an item listed as being an "SCA hard drive", how do I get
> it's parents (subcategories and toplevel parent)?
>
> Pointers to documentation/books/web sites with this sort of information
> are greatly appreciated.
>
> Much thanks in advance.
>
> Mike.
>
> ======================================================================
>   Mike Frisch                         Email: mfrisch@saturn.tlug.org
>   Northstar Technologies        WWW: http://saturn.tlug.org/~mfrisch
>   Newmarket, Ontario, CANADA
> ======================================================================

> I am trying to write code to access a product catalog (more as a learning
> exercise than anything else) and need to implement some sort of searchable
> hierarcy.  For example:
>
> Computer Hardware (toplevel)
>    Hard Drives
>       Internal
>          SCSI
>             Fast SCSI
>             Wide SCSI
>             SCA
>
> Assuming these 'categories' are all in the same table as follows:
>
> prkey (primary key)
> descr varchar
> parent (for subcategories, toplevel parent is 0)

I don't know if there is a 'right' way to do this, but I have done something
similar having an extra table that contains a tuple listing (node, ancestor)
pairs.  This is kept in sync with the main table using a couple of triggers.
The code is at the end

A sequence is used for the primary key in the main table, and the hierarchy
is then implicit since you can't create a child before the parent (at least
my application doesn't let you move an existing child to another parent).

Rob


---

CREATE TABLE places (
 id      INT4 DEFAULT NEXTVAL('places_seq') PRIMARY KEY,
 name    TEXT NOT NULL,
 parent  INT4 DEFAULT 0
);

CREATE TABLE places_tree (
 place    INT4,
 ancestor INT4,
 PRIMARY KEY (place, ancestor)
);

CREATE FUNCTION explode_place () RETURNS OPAQUE AS
' DECLARE
    row      places_tree%ROWTYPE;
  BEGIN

    FOR row IN SELECT * FROM places_tree WHERE place = NEW.parent LOOP
      INSERT INTO places_tree VALUES (NEW.id, row.ancestor);
    END LOOP;

    IF NEW.parent <> 0 THEN
      INSERT INTO places_tree VALUES (NEW.id, NEW.parent);
    END IF;

    RETURN NEW;
  END;

' LANGUAGE 'plpgsql';

CREATE FUNCTION implode_place () RETURNS OPAQUE AS
' DECLARE
    row      places_tree%ROWTYPE;
  BEGIN

    DELETE FROM places_tree WHERE place = OLD.id;

    FOR row IN SELECT * FROM places_tree WHERE ancestor = OLD.id LOOP
      DELETE FROM places WHERE id = row.place;
    END LOOP;

    RETURN OLD;
  END;

' LANGUAGE 'plpgsql';

CREATE TRIGGER explode_place_trigger AFTER INSERT ON places FOR EACH ROW
  EXECUTE PROCEDURE explode_place();

CREATE TRIGGER implode_place_trigger BEFORE DELETE ON places FOR EACH ROW
  EXECUTE PROCEDURE implode_place();