deadlock detection problem mysql/php problem

here my problem:

i am developing a web application allowing you to create modules(a piece of code to execute) and execute them. One particularity about the application is that you can make compositions of modules. i.e. a module can be composed of several other modules. I have designed a scenario below so that you can understand more easily:

i have 8 modules: 1,2,3, 4,5,6,7 and 8

I have my initial setup (Scenario 1)

http://forums.codeguru.com/

Module 1 is composed of module 2 and 3.
Module 2 is composed of module 4 and 6.
Module 5 is composed of module 1 and 7.
Module 8 is composed of module 5

Execute module 1:
Now,e.g., if i execute module 1... it will execute module 2 + module 3.

As module 2 is composed of module 4 and 6, the latters will also be executed.

This is the execution chain. In the diagram, the left hand side shows all the modules that are actually executed

http://postimage.org/image/5cspmguc/
The problem
In scenario 1, everything is ok and executes smoothly... but in scenario 2, i add module 5 to module 1.

When you execute module 1, it will execute module 2, 3 and 5. As module 2 is a composition, it will also executes module 4 and 6 found in module 2. And as module 5 is a composition too, it will execute module 1 and 7 found in 5.

The problem is that the module 1 found in module 5. It will also execute.... you can see that this will result in an infinte loop!!! kind of a deadlock!

same thing happens in scenario 3 where i add module 8 to module 1. Module 8 has module 5 as child and the latter has module 1 as child. This will also result in a deadlock!!

What is the solution??

My problem is how to detect such deadlocks?? When i am composing module 1, e.g., i should not be given the option to add module 5 or module 8 as they would cause a deadlock....

In my interface, when i am composing/editing a module, i am giving a list of all modules available (1,2,3,4,5,6,7,8) which i can click and add to the module i am composing/editing. I need to filter/hide all the modules that will cause a deadlock.

database structure
Below is my database structure:

http://imageshack.us/photo/my-images/840/tablesq.png

The values in the tables are for scenario 1.

and i am using javascript/html, php and mysql. I have idea how to efficiently detect these deadlocks... can it be done all in a query? (e.g. when i am editing module 1, i write a query to fetch only modules that will not cause deadlocks)

Your advices and tips are most welcomed.. thx for reading this lengthy topic.

just realised i haven't attached the pics properly; here they are:

1. scenarios
http://postimage.org/image/5cspmguc/

2.database
http://imageshack.us/photo/my-images/840/tablesq.png

Quote:

---

Originally Posted by yeahman45

My problem is how to detect such deadlocks?? When i am composing module 1, e.g., i should not be given the option to add module 5 or module 8 as they would cause a deadlock....

---

Strictly you don't have a deadlock. That terms is used for a certain concurrency problem.

To avoid cycles you must ensure that compositions always stay a DAG (Directed Acyclic Graph). So when a composition is defined it should be a DAG. And when it's changed you need to establish that it's still a DAG otherwise you must reject the change.

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

http://allisons.org/ll/AlgDS/Graph/DAG/