APPENDIX Network Model In the relational model,the data and the relationships among data are represented by a collection of tables.The network model differs from the relational model in that data are represented by collections of records,and relationships among data are represented by links. In this chapter we illustrate our concepts using a bank enterprise with the schema shown in Figure 2.15. D.1 Basic Concepts A network database consists of a collection of records connected to one another through links.A record is in many respects similar to an entity in the E-R model. Each record is a collection of fields(attributes),each of which contains only one data value.A link is an association between precisely two records.Thus,a link can be viewed as a restricted(binary)form of relationship in the sense of the E-R model. As an illustration,consider a database representing a customer-account rela- tionship in a banking system.There are two record types,customer and account.As we saw earlier,we can define the customer record type,using Pascal-like notation: type customer record customer name:string; customer_street:string; customer_city:string; end The account record type can be defined as type account record account_number:string; balance:integer; end The sample database in Figure D.1 shows that Hayes has account A-102,Johnson has accounts A-101 and A-201,and Turner has account A-305. 1
APPENDIX D Network Model In the relational model, the data and the relationships among data are represented by a collection of tables. The network model differs from the relational model in that data are represented by collections of records, and relationships among data are represented by links. In this chapter we illustrate our concepts using a bank enterprise with the schema shown in Figure 2.15. D.1 Basic Concepts A network database consists of a collection of records connected to one another through links. A record is in many respects similar to an entity in the E-R model. Each record is a collection of fields (attributes), each of which contains only one data value. A link is an association between precisely two records. Thus, a link can be viewed as a restricted (binary) form of relationship in the sense of the E-R model. As an illustration, consider a database representing a customer-account relationship in a banking system. There are two record types, customer and account. As we saw earlier, we can define the customer record type, using Pascal-like notation: type customer = record customer name: string; customer street: string; customer city: string; end The account record type can be defined as type account = record account number: string; balance: integer; end The sample database in Figure D.1 shows that Hayes has account A-102, Johnson has accounts A-101 and A-201, and Turner has account A-305. 1
2 Appendix D Network Model Hayes Main Harrison A-102400 A-101500 Johnson Alma Palo Alto A-201 900 Turner Putnam Stamford A-305350 Figure D.1 Sample database. D.2 Data-Structure Diagrams A data-structure diagram is a schema representing the design of a network database. Such a diagram consists of two basic components: 1.Boxes,which correspond to record types 2.Lines,which correspond to links A data-structure diagram serves the same purpose as an E-R diagram;namely,it specifies the overall logical structure of the database.So that you will understand how such diagrams are structured,we shall show how to transform E-R diagrams into their corresponding data-structure diagrams. D.2.1 Binary Relationship Consider the E-R diagram of Figure D.2a,consisting of two entity sets,customer and account,related through a binary,many-to-many relationship depositor,with no descriptive attributes.This diagram specifies that a customer may have sev- eral accounts,and that an account may belong to several different customers. The corresponding data-structure diagram appears in Figure D.2b.The record type customer corresponds to the entity set customer.It includes three fields- customer account customer name depositor account_number customer_street balance customer_city (a)E-R diagram customer_name customer_street customer_cily account number balance depositor (b)Data structure-diagram Figure D.2 E-R diagram and its corresponding data-structure diagram
2 Appendix D Network Model Figure D.1 Sample database. D.2 Data-Structure Diagrams A data-structure diagram is a schema representing the design of a network database. Such a diagram consists of two basic components: 1. Boxes, which correspond to record types 2. Lines, which correspond to links A data-structure diagram serves the same purpose as an E-R diagram; namely, it specifies the overall logical structure of the database. So that you will understand how such diagrams are structured, we shall show how to transform E-R diagrams into their corresponding data-structure diagrams. D.2.1 Binary Relationship Consider the E-R diagram of Figure D.2a, consisting of two entity sets, customer and account, related through a binary, many-to-many relationship depositor, with no descriptive attributes. This diagram specifies that a customer may have several accounts, and that an account may belong to several different customers. The corresponding data-structure diagram appears in Figure D.2b. The record type customer corresponds to the entity set customer. It includes three fields— Figure D.2 E-R diagram and its corresponding data-structure diagram
D.2 Data-Structure Diagrams 3 customer name customer_street customer city account number balance customer (a) account customer_name customer_street customer city account number balance custoner (b) account Figure D.3 Two data-structure diagrams. customer-name,customer-street,and customer-city-as defined in Section D.1.Simi- larly,account is the record type corresponding to the entity set account.It includes the two fields account number and balance.Finally,the relationship depositor has been replaced with the link depositor. The relationship depositor is many to many.If the relationship depositor were one to many from customer to account,then the link depositor would have an arrow pointing to customer record type(Figure D.3a).Similarly,if the relationship deposi- tor were one to one,then the link depositor would have two arrows:one pointing to account record type and one pointing to customer record type(Figure D.3b).Since, in the E-R diagram of Figure D.2a,the depositor relationship is many to many,we draw no arrows on the link depositor in Figure D.2b. A database corresponding to the described schema may thus contain a num- ber of customer records linked to a number of account records.A sample database corresponding to the data-structure diagram of Figure D.2 appears in Figure D.4. Since the relationship is many to many,we show that Johnson has accounts A-101 and A-201 and that account A-201 is owned by both Johnson and Smith.A sample database corresponding to the data-structure diagram of Figure D.3a is depicted in Figure D.1.Since the relationship is one to many from customer to account,a customer may have more than one account,as Johnson does-she owns both A-101 and A-201.An account,however,cannot belong to more than one customer, and the database observes this restriction.Finally,a sample database correspond- ing to the data-structure diagram of Figure D.3b is shown in Figure D.5.Since the relationship is one to one,an account can be owned by precisely one customer, and a customer can have only one account;the sample database follows those rules. Hayes Main Harrison A-102400 A-101 500 Johnson Alma Palo Alto A-201 900 Turner Putnam Stamford A-305350 Figure D.4 Sample database corresponding to diagram of Figure D.2b
D.2 Data-Structure Diagrams 3 Figure D.3 Two data-structure diagrams. customer-name, customer street, and customer city—as defined in Section D.1. Similarly, account is the record type corresponding to the entity set account. It includes the two fields account number and balance. Finally, the relationship depositor has been replaced with the link depositor. The relationship depositor is many to many. If the relationship depositor were one to many from customer to account, then the link depositor would have an arrow pointing to customerrecord type (Figure D.3a). Similarly, if the relationship depositor were one to one, then the link depositor would have two arrows: one pointing to account record type and one pointing to customer record type (Figure D.3b). Since, in the E-R diagram of Figure D.2a, the depositor relationship is many to many, we draw no arrows on the link depositor in Figure D.2b. A database corresponding to the described schema may thus contain a number of customer records linked to a number of account records. A sample database corresponding to the data-structure diagram of Figure D.2 appears in Figure D.4. Since the relationship is many to many, we show that Johnson has accounts A-101 and A-201 and that account A-201 is owned by both Johnson and Smith. A sample database corresponding to the data-structure diagram of Figure D.3a is depicted in Figure D.1. Since the relationship is one to many from customer to account, a customer may have more than one account, as Johnson does—she owns both A-101 and A-201. An account, however, cannot belong to more than one customer, and the database observes this restriction. Finally, a sample database corresponding to the data-structure diagram of Figure D.3b is shown in Figure D.5. Since the relationship is one to one, an account can be owned by precisely one customer, and a customer can have only one account; the sample database follows those rules. Figure D.4 Sample database corresponding to diagram of Figure D.2b
Appendix D Network Model Hayes Main Harrison A-102400 Lindsay Park Pittsfield A-222700 Turner Putnam Stamford A-305 350 Figure D.5 Sample database corresponding to diagram of Figure D.3b If a relationship includes descriptive attributes,the transformation from an E-R diagram to a data-structure diagram is more complicated.A link cannot contain any data value,so a new record type needs to be created and links need to be established. Consider the E-R diagram of Figure D.2a.Suppose that we add the attribute access date to the relationship depositor,to denote the most recent time that a customer accessed the account.This newly derived E-R diagram appears in Fig- ure D.6a.To transform this diagram to a data-structure diagram,we must 1.Replace entities customer and account with record types customer and account, respectively. 2.Create a new record type access date with a single field to represent the date. 3.Create the following many-to-one links: access_date customer account cusfonter_name depositor account number customer_street balance customer city (a)E-R diagram customer_name customer_sfreet customer_cify account number balance customer account customer_date account date access date access date (b)Network diagram Figure D.6 E-R diagram and its corresponding network diagram
4 Appendix D Network Model Figure D.5 Sample database corresponding to diagram of Figure D.3b. If a relationship includes descriptive attributes, the transformation from an E-R diagram to a data-structure diagram is more complicated. A link cannot contain any data value, so a new record type needs to be created and links need to be established. Consider the E-R diagram of Figure D.2a. Suppose that we add the attribute access date to the relationship depositor, to denote the most recent time that a customer accessed the account. This newly derived E-R diagram appears in Figure D.6a. To transform this diagram to a data-structure diagram, we must 1. Replace entities customer and account with record types customer and account, respectively. 2. Create a new record type access date with a single field to represent the date. 3. Create the following many-to-one links: Figure D.6 E-R diagram and its corresponding network diagram
D.2 Data-Structure Diagrams 5 Hayes Main Harrison 10 June 2009 A-102 400 24May2009 Johnson Alma Palo Alto 17June2009 A-201 900 Turner Putnam Stamford 28May2009 A-305 350 Figure D.7 Sample database corresponding to diagram of Figure D.6b. customer date from the access date record type to the customer record type .account date from the access date record type to the account record type The resulting data-structure diagram appears in Figure D.6b. An instance of a database corresponding to the described schema appears in Figure D.7.It shows that: Account A-201 is held by Johnson alone,and was last accessed by her on 17 June Account A-305 is held by Turner alone,and was last accessed by him on 28 May. Account A-102 is held by both Hayes and Johnson.Hayes accessed it last on 10 June,and Johnson accessed it last on 24 May. D.2.2 General Relationships Consider the E-R diagram of Figure D.8a,which consists of three entity sets- account,customer,and branch-related through the general relationship CAB with no descriptive attribute. Since a link can connect precisely two different record types,we need to connect these three record types through a new record type that is linked to each of them directly. To transform the E-R diagram of Figure D.8a to a network data-structure diagram,we need to do the following: 1.Replace entity sets account,customer,and branch with record types account, customer,and branch,respectively. 2.Create a new record type Rlink that may either have no fields or have a single field containing a unique identifier.The system supplies this identifier,and the application program does not use it directly.This new type of record is sometimes referred to as a dummy(or link or junction)record type
D.2 Data-Structure Diagrams 5 Figure D.7 Sample database corresponding to diagram of Figure D.6b. • customer date from the access date record type to the customer record type • account date from the access date record type to the account record type The resulting data-structure diagram appears in Figure D.6b. An instance of a database corresponding to the described schema appears in Figure D.7. It shows that: • Account A-201 is held by Johnson alone, and was last accessed by her on 17 June. • Account A-305 is held by Turner alone, and was last accessed by him on 28 May. • Account A-102 is held by both Hayes and Johnson. Hayes accessed it last on 10 June, and Johnson accessed it last on 24 May. D.2.2 General Relationships Consider the E-R diagram of Figure D.8a, which consists of three entity sets— account, customer, and branch—related through the general relationship CAB with no descriptive attribute. Since a link can connect precisely two different record types, we need to connect these three record types through a new record type that is linked to each of them directly. To transform the E-R diagram of Figure D.8a to a network data-structure diagram, we need to do the following: 1. Replace entity sets account, customer, and branch with record types account, customer, and branch, respectively. 2. Create a new record type Rlink that may either have no fields or have a single field containing a unique identifier. The system supplies this identifier, and the application program does not use it directly. This new type of record is sometimes referred to as a dummy (or link or junction) record type
Appendix D Network Model branch branch name branch_city branch_assets customer account customer name CAB account_number customer_street balance customer_city (a)E-R diagram customer name customer_street customer city branch_name branch_city assets customer branch account_number balance CustRInk account AcctRink BrnchRInk Rlink (b)Data structure diagram Figure D.8 E-R diagram and its corresponding data-structure diagram. 3.Create the following many-to-one links: CustRInk from Rlink record type to customer record type .AcctRInk from Rlink record type to account record type BrncRInk from Rlink record type to branch record type The resulting data-structure diagram appears in Figure D.8b. A sample database corresponding to the described schema appears in Fig- ure D.9.It shows that Hayes has account A-102 in the Perryridge branch,Johnson has accounts A-101 and A-201 in the Downtown and Perryridge branches,re- spectively,and Turner has account A-305 in the Round Hill branch. We can extend this technique in a straightforward manner to deal with rela- tionships that span more than three entity sets.We create a many-to-one link from the Rlink record to the record types corresponding to each entity set involved in the relationship.We can also extend the technique to deal with a general rela- tionship that has descriptive attributes.We need to add one field to the dummy record type for each descriptive attribute
6 Appendix D Network Model Figure D.8 E-R diagram and its corresponding data-structure diagram. 3. Create the following many-to-one links: • CustRlnk from Rlink record type to customer record type • AcctRlnk from Rlink record type to account record type • BrncRlnk from Rlink record type to branch record type The resulting data-structure diagram appears in Figure D.8b. A sample database corresponding to the described schema appears in Figure D.9. It shows that Hayes has account A-102 in the Perryridge branch, Johnson has accounts A-101 and A-201 in the Downtown and Perryridge branches, respectively, and Turner has account A-305 in the Round Hill branch. We can extend this technique in a straightforward manner to deal with relationships that span more than three entity sets. We create a many-to-one link from the Rlink record to the record types corresponding to each entity set involved in the relationship. We can also extend the technique to deal with a general relationship that has descriptive attributes. We need to add one field to the dummy record type for each descriptive attribute
D.3 The DBTG CODASYL Model 7 A-102400 A-101500 A-201900 A-305350 Hayes Main Harrison Perryridge Horseneck 1700000 Lindsay Park Pittsfield Downtown Brooklyn 9000000 Turner Putnam Stamford 4 Round Hill Horseneck 8000000 Figure D.9 Sample database corresponding to diagram of Figure D.8b. D.3 The DBTG CODASYL Model The first database-standard specification,called the CODASYL DBTG 1971 report, was written in the late 1960s by the Database Task Group.Since then,a number of changes have been proposed many of which are reflected in our discussion concerning the DBTG model. D.3.1 Link Restriction In the DBTG model,only many-to-one links can be used.Many-to-many links are disallowed to simplify the implementation.We represent one-to-one links using a many-to-one link.These restrictions imply that the various algorithms of Section D.2 for transforming an E-R diagram to a data-structure diagram must be revised. Consider a binary relationship that is either one to many or one to one.In this case,the transformation algorithm defined in Section D.2.1 can be applied directly.Thus,for our customer-account database,if the depositor relationship is one to many with no descriptive attributes,then the appropriate data-structure diagram is as shown in Figure D.10a.If the relationship has a descriptive attribute (for example,access-date),then the appropriate data-structure diagram is as shown in Figure D.10b. If the depositor relationship,however,is many to many,then our transforma- tion algorithm must be refined;if the relationship has no descriptive attributes (Figure D.11a),then this algorithm must be employed: 1.Replace the entity sets customer and account with record types customer and account,respectively. 2.Create a new dummy record type,Rlink,that may either have no fields or have a single field containing an externally defined unique identifier. 3.Create the following two many-to-one links:
D.3 The DBTG CODASYL Model 7 Figure D.9 Sample database corresponding to diagram of Figure D.8b. D.3 The DBTG CODASYL Model The first database-standard specification, called the CODASYL DBTG 1971 report, was written in the late 1960s by the Database Task Group. Since then, a number of changes have been proposed many of which are reflected in our discussion concerning the DBTG model. D.3.1 Link Restriction In the DBTG model, only many-to-one links can be used. Many-to-many links are disallowed to simplify the implementation. We represent one-to-one links using a many-to-one link. These restrictions imply that the various algorithms of Section D.2 for transforming an E-R diagram to a data-structure diagram must be revised. Consider a binary relationship that is either one to many or one to one. In this case, the transformation algorithm defined in Section D.2.1 can be applied directly. Thus, for our customer-account database, if the depositor relationship is one to many with no descriptive attributes, then the appropriate data-structure diagram is as shown in Figure D.10a. If the relationship has a descriptive attribute (for example, access-date), then the appropriate data-structure diagram is as shown in Figure D.10b. If the depositor relationship, however, is many to many, then our transformation algorithm must be refined; if the relationship has no descriptive attributes (Figure D.11a), then this algorithm must be employed: 1. Replace the entity sets customer and account with record types customer and account, respectively. 2. Create a new dummy record type, Rlink, that may either have no fields or have a single field containing an externally defined unique identifier. 3. Create the following two many-to-one links:
8 Appendix D Network Model customer name customer_streef customer city account number balance customer account (a) customer_name customer street customer_city account_number balance customer account access date access date (b) Figure D.10 Two data-structure diagrams. .CustRInk from Rlink record type to customer record type AcctRInk from Rlink record type to account record type The corresponding data-structure diagram is as shown in Figure D.11b.An instance of a database corresponding to the described schema appears in Fig- ure D.12.We encourage you to compare this sample database with the one de- scribed in Figure D.4. If the relationship depositor is many to many with a descriptive attribute (for example,access date),then the transformation algorithm is similar to the one described.The only difference is that the new record type Rlink now contains the field access date. customer account customer name depositor account number customer street balance customer_city (a)E-R diagram customer_name customer_street customer_cify account_number balance customer accouni CustRInk AcctRInk Rlink (b)Data structure-diagram Figure D.11 E-R diagram and its corresponding data-structure diagram
8 Appendix D Network Model Figure D.10 Two data-structure diagrams. • CustRlnk from Rlink record type to customer record type • AcctRlnk from Rlink record type to account record type The corresponding data-structure diagram is as shown in Figure D.11b. An instance of a database corresponding to the described schema appears in Figure D.12. We encourage you to compare this sample database with the one described in Figure D.4. If the relationship depositor is many to many with a descriptive attribute (for example, access date), then the transformation algorithm is similar to the one described. The only difference is that the new record type Rlink now contains the field access date. Figure D.11 E-R diagram and its corresponding data-structure diagram
D.3 The DBTG CODASYL Model 9 Hayes Main Harrison A-102400 2 A-101 500 Johnson Alma Palo Alto 3 A-201 900 Smith North Rye A-215 700 5 Figure D.12 Sample database corresponding to the diagram of Figure D.11. In the case of general(that is,nonbinary)relationships,the transformation algorithm is the same as the one described in Section D.2.2.Thus,the E-R diagram of Figure D.8a is transformed into the data-structure diagram of Figure D.8b. D.3.2 DBTG Sets Given that only many-to-one links can be used in the DBTG model,a data-structure diagram consisting of two record types that are linked together has the general form of Figure D.13.This structure is referred to in the DBTG model as a DBTG set.The name of the set is usually chosen to be the same as the name of the link connecting the two record types. In each such DBTG set,the record type A is designated as the owner (or parent) of the set,and the record type B is designated as the member(or child)of the set. Each DBTG set can have any number of set occurrences-that is,actual instances of linked records.For example,in Figure D.14,we have three set occurrences corresponding to the DBTG set of Figure D.13. Since many-to-many links are disallowed,each set occurrence has precisely one owner,and has zero or more member records.In addition,no member record of a set can participate in more than one occurrence of the set at any point.A mem- ber record,however,can participate simultaneously in several set occurrences of different DBTG sets. As an illustration,consider the data-structure diagram of Figure D.15.There are two DBTG sets: A 、B Figure D.13 DBTG set
D.3 The DBTG CODASYL Model 9 Figure D.12 Sample database corresponding to the diagram of Figure D.11. In the case of general (that is, nonbinary) relationships, the transformation algorithm is the same as the one described in Section D.2.2. Thus, the E-R diagram of Figure D.8a is transformed into the data-structure diagram of Figure D.8b. D.3.2 DBTG Sets Given that only many-to-one links can be used in the DBTGmodel, a data-structure diagram consisting of two record types that are linked together has the general form of Figure D.13. This structure is referred to in the DBTG model as a DBTG set. The name of the set is usually chosen to be the same as the name of the link connecting the two record types. In each such DBTG set, the record type A is designated as the owner (or parent) of the set, and the record type B is designated as the member (or child) of the set. Each DBTG set can have any number of set occurrences— that is, actual instances of linked records. For example, in Figure D.14, we have three set occurrences corresponding to the DBTG set of Figure D.13. Since many-to-many links are disallowed, each set occurrence has precisely one owner, and has zero or more member records. In addition, no member record of a set can participate in more than one occurrence of the set at any point. A member record, however, can participate simultaneously in several set occurrences of different DBTG sets. As an illustration, consider the data-structure diagram of Figure D.15. There are two DBTG sets: Figure D.13 DBTG set
10 Appendix D Network Model al a3 b3 b4 b5 Figure D.14 Three set occurrences. 1.depositor,which has customer as the owner of the DBTG set,and account as the member of the DBTG set 2.account branch,which has branch as the owner of the DBTG set,and account as the member of the DBTG set The set depositor can be defined as follows: set name is depositor owner is customer member is account The set account branch can be defined similarly: set name is account _branch owner is branch member is account An instance of the database appears in Figure D.16.There are six set occur- rences listed next:three of set depositor (sets 1,2,and 3),and three of set account branch (sets 4,5,and 6). 1.Owner is customer record Hayes,with a single member account record A-102 2.Owner is customer record Johnson,with two member account records A-101 and A-201 3.Owner is customer record Turner,with three member account records A-305, A-402,andA-408. customer_name customer streef customer_city branch_name branch_city assets customer brancht depositor account branch account number balance account Figure D.15 Data-structure diagram
10 Appendix D Network Model Figure D.14 Three set occurrences. 1. depositor, which has customer as the owner of the DBTG set, and account as the member of the DBTG set 2. account branch, which has branch as the owner of the DBTG set, and account as the member of the DBTG set The set depositor can be defined as follows: set name is depositor owner is customer member is account The set account branch can be defined similarly: set name is account branch owner is branch member is account An instance of the database appears in Figure D.16. There are six set occurrences listed next: three of set depositor (sets 1, 2, and 3), and three of set account branch (sets 4, 5, and 6). 1. Owner is customerrecord Hayes, with a single member accountrecord A-102. 2. Owner is customer record Johnson, with two member account records A-101 and A-201. 3. Owner is customer record Turner, with three member account records A-305, A-402, and A-408. Figure D.15 Data-structure diagram