Transcript The Blossoming of Relational Database Theory

Alberto Mendelzon at Princeton:
The Blossoming of Relational
Database Theory
David Maier
Dept. of Computer Science
Portland State University
DB Theory: Toronto to Princeton
• Dennis Tsichritzis (Toronto) goes to IBM Yorktown
Heights for the summer to work on OS. Finds
database work with Frank King, Don Chamberlin and
Ray Boyce more interesting (1973).
• Returns to Toronto, announces to OS group
(including Phil Bernstein) that they are now the DB
group.
• Phil does PhD on 3NF synthesis (1975), remains at
UT as a postdoc.
• Catriel Beeri arrives at Toronto for a postdoc (75-76),
shares an office with Phil. Switches from automata to
database theory.
The Word Spreads
• Phil goes to Harvard (1976)
• Catriel goes to Princeton (1976), teaches DB class,
gets Ullman and Aho interested in relational
databases
• Most of Ullman’s PhD students start working on
relational database theory
Alberto arrives in Fall 1975, becomes one of the first of
Ullman’s students working on database theory
Main Questions
• Dependency implication
+ What kind of dependencies are there?
• What’s a good DB scheme?
+ What’s a good a good class of DB schemes?
• When are two DB schemes equivalent?
+ What does “equivalent” mean?
• When are two queries equivalent?
Realizations
• 23
• Not every dependency is an FD
• Real DBs aren’t always the projection of a single
instance
First Papers
J. Howard
MY
AVA
RF
CB
YS
JDU
PAB
N. Goodman
1977 1978
We Get Hyper
ES
R.E.Ladner
PH
MY
AVA
RF
YS
DM
CB
MYV
JDU
AOM
PAB
FS
HFK
1977 1978 1979 1980
CHP
1979-80 Work
• MVDS: Independence of inference axioms
• Chase: Tableaux as mappings, tableaux as templates
[MMS]
• Equivalence: Same set of fixpoint instances (vs.
embedding equivalent FDs) [BMSU]
• Adequacy of decompositions: Distinguishing
Rissanen’s, Arora & Carlson’s notions [MMSU]
• Generalized mutual dependencies [MM]
Are We Cyclic Yet?
C.Delobel
ES
PH
CHP
D.S.Parker
MY
AVA
RF
YS
DM
CB
MYV
JDU
AOM
PAB
FS
HFK
1977 1978 1979 1980 1981
DSW
1981-2 Topics
• Acyclic database schemes: 9 characterizations end
up being equivalent; JD = MVDs [BFMMUY]
• Weak instance model, testing equivalence w/
tableaux
• Equivalence of queries with dependencies [GM]
Need to Stop Somewhere
ES
PH
CHP
M.Casanova
S.Walecka S.Kuck MY
AVA
YS
RF
DM
CB
MYV
JDU
AOM
PAB
FS
HFK
1977 1978 1979 1980 1981 1982
DSW
M.Graham
J.Stein
D.Rozenshtein
S.Salveter
1983 & Beyond
Publishing with students at Toronto
Graphical query languages
Deductive databases