Tables Referencing themselves As Foreign Keys

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:

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

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

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

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

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...