Eliminating Combinatorial Relationship Multiplication

[Jeff Lanfield]

Suppose I have users that can belong to organizations. Organizations
are arranged in a tree. Each organization has only one parent
organization but a user maybe a member of multiple organizations.

The problem that I'm facing that both organizations and individual
users may have relationships with other entities which are
semantically the same. For instance, an individual user can purchase
things and so can an organization. An individual user can have
business partners and so can an organization. So it seems that I would
need to have a duplicate set of link tables that link a user to a
purchase and then a parallel link table linking an organization to a
purchase. If I have N entities with which both users and organizations
may have relationships then I need 2*N link tables. There is nothing
wrong with that per se but just not elegant to have two different
tables for a relationship which is the same in nature, e.g.
purchaser->purchasedite m.

One other approach I was thinking of is to create an intermediate
entity (say it's called "holder") that will be used to hold references
to all the relationships that both an organization and an individual
may have. There will be 2 link tables linking organizations to
"holder" and users to "holder". Holder will in turn reference the
purchases, partners and so on. In this case the number of link tables
will be N+2 as opposed to 2*N but it will have a performance cost of
an extra join.

Is there a better way of modelling this notion of 2 different entities
that can possess similar relationships with N other entities?

[Dawn M. Wolthuis]

"Jeff Lanfield" <jl***********@ yahoo.com> wrote in message
news:23******** *************** ***@posting.goo gle.com...

Suppose I have users that can belong to organizations. Organizations
are arranged in a tree. Each organization has only one parent
organization but a user maybe a member of multiple organizations.

The problem that I'm facing that both organizations and individual
users may have relationships with other entities which are
semantically the same. For instance, an individual user can purchase
things and so can an organization. An individual user can have
business partners and so can an organization. So it seems that I would
need to have a duplicate set of link tables that link a user to a
purchase and then a parallel link table linking an organization to a
purchase. If I have N entities with which both users and organizations
may have relationships then I need 2*N link tables. There is nothing
wrong with that per se but just not elegant to have two different
tables for a relationship which is the same in nature, e.g.
purchaser->purchasedite m.

One other approach I was thinking of is to create an intermediate
entity (say it's called "holder") that will be used to hold references
to all the relationships that both an organization and an individual
may have. There will be 2 link tables linking organizations to
"holder" and users to "holder". Holder will in turn reference the
purchases, partners and so on. In this case the number of link tables
will be N+2 as opposed to 2*N but it will have a performance cost of
an extra join.
This is common scenario for a Customer, for example, where the Customer can
then be either an organization or an individual.
Is there a better way of modelling this notion of 2 different entities
that can possess similar relationships with N other entities?

If you are just looking to model it, then using an interface/implementation
approach would work where you have Customer (Holder) as an interface and
Organization and Person both implementing that interface. You could toss in
an abstract class (partial implementation of the Interface) for the
relationship implementations and extend that too. This is more handily
modeled in UML OO types of diagrams than with relations, it seems to me.

But, if you are looking to model it in order to implement in a SQL database
then I think you are headed down the right path with your Holder pattern,
although there could be other approaches that I'm missing too. I'd suggest
putting some work into picking a meaningful name for the Holder relation
(for example, it makes complete sense to everyone that a Customer could be a
person or an org).

Cheers! --dawn

[Alan]

"Jeff Lanfield" <jl***********@ yahoo.com> wrote in message
news:23******** *************** ***@posting.goo gle.com...

Suppose I have users that can belong to organizations. Organizations
are arranged in a tree. Each organization has only one parent
organization but a user maybe a member of multiple organizations.

The problem that I'm facing that both organizations and individual
users may have relationships with other entities which are
semantically the same. For instance, an individual user can purchase
things and so can an organization. An individual user can have
business partners and so can an organization. So it seems that I would
need to have a duplicate set of link tables that link a user to a
purchase and then a parallel link table linking an organization to a
purchase. If I have N entities with which both users and organizations
may have relationships then I need 2*N link tables. There is nothing
wrong with that per se but just not elegant to have two different
tables for a relationship which is the same in nature, e.g.
purchaser->purchasedite m.

One other approach I was thinking of is to create an intermediate
entity (say it's called "holder") that will be used to hold references
to all the relationships that both an organization and an individual
may have. There will be 2 link tables linking organizations to
"holder" and users to "holder". Holder will in turn reference the
purchases, partners and so on. In this case the number of link tables
will be N+2 as opposed to 2*N but it will have a performance cost of
an extra join.

Is there a better way of modelling this notion of 2 different entities
that can possess similar relationships with N other entities?

You need to convert the following into an ERD. I've supplied particpation
(may) constraints and cardinality constraints. Once the ERD is done, it is a
snap to convert to a relational schema.

PEOPLE n (may) have m BUSINESS_PARTNE RS
ORGANIZATIONS n (may) have BUSINESS_PARTNE RS
PEOPLE n (may) belong_to m ORGANIZATIONS
PEOPLE 1 (may) buy n GOODS
ORGANIZATIONS 1 (may) buy n GOODS

So, in mock pseudo ERD form:

PEOPLE == >have m:n ==> BUSINESS_PARTNE RS <== n:m have <== ORGANIZATIONS
" ==> people_order ==> 1:m GOODS m:1
<== orgs_order <== "

So, you wind up with

PEOPLE
person_id PK
etc

ORGANIZATIONS
org_id PK
etc

BUSINESS_PARTNE RS
person_id PK (FK)
org_id PK (FK)

GOODS
item_id (PK)
description
etc

PEOPLE_ORDER
order_id PK
person_id (FK)
item_id (FK)
order_date
etc

You can now either create an ORGS_ORDER table, or add in org_id to the
PEOPLE_ORDER table, and change the table name to ORDER. This is a decsion
based on many things, primarily the semantics of person_id and org_id. If
they are mutually exclusive, then you can combine the tables simply by
adding org_id. If they are not mutually exclusive, a horrible option is to
add a flag to the ORDERS table, indicating whether the order is from a
person or an organization. Don't do it.

[--CELKO--]

Here is the link on Amazon.com for my new book on "Trees & Hierarchies
in SQL"

http://www.amazon.com/exec/obidos/tg...roduct-details

Separate the tree structure from the nodes. Ilike the nested sets
model for the structure, but you can pick whatever works best for your
situation. Then the nodes can go into another table.

The classic scenario calls for a root class with all the common
attributes and then specialized sub-classes under it. As an example,
let's take the class of Vehicles and find an industry standard
identifier (VIN), and add two mutually exclusive sub-classes, Sport
utility vehicles and sedans ('SUV', 'SED').

CREATE TABLE Vehicles
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) NOT NULL
CHECK(vehicle_t ype IN ('SUV', 'SED')),
UNIQUE (vin, vehicle_type),
..);

Notice the overlapping candidate keys. I then use a compound candidate
key (vin, vehicle_type) and a constraint in each sub-class table to
assure that the vehicle_type is locked and agrees with the Vehicles
table. Add some DRI actions and you are done:

CREATE TABLE SUV
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SUV' NOT NULL
CHECK(vehicle_t ype = 'SUV'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE Sedans
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SED' NOT NULL
CHECK(vehicle_t ype = 'SED'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

I can continue to build a hierarchy like this. For example, if I had
a Sedans table that broke down into two-door and four-door sedans, I
could a schema like this:

CREATE TABLE Sedans
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SED' NOT NULL
CHECK(vehicle_t ype IN ('2DR', '4DR', 'SED')),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE TwoDoor
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT '2DR' NOT NULL
CHECK(vehicle_t ype = '2DR'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Sedans(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE FourDoor
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT '4DR' NOT NULL
CHECK(vehicle_t ype = '4DR'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Sedans (vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

The idea is to build a chain of identifiers and types in a UNIQUE()
constraint that go up the tree when you use a REFERENCES constraint.
Obviously, you can do variants of this trick to get different class
structures.

If an entity doesn't have to be exclusively one subtype, you play with
the root of the class hierarchy:

CREATE TABLE Vehicles
(vin CHAR(17) NOT NULL,
vehicle_type CHAR(3) NOT NULL
CHECK(vehicle_t ype IN ('SUV', 'SED')),
PRIMARY KEY (vin, vehicle_type),
..);

Now start hiding all this stuff in VIEWs immediately and add an
INSTEAD OF trigger to those VIEWs.

[John]

--CELKO-- wrote:

Here is the link on Amazon.com for my new book on "Trees & Hierarchies
in SQL"

http://www.amazon.com/exec/obidos/tg...roduct-details

Separate the tree structure from the nodes. Ilike the nested sets
model for the structure, but you can pick whatever works best for your
situation. Then the nodes can go into another table.

<snip a clever way of storing tree structures>

I have a couple of questions:

1. What's to stop you putting extra information into the Sedans or SUV
tables (like descriptions etc.) instead of creating separate tables?

2. Do you think it would be good to have primary keys that span two
tables in order to get rid of the vehicles table? Would there be any
disadvantage to doing it this way instead of the way you outlined?

John

PS: Apologies in advance for (predictably) missing obvious things.

[Joe Celko]

>> 1. What's to stop you putting extra information into the Sedans or
SUV tables (like descriptions etc.) instead of creating separate tables?
<<

If you don't need further subclass breakdowns, then by all means stop at
this level and get all the attributes in the table. In your case,
organizations might have tax status codes which are different from
individuals, so the Customers references the Organzations table and the
Organzations table has a column for tax status which is not in the
Individuals table.

2. Do you think it would be good to have primary keys that span two

tables in order to get rid of the vehicles table? Would there be any
disadvantage to doing it this way instead of the way you outlined? <<

The reason for having a Vehicles table is to establish a class that is
then broken down into disjoint sub-classses; this is the mechanism that
assures a VIN belongs to SUV or Sedans but never both.

What I am proposing is a bit complicated at first sight. You have a
nested set (or whatever) model for the tree structure that might look
like this:

CREATE TABLE Heirarchy
(vin CHAR(17) UNIQUE -- not null? default?
REFERENCES Vehicles (vin)
ON UPDATE CASCADE
ON DELETE ??, -- need a rule
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL,
PRIMARY KEY (lft, rgt),
<<more constraints -- see book>>);

You now have to sit down and really think about the business rules for
the Heirarchy.

The nodes (vehicles) have their class hierarchy on that side of the
RDBMS. You do joins from OrgChart (structure)-> Vehicles (node class)
-> SUV or Sedans (node sub-class) to get your data.

--CELKO--
=============== ============
Please post DDL, so that people do not have to guess what the keys,
constraints, Declarative Referential Integrity, datatypes, etc. in your
schema are.

*** Sent via Devdex http://www.devdex.com ***
Don't just participate in USENET...get rewarded for it!

[Jeff Lanfield]

> Separate the tree structure from the nodes. Ilike the nested sets

model for the structure, but you can pick whatever works best for your
situation. Then the nodes can go into another table.

The classic scenario calls for a root class with all the common
attributes and then specialized sub-classes under it.

The problem I described was not so much with modelling the tree
(thanks partly to tips from your book which I do own) but with 2
entities having semantically identical relationships with N other
entities. In my case the 2 entities are nodes and leaves -
organizations and users.

For simplicity of the example I'll use the path enumeration model (I
know nested set is better).

create table organizations (int id, varchar name ... etc)
create table users (int id, varchar name ... etc)
create table orgtree (varchar path, int orgId)
create table members (int orgId, int userId) // which organizations a
user belongs to

create table partners (int id, ... etc)
create table purchases (int id, ... etc)
create table customers (int id, ... etc)

The problem is that both users and organizations can have
relationships with partners, purchases, and customers. Thus I have to
have 2*N = 6 link tables to represent that. This example is
simplified, in reality I have about 12 entities with which both
organizations and users can have relationships so I have to have 24
link tables. Nothing wrong with that per se but I just think it is
inelegant.

In OO technology there are standard solutions for this kind of thing
but in SQL the only approach I could think of is to introduce an
"intermedia te" entity (say it's called "holder") which will hold the
references to the relationships that both a user and an organization
can have. Users and Organizations can then in turn have a relationship
with this "holder" entity. Thus the number of link tables will be N +
2 or 14 instead of 24.

My question is: Are there any other approaches to this problem? Seems
like a fairly common issue.

Thanks!

Jeff

P.S. CELKO,

I have to deal with tree stuff in SQL a lot and I originally I bought
your book simply because there was nothing else on the topic and I
looked hard both recently and in the past! I did not have high
expectations because I thought it was just a quickie to capitalize on
success of "SQL for smarties" but I was pleasently surprised: as the
title suggests, it is definitely the most comprehensive compilation of
SQL techiques for modelling trees in relational structures all
gathered in one place that I ever saw. Well worth the price,thanks for
putting it together!

jc*******@earth link.net (--CELKO--) wrote in message news:<18******* *************** ****@posting.go ogle.com>... Here is the link on Amazon.com for my new book on "Trees & Hierarchies
in SQL"

http://www.amazon.com/exec/obidos/tg...roduct-details

Separate the tree structure from the nodes. Ilike the nested sets
model for the structure, but you can pick whatever works best for your
situation. Then the nodes can go into another table.

The classic scenario calls for a root class with all the common
attributes and then specialized sub-classes under it. As an example,
let's take the class of Vehicles and find an industry standard
identifier (VIN), and add two mutually exclusive sub-classes, Sport
utility vehicles and sedans ('SUV', 'SED').

CREATE TABLE Vehicles
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) NOT NULL
CHECK(vehicle_t ype IN ('SUV', 'SED')),
UNIQUE (vin, vehicle_type),
..);

Notice the overlapping candidate keys. I then use a compound candidate
key (vin, vehicle_type) and a constraint in each sub-class table to
assure that the vehicle_type is locked and agrees with the Vehicles
table. Add some DRI actions and you are done:

CREATE TABLE SUV
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SUV' NOT NULL
CHECK(vehicle_t ype = 'SUV'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE Sedans
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SED' NOT NULL
CHECK(vehicle_t ype = 'SED'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

I can continue to build a hierarchy like this. For example, if I had
a Sedans table that broke down into two-door and four-door sedans, I
could a schema like this:

CREATE TABLE Sedans
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SED' NOT NULL
CHECK(vehicle_t ype IN ('2DR', '4DR', 'SED')),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE TwoDoor
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT '2DR' NOT NULL
CHECK(vehicle_t ype = '2DR'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Sedans(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE FourDoor
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT '4DR' NOT NULL
CHECK(vehicle_t ype = '4DR'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Sedans (vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

The idea is to build a chain of identifiers and types in a UNIQUE()
constraint that go up the tree when you use a REFERENCES constraint.
Obviously, you can do variants of this trick to get different class
structures.

If an entity doesn't have to be exclusively one subtype, you play with
the root of the class hierarchy:

CREATE TABLE Vehicles
(vin CHAR(17) NOT NULL,
vehicle_type CHAR(3) NOT NULL
CHECK(vehicle_t ype IN ('SUV', 'SED')),
PRIMARY KEY (vin, vehicle_type),
..);

Now start hiding all this stuff in VIEWs immediately and add an
INSTEAD OF trigger to those VIEWs.

[Jeff Lanfield]

> Separate the tree structure from the nodes. Ilike the nested sets

model for the structure, but you can pick whatever works best for your
situation. Then the nodes can go into another table.
CELKO,

Just wanted to double check: by "separating the nodes from the tree"
do you mean doing this (using path enumeration model):

nodes (id int, name varchar, ... etc)
nodetree (path varchar, int nodeId)

AS OPPOSED TO THIS:
nodes (id int, name varchar, path varchar, ... etc)

Thanks again!
Jeff
jc*******@earth link.net (--CELKO--) wrote in message news:<18******* *************** ****@posting.go ogle.com>... Here is the link on Amazon.com for my new book on "Trees & Hierarchies
in SQL"

http://www.amazon.com/exec/obidos/tg...roduct-details

Separate the tree structure from the nodes. Ilike the nested sets
model for the structure, but you can pick whatever works best for your
situation. Then the nodes can go into another table.

The classic scenario calls for a root class with all the common
attributes and then specialized sub-classes under it. As an example,
let's take the class of Vehicles and find an industry standard
identifier (VIN), and add two mutually exclusive sub-classes, Sport
utility vehicles and sedans ('SUV', 'SED').

CREATE TABLE Vehicles
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) NOT NULL
CHECK(vehicle_t ype IN ('SUV', 'SED')),
UNIQUE (vin, vehicle_type),
..);

Notice the overlapping candidate keys. I then use a compound candidate
key (vin, vehicle_type) and a constraint in each sub-class table to
assure that the vehicle_type is locked and agrees with the Vehicles
table. Add some DRI actions and you are done:

CREATE TABLE SUV
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SUV' NOT NULL
CHECK(vehicle_t ype = 'SUV'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE Sedans
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SED' NOT NULL
CHECK(vehicle_t ype = 'SED'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

I can continue to build a hierarchy like this. For example, if I had
a Sedans table that broke down into two-door and four-door sedans, I
could a schema like this:

CREATE TABLE Sedans
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT 'SED' NOT NULL
CHECK(vehicle_t ype IN ('2DR', '4DR', 'SED')),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Vehicles(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE TwoDoor
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT '2DR' NOT NULL
CHECK(vehicle_t ype = '2DR'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Sedans(vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

CREATE TABLE FourDoor
(vin CHAR(17) NOT NULL PRIMARY KEY,
vehicle_type CHAR(3) DEFAULT '4DR' NOT NULL
CHECK(vehicle_t ype = '4DR'),
UNIQUE (vin, vehicle_type),
FOREIGN KEY (vin, vehicle_type)
REFERENCES Sedans (vin, vehicle_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
..);

The idea is to build a chain of identifiers and types in a UNIQUE()
constraint that go up the tree when you use a REFERENCES constraint.
Obviously, you can do variants of this trick to get different class
structures.

If an entity doesn't have to be exclusively one subtype, you play with
the root of the class hierarchy:

CREATE TABLE Vehicles
(vin CHAR(17) NOT NULL,
vehicle_type CHAR(3) NOT NULL
CHECK(vehicle_t ype IN ('SUV', 'SED')),
PRIMARY KEY (vin, vehicle_type),
..);

Now start hiding all this stuff in VIEWs immediately and add an
INSTEAD OF trigger to those VIEWs.

[Joe Celko]

>> in reality I have about 12 entities with which both
organizations and users can have relationships so I have to have 24 link
tables. Nothing wrong with that per se but I just think it is inelegant.
<<

Well, sometimes the model is complex. If those relationships are all
different, then you need to have table for each relationship.

I did not have high expectations because I thought it was just a

quickie to capitalize on success of "SQL for smarties" but I was
pleasantly surprised: as the title suggests, it is definitely the most
comprehensive compilation of SQL techiques for modelling trees in
relational structures all gathered in one place that I ever saw. <<

Thank you! Where were you when I needed jacket copy?

--CELKO--
=============== ============
Please post DDL, so that people do not have to guess what the keys,
constraints, Declarative Referential Integrity, datatypes, etc. in your
schema are.

*** Sent via Devdex http://www.devdex.com ***
Don't just participate in USENET...get rewarded for it!

[--CELKO--]

>> Just wanted to double check: by "separating the nodes from the
tree" do you mean doing this (using path enumeration model): <<

Where is the DDL? What you posted was useless on several levels.
NEVER use something as vague as "id" for a column name. NEVER, NEVER,
NEVER name a data element for its current location -- node_id always a
node_id wherever it appears. This is fundamental data modeling --
name thing s for what they are in the logical model, not for how or
where they are PHYSICALLY stored or how they are used in one place.

I think that you might have meant this:

CREATE TABLE Nodes
(node_id INTEGER NOT NULL PRIMARY KEY,
node_name CHAR(20) NOT NULL,
... );

CREATE TABLE Tree
(node_id INTEGER NOT NULL
REFERENCES Nodes (node_id)
ON UPDATE CASCADE
ON DELETE CASCADE,
path VARCHAR(100) NOT NULL
CHECK (<< valid path predicate >>),
.. );

Now you need to decide how to handle DRI actions; I made a guess. And
how you want to build the path string - letters, digits, fixed or
variable substring components, etc.