Logic to Implement Parent Child Relationship in efficient manner.

Question

Hi.. Friends,
I have a Table where Parent Child Relation ship is stored as:
ChildID Name ParentID
1 A1 Null
2 A2 1
3 B1 Null
4 A3 2
5 A4 1
I m Woking on Objective C and I need to Generate a text File in Manner:
Name =A1> Name =A2> Name =A3/> Name =A2/>
Name =A4/>
Name =B1/>

I was using a approch where I catch the Last Element (Id=5) first and then checking all other nodes to get its Parent Nodes. n Complexity comes to be as n*n-1, Is there any other better approach as this approach is not a succes when we have lasrge data in Database.

Database Structure is flexible, we can change that, if there is something better...

Looking for your help and support.

Answer 1

From your output structure, I assume your data represents a tree. You therefore have a simple "get all children of a node" request as SELECT childId, name FROM tree WHERE parentId = ?, which lets you perform a standard tree traversal. Pseudocode:

def displayNode(node)  
  children = selectChildren(node.id)
  if (empty(children)) 
    print '<'+node.name+'/>'
  else 
    print '<'+node.name+'>'
    for (child in children) 
      displayNode(child)
    print '</'+node.name+'>'

An optimization, if running one query per node is too much (which probably is the case) is to run a single query to fetch all the data and place it in an optimized data structure:

for (node in selectAllNodes())
  nodes[node.parent].append(node);

def selectChildren(id)
  return nodes[id]