How to best enforce single-level recursion in a SQL table?

Question

Let's say you have a table for branches in your organization. Some of them are "main" branches, and others are satellite offices that roll up to a main branch. Other than this distinction, which only impacts a few things in the system, the branches are all peers and have the same attributes (address, etc.). One way to model this is in a table like:

CREATE TABLE Branch (
    branch_id INT NOT NULL PRIMARY KEY IDENTITY(1,1),
    branch_name VARCHAR(80) NOT NULL,
    street VARCHAR(80) NULL,
    city VARCHAR(30) NULL,
    state CHAR(2) NULL,
    zip CHAR(5) NULL,
    is_satellite_office BIT NOT NULL DEFAULT(0),
    satellite_to_branch_id INT NULL REFERENCES Branch(branch_id)
)

Where is_satellite_office = 1 iff this record is a satellite to another branch, and satellite_to_branch_id refers to which branch you're a satellite of, if any.

It's easy enough to put a constraint on the table so that those two columns agree on any given record:

CONSTRAINT [CK_Branch] CHECK 
  (
    (is_satellite_office = 0 AND satellite_to_branch_id IS NULL) 
    OR (is_satellite_office = 1 AND satellite_to_branch_id IS NOT NULL)
  )

However, what I really want is a way to guarantee that this recursion only goes one level deep ... that is, that if I point to a branch as my parent, it must not have a parent itself, and its value for is_satellite_office must be 0. Put differently, I don't really want a fully recursive tree structure, I just want to limit it to a single parent / child relationship. That's how I'm going to write the code, and if there's a way to enforce it in the database that won't perform like total crap, I'd like to.

Any ideas? I'm working on MSSQL 2005, but general (non-vendor-specific) solutions are preferred. And no triggers need apply, unless there's truly no other way to do it.

EDIT: To be clear, satellite_to_branch_id is the recursive pointer to another record in the same Branch table. I know that I could remove the is_satellite_office BIT and rely on IsNull(satellite_to_branch_id) to give me the same information, but I find it's a little clearer to be explicit, and besides which, that's not the gist of the question. I'm really looking for a pure SQL-constraint way to prevent recursion-depth of greater than 1.

Answer 1

Seems to me like a business constraint, difficult to enforce at the data definition level. I don't believe the relational algebra has any support to determine a limit for self references depth.

Answer 2

What about this slightly different structure?

CREATE TABLE Branch (
    branch_id INT NOT NULL PRIMARY KEY IDENTITY(1,1),
    branch_name VARCHAR(80) NOT NULL,
    street VARCHAR(80) NULL,
    city VARCHAR(30) NULL,
    state CHAR(2) NULL,
    zip CHAR(5) NULL,
    parent_id int NULL
)

PARENT_ID will simply point to the BRANCH_ID of another record in the same table. If it is null, then you know it has no parents.

Then, to get one level of recursion, you can just join the table to itself once, like this:

SELECT
  PARENT.BRANCH_NAME AS PARENT_BRANCH
 ,CHILD.BRANCH_NAME AS CHILD_BRANCH
FROM
  BRANCH PARENT
 ,BRANCH CHILD
WHERE CHILD.PARENT_ID PARENT.BRANCH_ID

If you want to enforce one level of depth in your tree, make an on-insert/update trigger that will raise an exception if this query returns anything.

SELECT *
FROM
  BRANCH B1
 ,BRANCH B2
 ,BRANCH B3
WHERE B1.PARENT_ID = :NEW.NEW_PARENT_ID
  AND B2.PARENT_ID = B1.BRANCH_ID
  AND B2.PARENT_ID = B3.BRANCH_ID;

Answer 3

Aren't you allowed to refer to a stored procedure in your constraint? You can in PostgreSQL, so I'd be surprised if 2005 didn't allow this.

Answer 4

You can bind a check constraint to the return value of a UDF. Create a UDF that takes the columns involved as input parameters, and then check your desired state using a select in the UDF.