#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2011
    Posts
    3
    Rep Power
    0

    Mysql/php deadlock problem..need efficient solution


    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)

    h**p//postimage.org/image/5cspmguc/

    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


    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:

    h**p://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.

    edit: srry i cannot post links so it replaced http by h**p
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2011
    Posts
    3
    Rep Power
    0
    i am going to retrieve all modules and do a recursion to predict deadlocks.. this is not efficient at all.. any other ideas are welcomed
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2011
    Posts
    3
    Rep Power
    0
    i ended up with 2 queries (one for building a relationship tree like array and one for retrieving all modules) then using recursion and a caching system(to reduce recursion depth) detect deadlocks...probably not the most efficient technique but i think caching can help here.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2011
    Posts
    3
    Rep Power
    0
    I am assuming that the addition of any module is ok where it allows the execution more than once of the same module further down the chain (tree) but doesn't cause the infinite looping..

    If not have you considered reversing the db design to using a parent_id attribute meaning a module only has the one parent. (Your current design lets children have more than one parent)

    Anyway have a look at http_www_sqlsummit_com/AdjacencyList_htm

    might give you some clues on how to attack this.

    Agree...I don't think you are going to be able to avoid some sort of SQL recursion so I would probably look at a stored proc rather than getting your application layer to do it.

IMN logo majestic logo threadwatch logo seochat tools logo