I have 2 tables "Foo" and "Bar". Both of these tables are used to represent a tree hierarchy.

Table Foo:
FooID (PK)
BarID (FK to table Bar)

Table Bar:
BarID (PK)
FooID (FK to table Foo)

Foo to Bar is a one-to-many relationship on Foo.BarID -> Bar.BarID and Bar to Foo is also a one-to-many relationship on Bar.FooID -> Foo.FooID (the business logic requires these two tables to be split up and not referenced in the same table). Since these are recursive relationships, the ON DELETE and ON UPDATE actions must be set to NO ACTION. What is the best way to go about trying to delete a record when it can have multiple subtrees which in turn can have multiple subtrees... and so on?

Also, these data sets are pretty large, a subtree can extend as far as thousands or even potentially millions or subtrees therefore using nested delete triggers (with a max of 32 recursions) will not work.