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

"Peter Laursen" <pl_at_mail1.remove.this.stofanet.dk> wrote in message news:3c7fc988$0$18443$ba624c82_at_nntp02.dk.telia.net...
> 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

You are right. It is a graph, I am just trying to represent it as a tree using a Windows Tree Control, which should be possible.

> 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.

That would indeed be the best solution. The problem is that there already is a database in place, with data that already is corrupt, so I need to check that too...

> 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?

That is a good idea...

> Maybee a lengthy process with millions of rows, but needs to
> run only once.

Indeed. Plus, we are talking about much less rows than a million, think of thousends.

>
> 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
>

I'll let you know, but table locking would probably be just fine, since modifying relations will be a fast and infrequent operation anyway.

Thanks for your ideas.

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