Re: Ora 9.2 SQL: What's the fastest way to do this set operation...

> The problem is that this is a set theory
> problem, and I am not a mathematician.

Actually, this is not really a set theory problem. This is a network flow problem. And yes...I not only play a mathematician on TV...I am one in real life as well.

> Point C is not known,

My solution does not require point C to be known. My SQL statement will determine the Point C's that let you get from point A to point B (through C).

> and there
> may be many points that (what's known as a block swap) can occur in
> both trains (in fact this is quite likely if they share part of a
> corridor). In addition, the swap does not have to be at the first
> train's destination, or the origin of the second train.

My solution only gave an answer in going from point A to B provided only one middle point was needed, but there may be many other midpoints in the path. In the study of network flows, this is called a "search". There are two different types of searching...depth first and breadth first. These searches typically use recursive techniques to solve, but are not limited to those.

While you may have a search involved, you may also want to perform some "shortest path" analysis as well. Why send a train through Seattle when the train needs to go from Los Angeles to Miami? Surely a shorter path from LA to Miami exists without having to go all the way up to Seattle. One of the most popular shortest path approaches in use is Dijkstra's Algorithm. Note, the shortest path is typically (but no limited to) either distance or time. The following shows a good description of Dijkstra's Algorithm:

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

They give pseudo-code on how to implement Dijkstra's Algorithm. From the pseudo-code you can see that a PL/SQL implementation is best for your type of problem. So you can code this in a Stored Procedure.

There are other shortest path algorithm's and some variations on Dijkstra's Algorithm as well. A Google search can bring up tons of information!

HTH,
Brian

-- 
===================================================================

Brian Peasland
oracle_dba_at_nospam.peasland.net
http://www.peasland.net

Remove the "nospam." from the email address to email me.


"I can give it to you cheap, quick, and good.
Now pick two out of the three" - Unknown