February 02, 2020
Amitraj
Mapping Hierarchies To Files
A technique for implementing the instance of a tree-structure
diagram is to associate one pointer with a record for each child that the record has. Consider the database tree. Figure 1 shows an implementation of this database using parent-to-child pointers.
Parent–child pointers, however, are not an ideal structure for the implementation of hierarchical databases, since a parent record may have an arbitrary number of children. Thus, fixed-length
records become variable-length records once the parent–child pointers are added.
-> Instead of parent–child pointers, we can use leftmost-child and next-sibling pointers. Figure 2 shows this structure for the database tree.
-> Under this structure, every record has exactly two pointer fields. Thus, fixedlength records retain their fixed length when we add the necessary pointers that the leftmost-child pointers for the account record are null, since account is a leaf of the tree.
-> Can use leftmost-child and next-sibling pointers which allow each record to contain exactly two pointers.
1. The leftmost-child pointer points to one child.
2.The next-sibling pointer points to another child of the same parent.
A) Implementation with parent-child pointers.
B) Implementation with leftmost child and next-sibling pointers.
C) The final child of a parent has no next sibling; rather
than setting the next-sibling filed to null, place a pointer (or
preorder thread) that points to the next record in preorder.
-> Using preorder threads allows us to process a tree instance in
preorder simply by following pointers.
-> A parent pointer is often added to records in an implementation of a hierarchical database. This pointer facilitates the processing of queries that give a value for a child record and request a value from the corresponding parent record. If we include parent pointers, a total of exactly three pointer fields is added to each
record.
-> To see how best to locate records of a hierarchical database physically on disk, we draw an analogy between the parent–child relationship within a hierarchy and the owner–member relationship within a DBTG set. In both cases, a one-to-many relationship is being represented. We want to store together the members and
the owners of a set occurrence. Similarly, we want to store physically close on disk the child records and their parent. This form of storage allows a sequence of Figure 3 Implementation using preorder threads.
A technique for implementing the instance of a tree-structure
diagram is to associate one pointer with a record for each child that the record has. Consider the database tree. Figure 1 shows an implementation of this database using parent-to-child pointers.
Parent–child pointers, however, are not an ideal structure for the implementation of hierarchical databases, since a parent record may have an arbitrary number of children. Thus, fixed-length
records become variable-length records once the parent–child pointers are added.
-> Instead of parent–child pointers, we can use leftmost-child and next-sibling pointers. Figure 2 shows this structure for the database tree.
-> Under this structure, every record has exactly two pointer fields. Thus, fixedlength records retain their fixed length when we add the necessary pointers that the leftmost-child pointers for the account record are null, since account is a leaf of the tree.
-> Can use leftmost-child and next-sibling pointers which allow each record to contain exactly two pointers.
1. The leftmost-child pointer points to one child.
2.The next-sibling pointer points to another child of the same parent.
A) Implementation with parent-child pointers.
 |
| figure 1 : Implementation with parent-child pointers |
B) Implementation with leftmost child and next-sibling pointers.
 |
| figure 2 :Implementation with leftmost child and next-sibling pointers |
C) The final child of a parent has no next sibling; rather
than setting the next-sibling filed to null, place a pointer (or
preorder thread) that points to the next record in preorder.
-> Using preorder threads allows us to process a tree instance in
preorder simply by following pointers.
 |
| figure 3 : Implementation using pre-order threads |
-> A parent pointer is often added to records in an implementation of a hierarchical database. This pointer facilitates the processing of queries that give a value for a child record and request a value from the corresponding parent record. If we include parent pointers, a total of exactly three pointer fields is added to each
record.
-> To see how best to locate records of a hierarchical database physically on disk, we draw an analogy between the parent–child relationship within a hierarchy and the owner–member relationship within a DBTG set. In both cases, a one-to-many relationship is being represented. We want to store together the members and
the owners of a set occurrence. Similarly, we want to store physically close on disk the child records and their parent. This form of storage allows a sequence of Figure 3 Implementation using preorder threads.
