Copyright © 1995 T. H. Merrett
308-612A Database Systems 951123
1 NESTED RELATIONS
Purpose of nesting is to support "complex objects":
attributes which are relations; hence ADTs.
So domain algebra should include relational algebra.
Example (Jaeschke & Schek, 1982):
BOOKS(AUTHORS TITLE PRICE DESCRIPTORS)
A1,A2 T1 P1 D1,D2
A2 T2 P2 D1,D2
A1 T3 P1 D1,D2,D3
Which books by A2 are described by both D1 and D2?
[TITLE] where AUTHORS sup {(A2)} and
DESCRIPTORS sup {(D1),(D2)} in BOOKS
This is handier than breaking into flat relations:
BOOK(BNO, TITLE, PRICE), AUTHORS(BNO, AUTHOR),
DESCRIPTORS(BNO, DESCRIPTOR)
BOOK icomp ((AUTHORS sup {A2}) ijoin
(DESCRIPTORS sup {D1,D2})
^L
308-612A Database Systems 951123
2 NESTED RELATIONS HAVE ATTRIBUTES
Example (Deshpande & Larson, 1987):
EMPLOYEE
(ENO NAME CHILDREN TRAINING
(NAME DOB SEX) (CNO DATE ))
105 John Jane 800510 F 314 791010
Eric 821005 M 606 810505
714 820620
______________________________________
123 Anne Maria 751112 F 315 810613
423 820711
______________________________________
153 Bruce 314 791010
______________________________________
205 Ian Bob 701016 M 314 791010
Steve 750115 M
Find employees without children
[ENO] where not ([] in CHILDREN) in EMPLOYEE
Instead of:
EMP(ENO, NAME), CHILDREN(ENO, CNAME, DOB, SEX),
TRAINING(ENO, CNO, DATE)
([ENO] in EMP) djoin [ENO] in CHILDREN
^L
308-612A Database Systems 951123
3
Find employees who took course 314
[ENO] where ([] where CNO=314 in TRAINING)
in EMPLOYEE
Find children of employees who took course 314
[CHILDREN] where ([] where CNO=314 in TRAINING)
in EMPLOYEE
Note result is still a nested relation:
(CHILDREN(NAME DOB SEX))
Jane 800510 F < John
Eric 821005 M
________________________
________________________ < Bruce
Bob 701016 M
Steve 750115 M < Ian
Find names of children ..
let C be [NAME]in CHILDREN; <>
[C] where ([] where CNO=314 in TRAINING) in EMPLOYEE
Also nested: NB R <- [C] where..
(C(NAME)) so R(C(N))
Jane :
Eric :
______
______
Bob
Steve
Note anonymous if don't assign in proj. list
^L
308-612A Database Systems 951123
4 UNNESTING I Merging Top Level Tuples
First, we make a single tuple, by reduction:
let ChildAll be red ujoin of CHILDREN;
[ChildAll] where ([] where CNO=314 in TRAINING)
in EMPLOYEE
(ChildAll(NAME DOB SEX))
Jane 800510 F
Eric 821005 M
Bob 701016 M
Steve 750115 M
or
let ChildName be red ujoin of CHILDREN.NAME;
[ChildName] where ([] where CNO=314 in TRAINING)
in EMPLOYEE
(ChildName(NAME))
Jane
Eric
Bob
Steve
These are both unary (only one attribute),
singleton (only one tuple) relations.
But the one tuple is the union of all rels.
^L
308-612A Database Systems 951123
5 UNNESTING II Removing a Level
Now we need new syntax.
lift operator on any unary singleton removes
the intermediate level name.
[lift ChildAll] where
([] where CNO=314 in TRAINING) in EMPLOYEE
(NAME DOB SEX)
Jane 800510 F
Eric 821005 M
Bob 701016 M
Steve 750115 M
[lift ChildName] where
([] where CNO=314 in TRAINING) in EMPLOYEE
(NAME)
Jane
Eric
Bob
Steve
Note. This applies even to ordinary relations:
R(A B )
1 "a"
S <- [lift A] in R; T <- [lift B] in R;
S(intg) T(strg)
1 "a"
^L
308-612A Database Systems 951123
6 UNNESTING III Multiple Nested Relations
let TEMPLOYEE be red ujoin of
ENO ijoin NAME ijoin CHILDREN ijoin TRAINING;
FlatEmp <- [lift TEMPLOYEE] in EMPLOYEE
FlatEmp
(intg strg NAME DOB SEX CNO DATE )
105 John Jane 800510 F 314 791010
105 John Jane 800510 F 606 810505
105 John Jane 800510 F 714 820620
105 John Eric 821005 M 314 791010
105 John Eric 821005 M 606 810505
105 John Eric 821005 M 714 820620
123 Anne Maria 751112 F 315 810613
123 Anne Maria 751112 F 423 820711
153 Bruce 314 791010
205 Ian Bob 701016 M 314 791010
205 Ian Steve 750115 M 314 791010
(We have taken the cartesian product of the
four attributes, treating ENO(intg) and
NAME(strg) as relations (they could be
renamed).)
This will work for any level of nesting,
provided we have a recursive mechanism.
This could be provided by procedure/
computations.
^L
308-612A Database Systems 951123
7 NESTING I Grouping
How do we nest the flat relation?
First we group attributes into singletons.
let TRAIN be group CNO, DATE;
let CHILD be group NAME, DOB, SEX;
let NAME be group strg;
let ENO be group intg;
(ENO NAME CHILD TRAIN )
intg strg (NAME DOB SEX) (CNO DATE )
105 John Jane 800510 F 314 791010
105 John Jane 800510 F 606 810505
105 John Jane 800510 F 714 820620
105 John Eric 821005 M 314 791010
105 John Eric 821005 M 606 810505
105 John Eric 821005 M 714 820620
123 Anne Maria 751112 F 315 810613
123 Anne Maria 751112 F 423 820711
153 Bruce 314 791010
205 Ian Bob 701016 M 314 791010
205 Ian Steve 750115 M 314 791010
^L
308-612A Database Systems 951123
8 NESTING II Clustering
Then we cluster the tuples into relations
let TRAINING be equiv ujoin of TRAIN by ~{TRAIN};
(ENO NAME CHILD TRAINING )
intg strg (NAME DOB SEX) (CNO DATE )
105 John Jane 800510 F 314 791010
606 810505
714 820620
______________________________________
105 John Eric 821005 M 314 791010
606 810505
714 820620
______________________________________
123 Anne Maria 751112 F 315 810613
423 820711
______________________________________
153 Bruce 314 791010
______________________________________
205 Ian Bob 701016 M 314 791010
______________________________________
205 Ian Steve 750115 M 314 791010
^L
308-612A Database Systems 951123
9 NESTING II Clustering
let CHILDREN be equiv ujoin of CHILD by ~{CHILD};
(ENO NAME CHILDREN TRAINING )
intg strg (NAME DOB SEX) (CNO DATE )
105 John Jane 800510 F 314 791010
Eric 821005 M 606 810505
714 820620
______________________________________
123 Anne Maria 751112 F 315 810613
423 820711
______________________________________
153 Bruce 314 791010
______________________________________
205 Ian Bob 701016 M 314 791010
Steve 750115 M
That is,
EMPLOYEE <- [ENO, NAME, CHILDREN, TRAINING]
in FlatEmp;
^L
308-612A Database Systems 951123
10 ABSTRACT DATA TYPES
Nesting and unnesting are relatively unimportant.
To support ADTs, we need relations with hidden tuples.
They can be hidden in procedure/computation.
E.g., adding complex numbers
proc C+-(a,b,c) is << Complex add/subtract >>
{ let ar be r;
let ai be i;
let br be r;
let bi be i;
let r be ar + br;
let i be ai + bi; << c <- a + b >>
c <- [r,i] in ([ar,ai] in a) ijoin [br,bi] in b;
} alt
{ ..
let r be cr - br;
let i be ci - bi; << a <- c - b >>
a <- [r,i] in ([cr,ci] in a) ijoin [br,bi] in b;
} alt
{ ..
let r be br - ar;
let i be bi - ai; << b <- c - a >>
b <- [r,i] in ([cr,ci] in a) ijoin [ar,ai] in a;
}
^L
308-612A Database Systems 951123
11 ABSTRACT DATA TYPES
Now we use this procedure as a computation.
Suppose we have R(x, y) where x, y are complex:
Then S <- C+- ijoin R
will give S(x, y, z) where z is complex sum of x, y.
How do we create complex numbers?
proc Cwr(rl,im,cx) is << Complex read/write >>
{ let r be real; << change attrib from rl(real)>>
let i be real; << change attrib from im(real)>>
cx <- ([r] in rl) ijoin [i] in im; << Cart. product>>
} alt
{ let real be r;
let real be i;
rl <- [real] in [r] in cx;
im <- [real] in [i] in cx;
}
Q(a b c d) R <- Cwr icomp Q icomp Cwr
1 0 2 3
1 1 2 2
0 1 2 3
^L
308-612A Database Systems 951123
12 IMPLEMENTING NESTING
We implement a nested relation as a set of flat
relations, connected by joins.
The connection is by relation surrogate.
Thus, R, above, is represented by two relations:
R(x y ) Cmpx(sr r i)
c1 c2 c1 1 0
c3 c4 c2 2 3
c5 c2 c3 1 1
c4 2 2
c5 0 1
The same idea extends to non-singleton components.
When we create S from R,
S(x y z ) Cmpx(sr r i)
c1 c2 c6 : : :
c3 c4 c6 c6 3 3
c5 c2 c7 c7 2 4
For abstract data types, we must hide the
component relations.
Otherwise, the tuples are accessible.
^L
308-612A Database Systems 951123
13 ALGEBRA FOR NESTED RELATIONS
We have seen selections and projections.
Equality of relation-valued attributes
(in order to do joins and some selects):
R = S iff R and S are the same,
i.e. the sigma join.
Ideally R = S iff their surrogates are the same
but practically R = S only if " " " " ":
surrogates would be signatures.
This is contrary to all the literature on joins.
We would probably not define inequality.
^L
308-612A Database Systems 951123
14 BIBLIOGRAPHY
The literature on nested relations gives undue emphasis on nest and unnest
as operators, but here is the basic work.
Author={A. Makinouchi},
Title={A Consideration on Normal Form of Not-necessarily Normalized
Relations in the Relational Model},
Note={examples of nest, recursive nest; discusses normalization, dep.},
Booktitle={Proc. 3rd Internat. Conf. on Very Large Data Bases},
Editor={A. G. Merten},
City={Tokyo},
Month={October},
Year=1977,
Pages={447--53}}
Author={G. Jaeschke and H.-J. Schek},
Title={Remarks on the algebra of non first normal form relations},
Booktitle={Proc. ACM Symposium on Principles of Database Systems},
Notes={nest/unnest & their commutativity; also ijoin equiv to flat},
City={Los Angeles},
Month={March},
Year=1982,
Pages={124--38}}
Author={H.-J. Schek and P. Pistor},
Title={Data Structures for an Integrated Data Base Management and
Information Retrieval System},
Booktitle={Proceedings of the Eight International Conference on Very
Large Data Bases},
Editor={D. McLeod and Y. F. Villasenor},
Address={Mexico City},
Month={Sept.},
Year=1982,
Pages={197..207}}
Author={P. Fischer and S. Thomas},
Title={Operators for Non-First-Normal-Form Relations},
Booktitle={Proc. 7th {COMPSAC}},
Notes={Extend JaeSchek:nfnf to multiple attibutes, multiple nesting
levels: generalize some JaeSchek:nfnf properties, refute others:
essentially, do (nest, op), (unnest, op), unnest*, op) commute,
and are nest, unnest inverses?},
Address={Chicago},
Month={November},
Year=1983,
Pages={464--75}}
Author={A. Deshpande and D. Van Gucht},
Title={A Storage Structure for Nested Relational Databases},
Institution={Indiana University Computer Science Department},
Address={Bloomington, Indiana},
Number={234},
Month={Nov.},
Year=1987}
Author={V. Deshpande and P.-\o{A}. Larson},
Title={An Algebra for Nested Relations},
Institution={University of Waterloo Computer Science Department},
Address={Waterloo, Ont.},
Number={{CS}-87-65},
Month={Dec.},
Year=1987}
Author={S. Abiteboul and C. Beeri},
Title={On the Power of Languages for the Manipulation of Complex
Objects},
Institution={{INRIA}},
Address={Domaine de Voluceau, Rocquencourt, Le Chesnay, France},
Number={846},
Month={May},
Year=1988}
Author={M. A. Roth and H. F. Korth and A. Silberschatz},
Title={Extended Algebra and Calculus for Nested Relational Databases},
Notes={Reworks FischThom:nfnf operators to guarantee commutativity:
operators on nested relations essentially proceed by flattening all
the way down, operating, then nesting - except select on nest attr.},
Journal={ACM TODS},
Volume=13,
Number=4,
Month={Dec.},
Year=1988,
Pages={389--417}}
Author={V. Deshpande and P.-\o{A}. Larson},
Title={Transforming from Flat Algebra to Nested Algebra},
Institution={University of Waterloo Computer Science Department},
Address={Waterloo, Ont.},
Number={{CS}-89-19},
Month={May},
Year=1989}
Author={J. A. Blakely and A. Deshpande},
Title={Processing Queries in {ANDA}: A Nested Relational Database
System},
Notes={Describes implementation. (Not clear which of 2 joins used.},
Institution={Indiana University Computer Science Department},
Address={Bloomington, Indiana},
Number={287},
Month={Aug.},
Year=1989}