Database Schema for an almost tree

Question

I have the following structure:

Block A
  Foo 1
    Bar 1
    Bar 2
  Foo 2
    Bar 1
    Bar 3
  Bar 4

Block B
  Foo 3

• Every Foo belongs to exactly on Block.
• Every Bar belongs to exactly on Block.
• A Bar can belong to none, one or more Foo's of the same Block.

The schema is currently like this:

    Block
   1/   \1
  n/     \n
Foo-n---m-Bar

The problem with this is that there can be Bar's which belong to Foo's of different Block's

Is there a schema which has neither redundancy nor allows inconsistencies?

Answer 1

Yes, there is a way. Include the primary key column of Block into the association table and use it to extend the foreign key constraints:

CREATE TABLE Blocks
  ( BlockID INT 
  , PRIMARY KEY (BlockID)
  ) ;

CREATE TABLE Foos
  ( BlockID INT
  , FooID INT
  , PRIMARY KEY (FooID)
  , FOREIGN KEY (BlockID)
      REFERENCES Blocks (BlockID)
  , UNIQUE (BlockID, FooID)              -- the Unique constraints are needed for 
  ) ;

CREATE TABLE Bars
  ( BlockID INT
  , BarID INT
  , PRIMARY KEY (BarID)
  , FOREIGN KEY (BlockID)
      REFERENCES Blocks (BlockID)
  , UNIQUE (BlockID, BarID)              -- the composite FKs below
  ) ;

CREATE TABLE Foo_Bars                    -- the m:n association tabletable
  ( BlockID INT
  , FooID INT
  , BarID INT
  , PRIMARY KEY (FooID, BarID)
  , FOREIGN KEY (BlockID, FooID)         -- composite FK constraints to Foos
      REFERENCES Foos (BlockID, FooID)
  , FOREIGN KEY (BlockID, BarID)         -- and Bars
      REFERENCES Bars (BlockID, BarID)
  ) ;

Answer 2

In addition to what ypercube said (+1 to him, BTW), you can do it with less index overhead if you are willing to change the structure of your keys:

Since FOO_BAR.BLOCK_ID references both "branches" all the way up to the BLOCK, then if FOO and BAR are connected they must also be connected to the same BLOCK.

Unless there are additional indexes needed (outside of the scope of your original question), this structure can be clustered very efficiently.

Answer 3

if I understand correctly you have a situation like this:

block_foo_bar

block   foo bar
A       1   1
A       1   2
A       2   1
A       2   3
A       0A  4
B       3   0B

• I used ID 0 for dummy Foos and Bars that represent the missing element (you can use NULL if you prefer)

A table like this handles the n-m, but it can't enforce the 1-n relationships.

My suggestion is to create two additional tables:

block_foo

block(FK) foo(PK)
A         0A
A         1
A         2
B         0B
B         3

and

block_bar

block(FK) bar(PK)
A         0A
A         1
A         2
A         3
A         4
B         0B

In this way the two new tables will enforce the uniqueness of for/bar-block relationship. Where block_foo_bar will allows you to handle the n-m relationship. To be sure that you won't have in block_foo_bar relationships not allowed by the block_foo and block_bar tables create two constrains in block_foo_bar:

• block_foo_bar_FK1 = block - foo in block_foo table
• block_foo_bar_FK2 = block - bar in block_bar table

As you probably noticed I created dummy IDs like 0A and 0B, I did it because IDs nullable are never a good idea, second because in this way I can enforce the PK on the ID. I understand that this means create a dummy record for each block without Foo/Bar in the Foo/Bar table (more work for ETL), but this usually saved me headaches later.

Hope my explanation makes sense for you.