General database quesion

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

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