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

Answer below

"OddesE" <OddesE_XYZ_at_hotmail.com> wrote in message news:a5nh7d$hj8$1_at_news.hccnet.nl...
> [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
>
>

Hi,

We had a very similar problem, with a new application, and ending up having the application test before an insert, that no circularity would happen after the insert. Our tablestructure is exact like yours. Our data is not a tree, but a directed graph - (yours look like one too?) with thousands of 'roots' but only 1-5 levels deep. Inserts into the Unit and the UnitLink table are always two transactions with commit in between. No updates ever happen on the unitLink table.
Now, if you can assert that there are no circular references before an insert the test to see if an insert will make one is fairly straight forward. Before inserting a new parent child relation, for each occurence of the child in the unitlink table, do a recursive forward search and if you hit the parent, you may not do the insert. The search will end as we have asserted that no circular referenes existed before the insert! Alternatively do the insert, and then search and rollback if you hit the parent.

As for asserting the data already there are ok, how about inserting one row at a time from the unitlink to unitlinktest with similar structure testing at each insert? Maybee a lengthy process with millions of rows, but needs to run only once.

Bot now to the difficult part (and the database part). How to make this work in a multitreaded environment with many users selecting and inserting data? If you allow many users do the test at the same time, each could assert that their insert would do no harm and go ahead and insert and commit, not seeing conflicting rows because they already searched that branch. I see no easy solution short of a table lock. I would love to know an elegant and efficient solution! If you want to try the trigger read this first http://osi.oracle.com/~tkyte/Mutate/index.html

When you decide on a solution I would be interested knowing what you did.

Peter Laursen Received on Fri Mar 01 2002 - 12:28:23 CST