Loading ...
Sorry, an error occurred while loading the content.

Try to avoid recursion to retrieve data from database

Expand Messages
  • Prasun Paul
    Hello All.......... Generally we face a problem to store hierarchical data in a database. The problem is how we should store this type of data in a database.
    Message 1 of 2 , May 1 9:22 PM
    • 0 Attachment
      Hello All..........
      Generally we face a problem to store hierarchical data in a database. The problem is how we should store this type of data in a database. Many well-known web applications use adjacency list representation of data to store in a database. But the problem arises when we retrieve data from database as we need to call multiple query and many times a recursive function is called to retrieve data. You know recursive functions consumed time and so it adds extra time thread to existing time thread of executing multiple query. By using an intelligent iterative function we can at least save recursion time. The following function will do this.
       
      function getMap (&$map,  $tbl_name, $parent_field_id_name,   
                                                     $child_field_id_name, $parent, $depth)
      {
       $head = 0;
       $stack[$head++] = $parent;
       $spl[$head-1] = 0;
      $map = array();
      while($head > 0)
      {
        $parent = $stack[--$head];
        $cdepth = $spl[$head];
        //here you can control depth of search
      if($cdepth > $depth)
      {
       break;
      }
      $query = “select * from $tbl_name where $parent_field_id_name =
      $parent”;
      $query_res = mysql_query($query);
      //according to your requirement you can reduce the execution time of this //loop.
      if(mysql_num_rows($query_res)>0)
      {
      while($row = mysql_fetch_object($query_res))
      {
       $stack[$head++] = $row->{$child_field_id_name};
       $spl[$head-1] = $cdepth + 1;
       $map[$parent][] = $stack[$head];
      }
      }
       }
       return;
       
      Here I have used Breadth First Search (BFS) to traverse the structure. This function returns a map which is actually a adjacency list representation of the stored structure up to a certain lebel. Generally you can follow the same strategy to avoid recursion.
      For example let us consider an structure:
      a  [1]
      ++++++++++++++d [2]
      +                          +++e [3]
      +                          +++f [4]
      +                          +++g  [5]
      +   
      ++++++++++++++h [8]
      +                          +++i  [6]
      +                          +++j  [7]
      +
      ++++++++++++++k [9]
      +
      ++++++++++++++l [10]
       
      [Then number inside “[]” is the node number calculated using modified pre-order traversal algorithm.]

      The above structure is stored in a database table in the following way:
      child_id   parent_id 
      a  
      d            a
      h            a
      k            a
      l             a
      e            d
      f             d
      g            d
      i             h
      j             h
      The function returns the following structure.
      a => d, h, k, l
      d => e, f, g
      h => i, j
       
      By applying another algorithm which is called modified preorder traversal, we can find any information by executing only one query.
      The database table structure of the above hierarchical data is given below:

      child_id parent_id left_node right_note node_id
      a                        2             10            1
      d         a             3             5              2
      h         a             6             7              8
      k         a             0             0              9
      l          a             0             0              10
      e         d             0             0              3
      f          d             0             0              4
      g         d             0             0              5
      i          h             0             0              6 
      j          h             0             0              7

      Now you need to execute only one query and you will find your required information. Suppose you want to find all the children of d whose left_node is 3 and right_node is 5. The query will be “select * from tbl_name where node_id >= 3 and node_id <= 5”.
      Again consider you need to find the children of d (node_id:2) and h(node_id:8). The query will be “select * from tbl_name where node_id >= 2 and node_id <= 8”.
       
      Thanks
      Prasun



      Get amazing travel prices for air and hotel in one click on Yahoo! FareChase

    Your message has been successfully submitted and would be delivered to recipients shortly.