• Relational Algebra (Pages: 88)

    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.

  • External Sorting (Pages: 143)

    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.

  • Crash Recovery in Database Systems (Pages: 130)

    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.

  • Evaluation of Relational operators (Pages: 140)

    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.

  • Database Problem Set (Pages: 90)

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

  • Serializing Data (Pages 104)

    Serialization, marshalling, uses, JSON, basic data types in JSON, example, data portability issues, json schema, JSON-RPC, AJAJ, comparison of JSON with other formats (YAML, XML), advantages and disadvantages of JSON over XML, YAML (YAML ain't Markup Language), example, comparison with other data structure formats languages, Google Protocol Buffers, example, tag, protoc compiler, language support, 5 reasons to Protocol Buffers over JSON for your next service, binary encoding format, when is JSON a better fit?, Comparison with Apache Thrift, Google Protocol Buffers and JSON, Apache Thrift (interface definition language and binary communication protocol), IDL (Interface Description Language), examples, JSON-RPC, notifications, method, params, id, sample request and responses (version 1.0 and 2.0), AJAJ (Asynchronous Javascript and JSON), similarities with AJAX (sends request to server and handles the server response without reloading the page in the process), advantages of AJAJ.

Database Systems