Perhaps the most straightforward approach to a solution for this information retrieval problem is to represent the collection of information by its image in memory as an array of records. To answer the question, "How many children does John Smith have?" requires a simple traversal of the records. Have a program look at the father's name field in each record and, whenever it comes to John Smith, increment a counter that represents the number of John Smith's children. When the traversal is complete, the program would print the counter value. To answer the question, "Who are the uncles of John Smith?", the program must first traverse, looking at the name field of each record, to find John Smith. It would note the father's name, which is in the fathersname field of that record. Then it would traverse again, looking at the fathersname fields. Each time John Smith's father's name appears, and "male" is listed as the corresponding sex field value, the program must print the name that appears in the corresponding name field. The same sequence would be repeated for John Smith's mother.
The execution time for these traversals can be proportional to the total number of records. This makes the solution time proportional to the amount of information represented in the system. For large systems, this would be impractical, as noted earlier.
What is the least amount of time that could be taken by any solution for these kinds of questions? Clearly, identifying the brothers of John Smith requires printing the names of the brothers. To display who the uncles of John Smith are, the program must print the names of each of his uncles. The least amount of time required for any solution would thus be proportional to the length of the answer to any given question. Length in the case of the uncles is the number of uncles. In the next section, you will see that a different way of representing the information allows a solution that is closer in execution time to this length. This is much better than having it proportional to the entire amount of information stored.