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

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
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 &gt; parent_level)