Postgres Pro
Downloads
Home   >   mailing lists

Thread: Tables Referencing themselves As Foreign Keys

Tables Referencing themselves As Foreign Keys

From
"Tony (Unihost)"
Date:
Hi,

I'm still new to this so if I'm sounding dumb or my premise is flawed
please forgive me.  I have a DB design which contains a table which has
categories, each category has a parent category, and is recursed until
the top category is reached, in order to create breadcrumbs.  Is there
any problem with using foreign keys to reference the same table?  So a
when category is added the CatParent MUST be present as a CatID

CatID - Serial
CatParent - int4 - References CatID
CatName - Text

Am I likeley to come unstuck with this?

Cheers

T.

Re: Tables Referencing themselves As Foreign Keys

From
Arjen van der Meijden
Date:
Tony,

That'll work, but you have to mind the first row/toprow you insert.
Will it have no parent (make the field nullable) or will it be its own
parent (you'll have to test whether that works, I don't know, foreign
keys are deferrable, so it should be possible if you specify that).

Best regards,

Arjen

Tony (Unihost) wrote:

> Hi,
>
> I'm still new to this so if I'm sounding dumb or my premise is flawed
> please forgive me.  I have a DB design which contains a table which has
> categories, each category has a parent category, and is recursed until
> the top category is reached, in order to create breadcrumbs.  Is there
> any problem with using foreign keys to reference the same table?  So a
> when category is added the CatParent MUST be present as a CatID
>
> CatID - Serial
> CatParent - int4 - References CatID
> CatName - Text
>
> Am I likeley to come unstuck with this?
>
> Cheers
>
> T.

Re: Tables Referencing themselves As Foreign Keys

From
Mike Mascari
Date:
Arjen van der Meijden wrote:

> Tony,
>
> That'll work, but you have to mind the first row/toprow you insert.
> Will it have no parent (make the field nullable) or will it be its own
> parent (you'll have to test whether that works, I don't know, foreign
> keys are deferrable, so it should be possible if you specify that).

A more traditional way to have hierarchical relationships in the
relational model is to have two relations (and not use NULLs):

CREATE TABLE categories (
 CatID bigint PRIMARY KEY NOT NULL,
 CatName text NOT NULL
);

CREATE TABLE category_parents (
 CatID bigint UNIQUE NOT NULL REFERENCES categories(CatID),
 ParentID bigint NOT NULL REFERENCES categories(CatID)
  CHECK (CatID <> ParentID)
);

The top category would be the only tuple in categories that did not
exist in category_parents.

HTH,

Mike Mascari
mascarm@mascari.com

Re: Tables Referencing themselves As Foreign Keys

From
Arjen van der Meijden
Date:
Mike Mascari wrote:

> Arjen van der Meijden wrote:
>
>> Tony,
>>
>> That'll work, but you have to mind the first row/toprow you insert.
>> Will it have no parent (make the field nullable) or will it be its own
>> parent (you'll have to test whether that works, I don't know, foreign
>> keys are deferrable, so it should be possible if you specify that).
>
>
> A more traditional way to have hierarchical relationships in the
> relational model is to have two relations (and not use NULLs):
>
> CREATE TABLE categories (
> CatID bigint PRIMARY KEY NOT NULL,
> CatName text NOT NULL
> );
>
> CREATE TABLE category_parents (
> CatID bigint UNIQUE NOT NULL REFERENCES categories(CatID),
> ParentID bigint NOT NULL REFERENCES categories(CatID)
>  CHECK (CatID <> ParentID)
> );
>
> The top category would be the only tuple in categories that did not
> exist in category_parents.

What you're modelling here is a general graph, not a tree.
This model allows to have multiple parents for children, parents to be
their childrens child, etc.

The singletable model is just a tree, nothing more. If you want the
above model to resemble a tree, you'd make sure that a tuple cannot be
the child of any of its children and a child can have only one parent.
And that would force you to create triggers, while the other model just
enforces that due to its structure :)
If you *need* a graph, then yes, that's the most traditional way.

Best regards,

Arjen

Re: Tables Referencing themselves As Foreign Keys

From
Mike Mascari
Date:
Arjen van der Meijden wrote:

