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 (sec. 1.2, pp. 5)
- Strict relational model (sec. 1.3, pp. 6-8)
- 1st Normal form (sec. 1.4, pp. 9)
- Redundancy (sec. 2.2, pp. 13-14)
- Integrity Constraints (sec. 2.3, pp. 14)
- Key Concepts: strict relational model
- Compare Codd's model with UG textbook
- column order: Properties 4 of relations (pp. 7)
- relations vs. relationships (pp. 8, footnote 2)
- join(R,S) in UG textbook = select( C, product(R, S))
- His join definition - no condition C
- ... leads to "plurality of joins" (pp. 11-12)
- Ex. Compare SQL with Codd's relational model
- Properties 3 of relations (pp. 7)
- Duplicate rows
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
S3: Codd's relational model
- 1st Normal form (sec. 1.4, pp. 9)
- Simple vs. non-simple domains ("complex objects").
- Normalization: removing non-simple domains.
- Algorithm: hierarchical model to 1NF relational model
- Redundancy (2.2, pp. 13-14) in a set of relations
- Strong - pi(R) derivable from other relations
- ... using projection, natural join, restriction
- Weak - derivable fromother relations
- ... using projection, arbitrary join, restriction
- Ex. Compare strong and weak redundancy with different NFs
- See UG textbook for Normalization theory
- Integrity Constraints (sec. 2.3, pp. 14)
- Redundancy declaration for a set of relations
- Check at update time
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
S4: Codd's relational model
- Rewrite today
- 1NF: 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)
S5: 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)
S6: 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)
S7: 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)
S8: 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)
S9: System R
- Outline: Evaluate Design decisions
- Test of time on the design decisions
- Relational Storage System
- manage devices, space allocation, indexes
- buffers, locking, recovery
- RDI: appendix III (pp. 34)
- Relational Data System (RDS), Interface (RDI)
- authorization, IC, views
- SQL, system catalogs, query optimizer
- RDI : appendix I (pp. 32)
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
S10: System R Details
- Design decisions surviving test of time
- parser:
- query rewrite:
- optimizer - cost-based dynamic programming (pp. 23)
- ... plans with 2-way joins only
- query executor - Nest-loop & sort-merge join,
- ... compiled queries
- access methods- mixed cluster (see links pp. 28)
- ... B+trees (see images pp. 28)
- But rejected hashing
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
S11: System R
- buffer manager
- lock manager: physical and logical locks (pp. 29)
- ... lock granularity (pp. 30-31)
- ... 3 levels of consistency (pp. 30)
- But predicate locking added complexity
- recovery manager - savepoints and restore (pp. 31)
- ... dual logs to support log failure
- But shadow paging (pp 31) lost to Write-ahead Log
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
S12: System R
- Other Contributions
- Modularization: RSS/RDS
- Design: catalogs as relations
- Sequel language (DDL, DML, DCL)
- ... SQL, cursors, NULLs, having (pp. 19-20)
- ... begin/end xact at user level (pp. 21)
- ... 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)