1Midterm ReviewLecture 14b14 Lectures So Far1. Introduction2. The Relational Model3. Disks and Files4. Relational Algebra5. File Org, Indexes6. Relational Calculus7. SQL8. Sorting & Joining9. Optimizing Queries10.SQL II11.The ER Model12.ER -> Relational13.Functional Dependencies14.NormalizationBy Topic• Introduction – what are databases for? (1)• Relational Topics– The Relational Model – basic SQL, Keys, ICs (1)– Relational Algebra (1)– Relational Calculus (1)–SQL (2)– The ER Model (2)– Functional Dependenciesand Normalization (2)• Database Internals– Storing Data: Disks and Files (1)– File Organization and Indexes (1)– External Sorting and Join Algorithms (1)– Query Optimization (1)Introduction – what are databases for? (1)• Definitions of database, DBMS• Useful properties of database systems– A.C.I.D.– Data Modelling–Querying– Levels of Abstraction• Comparing Database Systems to...– WWW– File Systems– Data Processing ProgramsThe Relational Model (1)• Tables: Rows and Columns• Basic SQL• Keys• ICs • Referential IntegrityRelational Algebra (1)• Somewhat Procedural Query Language• Basic Ops:–Selection( σ ) Selects a subset of rowsfrom relation (horizontal).–Projection( π ) Retains only wanted columnsfrom relation (vertical).–Cross-product( × ) Allows us to combine two relations.–Set-difference( — ) Tuples in r1, but not in r2.–Union( ∪ ) Tuples in r1 and/or in r2.•Other ops:• Intersection ( ∩ )• Join ( ) – merge 2 tables based on common columns• Division ( / ) – used in “for all” queries2Relational Calculus (1)• Formal logic as declarative Query Language•{S | S∈Sailors ∧ S.rating > 7 ∧∃R(R∈Reserves ∧ R.sid = S.sid ∧ R.bid = 103)}• Concentrated on Tuple Relational Calculus• Also talked about Domain Relational CalculusSQL (2)• Data Definition Language (DDL)• Data Manipulation Language (DML)– Range variables in Select clause– Expressions in Select, Where clauses– Set operators between queries:• Union, Intersect, Except/Minus– Set operators in nested queries:• In, Exists, Unique, <op> Any, <op> All– Aggregates: Count, Sum, Avg, Min, Max–Group By–Group By/Having•Other FeaturesInsertDeleteUpdateNull Values – Outer JoinsViewsOrder ByAccess ControlIntegrity ConstraintsThe ER Model (2)• A Visual Language for Modelling the Real World• Entities, Relationships, AttributesFunctional Dependencies and Normalization (2)• We’ve just talked about thisStoring Data: Disks and Files (1)• Laying out fields in records in pages in files• Buffer ManagementFile Organization and Indexes (1)• Heap File vs Sorted File vs B-Tree Index vs Hash Index• What are advantages, disadvantages of each?3External Sorting and Join Algorithms (1)• External Sorting– Sort a file of any size using only 3 pages of memory– Understand optimizations with more memory• Join Algorithms– Nested Loops– Indexed Nested Loops–Sort-Merge Join–Hash Join– What are tradeoffs for different algorithmsQuery Optimization• Query Plans – trees of operations• How to change plan to find more efficient
View Full Document