# Symmetric self-referential many-to-many

I'm trying to model a hierarchy of categories where a category can have multiple parents ( an overlapping tree model as described in this book )

I have the following tables

video_categories
int     id
string  name

int     parent_id  (foreign_key to video_categories.id)
int     child_id   (foreign_key to video_categories.id)


and an index on [ parent_id, child_id ] for uniqueness

The issue with this setup is that A can be parent of B, and B can be parent of A at the same time

Is there a way to specify a db constraint to avoid this or should I ensure it at the application level?

Thank you very much

• Maybe you could use a trigger on insert to check if inserting the new record would create a cycle and throw an error if it does? – FrustratedWithFormsDesigner Feb 11 '13 at 15:23
• Unless you're prepared to implement some kind of additional constraint, such as that suggested by Alex Kuznetsov - which I think is probably too restrictive - then you can't use declarative constraints to prevent cycles. Cycles could happen at multiple degrees, e.g. A>B>C>A and so forth. This has to be handled with application logic. Declarative constraints only go as far as fields within one record or the key of a record referencing a key in one other record. – Joel Brown Feb 12 '13 at 14:45
• @JoelBrown: Actually, I was thinking that the trigger could call a procedure (assuming the OP's environment supports that) that does deep testing for cycles - but there would probably be a bit of a performance hit. – FrustratedWithFormsDesigner Feb 12 '13 at 15:51
• @FrustratedWithFormsDesigner Agreed, that is how I would do it. While the trigger is declarative the procedure for cycle checking that would be performed by the trigger is ultimately procedural. That's why I said you can't do it declaratively. I guess I should have said strictly declarative. – Joel Brown Feb 12 '13 at 17:44
• @JoelBrown can you please elaborate on your " probably too restrictive" concern - which legitimate scenarios does it disallow? – A-K Feb 13 '13 at 14:49

I would define levels in the hierarchy:

video_categories
int     id
int level
string  name


I would propagate the parent and child levels into your link table:

video_category_links
int     parent_id
int parent_level ((parent_id  , parent_level) foreign_key to video_categories(id, level))
int     child_id
int child_level((child_id  , child_level) foreign_key to video_categories(id, level))
check(child_level > parent_level)