> Mike Mascari wrote:
>
>> A more traditional way to have hierarchical relationships in the
>> relational model is to have two relations (and not use NULLs):
>>
>> CREATE TABLE categories (
>> CatID bigint PRIMARY KEY NOT NULL,
>> CatName text NOT NULL
>> );
>>
>> CREATE TABLE category_parents (
>> CatID bigint UNIQUE NOT NULL REFERENCES categories(CatID),
>> ParentID bigint NOT NULL REFERENCES categories(CatID)
>>  CHECK (CatID <> ParentID)
>> );
>>
>> The top category would be the only tuple in categories that did not
>> exist in category_parents.
>
>
> What you're modelling here is a general graph, not a tree.
> This model allows to have multiple parents for children

The UNIQUE constraint prevents that.

> parents to be their childrens child, etc.

Nothing in the single-relation design prevents that, either:

INSERT INTO categories (CatID, ParentID) VALUES (1, 1); <- Root Node
INSERT INTO categories (CatID, ParentID) VALUES (2, 1);
INSERT INTO categories (CatID, ParentID) VALUES (3, 2);

UPDATE categories SET ParentID = 3 WHERE CatID = 2;

A CHECK constraints composed of a recursive function (transitive closure
check) will be necessary in *both* designs. If you are just growing a
tree and children never change parents, in both designs, one might be
able to achieve the goal with a check constraint:

CHECK (CatID > ParentID)

> The singletable model is just a tree, nothing more. If you want the
> above model to resemble a tree, you'd make sure that a tuple cannot be
> the child of any of its children and a child can have only one parent.
> And that would force you to create triggers, while the other model
> just enforces that due to its structure :)

Not quite. See above. In addition, there's nothing, without the use of a
partial + functional index, or some other hackery, to prevent:

INSERT INTO categories (CatID, ParentID) VALUES (1, 1);
INSERT INTO categories (CatID, ParentID) VALUES (2, 2);

which may or may not be what you want. The same holds true of the
two-relation variable design as well, of course.

> If you *need* a graph, then yes, that's the most traditional way.

I'm in the Christmas spirit, so I will add some weight to your argument.
:-)

If the purpose of the two-relation variable design is to eliminate the
use of NULLs and/or the self-referencing parent, I fail to see how one
could have an ON DELETE CASCADE RI constraint to delete the descendants
of a parent which has been deleted, unless the constraint is added after
the first generation of children have been created. A minor detail the
anti-NULL adherents, and I usually include myself in that category,
haven't expounded upon...

Mike Mascari
mascarm@mascari.com

Re: Tables Referencing themselves As Foreign Keys

From
Robert Treat
Date:
On Mon, 2003-12-22 at 05:57, Tony (Unihost) wrote:
> Hi,
>
> I'm still new to this so if I'm sounding dumb or my premise is flawed
> please forgive me.  I have a DB design which contains a table which has
> categories, each category has a parent category, and is recursed until
> the top category is reached, in order to create breadcrumbs.  Is there
> any problem with using foreign keys to reference the same table?  So a
> when category is added the CatParent MUST be present as a CatID
>

Hmm... breadcrubs make me think you should look at using a nested set.
(Google "nested set celko" for more info)

Robert Treat
--
Build A Brighter Lamp :: Linux Apache {middleware} PostgreSQL

Re: Tables Referencing themselves As Foreign Keys

From
"Ezra Epstein"
Date:
This is a fine approach.  The FK will work fine.  You'll probably want CatID
to be NOT NULL and CatParent to allow nulls.  Having a Null parent
indicating root is easier for traversals.

Common other features to add include:
     a "path" column that is maintaned by insert/update triggers.  Quite
easy to do and very helpful.
 Once you have that you can do a simple test for circularity also on
insert/update, like:
         IF "path" ~ '(^|\\.)' || "CatID"::text || '(\\.|$)'   THEN
             RAISE EXCEPTION ''circular hierarchy detected...'';
         END IF;
There's also a short-cut way to do this since you use Serial for the CatIDs.
Just do a CHECK (CatParent < CatID) -- of course it makes an assumption
about the CatIDs really come in serially...

== Ezra Epstein


""Tony (Unihost)"" <tony@unihost.net> wrote in message
news:3FE6CE27.5080102@unihost.net...
> Hi,
>
> I'm still new to this so if I'm sounding dumb or my premise is flawed
> please forgive me.  I have a DB design which contains a table which has
> categories, each category has a parent category, and is recursed until
> the top category is reached, in order to create breadcrumbs.  Is there
> any problem with using foreign keys to reference the same table?  So a
> when category is added the CatParent MUST be present as a CatID
>
> CatID - Serial
> CatParent - int4 - References CatID
> CatName - Text
>
> Am I likeley to come unstuck with this?
>
> Cheers
>
> T.
>
>
>
>
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 8: explain analyze is your friend
>