S1: Csci 8701 - Week 3
- Administrative
- HW 1 - DUE
- Project source selection
- DBLP (papers), amazon.com (books)
- Attach search results, justify 6-8 choice
- Goals:
- Review of Relational Roots
- Relational data model, System R
- Recommended Readings:
- Codd, A Relational Model of Data for ...
- 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)