locked
General database quesion RRS feed

  • Question

  • guys i have a programming question i have table called prerequsites
    which is like this
    prerequisite component                       component

    a                                                         b

    so inside my before insert trigger i have to check if the prerequisite is a valid entry like for instance
    an entry like b is a prerequisite component for component a which is not a valid entry since i already have an entry in the prerequisite table which defines that comonent a is a prerequisite of b. however this is
    very basic so i can test it easy some thing like this in my before insert
    prerequisite component                       component

    a                                                         b
    b                                                         a (  Not a valid entry)
    select count(*)  from prerequisite where component = value of prerequisite component  
    and prerequisite component  = value of component
    the above select statement will actually tell me if entry is allowed for insert and does not override other prerequsites

    but it can get very complex depending on how the user chooses so if someone can tell me a nice algorithm or good logic to approach this problem it would be great like for instance

    prerequisite component                       component

    a                                                         b
    b                                                         c
    c                                                         a ( Not a valid entry. so how do i ensure that this entry is not allowed considering that complexity for prerequsites can increase quite greatly)

    please can someone tell me how to approach this problem.

    The database i am using is Oracle 9i but it does not really matter since it is a general database question

    Wednesday, August 3, 2005 8:08 PM

Answers

  • This is a directed graph.  If you find a cycle in it, then it is an invalid entry.

    a<-b     //  a preceeds b
    b<-c     //  b preceeds c
    c<-a     //  c preceeds a, but this forms a cycle: a<-b<-c<-a

    You can use a depth first search or a breadth first search to find the cycle.  Any standard algorithms book or website will tell you how to do it.  You will need a stack or recursion for DFS or a queue for BFS.

    See

    http://en.wikipedia.org/wiki/Graph_theory

    You can also try a time/space tradeoff and solve the problem in O(1) time without a stack or queue by using a technique called "path enumeration".  The idea is to precompute all edges - even those with path length > 1.  The problem is the #of edges can grow very large depending on the topology of your graph.   But in some cases with relatively "flat" and "bushy" graphs, this might be a very acceptable tradeoff.  This was explained in a Joe Celko book.

    Regards,
    Clifford Dibble

    Friday, August 5, 2005 1:20 AM