2 Appendix E Hierarchical Model Hayes Main Harrison Johnson Alma Palo Alto Turner Putnam Stamford A-102 400 A-101 500 A-201 900 A-305350 Figure E.1 Sample database. same database tree or in several different trees.Record replication has two major drawbacks: 1.Data inconsistency may result when updating takes place. 2.Waste of space is unavoidable. We shall deal with this issue in Section E.5 by introducing the concept of a virtual record. E.2 Tree-Structure Diagrams A tree-structure diagram is the schema for a hierarchical database.Such a diagram consists of two basic components: 1.Boxes,which correspond to record types 2.Lines,which correspond to links A tree-structure diagram serves the same purpose as an entity-relationship(E-R) diagram;namely,it specifies the overall logical structure of the database.A tree- structure diagram is similar to a data-structure diagram in the network model. The main difference is that,in the latter,record types are organized in the form of an arbitrary graph,whereas in the former,record types are organized in the form of a rooted tree. We have to be more precise about what a rooted tree is.First,there can be no cycles in the underlying graph.Second,there is a record type that is designated as the root of the tree.The relationships formed in the tree-structure diagram must be such that only one-to-many or one-to-one relationships exist between a parent and a child.The general form of a tree-structure diagram appears in Figure E.2. Note that the arrows are pointing from children to parents.A parent may have an arrow pointing to a child,but a child must have an arrow pointing to its parent. The database schema is represented as a collection of tree-structure diagrams. For each such diagram,there exists one single instance of a database tree.The root of this tree is a dummy node.The children of the dummy node are instances of the2 Appendix E Hierarchical Model Figure E.1 Sample database. same database tree or in several different trees. Record replication has two major drawbacks: 1. Data inconsistency may result when updating takes place. 2. Waste of space is unavoidable. We shall deal with this issue in Section E.5 by introducing the concept of a virtual record. E.2 Tree-Structure Diagrams A tree-structure diagram is the schema for a hierarchical database. Such a diagram consists of two basic components: 1. Boxes, which correspond to record types 2. Lines, which correspond to links A tree-structure diagram serves the same purpose as an entity–relationship (E-R) diagram; namely, it specifies the overall logical structure of the database. A tree￾structure diagram is similar to a data-structure diagram in the network model. The main difference is that, in the latter, record types are organized in the form of an arbitrary graph, whereas in the former, record types are organized in the form of a rooted tree. We have to be more precise about what a rooted tree is. First, there can be no cycles in the underlying graph. Second, there is a record type that is designated as the root of the tree. The relationships formed in the tree-structure diagram must be such that only one-to-many or one-to-one relationships exist between a parent and a child. The general form of a tree-structure diagram appears in Figure E.2. Note that the arrows are pointing from children to parents. A parent may have an arrow pointing to a child, but a child must have an arrow pointing to its parent. The database schema is represented as a collection of tree-structure diagrams. For each such diagram, there exists one single instance of a database tree. The root of this tree is a dummy node. The children of the dummy node are instances of the