|
Example 7-1. A hierarchical schema for the university application follows. Only the order-less part is shown in the figure. |
Figure 7-1.An orderless hierarchical schema for the university application.
| Note: | We can prove the truth of the following statements from the definition of the hierarchical schemas: |
| a. | The relations between the abstract categories of any orderless hierarchical schema form a set of directed trees. (This is the reason for the name Hierarchical.) |
| b. | The root of every tree is an independent category. |
| c. | All the relations between distinct abstract categories are onto. |
| d. | Since every category C has only one entering relation RC from another category, every category has only one order NEXTRC. Thus, we can speak about the order of the objects of a category. |
|
Example 7-2. The following figures represent an instantaneous database for the schema of Figure ___. This instantaneous database represents the same state of the application's real world as the binary instantaneous database of Figure ___ on page ___. |
INSTRUCTOR
| id | last-name | first-name | birth-year | address |
| 11332 | Brown | George | 1956 | 112 Lucky Dr. |
| 14352 | Whatson | Mary | 1953 | 231 Fortune Dr. |
| 24453 | Blue | John | 1950 | 536 Orange Dr. |
Figure 7-2. An instantaneous database for the hierarchical schema of the university application. Part I. The flat tree of INSTRUCTOR.
STUDENT
|last-name| first-name| birth-year| address | major-dept- | minor-dept-|
| | | | | main-name | main-name |
| | | | | | |
+---------+------------+------------+-------------+------------------+-------------+
|Victory | Elizabeth | 1966 | 100 Sun St.| Computer Science| Economics |
COURSE ENROLLMENT
| instructor-id | course-name | year | season | final-grade |
| | | | | |
| | | | | |
|---------------+--------------+-------+---------+--------------+
| 11332 | Gastronomy | 1990 | Fall | 100 |
STUDENT
|last-name| first-name| birth-year| address | major-dept-| minor-dept-|
| | | | | main-name | main-name |
| | | | | | |
+---------+------------+------------+-----------+-------------+-------------+
|Howards | Jane | 1965 | 200 Dorms| Arts | Economics |
COURSE ENROLLMENT
| instructor-id | course-name | year | season | final-grade |
| | | | | |
| | | | | |
|---------------+--------------+-------+---------+--------------+
| 11332 | Gastronomy | 1990 | Fall | 70 |
| 11332 | Databases | 1990 | Fall | 80 |
STUDENT
|last-name| first-name| birth-year| address | major-dept-| minor-dept-|
| | | | | main-name | main-name |
| | | | | | |
+---------+------------+------------+-----------+-------------+-------------+
|Wood | Michael | 1964 | 110 Dorms| Arts | Economics |
Figure 7-3. An instantaneous database for the hierarchical schema of
the university application. Part II. The tree of STUDENT.
DEPARTMENT
------------------ DEPARTMENT NAMING
| main-name |
| | | name |
+----------------+ | |
Computer Science
| | |------------------+
------------------ | CS |
WORK
| instructor-id|
| |
| |
|--------------+
| 11332 |
DEPARTMENT DEPARTMENT NAMING
| main-name | | name |
| | | |
| | |
+-----------+ |------------------+
|Mathematics| | Math |
WORK
| instructor-id|
| |
| |
|--------------+
| 11332 |
| 24453 |
DEPARTMENT WORK
|main-name | | instructor-id|
| | | |
| | |
+----------+ |--------------+
|Physics | | 14352 |
DEPARTMENT
|main-name |
| |
+----------+
|Arts |
|Economics |
Figure 7-4. An instantaneous database for the hierarchical schema of
the university application. Part III. The tree of DEPARTMENT.
COURSE
| name |
| |
+---------+
|Databases|
COURSE OFFERING
| instructor-id | year | season |
|------------------------+-----------------+-------------------+
| 11332 | 1990 | Fall |
COURSE
| name |
| |
+--------+
|Football|
COURSE OFFERING
| instructor-id | year | season |
|------------------------+-----------------+-------------------+
11332 1990 Fall
COURSE
| name |
| |
+----------+
|Gastronomy|
COURSE OFFERING
| instructor-id | year | season |
|------------------------+-----------------+-------------------+
| 11332 | 1990 | Fall |
Figure 7-5. An instantaneous database for the hierarchical schema of
the university application. Part IV. The tree of COURSE.
QUARTER
| year| season|
| | |
| | |
|-----+--------+
| 1990| Fall |
| 1990| Winter|
| 1990| Spring|
Figure 7-6. An instantaneous database for the hierarchical schema of
the university application. Part V. The flat tree of QUARTER.
Hierarchical schema terminology
Segment type - record type.
| |
Example 7-3. |
| ------- - - |
| |
DEPARTMENT. |
| ---------- |
| |
Segment occurrence - record occurrence.
| |
Example 7-4. |
| ------- - - |
| |
| One course and its name. |
| |
| |
| |
Example 7-5. |
| ------- - - |
| |
| One student and his or her last name, first name, address, and |
| the main names of his or her major and minor departments. |
| |
| |
If there is a relation from a segment-type C to another C , then
1 2
C is the parent of C and C is a child of C .
1 2 2 1
| |
| Example 7-6. |
| ------- - - |
| DEPARTMENT is the parent of DEPARTMENT-NAMING. |
| DEPARTMENT-NAMING is a child of DEPARTMENT. |
| ---------- ------ ---------- |
| |
[] SELF - category
[] PARENT - category
[] SIBLING - category
[] CHILD - category
[] SIBLING - category
[] CHILD - category
[] - relation from PARENT to SELF (1:m)
[] - relation from PARENT to SIBLING (1:m)
[] - relation from PARENT to SIBLING (1:m)
[] - relation from SELF to CHILD (1:m)
[] - relation from SELF to CHILD (1:m)
Figure 7-7. Family relations in a hierarchical schema.
Root segment type - a segment type whose parent is SYSTEM.
| |
Example 7-7. |
| ------- - - |
| |
DEPARTMENT, INSTRUCTOR, STUDENT, COURSE, QUARTER. |
| ---------- ---------- ------- ------ ------- |
| |
The hierarchical model is not the most natural model to describe the
real world of an application. One should notice that what is
sometimes called "a hierarchical real world" usually implies a
hierarchical relation between objects in the real world, not a
hierarchical schema.
| |
Example 7-8. |
| ------- - - |
| |
| Consider an oversimplified military world, where every soldier |
| has at most one commander. A binary schema for this world is: |
| |
| [diagram skipped] |
| This is not a hierarchical schema, since it contains a cycle. |
No hierarchical schema can represent this world in a natural |
| -------
| way. |
| |
| |
7.2. Database Design
Conversion algorithm of a semantic schema into a hierarchical schema
whose quality is among the highest possible for the latter
(provided the original semantic schema is of high quality).
1. Convert the binary schema into a network schema.
2. For every abstract category, excluding SYSTEM, choose its
parent-relation R so that
When all the relations, except the parent relations,
are removed from the schema, every abstract category
would still indirectly depend on SYSTEM.
Note: The parent relation for category C must be onto C.
| |
Example 7-9. |
| ------- - - |
| |
The parent relation of OFFERING may be COURSE-OFFERING or |
| -------- ------ --------
INSTRUCTOR-OFFERING or QUARTER-OFFERING. |
| ---------- -------- ------- -------- |
| |
The parent relation for ENROLLMENT may be OFFERING-ENROLLMENT |
| ---------- -------- ----------
or STUDENT-ENROLLMENT. |
| ------- ---------- |
| |
The parent relation for WORK may be DEPARTMENT-WORK or |
| ---- ---------- ----
INSTRUCTOR-WORK. |
| ---------- ---- |
| |
| The parent relation for DEPARTMENT-NAMING is |
DEPARTMENT-DEPARTMENT-NAMING. |
| ---------- ---------- ------ |
| |
Note: The parent relations of independent categories are from
SYSTEM.
| |
| Example 7-10. |
| ------- - -- |
| The parent relation of STUDENT is SYSTEM-STUDENT. |
| ------- ------ ------- |
| The parent relation of INSTRUCTOR is SYSTEM-INSTRUCTOR. |
| ---------- ------ ---------- |
| The parent relation of DEPARTMENT is SYSTEM-DEPARTMENT. |
| The parent relation of COURSE is SYSTEM-COURSE. |
| ------ ------ ------ |
| |
The parent relation of QUARTER is SYSTEM-QUARTER. |
| ------- ------ ------- |
| |
3. Convert the schema into a tree: for every abstract category C
that has more than one entering relation, do the following.
Let R be its parent relation and R ,..., R the other entering
1 n
relations, whose domains are C ,...,C .
1 n
[] C - category
[] C1 - category
[] C2 - category
[] Parent-of-C - category
[] R - relation from Parent-of-C to C (1:m,parent)
[] R2 - relation from C2 to C (1:m,toberemoved)
[] R1 - relation from C1 to C (1:m,toberemoved)
For each of the relations R perform the following:
i
a. Find a key for the category C . (C is the domain of the
- i i
relation R which we intend to eliminate.) Add the key to
i
the schema (if this key has not been added yet).
[] C - category
[] C1 - category
[] C2 - category
[] Parent-of-C - category
[] R - relation from Parent-of-C to C (1:m,parent)
[] R2 - relation from C2 to C (1:m,toberemoved)
[] R1 - relation from C1 to C (1:m,toberemoved)
[] key - attribute of C1, range: Attributes (m:1)
[] key - attribute of C2, range: Attributes (m:1)
b. Add to C a new attribute, or a group of attributes, that is
the composition of the inverse of R on the key of C .
i i
[] C - category
[] C1 - category
[] C2 - category
[] Parent-of-C - category
[] R - relation from Parent-of-C to C (1:m,parent)
[] R2 - relation from C2 to C (1:m,toberemoved)
[] R1 - relation from C1 to C (1:m,toberemoved)
[] key-of-the-owner-of-R1 - attribute of C, range:
Attributes (m:1)
[] key-of-the-owner-of-R2 - attribute of C, range:
Attributes (m:1)
[] key - attribute of C1, range: Attributes (m:1)
[] key - attribute of C2, range: Attributes (m:1)
c. Remove the relation R (and its order).
- i
[] C - category
[] C1 - category
[] C2 - category
[] Parent-of-C - category
[] R - relation from Parent-of-C to C (1:m,parent)
[] key-of-the-owner-of-R1 - attribute of C, range:
Attributes (m:1)
[] key-of-the-owner-of-R2 - attribute of C, range:
Attributes (m:1)
[] key - attribute of C1, range: Attributes (m:1)
[] key - attribute of C2, range: Attributes (m:1)
d. Add the referential integrity constraints that the values of
the new attributes of C must refer to the values of the keys
of the categories C . (This is similar to what is done in
i
the relational model.)
4. Remove from every category attributes which can be inferred from
other attributes of that category, its parent, or its ancestors.
5. 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.
Note:
o In the first step, it is not strictly necessary to go all the way
through in the conversion from the binary schema to the network
schema. We can omit the substep where the 1:m relations from a
category to itself are eliminated. Later, in Step 3 of the
hierarchical conversion, these relations will be taken care of as
all the nonparent relations.
If we do this in Step 3 rather than in Step 1 we get a slightly
better hierarchical schema. If we were to follow the network
conversion in Step 1 fully, we could get one extra category for
the relation-split of each 1:m relation from a category to
itself.
7.3. Hierarchical Languages
7.3.1. Fourth-generation programming
Syntactically, this language is the same as the binary extension of
Pascal but is used for the hierarchical schema (every hierarchical
schema is a binary schema). Pragmatically, there is one difference:
the for loops are performed in the order corresponding to the ordering
of objects in the database. (In the Binary Model, the order in which
a for loop is performed is transparent to the application programmer.)
| |
Example 7-11. |
| ------- - -- |
| |
| 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,
comp-science-name, Good-employment, 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);
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';
Prof-Good. ID := 1234;
create new Good-Offer in OFFERING;
relate: Computer-Pass-Course OFFERING Good-Offer;
Good-Offer. INSTRUCTOR-ID := 1234;
Good-Offer. YEAR := current-year;
Good-Offer. SEASON := `Winter';
end
for comp-science-name in DEPARTMENT-NAMING
satisfying (comp-science-name. NAME= `COMPUTER SCIENCE') do
for comp-science in DEPARTMENT
satisfying (comp-science DEPARTMENT-DEPARTMENT-NAME
comp-science-name) do begin
transaction begin
create new Good-employment in WORK;
relate: comp-science DEPARTMENT-WORK Good-employment;
Good-employment. ID := 1234
end;
for cs-student in STUDENT
satisfying (cs-student. MAJOR-DEPARTMENT-MAIN-
NAME = comp-science. MAIN-NAME) 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 ENROLLMENT her-
enrollment and not her-enrollment
FINAL-GRADE null) do begin
the-grade :=
her-enrollment.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 ENROLLMENT
fictitious-enrollment;
fictitious-enrollment. FINAL-GRADE :=
desired-grade;
fictitious-enrollment. YEAR := current-
year;
fictitious-enrollment. SEASON :=
`Winter';
fictitious-enrollment. INSTRUCTOR-ID :=
1234;
fictitious-enrollment. COURSE-NAME :=
`Computer Pass'
end
end
end
end.
7.3.2. Logic
Since every hierarchical schema is a binary schema, we can use the
same language of Predicate Calculus as was defined for the Semantic
Binary Model.
| |
Example 7-12. |
| ------- - -- |
| |
| Has every student taken at least one course in 1990? |
| |
| |
| |
| |
for every st in STUDENT: |
| ------- |
| |
exists enrl in ENROLLMENT: |
| ---------- |
| |
((st STUDENT-ENROLLMENT enrl ) and |
| ------- ---------- |
| |
(enrl. YEAR=1990)) |
| ---- |
| |
| |
Example 7-13. |
| ------- - -- |
| |
| Who took Prof. Smith's courses? |
| |
| |
| |
| |
get student.LAST-NAME where |
| ---- ---- |
| |
exists enrl in ENROLLMENT: |
| ---------- |
| |
(student STUDENT-ENROLLMENT enrl and |
| ------- ---------- |
| |
exists inst in INSTRUCTOR: |
| ---------- |
| |
(inst.LAST-NAME = `Smith' and |
| ---- ----
| |
enrl. INSTRUCTOR-ID = inst.ID)) |
| ---------- -- -- |
| |
| |
Example 7-14. |
| ------- - -- |
| |
| What students have their average grade below 60? |
| |
| |
| |
| |
get std. LAST-NAME |
| ---- ---- |
| |
| where 60 > |
| |
| |
average enrl. FINAL-GRADE |
| ----- ----- |
| |
| where |
| |
| |
std STUDENT-ENROLLMENT enrl |
| ------- ----------
| |
| |
Example 7-15. |
| ------- - -- |
| |
| Print the average of grades for every computer science |
| student. |
| |
| |
| |
| |
get student. LAST-NAME, |
| ---- ---- |
| |
(average enrollment. FINAL-GRADE |
| ----- ----- |
| |
| where |
student STUDENT-ENROLLMENT |
| ------- ----------
| enrollment) |
| |
| |
where student is a STUDENT and |
| ------- |
| |
(student. MAJOR-DEPARTMENT-MAIN-NAME = `Computer |
| ----- ---------- ---- ----
| Science') |
| |
| |
| |
Example 7-16. |
| ------- - -- |
| |
| How many students are there in the university? |
| |
get (count std where std is a STUDENT) |
| ------- |
| |
Figure Ref-1. A semantic schema for a university application.
Figure Ref-2. A relational schema for the university
application.