Overview, terminology, five primitive operations, select and project, symbolic notation, union, intersection, difference, bank example, cartesian product, join operation, natural join, renaming operation, aggregate functions, hierarchies, outer joins, fundamental and derivable operators, equivalence, relational algebra and sql compared, implementations.
Overview, simple two-way merge sort, run (sorted subfile), example, number of passes - ((log N)+1), overall cost -- (2N*(log_N+1)), External merge sort algorithm, B buffer pages, example, total cost -- (2N*((log(ceil(N/B))_base_(B-1))+ 1)), minimizing the number of runs in external merge sort using Replacement sort, produces runs that are about (2*B) pages long on average, Blocked I/O, ceil((B-1)/b) runs each pass, example, the base of the logarithm will be ((B-b)/b), example: number of passes of external merge sort with block size b=32, double buffering, using B+ tree for sorting, clustered and unclustered indices.
Introduction, No-Force Policy, ARIES recovery algorithm, Analysis-Redo-Undo phases, LSN (Log Sequence Number), the Log, pageLSN, updating a page, commit, abort, End, undoing an update (CLR), prevLSN, Update log records, Compensation Log Records (CLR), undoNextLSN, Transaction table, Dirty Page table, the WAL (Write Ahead Log) protocol, Checkpointing, recovery from the system crash, the analysis phase, example, the Redo phase, example, the Undo phase, example, aborting a transaction, example of undo with repeated crashes, Exercise questions.
Overview, introduction to query processing, iteration, indexing and partitioning, access paths, selectivity, examples of cost and calculations, Reserves table, Sailors table, the Selection operation, no-index and unsorted data, no-index and sorted data, B+ Tree index, clustered B+ tree vs. Unclustered B+ tree, reducing the number of I/Os to retrieve the qualifying tuples by sorting the rids, use of an unclustered index for range selection could be expensive, Hash-index and equality selection, general selection conditions, conjunctive normal form (CNF), CNF and index matching, examples, evaluating selections without disjunctions, selections with disjuctions, the Projection operation, projection based on sorting, Join operation, Nested Loop join, total cost: M+(M*N) for one-page-at-a-time join, Block Nested loop join, building a hash table for use with Block-nested loop join, buffer usage in block nested loops, I/O cost of block nested loops with B buffers -- (N*Ceil(M/(B-2))+M), impact of blocked access in block nested loop algorithm, indexed nested loop join algorithm.
Question 1 (External Sorting), Question 2 (B+ tree Indexing), Question 3 (External Sorting), Question 4 (Join operation), Question 5 (B+ tree Indexing) -- not done, Question 6 (Transaction Management), Question 7 (ARIES Recovery algorithm).
Last Updated: Mar 2018