Lecture 30: Final ReviewThe FinalWhat to Prepare for the FinalData ModelingRelational AlgebraXMLSQLSQL (continued)Data StorageIndex StructuresPhysical OperatorsOptimizationsRecoveryGeneral AdviceLecture 30: Final ReviewWednesday, December 6, 2000The Final•Date: Friday, December 8•Time: 2:30 – 4:20•Place: BAG 260•Open book exam !What to Prepare for the FinalEverything !•Data modeling•Relational model•XML•Relational algebra•SQL•Storage•Indexes•Physical operators•Optimization•RecoveryData Modeling•E/R diagrams, ODL•Keys•Relationships•Inheritance•Mapping to relationsRelational Algebra•Relations•Keys•Functional dependencies•Decomposition•Normal formsXML•XML syntax•DTD•From relations to XML•From XML to relationsSQL•Select-from-where•Subqueries•Aggregation•Nulls•Outer joinsSQL (continued)•Database modification•Defining and modifying relation schemas•Constraints–On attribute values–Keys–Foreign keys•Embedded SQLData Storage•The I/O model of computation•Representing data elements:–Grouping records into blocks–Variable length records–Overflow blocksIndex Structures•Terminology:–Dense/sparse index–Primary/secondary index•B+-trees•Hash tablesPhysical Operators•One-pass algorithms•Nested-loop joins•Two-pass algorithms based on sorting•Two-pass algorithms based on hash tables•Index-based algorithmsOptimizations•Extended logical operators•Algebraic identities•Heuristic based optimization:–Push down selections–Push down projections•Cost based optimization:–Size estimation–Dynamic programming for join orderRecovery•Undo logging•Redo logging•Undo/redo loggingGeneral Advice•Some problems will require thinking–Use judgment–Do not look for “similar” problem in HW or book•Problem difficulty may be uneven:–do the easy ones
View Full Document