[X] Tree/Graph structure in many-to-many relationship, avoiding/detecting circularity

[X] Cross-posted to:
comp.databases;
comp.databases.oracle.server

This is my first post here on these groups, so sorry if I break any nettiquette. Sorry too to start out with a cross post, but I need the best info from both groups so please read on :)

I am currently working on an application that uses a legacy database from another application, implemented in Oracle. Updating the table structure of the database is not possible, because the other application may not be broken.

I am facing a problem with parsing a graph from two tables in the database when there is a circular relation between two or more records. I will first describe the structure of the two tables and what I am trying to accomplish in my code. Next I will describe the problem I encounter:

There are two tables, Unit and UnitLink. Unit contains records with a unique ID and other fields such as name, date, etc. At the moment I am only interested in the ID. UnitLink is a link table which describes the many-to-many relationship that exists between units, like so:

+-----------+-----------+-----------+
| ID | ParentID | ChildID |

+-----------+-----------+-----------+
| 0 | 0 | 1 |
| 1 | 0 | 2 |
| 2 | 0 | 3 |
| 3 | 0 | 4 |
| 4 | 2 | 3 |
| 5 | 2 | 5 |
| 6 | 2 | 6 |
| 7 | 7 | 8 |
| 8 | 8 | 9 |
| 9 | 9 | 7 |

+-----------+-----------+-----------+

• Root |-- * 0 | |-- * 1 | |-- * 2 | | |- * 3 | | |- * 5 | | \- * 6 | |-- * 3 | \-- * 4 \-- * 7 \-- * 8 \- * 9 \- * 7 !!! Circular

As you can see I am trying to insert the Unit ID's into a tree. I have created a single root node under which all the unit's that do not have a parent will be placed. Since the graph is a many to many relation a tree isn't perfectly suited, but because I am only referencing the records in the Unit table by their ID, duplicating the same ID under more branches isn't a problem. However, I do get into trouble when there is a circular relationship, such as the example where node 7 contains node 8, which contains node 9, which in turn contains node 7 again! My recursive algorithm will keep running around in circles!

Keep in mind that:
a) A circular relationship is never needed in the

   problem domain modelled by the database b) The original problem does not check for circular

   references so they might exist
c) The table structure may not be altered because

   the original problem must be altered as least as    possible.

Questions:
1) Is it possible to create an algorithm to detect

   this circularity? I have tried running recursively    back up to the root to check parents for duplicates    but so far haven't been succesful. Is there anyone    on these groups that has experience with this? 2) Is it possible to create a trigger or stored

   procedure in Oracle that prevents anyone from entering    a record in the database that would cause a circular    relationship?

Thank you for any answers, and for reading this lengthy post! :)

--
Stijn
OddesE_XYZ_at_hotmail.com
http://OddesE.cjb.net
________________________________________________________
Please remove _XYZ from my address when replying by mail