Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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

video_category_links
  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

share|improve this question
1  
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
1  
@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? –  AlexKuznetsov Feb 13 '13 at 14:49

1 Answer 1

up vote 4 down vote accepted

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)
share|improve this answer
    
I'm sorry, I just noticed I forgot to accept your answer –  Cec Jan 10 at 16:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.