S1: Csci 8701 - Week 3
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)