Figure Ref-1. A semantic schema for a university application.
Figure Ref-2. A relational schema for the university
application.
This chapter defines the Network Data Model and adapts the top-down
database design methodology to network databases. Section 3 of this
chapter discusses network database languages: application of the
generic fourth-generation and logic-based languages and a special
navigational language for the Network Model.
Since the 1970s, the Network Data Model has been very popular in the
industry. An alternative name of the model is CODASYL/DBTG, after the
name of the committee that produced a standard for the Network Model
(CODASYL Data Base Task Group).
6.1. Definitions
Orderless network schema - a binary schema satisfying the following:
a. All the abstract categories are pairwise disjoint.
b. Every relation is either an attribute (an m:1 relation to a
concrete category), or a 1:m relation between different
abstract categories.
[] DEPARTMENT - category
[] STUDENT - category
[] INSTRUCTOR - category
[] QUARTER - category
[] COURSE - category
[] OFFERING - category
[] ENROLLMENT - category
[] WORK - category
[] - relation from INSTRUCTOR to WORK (1:m)
[] - relation from DEPARTMENT to WORK (1:m)
[] DEPARTMENT-NAMING - category
[] - relation from DEPARTMENT to DEPARTMENT-NAMING (1:m)
[] the-name - attribute of DEPARTMENT-NAMING, range: String
(m:1)
[] last-name - attribute of STUDENT, range: String (m:1)
[] first-name - attribute of STUDENT, range: String (m:1)
[] birth-year - attribute of STUDENT, range: 1870..1990 (m:1)
[] address - attribute of STUDENT, range: String (m:1)
[] last-name - attribute of INSTRUCTOR, range: String (m:1)
[] first-name - attribute of INSTRUCTOR, range: String (m:1)
[] birth-year - attribute of INSTRUCTOR, range: 1870..1990
(m:1)
[] address - attribute of INSTRUCTOR, range: String (m:1)
[] major-st - relation from DEPARTMENT to STUDENT (1:m)
[] minor-st - relation from DEPARTMENT to STUDENT (1:m)
[] year - attribute of QUARTER, range: 1980..1995 (m:1)
[] season - attribute of QUARTER, range: String (m:1)
[] name - attribute of COURSE, range: String (m:1)
[] - relation from INSTRUCTOR to OFFERING (1:m)
[] - relation from COURSE to OFFERING (1:m)
[] - relation from QUARTER to OFFERING (1:m)
[] final-grade - attribute of ENROLLMENT, range: 0..100 (m:1)
[] - relation from OFFERING to ENROLLMENT (1:m)
[] - relation from STUDENT to ENROLLMENT (1:m)
Figure 6-1. An orderless network schema for the university
application.
Example 6-1.
The schema on Figure could be an orderless network schema
for a university, provided there are no persons but students
and instructors, and the categories INSTRUCTOR and STUDENT are
disjoint.
Default names of relations
It is customary in the network model to name relations as
domain hyphen range
Of course, this convention may be used only when there is no
other relation between the same domain and range.
In the graphic representation of network schemas we may omit some
of the names of the relations. The omitted names by default
conform to the above convention.
Example 6-2.
[] instructor-work - relation from INSTRUCTOR to WORK
(1:m)
Onto relation - a relation whose inverse is total.
This means that a relation R from C to C is onto if for every
- 1 2
object y of C there is an object x of C such that xRy.
- 2 - 1 ---
Example 6-3.
[] - relation from STUDENT to ENROLLMENT (1:m,onto)
(It is onto because every enrollment has a student
related to it.)
[] - relation from INSTRUCTOR to WORK (1:m,onto)
(It is onto because every event of work is related to an
instructor.)
The phrase ``relation R is onto category C'' means:
R is an onto relation, and its range is C.
The phrase ``category C depends on category C '' means:
2 1
there is a relation from C onto C
-------- 1 ---- 2
(that is, there is a relation which relates every object of C to
2
an object of C ).
1
[diagram skipped]
Figure 6-2. C depends on C .
------ - - 2 1
Example 6-4.
o OFFERING depends on COURSE
o OFFERING depends on QUARTER
o OFFERING depends on INSTRUCTOR
o ENROLLMENT depends on OFFERING
o ENROLLMENT depends on STUDENT
o DEPARTMENT-NAMING depends on DEPARTMENT
o WORK depends on DEPARTMENT
o WORK depends on INSTRUCTOR
The phrase ``category C indirectly depends on category C '' means
1 2
(recursively):
C depends on C , or there exists C such that C depends on
1 2 3 1
C and C indirectly depends on C .
3 3 2
Example 6-5.
o ENROLLMENT indirectly depends on OFFERING
(since ENROLLMENT depends on OFFERING).
o ENROLLMENT indirectly depends on COURSE
Independent category - an abstract category which depends on no
category.
Example 6-6.
Independent categories:
STUDENT, INSTRUCTOR, DEPARTMENT, COURSE, QUARTER.
Ordered network schema - a binary system consisting of:
a. An orderless network schema.
b. A category, called SYSTEM, in which at all times there is
only one and the same object SYSTEM.
c. Relations from SYSTEM onto some of the abstract categories
of the orderless schema, such that every abstract category
of the orderless schema would be indirectly dependent on
SYSTEM.
Example 6-7.
[] - relation from SYSTEM to STUDENT (1:m,onto)
[] - relation from SYSTEM to INSTRUCTOR (1:m,onto)
[] - relation from SYSTEM to DEPARTMENT (1:m,onto)
[] - relation from SYSTEM to COURSE (1:m,onto)
[] - relation from SYSTEM to QUARTER (1:m,onto)
d. For every relation R between different abstract categories
C and C there is a relation NEXT such that:
1 2 R
o The domain of NEXT is C .
R 2
o The range of NEXT is C .
R 2
o For every object x in C , NEXT constitutes a linear
- 1 R
order of C 's objects connected by R to x.
2 -
[diagram skipped]
Example 6-8.
[] next-system-department - relation from DEPARTMENT to
DEPARTMENT (1:1)
This is a chain connecting all of the departments:
d ->d ->d ->d
1 2 3 4
Example 6-9.
[] next-system-student - relation from STUDENT to
STUDENT (1:1)
This is a chain connecting all of the students:
s ->s ->s ->...->s
1 2 3 500
Example 6-10.
[] next-major-st - relation from STUDENT to STUDENT
(1:1)
This is a set of chains, one chain per department, connecting
all the majoring students of the department.
For department d : s ->s ->s ->s
1 11 25 3 15
For department d : trivial chain because the department has
2
only 1 majoring student.
For department d : empty chain because the department has no
3
majoring students.
For department d : s ->s ->s
4 1 220 31
(The remaining 492 students have not declared their majors.)
Network schema terminology
The following terms are frequently used in network database
management systems. Most of them have synonyms in the binary
terminology.
Record-type - abstract category.
Example 6-11.
DEPARTMENT is a record-type.
Field - attribute.
Example 6-12.
LAST-NAME is a field.
Set-type - a nonattribute relation between different categories.
Example 6-13.
[] major-st - relation from DEPARTMENT to STUDENT
(1:m)
[] instructor-work - relation from INSTRUCTOR to WORK
(1:m)
Record occurrence - a part of an instantaneous database, consisting of
exactly one abstract object and all its attributes.
Example 6-14.
A record occurrence of record-type STUDENT:
[] ONE-student - category
[] last-name - attribute of ONE-student, range:
Jackson (m:1)
[] first-name - attribute of ONE-student, range: Mary
(m:1)
[] birth-year - attribute of ONE-student, range: 1970
(m:1)
[] address - attribute of ONE-student, range:
123 Dorms (m:1)
Set occurrence of a set-type R for an object x - a part of an
instantaneous database consisting only of x, all the objects
related to x by R, and the relation NEXT on these objects.
R
Example 6-15.
Let s , s , s , s be the only majoring students of department
1 2 3 4
d. Then the following may be a set occurrence:
d, s NEXT s NEXT s NEXT s
- 1 major-st 2 major-st 3 major-st 4
[diagram skipped]
Each set-type whose domain is SYSTEM has exactly one set-
occurrence, since there is only one object of the record-type
SYSTEM.
Example 6-16.
The following is the set-occurrence of SYSTEM-STUDENT in an
instantaneous database.
first next next
SYSTEM ------- student ------ student ------ student
1 2 3
Example 6-17.
The following figure shows a part of a network instantaneous
database. This part contains all the record-occurrences of
STUDENT, DEPARTMENT, and DEPARTMENT-NAMING and all the set-
occurrences of SYSTEM-STUDENT, SYSTEM-DEPARTMENT, DEPARTMENT-
-DEPARTMENT-NAMING, MAJOR-ST, and MINOR-ST.
[] SYSTEM - category
[] DEPARTMENT1 - category
[] DEPARTMENT2 - category
[] DEPARTMENT3 - category
[] DEPARTMENT4 - category
[] DEPARTMENT5 - category
[] STUDENT1 - category
[] last-name - attribute of STUDENT1, range: Victory (m:1)
[] first-name - attribute of STUDENT1, range: Elizabeth (m:1)
[] birth-year - attribute of STUDENT1, range: 1966 (m:1)
[] address - attribute of STUDENT1, range: 100 Sun St (m:1)
[] STUDENT2 - category
[] last-name - attribute of STUDENT2, range: Wood (m:1)
[] first-name - attribute of STUDENT2, range: Michael (m:1)
[] birth-year - attribute of STUDENT2, range: 1964 (m:1)
[] address - attribute of STUDENT2, range: 110 Dorms (m:1)
[] last-name - attribute of STUDENT3, range: Howards (m:1)
[] first-name - attribute of STUDENT3, range: Jane (m:1)
[] birth-year - attribute of STUDENT3, range: 1965 (m:1)
[] address - attribute of STUDENT3, range: 200 Dorms (m:1)
[] STUDENT3 - category
[] DEPARTMENT-NAMING1 - category
[] DEPARTMENT-NAMING2 - category
[] DEPARTMENT-NAMING3 - category
[] DEPARTMENT-NAMING4 - category
[] DEPARTMENT-NAMING5 - category
[] DEPARTMENT-NAMING6 - category
[] DEPARTMENT-NAMING7 - category
[] s-st - relation from SYSTEM to STUDENT1 (first)
[] s-st - relation from STUDENT1 to STUDENT2 (next)
[] s-st - relation from STUDENT2 to STUDENT3 (next)
[] s-dp - relation from SYSTEM to DEPARTMENT1 (first)
[] s-dp - relation from DEPARTMENT1 to DEPARTMENT2 (next)
[] s-dp - relation from DEPARTMENT2 to DEPARTMENT3 (next)
[] s-dp - relation from DEPARTMENT3 to DEPARTMENT4 (next)
[] s-dp - relation from DEPARTMENT4 to DEPARTMENT5 (next)
[] d-dn - relation from DEPARTMENT1 to DEPARTMENT-NAMING1
(first)
[] d-dn - relation from DEPARTMENT-NAMING1 to DEPARTMENT-
NAMING2 (next)
[] d-dn - relation from DEPARTMENT2 to DEPARTMENT-NAMING3
(first)
[] d-dn - relation from DEPARTMENT-NAMING3 to DEPARTMENT-
NAMING4 (next)
[] d-dn - relation from DEPARTMENT3 to DEPARTMENT-NAMING5
(first)
[] d-dn - relation from DEPARTMENT4 to DEPARTMENT-NAMING6
(first)
[] d-dn - relation from DEPARTMENT5 to DEPARTMENT-NAMING7
(first)
[] mnr - relation from STUDENT2 to STUDENT1 (next)
[] mjr - relation from STUDENT2 to STUDENT3 (next)
[] mnr - relation from STUDENT3 to STUDENT2 (next)
[] mnr - relation from DEPARTMENT4 to STUDENT3 (first)
[] mjr - relation from DEPARTMENT2 to STUDENT1 (first)
[] mjr - relation from DEPARTMENT3 to STUDENT2 (first)
[] name - attribute of DEPARTMENT-NAMING1, range: Mathematics
(m:1)
[] name - attribute of DEPARTMENT-NAMING2, range: Math (m:1)
[] name - attribute of DEPARTMENT-NAMING3, range: Computer-
Science (m:1)
[] name - attribute of DEPARTMENT-NAMING4, range: CS (m:1)
[] name - attribute of DEPARTMENT-NAMING5, range: Arts (m:1)
[] name - attribute of DEPARTMENT-NAMING6, range: Economics
(m:1)
[] name - attribute of DEPARTMENT-NAMING7, range: Physics
(m:1)
Figure 6-3. A part of a network instantaneous database.
Owner of a set-type R - its domain.
Example 6-18.
DEPARTMENT is the owner of MAJOR-ST.
Member of a set-type R - its range.
Example 6-19.
STUDENT is the member of MAJOR-ST.
[diagram skipped]
Order-type of a set type R - the integrity constraints, the
implementational restrictions, or the inference rules regarding
the ordering of a set-occurrence (as determined by the relation
NEXT ).
R
Many network database management systems recognize the following
order types:
`order is last' - the member object last related (in time) to a
given owner object becomes the last in the order among all
the member objects related by the relation to the owner
object.
Example 6-20.
Let the following be the set occurrence of MAJOR-ST for
department d:
d, s NEXT s NEXT s NEXT s
- 1 major-st 2 major-st 3 major-st 4
Now assume that another student s becomes a majoring student
of d. Then the new set occurrence would be
d, s NEXT s NEXT s NEXT s NEXT s
1 major-st 2 major-st 3 major-st 4 major-st
`order is first' - the member object last (in time) related to a
given owner object becomes the first in the order among all
the member objects related by the relation to the owner
object.
Example 6-21.
Let the following be the set occurrence of MAJOR-ST for
department d:
d, s NEXT s NEXT s NEXT s
- 1 major-st 2 major-st 3 major-st 4
Now assume that another student s becomes a majoring student
of d. Then the new set occurrence would be
d,
s NEXT s NEXT s NEXT s NEXT
major-st 1 major-st 2 major-st 3 major-
s
st 4
`order is ascending by field f' - the member object last related
to a given owner object is put in a position within the
order according to the following criterion for every two
member objects y and y :
1 2
if y NEXT y then y .f < y .f
1 R 2 1 - 2
This order type is often also called order by key. This
``key'' has nothing to do with the concept of key as defined
for the relational model. To avoid confusion, the "order by
key" terminology is not used in this text.
`order is descending by field f' - the member object last related
to a given owner object is put in a position within the
order according to the following criterion for every two
member objects y and y :
1 2
if y NEXT y then y .f > y .f
1 R 2 1 - 2
`order is o , o ,..., o ', where each o is of the form
1 2 k i
`ascending by field f ' or `descending by field f '
i i
- a lexicographic combination of ordering conditions on
several fields.
`order is current' -- no constraints, restrictions, or program-
independent rules for the order. Pragmatically, the
position of a new object is determined by the application
program: the position will be right next to the last object
accessed by the program within the same set-occurrence.
6.2. Database Design
Conversion algorithm of a semantic schema into a network schema whose
quality is among the highest possible for the latter (provided
the original semantic schema is of high quality):
1. Convert all abstract categories into disjoint ones as in the
conversion for the Relational Model.
Note:
o In the Network Model, the categories need not have keys.
Thus, when the solution Events is chosen, its redundancy
cannot be controlled in terms of the key. If the
supercategory has a 1:1 attribute, then we can specify an
integrity constraint controlling the Events redundancy in
terms of that attribute.
Example 6-22.
Suppose we had
[] ssn - attribute of PERSON, range: Integer (1:1)
After the conversion into Events we would have
[] ssn - attribute of STUDENT, range: Integer (1:1)
[] ssn - attribute of INSTRUCTOR, range: Integer (1:1)
In this case, we can specify a constraint for every relation
whose domain or range was the category PERSON. For the
relation ADDRESS such a constraint is:
for every s in STUDENT:
for every i in INSTRUCTOR:
if s.SSN=i.SSN
then
s.ADDRESS=i.ADDRESS or
(s ADDRESS null and i ADDRESS null)
o The available network database management systems usually do
not support sophisticated userviews; they support only
subschemas, which are trivial userviews. This means that
normally the solution Union+Events should not be chosen in
the design of a network schema.
2. Convert every proper 1:m or m:m relation whose range is a
concrete category into a new abstract category and its two
functional relations through a relation-split.
3. Convert every proper many-to-many relation into a category and
two functional relations through a relation-split.
4. Convert every m:1 nonattribute relation into a 1:m relation by
changing its direction and its name.
Example 6-23.
Instead of
[] the-student - relation from ENROLLMENT to STUDENT
(m:1)
we have
[] student-enrollment - relation from STUDENT to
ENROLLMENT (1:m)
5. Convert every 1:m relation whose domain and range are the same
category into a new category, a 1:1 onto relation, and a 1:m onto
relation, through a relation-split.
Example 6-24.
If we had:
[] subdepartment - relation from DEPARTMENT to
DEPARTMENT (1:m)
then we would convert it into:
[] event-of-SUBDEPARTMENT - category
[] the-event-of-the-same-department - relation from
DEPARTMENT to event-of-SUBDEPARTMENT (1:1,onto)
[] department-subdepartment - relation from DEPARTMENT
to event-of-SUBDEPARTMENT (1:m,onto)
Example 6-25.
The binary schema of the university has been converted so far
into the orderless network schema of Figure on page .
6. Add the category SYSTEM, which always has just one object - the
enterprise or the world for which the database is being designed.
7. Relate every independent category C to the category SYSTEM:
[] system-C - relation from SYSTEM to C (1:m,onto)
Example 6-26.
[] system-department - relation from SYSTEM to
DEPARTMENT (1:m,onto)
8. If there are still abstract categories C that do not indirectly
depend on SYSTEM (a very rare case), then relate them to SYSTEM:
[] system-C - relation from SYSTEM to C (1:m,onto)
Example 6-27.
There is no such problem in our schema. Let's spoil our
schema a bit to have such a problem. If the relation MAJOR-ST
were onto:
[] major-st - relation from DEPARTMENT to STUDENT
(1:m,onto)
and in addition we had a relation assigning one student
council liaison to several departments:
[] student-council-liaison-for-department - relation
from STUDENT to DEPARTMENT (1:m,onto)
then the categories STUDENT and DEPARTMENT would depend on
each other. None of the categories would be independent. We
have to link at least one of them to SYSTEM, so that they
would indirectly depend on SYSTEM:
[] system-department - relation from SYSTEM to
DEPARTMENT (1:m,onto)
9. Define order-type of every nonattribute relation R as follows:
If the domain of the relation is SYSTEM
a. then (``order is by ascendance or descendance by fields''):
(1) Let C be the range of this relation. Pick an attribute
of C, or a list of attributes, so that the application
programs are most likely to access the objects of C in
the order which can be defined by these attributes.
(2) Specify the order-type to preserve the ascendance-
descendance of the above attributes.
(A list of attributes establishes precedence between
them: the objects are ordered primarily according to
the first attribute in the list. Two objects that have
the same value of the first attribute in the list are
ordered according to the second attribute, and so on.)
This need not be a deterministic (unambiguous)
specification of the order - two distinct objects may
have equal values in each of the attributes in the
list. (In many DBMSs, such two objects are called
duplicates.)
The list of attributes may be empty, as it is, for
example, when C has no attributes at all.
Example 6-28.
o The order of SYSTEM-COURSE is ascending by NAME.
o The order of SYSTEM-QUARTER is ascending by YEAR,
descending by SEASON. (Fortunately, the alphabetic order
of seasons, `Winter' > `Spring' > `Fall', coincides with
their natural order.)
o The order of SYSTEM-INSTRUCTOR is ascending by LAST-NAME,
ascending by FIRST-NAME.
o The order of SYSTEM-STUDENT is ascending by LAST-NAME,
ascending by FIRST-NAME.
o The order of SYSTEM-DEPARTMENT has no constraint.
b. else (``order is last''):
Let the order be the order of insertion or connection, that
is, there is a dynamic constraint (restriction) that when an
object x becomes connected by R to an object y, this x
becomes the last by NEXT among the objects connected by R
R
to y.
10. Translate the integrity constraints into the terms of the new
schema:
a. The constraints of the original schema.
b. The additional constraints accumulated during the conversion
process.
6.3. Network Languages
6.3.1. Fourth-generation programming
Syntactically, this language is the same as the binary extension of
Pascal but is used for network schemas. Pragmatically, there is one
difference:
o In the Binary and Relational models, there is no order between
the objects. Thus, the for loops are performed in an arbitrary
order, transparent to the application programmer. The DBMS would
usually attempt to find the most efficient order dependent on the
circumstances of the program run and the physical structure of
the database.
o In the Network Model, the loops are performed in the order
specified by the NEXT ordering relations. This reduces the
flexibility of the application program by making it depend on
information which is not strictly relevant for the program's
goals. Also, this does not allow for optimization of the program
by the DBMS.
Example 6-29.
The university has decided to expel all the students whose
average grade is below 60 (out of 100). To prevent this
wrong-doing to computer science students, the department
offered a fictitious course, Computer-Pass, by Prof. Good, in
which all computer science students are to receive a
sufficient grade so as to not to be expelled, if possible.
The following program fabricates Prof. Good and the
Computer-Pass course, enrolls students in this course, grades
them accordingly, and prints the names of those computer
science students whom this measure cannot help.
program Pass (Input, Output, UNIVERSITY-DB, UNIVERSITY-MASTER-VIEW);
var Computer-Pass-Course, Prof-Good, Good-Offer, comp-science,
work, this-quarter, cs-student, her-enrollment, fictitious-enrollment:
ABSTRACT;
var the-grade, desired-grade, number-of-grades,
total-of-grades, current-year: INTEGER;
begin
(* Get the current year from the standard input file.*)
read (current-year);
(* Fabricate the course, Prof. Good, and the offering. *)
transaction begin
create new Computer-Pass-Course in COURSE;
Computer-Pass-Course. NAME := `Computer Pass';
create new Prof-Good in INSTRUCTOR;
Prof-Good. LAST-NAME := `Good';
create new Good-Offer in OFFERING;
relate: Computer-Pass-Course COURSE-OFFERING Good-Offer;
relate: Prof-Good INSTRUCTOR-OFFERING Good-Offer;
for this-quarter in QUARTER
satisfying (this-quarter. YEAR = current-year and
this-quarter. SEASON = `Winter') do
relate: this-quarter QUARTER-OFFERING Good-Offer;
end;
(*The following two nested loops will be performed only once. Inside
the body of the second loop, the variable comp-science will refer
to the Computer Science Department.*)
for computer-science-name in DEPARTMENT-NAMING
satisfying (computer-science-name.NAME= `COMPUTER SCIENCE') do
for comp-science in DEPARTMENT
satisfying (computer-science DEPARTMENT-DEPARTMENT-
NAMING comp-science-name) do
begin
transaction begin
create new work in WORK;
relate: Prof-Good INSTRUCTOR-WORK work;
relate: comp-science DEPARTMENT-WORK work
end;
for cs-student in STUDENT
satisfying (comp-science MAJOR-ST cs-student) do
begin
(* calculate this student's current statistics: number-of-
grades and total-of-grades *)
number-of-grades := 0;
total-of-grades := 0;
for her-enrollment in ENROLLMENT
satisfying (cs-student STUDENT-ENROLLMENT her-
enrollment and not her-enrollment FINAL-GRADE
null) do
begin
the-grade :=
cs-student.FINAL-GRADE;
number-of-grades := number-of-grades + 1;
total-of-grades := total-of-grades + the-
grade
end;
(* calculate the minimal desired grade in the computer-pass
course, solving the equation
(total+x)/(number+1) = 60 *)
desired-grade := 60 * (number-of-grades + 1) - total-
of-grades;
if desired-grade > 100
then
(* the student cannot be helped. Print a
message *)
writeln (`The student ', cs-student.
LAST-NAME, ` cannot be helped.
Sorry!')
else
if desired-grade > 60 then
transaction begin
create new fictitious-enrollment in
ENROLLMENT;
relate: cs-student STUDENT-
ENROLLMENT fictitious-enrollment;
relate: Good-Offer OFFERING-
ENROLLMENT fictitious-enrollment;
fictitious-enrollment. FINAL-GRADE
:= desired-grade
end
end
end
end.
6.3.2. Logic
Since every network schema is a binary schema, we can use the same
language of Predicate Calculus as was defined for the Binary Model.
Example 6-30.
Has every student taken at least one course in 1990?
for every st in STUDENT:
exists enrl in ENROLLMENT:
((st STUDENT-ENROLLMENT enrl) and
exists offer in OFFERING:
exists quarter in QUARTER:
quarter QUARTER-OFFERING offer and
offer OFFERING-ENROLLMENT enrl and
quarter.YEAR=1990)
Example 6-31.
Who took Prof. Smith's courses?
get student.LAST-NAME where
exists enrl in ENROLLMENT:
exists prof in INSTRUCTOR:
exists offer in OFFERING:
prof.LAST-NAME=`Smith' and
prof INSTRUCTOR-OFFERING offer and
offer OFFERING-ENROLLMENT enrl and
student STUDENT-ENROLLMENT enrl
6.3.3. *Navigation
The language presented here is a lower-level extension of Pascal for
network data manipulation. Unlike the structured extension of Pascal,
here the user herself is responsible for the organization of loops and
for navigating in the labyrinth of the database.
The model language presented in this section is an adaptation to
Pascal of the logical features of the network data manipulation
language proposed by the standard committee CODASYL/DBTG and used with
minor variations in many commercial network database management
systems.
1. Program heading - same as in the structured extension.
Example 6-32.
program MY (input, output, University-data-base, University-
principal-subschema)
2. There are automatically-generated Pascal record types for every
record-type of the subschema.
Example 6-33.
type DEPARTMENT-NAMING =
record
the-name : String end;
type STUDENT =
record
last-name, first-name : String;
birth-year : 1870..1990;
address : String end;
type INSTRUCTOR =
record
last-name, first-name : String;
birth-year : 1870..1990;
address : String end;
type QUARTER =
record
year : 1980..1995;
season : String end;
type COURSE =
record
name : String end;
type ENROLLMENT =
record
final-grade : 0..100 end;
type NULL-RECORD =
record
end;*
type WORK = NULL-RECORD;
type DEPARTMENT = NULL-RECORD;
type OFFERING = NULL-RECORD
3. Automatically generated Pascal record variables for every
record-type in the subschema.
These variables bear the same names as the corresponding types.
These variables are called template variables. The template
variable for a database record-type is used as a buffer to store
the attributes of record-occurrences when they are moved between
the database and the program.
Example 6-34.
var student : STUDENT;
* Standard Pascal does not allow records without
fields. So, a dummy field may have to be introduced:
type DEPARTMENT =
record
dummy : 0..0 end;
var enrollment : ENROLLMENT;
etc.
4. Pascal data type ABSTRACT.
The variables of type ABSTRACT reference database objects.
In many network database management systems this type is called
DBKEY.
5. System variables (read-only).
There are several automatically generated system variables. The
user may not perform explicit assignments to these variables.
These variables are updated by the system as a side effect of
performing user commands.
var Error-status : (ok, end-of-set, error)
After the execution of any database command, this variable
is automatically assigned one of the following values:
o end-of-set - if the user attempted to locate the next
record occurrence in a particular set-occurrence and no
next record-occurrence existed
o error - if another logical or physical error occurred
o ok - otherwise.
var current-of-run-unit : ABSTRACT
This variable references the last accessed object.
Initially, it is the object SYSTEM.
var current-of-record-type-record-type : ABSTRACT
For every record-type in the subschema, there is a variable
referencing the last accessed object of that record-type.
Example 6-35.
var current-of-record-type-DEPARTMENT, current-of-record-
type-STUDENT, current-of-record-type-INSTRUCTOR, current-of-
record-type-QUARTER, current-of-record-type-COURSE, current-
of-record-type-OFFERING, current-of-record-type-ENROLLMENT,
current-of-record-type-WORK, current-of-record-type-
DEPARTMENT-NAMING : ABSTRACT
var current-of-set-type-set-type : ABSTRACT
For every set-type in the subschema, there is a variable
referencing the last accessed object of a record-type which
is the owner or the member of this set-type. For the set-
types whose owner is SYSTEM, these variables initially
contain the object SYSTEM. Otherwise the variables are
uninitialized.
Example 6-36.
var current-of-set-type-SYSTEM-INSTRUCTOR, current-of-set-
type-SYSTEM-STUDENT, current-of-set-type-SYSTEM-DEPARTMENT,
current-of-set-type-SYSTEM-COURSE, current-of-set-type-
SYSTEM-QUARTER, current-of-set-type-INSTRUCTOR-WORK, current-
of-set-type-DEPARTMENT-WORK, current-of-set-type-DEPARTMENT-
DEPARTMENT-NAMING, current-of-set-type-MAJOR-ST, current-of-
set-type-MINOR-ST, current-of-set-type-INSTRUCTOR-OFFERING,
current-of-set-type-COURSE-OFFERING, current-of-set-type-
QUARTER-OFFERING, current-of-set-type-OFFERING-ENROLLMENT,
current-of-set-type-STUDENT-ENROLLMENT : ABSTRACT
6. Expressions - there is no extension to the syntax of Pascal
expressions.
Particularly, there are no operations on the objects of type
ABSTRACT. For example, if x is a variable of type ABSTRACT, and
A is an attribute, then x.A would be an expression in the
structured extension of Pascal but not in the navigational
extension.
However, if x is not an abstract variable, but a variable of a
Pascal type record, for example
var x: record
A: Integer,
B: Integer
end
then x.A would be a usual Pascal expression and thus can be used
in the navigational language.
Statements
7. find first within set-name
The first member object is located in the current set-occurrence
of this set-type, the set occurrence to which the object
current-of-set-type-set-type belongs.
If there are no member-objects in the set-occurrence, the system
variable Error-status is set to end-of-set. (Otherwise, if the
instruction is successfully performed, the variable Error-status
is set to ok.)
If an object is found, the currency variables are updated: the
found object becomes
o The current of run-unit
o The current of this set-type
o The current of this object's record-type
o The current of every set-type whose owner or member is the
category of this object
Example 6-37.
Are there any students in the database?
find first within SYSTEM-STUDENT;
if Error-status = end-of-set
then writeln (`no');
if Error-status = ok
then writeln (`yes');
if Error-status = error
then writeln (`I do not know. I have system
problems.');
8. get
This instruction assigns the attributes' values of the current
object of run-unit to the template variable corresponding to the
category of the object.
Example 6-38.
Print the address of one student.
(* locate one student, the one which happens to be the
first in the order of SYSTEM-STUDENT*)
find first within SYSTEM-STUDENT;
(* assign the attribute values of the student to the
variable student*)
get;
(* print *)
writeln (`The address of a student is:',
student.ADDRESS)
9. find next within set-name
The next member object is located in the order of the set-type
after the current object of the set-type.
If there are no next member-objects in the set-occurrence, the
system variable Error-status is set to end-of-set.
If an object is found, the currency variables are updated: the
found object becomes the current of run-unit, the current of this
set-type, the current of this object's record-type, and the
current of every set-type whose owner or member is the category
of this object.
Example 6-39.
Print names and addresses of all the students.
find first within SYSTEM-STUDENT;
while (Error-status = end-of-set) do
begin
(* assign the attribute values of the current
student to the variable student *)
get;
(* print *)
writeln (`The address of Student',
student.LAST-NAME, ` is: ',
student.ADDRESS)
find next within SYSTEM-STUDENT
end;
10. find owner within set-name
The owner object of the set occurrence of the current object of
the set-type is located.
The currency variables are updated: the found object becomes the
current of run-unit, the current of this set-type, the current of
this object's record-type, and the current of every set-type
whose owner or member is the category of this object.
Example 6-40.
Print names and major departments of all the students.
find first within SYSTEM-STUDENT;
while (Error-status = end-of-set) do
begin
(* assign the attribute values of the current
student to the variable student *)
get;
(* find the major department of the student *)
find owner within MAJOR-ST;
(* find the name of the department; if the
department has more than one name, the first
found will do.*)
find first within DEPARTMENT-DEPARTMENT-NAMING
;
(* assign the attribute value of the current
department-naming to the variable department-
naming *)
get
(* print *)
writeln (`The major department of Student',
student.LAST-NAME, ` is: ', department-
naming. NAME);
find next within SYSTEM-STUDENT
end;
11. find db-key is variable-of-type-ABSTRACT
(This statement is used to find and restore the currency of an
object which was previously accessed by the program and whose
reference was saved in a variable.)
The object referred to by the variable is located. The currency
variables are updated: the found object becomes the current of
run-unit and the current of every set-type whose owner or member
is the category of this object.
Example 6-41.
For every student, print the names of the students of the same
major.
var student-to-remember: ABSTRACT;
begin
find first within SYSTEM-STUDENT;
while (Error-status = end-of-set) do begin
(* assign the attribute values of the current
student to the variable student *)
get;
(* find the major department of the student *)
find owner within MAJOR-ST;
(* print a heading for the current student's list of
co-majors. *)
writeln (`Student', student.LAST-NAME, ` has
the same major as the following students:
');
(* remember the current student, so that we can
return to her after we have finished processing
the co-majors. *)
student-to-remember := current-of-set-type-
SYSTEM-STUDENT;
(* process the students connected in the set-type
MAJOR-ST to the current department *)
find first within MAJOR-ST;
while (Error-status = end-of-set) do
begin
get;
write (student. LAST-NAME);
find next within MAJOR-ST
end;
(* restore the currency of the student of the
principal loop.*)
find db-key is student-to-remember;
find next within SYSTEM-STUDENT
end;
end.
12. find within set-name using attribute
Among the member objects in the set occurrence of the current
object of the set-type, find the first object whose value of the
attribute is the same as in the template variable of the member
record-type.
The currency variables are updated: the found object becomes the
current of run-unit, the current of this set-type, the current of
this object's record-type, and the current of every set-type
whose owner or member is the category of this object.
This is roughly equivalent to the following program, where S is
the set-type and rec is the member record-type:
attribute-to-compare := rec. attribute;
find first within S;
found := false;
while (Error-status = end-of-set) and (not found) do
begin
get;
found := (rec.attribute = attribute-to-compare);
if not found
then find next within S
end;
Example 6-42.
How many times was the Databases course offered?
(* find the Databases course *)
course.NAME := 'Databases';
find within SYSTEM-COURSE using NAME;
(* count the offerings *)
number := 0;
find first within COURSE-OFFERING;
while Error-status = end-of-set do
begin
number := number+1;
find next within COURSE-OFFERING;
end
writeln (`Databases was offered ', number, `
times.')
13. modify record-type
The attributes' values of the current object of this record-type
are updated according to the values in the template variable of
this record-type.
Example 6-43.
Change the name of every Fall quarter to Autumn.
find first within SYSTEM-QUARTER;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
if quarter. SEASON = `Fall' then
begin
quarter. SEASON := `Autumn';
modify QUARTER;
end;
find next within SYSTEM-QUARTER
end;
14. erase record-type
The current object of the record-type is deleted from the
database.
If the object is the owner of a set-occurrence of a set-type onto
the member, then all the member objects of that set occurrence
are automatically erased. This process is recursive: the
deletion of some objects may trigger deletion of more objects.
Example 6-44.
Cancel everything that happened in any summer.
find first within SYSTEM-QUARTER;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
if quarter. SEASON = `Summer' then
erase QUARTER;
find next within SYSTEM-QUARTER
end;
15. connect record-type to set-type
The current object of the record-type is inserted as a member
into the current set-occurrence of the set-type - the set-
occurrence in which the current object of the set-type is the
owner or a member.
Example 6-45.
Let every student have the same minor as his major, assuming
that every student had (until now) a major and no minor
department.
find first within SYSTEM-STUDENT;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
find owner within MAJOR-ST;
if Error-status = error then
writeln (` Oh-oh. Wrong assumption about having
a major department for ', student. LAST-
NAME);
connect STUDENT to MINOR-ST;
if Error-status = error then
writeln (` Oh-oh. Wrong assumption about not
having a minor department for ', student.
LAST-NAME);
find next within SYSTEM-STUDENT
end;
16. disconnect record-type from set-type
The current object of the record-type will no longer be a member
in the current set-occurrence of the set-type (the set-occurrence
in which the current object of the set-type is the owner or a
member).
Example 6-46.
Let every student have the same minor as his major, by
canceling the present minors. Assume that every student had a
major department.
find first within SYSTEM-STUDENT;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
disconnect STUDENT from MINOR-ST;
find owner within MAJOR-ST;
if Error-status = error then
writeln (` Oh-oh. Wrong assumption about having
a major department for ', student. LAST-
NAME);
connect STUDENT to MINOR-ST;
find next within SYSTEM-STUDENT
end;
17. reconnect record-type to set-type
The current object of the record-type will no longer be a member
in its former set-occurrence of the set-type.
Instead, the current object of the record-type is inserted as a
member into the current set-occurrence of the set-type (the set-
occurrence in which the current object of the set-type is the
owner or a member).
Example 6-47.
Let every student have the same minor as his major, canceling
the present minor, assuming that every student had a major
department.
find first within SYSTEM-STUDENT;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
find owner within MAJOR-ST;
if Error-status = error then
writeln (` Oh-oh. Wrong assumption about having
a major department for ', student. LAST-
NAME);
reconnect STUDENT to MINOR-ST;
find next within SYSTEM-STUDENT
end;
18. store record-type
A new object of the record-type is created.
The object automatically gets the values of its attributes from
the template variable of this record-type.
This object becomes the current of the record-type.
19. transaction compound-statement
- as in the structured extension of Pascal.
Example 6-48.
Let Prof. Asteroid (a unique name for this instructor, so no
confusion with other instructors is possible) offer the course
Databases every quarter.
instructor. LAST-NAME = `Asteroid';
course. NAME := `Databases';
find within SYSTEM-INSTRUCTOR using LAST-NAME;
find within SYSTEM-COURSE using NAME;
find first within SYSTEM-QUARTER;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
transaction begin
store OFFERING;
connect OFFERING to QUARTER-OFFERING;
connect OFFERING to COURSE-OFFERING;
connect OFFERING to INSTRUCTOR-OFFERING
end
find next within SYSTEM-QUARTER
end;
Example 6-49.
A navigational program for the expulsion prevention problem
which has been previously solved in the structured extension
of Pascal.
program Pass (Input, Output, UNIVERSITY-DB, UNIVERSITY-PRINCIPAL-
SUBSCHEMA);
(* The comments in the boxes are the corresponding
program fragments in the structured extension of
Pascal. It is recommended that when a program
needs to be written in the navigational language,
it should first be written in the higher-level
language. Then, when the higher-level program is
translated into the lower-level navigational
language, the commands of the original program
should become algorithmic comments within the
navigational program. *)
var Good-Offer: ABSTRACT;
var the-grade, desired-grade, number-of-grades, total-of-grades,
current-year: INTEGER;
const null-year = 1870 (* to represent missing birth-year,
assuming nobody was born in 1870*);
const null-name = `' (* to represent missing names *);
const null-address = `' (* to represent missing addresses *);
const null-grade = 0 (* to represent missing grades, assuming
that 0 is never given as a real grade+ *);
begin (* Get the current year from the standard input file.*)
read (current-year);
transaction begin
(*
create new Computer-Pass-Course in COURSE;
Computer-Pass-Course. NAME := `Computer Pass'; *)
+ If the type of the variable enrollment.Final-grade
technically allows for negative values, then a better
representation of the missing grade is -1.
course. NAME := `Computer Pass';
store COURSE;
connect COURSE to SYSTEM-COURSE;
(*
create new instructor in INSTRUCTOR;
instructor. LAST-NAME := `Good'; *)
instructor. LAST-NAME := `Good';
instructor. FIRST-NAME := null-name;
instructor. BIRTH-YEAR := null-year;
instructor. ADDRESS := null-address;
store INSTRUCTOR;
connect INSTRUCTOR to SYSTEM-INSTRUCTOR;
(*
create new Good-Offer in OFFERING;
relate: Computer-Pass-Course COURSE-OFFERING
Good-Offer;
relate: Prod-Good INSTRUCTOR-OFFERING Good-Offer;
*)
store OFFERING;
connect OFFERING to INSTRUCTOR-OFFERING;
connect OFFERING to COURSE-OFFERING;
Good-Offer := current-of-record-type-OFFERING;
(*
for quarter in QUARTER
satisfying (quarter. YEAR = current-year and
quarter. SEASON = `Winter') do
relate: quarter QUARTER-OFFERING Good-Offer;
*)
found := false;
find first within SYSTEM-QUARTER;
while (Error-status = end-of-set and not found) do
begin;
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
found := (quarter. YEAR = current-year and quarter.
SEASON = `Winter');
if not found then
find next within SYSTEM-QUARTER
end;
connect OFFERING to QUARTER-OFFERING;
end (*transaction*);
(* Prepare-Department:
for department-naming in DEPARTMENT-NAMING
satisfying (department-naming.NAME= `COMPUTER SCIENCE')
do
for department in DEPARTMENT
satisfying (department
DEPARTMENT-DEPARTMENT-NAMING
department-naming) do
*)
found := false;
find first within SYSTEM-DEPARTMENT;
while (Error-status = end-of-set and not found) do
begin;
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
found := false;
find first within DEPARTMENT-DEPARTMENT-NAMING;
while (Error-status = end-of-set and not found) do
begin;
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
found := (department-naming. NAME = `Computer Science');
if not found then
find next within DEPARTMENT-DEPARTMENT-NAMING
end;
if not found then
find next within SYSTEM-DEPARTMENT
end;
(**end Prepare-department**)
transaction begin
(*
create new work in WORK;
relate: instructor INSTRUCTOR-WORK work;
relate: department DEPARTMENT-WORK work *)
store WORK;
connect WORK to INSTRUCTOR-WORK;
connect WORK to DEPARTMENT-WORK;
end (* transaction *);
(* Student-loop:
for student in STUDENT
satisfying (department MAJOR-ST student) do *)
find first within MAJOR-ST;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
(**end of the opening of Student-loop **)
(* calculate this student's current statistics: number-of-grades
and total-of-grades *)
number-of-grades := 0;
total-of-grades := 0;
(* Enrollment-loop:
for enrollment in ENROLLMENT
satisfying (student STUDENT-ENROLLMENT
enrollment and not enrollment FINAL-
GRADE null) do *)
find first within STUDENT-ENROLLMENT;
while (Error-status = end-of-set) do
begin
if Error-status = error then begin
writeln (` SYSTEM ERROR'); stop end;
get;
if student. FINAL-GRADE = null-grade then
begin
(**end of the opening of Enrollment-loop **)
the-grade := student.FINAL-GRADE;
number-of-grades := number-of-grades + 1;
total-of-grades := total-of-grades + the-grade
(**closing Enrollment-loop **)
end;
find next within STUDENT-ENROLLMENT
end;
(**end Enrollment-loop **)
(* calculate the minimal desired grade in the computer-pass
course, solving the equation (total+x)/(number+1) = 60 *)
desired-grade := 60 * (number-of-grades + 1) - total-of-
grades;
if desired-grade > 100
then
(* the student cannot be helped. Print a message
*)
writeln (` The student ', student. LAST-
NAME, ` cannot be helped. Sorry!')
else
if desired-grade > 60 then
transaction begin
(*
create new fictitious-
enrollment in ENROLLMENT;
relate: student STUDENT-
ENROLLMENT fictitious-
enrollment;
relate: Good-Offer OFFERING-
ENROLLMENT fictitious-
enrollment;
fictitious-enrollment. FINAL-
GRADE := desired-grade *)
enrollment. FINAL-GRADE := desired-
grade;
store ENROLLMENT;
connect ENROLLMENT to STUDENT-
ENROLLMENT;
find db-key is Good-Offer; (*We have to
restore the currency of the
fabricated offering remembered in
the variable Good-Offer, because
the currency may have changed in
the meantime.*)
connect ENROLLMENT to OFFERING-
ENROLLMENT;
end
(**closing Student-loop**)
find next within MAJOR-ST
end;
(**end Student-loop **)
end.
Figure Ref-2. A relational schema for the university
application.