Circular Record Reference

[ruse7013]

To: All Who Love Oracle Challenges

Environment:
Oracle8i (8.1.7)

Scenario:
The following records exist in a table:

ITEM DEST SRC
---- ---- ----
1111 101 201
1111 201 202
1111 202 101

or in a generic example, we have:

ITEM DEST SRC
---- ---- ----
1111 A B
1111 B C
1111 C A

Question:
What would be the best approach in Oracle8i to find a circular reference in columns DEST and SRC? For example, for ITEM=1111, the following circular reference exists for DEST->SRC: A->B->C->A

Any ideas are highly appreciated!
Thanks.

Regards,
<ruse7013>

 

[carp]

Ruse -
What signifies the end of a sequence - a null value in SRC?

 

[ruse7013]

The end of a sequence occurs when a SRC value (child) is equal to a DEST value (parent/ancestor), a.k.a. self-referencing.

For instance, please take a look at my original example:

Record #1 –
For a specific ITEM (1111), DEST of “A” is a parent of a SRC of “B”. Therefore, SRC of “B” is a child of “A”.

Record #2 –
Furthermore, the child “B” becomes a parent of “C”.

Record #3 –
Finally, “C” becomes a parent of “A” (Wrong!!! – A parent/ancestor – “A” – cannot become a child of his/her children/grandchildren).

How can we catch this error?

 

[carp]

And are there any other columns that indicate the order of items? In other words, is there a simple way of telling which record is first, second, etc?

 

[carp]

The following code assumes that the path should be checked in ascending order of DEST. If you have a different method for sorting first record to last, you will want to modify the ORDER BY clause accordingly.

Also note that I just called the table item_table; you probably are using another name.

There is probably a more efficient way to do this; the following code is just a quick hack:

FUNCTION circular_path(p_item IN item_table.item%TYPE) RETURN VARCHAR2 IS
   TYPE item_table_type IS TABLE OF item_table%ROWTYPE INDEX BY BINARY_INTEGER;
   l_table  item_table_type;
   l_path   VARCHAR2(4000) := NULL;
   l_row    NUMBER := 1;
   l_flawed BOOLEAN := FALSE;
BEGIN
-- LOAD THE RECORD TABLE
   SELECT * BULK COLLECT INTO l_table 
     FROM item_table
    WHERE item = p_item
    ORDER BY dest;
-- START RECORDING THE PATH   
   l_path := l_table(1).DEST;
   FOR i IN l_table.FIRST..l_table.LAST LOOP
      EXIT WHEN l_table(i).dest = l_table(i).src; -- END OF CHAIN
-- UPDATE THE PATH
      l_path := l_path||' => '||l_table(i).src;
-- CHECK TO SEE IF A CIRCULAR RELATIONSHIP HAS BEEN DEFINED
      FOR j IN 1..l_row LOOP
      	IF (l_table(j).dest = l_table(i).src) THEN
      		l_flawed := TRUE;
      		EXIT;
      	END IF;
      END LOOP;
      IF l_flawed THEN
       	EXIT;
      ELSE
      	l_row := l_row + 1;
      END IF;
  END LOOP;
  IF l_flawed THEN
  	RETURN l_path;
  ELSE
  	RETURN null;
  END IF;
END circular_path;

My table looks like:

16:10:57 SQL> select * from item_table;

      ITEM DEST  SRC
---------- ----- -----
      1111 A     B
      1111 B     C
      1111 C     D
      1111 D     A
       222 A     B
       222 B     C
       222 C     C

7 rows selected.

So - to test the function:

16:14:22 SQL> select circular_path(1111) from dual;

CIRCULAR_PATH(1111)
----------------------------------------------------
A => B => C => D => A

16:15:19 SQL> select NVL(circular_path(222),'Not Circular') from dual;

NVL(CIRCULAR_PATH(222),'NOTCIRCULAR')
----------------------------------------------------
Not Circular


SQL> SELECT DISTINCT item, 
     NVL(circular_path(item),'Not Circular') path 
     FROM item_table;

      ITEM     PATH
-----------    --------------------------------------
       222     Not Circular
      1111     A => B => C => D => A

Once you are convinced the function works the way you want it to, you might also want to modify the return values (e.g., 0 for "Is Not Circular" and 1 for "Is Circular") instead of NULL vs. the full path (which will cause problems if it goes over 4000 characters).

Please let us know if this will take care of your situation.

Elbert, CO
1621 MST