Astrahan, et al., System R: Relational Approach to ...
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S2: Codd's Relational Model ...
Contributions
Case for physical independence.
sort order, index, access path
Avoid non-simple domains
Key Concepts
strict relational model (not SQL)
Simple vs. non-simple domains ("complex objects").
Normalization: removing non-simple domains.
Normalization theory - see textbook
Ex. Compare SQL with Codd's relational model
Properties 3, 4 of relations (pp. 7)
relations vs. relationships (pp. 8, footnote 2)
join definition - "plurality of joins" (pp. 11-12)
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S3: Codd's relational model
Rewrite today
Problems with non-simple domains.
hard to represent
hard to translate to other systems
Model versions of relations (time travel)
OODB use non-simple domains.
How do OODBMSs address these problems?
OODB clustering
OODB bulk loading
POSTGRES storage manager - version manager
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S4: Relational System Architecture
Motivation - Macro design issue
Identify Design Issues
Identify alternatives for each design issue
Disk management choices:
file per relation
big file in file system
raw device
Process Model:
thread or process per user
server
multi-server
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S5: Modularization of DBMS
Why modularize?
Databases is a large software
Basic modules (See chapter 1 of textbook):
parser, query rewrite, optimizer
query executor, access methods, buffer manager
lock manager, log/recovery manager
Functionalities of modules
Query Rewriter
Flattens views (why?)
change query using constraints
Optimizer
search space of eqv. relational plans
choose a optimal (?) plan
output: interpretable plan tree / compiled code
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S6: Modularization of DBMS
Executor
implements operations like joins, sort, ...
calls Access Methods for operations on relations
Access Methods
operational interface (open, get next),
many implementations: heap, B-tree, hashing
Ex. INGRES AMI, System R's RSS
Buffer Manager
Cache disk block in memory (user-level)
interacts w/ lock manager
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S7: Modularization of DBMS
Lock Manager
efficient access to lock table
deadlock handling: detection
Log/Recovery Manager
Issues: failures on disk or tape.
maintain logs (before/after values)
recovery algorithms (redo/undo)
checkpoint/restore for quick recovery
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S8: System R
Outline: Evaluate Design decisions
Test of time on the design decisions
Design decisions surviving test of time
parser:
query rewrite:
optimizer - cost-based dynamic programming
... plans with 2-way joins only
query executor - Nest-loop & sort-merge join,
... compiled queries
access methods- clustering, B-trees
But rejected hashing
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S9: System R
buffer manager
lock manager: physical and logical locks
... lock granularity
But predicate locking added complexity
recovery manager - savepoints and restore
... dual logs to support log failure
But shadow paging lost to Write-Ahead Logging!
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S10: System R
Other Contributions
Modularization: RSS/RDS
Design: catalogs as relations
Language - SQL, cursors, NULLs, group by
... begin/end xact at user level
... GRANT/REVOKE, integrity constraints, triggers
updatable single-table views
Controversial choices
SQL language - duplicate semantics
...subqueries vs. joins
...outer join
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.