CSC 485E / CSC 571: Advanced Databases - Fall 2008

Text: Database Systems: The Complete Book
by Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Widom, 2nd Edition, Prentice Hall, 2008

Reference: Readings in Database Systems, 4th Edition
by Michael Stonebraker and Joseph M. Hellerstein (Editors), The MIT Press 2005.

Marks so far: Link

The midterm will be on Oct 15. (Coverage: Everything up to query compiler) Solutions.

Assignments:

Assignment 1. Solutions: 1,2,3,6. 4a. 4b. 5.
Assignment 2. Hints. Some Recovery Examples. Slides. Solutions: Ex. 1, Ex. 2-5.
Assignment 3. Solutions.

Project: Description. RTree Algorithms. Oracle. Ssh Tunnel. Bundle. Comments.

Alternate Project: Description.

Term Paper: Choose one paper from the same description and follow the guidelines given there.

Reading list: Link

Lecture Notes

• Storage Management
  • Intro to Database Management Systems Slides.
  • Memory Hiearchy, Disks mechanics, Computation Model Slides
  • Using Secondary Storage Effectively. Two Phase Multiway Merge Sort (2PMMS). Impact of block size. Sorting very large relations. Cylindrification. Multiple Disks. Prefetching and large scale buffering. Slides
  • Reliability of Disk Systems. Disk failures. RAID 4, RAID 5, RAID 6. Nested levels. Slides, Slides (b).
• Index Structures
  • Primary Indexes. Dense and Sparse Indexes. Secondary Indexes. Inverted Indexes. B-Trees. Insertion into B-Trees. Number of Levels in B-trees. Deletion from B-Trees. Slides
  • Secondary-Storage Hash Tables. Dynamic Hashing Framework: Extensible Hashing, Linear Hashing. Slides
  • Multidimensional Data. Attempts at using B-trees for MD-queries. Grid files. Partitioned hashing. Slides
  • Multiple-key indexes. KD-Trees. Quad trees. R-Trees. Bitmap Indexes. Slides (Updated)
• Query Processing
  • Query Execution I: Introduction to Physical-Query-Plan Operators, The Model of Computation for Physical Operators, Iterators, One pass algorithms. Slides
  • Query Execution II: Block-based nested loops, Two-pass algorithms based on sorting, Two-pass algorithms based on hashing Slides
  • Index joins. Zigzag Join. Slides
  • Query Compiler: Query and parse tree, Algebraic laws, Pushing selections. Laws for (bag) Projection, duplicate elimination, aggregations. Slides
  • From SQL parse trees to RA expression trees. Oracle query plans. Slides
  • Estimating the Cost of Operations: Estimating the size of joins, Containment of value sets, Preservation of set values, Size estimates for other operations, Incremental computation of statistics. Slides
  • Cost based transformations. Heuristics for selecting the physical plan. Dynamic Programming to Select a Join Order and Grouping. Greedy Algorithm for Join Order. Slides
  • Completing the Physical-Query-Plan. Pipelining Versus Materialization. Slides
• Recovery
  Coping With System Failures: Undo Logging, Redo Logging, Undo/Redo Logging. Slides. Some Examples. Slides.
• Concurrency
  • Concurrent Transactions. Serial and Serializable Schedules. Conflicts. Serializability/precedence graphs. Why two phase locking works. Shared/Exclusive Locks. Upgrading Locks. Deadlocks. Solution: Update Locks. Compatibility Matrix. Slides
  • Shared/Exclusive Locks. Upgrading Locks. Deadlocks. Solution: Update Locks. Compatibility Matrix. Slides
  • Timestamps. Serializability Via Timestamps. Physically unrealizable events. Abort/Update Decisions. Timestamps Versus Locks. Slides. Short version Slides.
• Parallel and Distributed Databases
  • Parallel Algorithms for Relational Operations: Models of Parallelism, Tuple-at-a- Time Operations in Parallel, Joins Slides
  • Google's Map-Reduce Parallelism Framework. Slides.
  • Distributed Databases. Distributed Query Processing. The Distributed Join Problem. Semijoin Reductions. Slides.
  • Distributed Commit. Supporting Distributed Atomicity. Two-Phase Commit. Slides.
  • Distributed Locking. Slides.
  • Peer-to-Peer Distributed Search. The Distributed-Hashing Problem. Slides.
• Information Integration
  • Modes of Information Integration. Wrappers in Mediator-Based Systems
  • Capability-Based Optimization.
  • Entity Resolution. Merging Similar Records. The R-Swoosh Algorithm for ICAR Records.
• Data Mining
  • Frequent-Itemset Mining. The Market-Basket Model. Association Rules. Slides.
  • Techniques for Frequent Itemsets. The A-Priori Algorithm. Slides (Adapted from J.D. Ullman's slides).
  • Park-Chen-Yu Algorithm, Multistage Algorithm, Approximate Algorithms. Slides (Adapted from J.D. Ullman's slides).
  • FP-Tree/FP-Growth Algorithm. Slides. Paper.
  • Finding Similar Items. The Jaccard Measure of Similarity. Minhashing. Locality-Sensitive Hashing. Slides (ppt), Slides (pdf).
  • Clustering of Large-Scale Data. Agglomerative Clustering. k-Means for Large-Scale Data. Slides (ppt).
• Database Systems and the Internet
  • Search engines. Web Crawlers. Query Processing in Search Engines
  • PageRank. Recursive Formulation of PageRank. Spider Traps and Dead Ends.
  • Data Streams. Data-Stream-Management Systems. Converting Streams Into Relations. Converting Relations Into Streams.
  • Data Mining of Streams.