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
    • 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)