query design problem

[Ivan Pavlov]

Hello,
I hope someone can help me with this. I have a large list of objects
(think of them as car parts). Each part may be a substitute for some
other part(s). E.g. p1 is a substitue for p2 and p3, but this doesn't
mean (necessarily) that p2 and p3 are substitues for p1. What I have
is a list a existing relationships, which will be updated constantly
(example):

TABLE PARTS (part_id, part_id2)
(2,1)
(3,1)
(4,3)
(1,6)

I need to create one or more tables (or modify the above) allowing me
to efficiently define these "substitution" relationships. I also need
to query the table(s) with a part number and get as a result all parts
which can substitute it. In the example above if I search for all
substitutes for 2, I should get 1 and 6 (the last because I have 2->1
and 1->6). It is possible that both entries (m,n) and (n,m) exist
sometimes.

The main table is large (several millions of distinct part ids).

Again my question is how to most efficiently query such a structure,
independent of the "depth of substitution relations" - i.e. I don't
know how long is the maximum chain of substitutions
a1->a2->....->a(n).

Thanks in advance.

[Bill Karwin]

Ivan Pavlov wrote:

I need to create one or more tables (or modify the above) allowing me
to efficiently define these "substitution" relationships. I also need
to query the table(s) with a part number and get as a result all parts
which can substitute it.
The main table is large (several millions of distinct part ids).

What you are describing is called a cyclic reconvergent graph.
Joe Celko's book, "SQL for Smarties" covers methods of representing and
querying trees and graphs. But even he fears to tread into cyclic
graphs (where both (m,n) and (n,m) are valid).

Regards,
Bill K.