CSE 562 CSE 462 Database Systems

UB CSE Database CoursesCSE 562Database SystemsCSE 462DatabaseConceptsIntroductionCSE 562DatabaseSystemsSome slides are based or modified from originals byDatabase Systems: The Complete Book,Pearson Prentice Hall 2nd Edition 2008 Garcia-Molina, Ullman, and WidomCSE 636DataIntegrationUB CSE 562 Spring 2010 Study key DBMS design issues:Tue & Thu @ 2-3pm210 Bell Hall– Query Languages, Indexing, Query Compilation, QueryExecution, Query Optimization– Recovery, Concurrency and other transactionmanagement issues TA: Xinglei ZhuWednesday @ 12-2pm329 Bell Hall– Data warehousing, Column-Oriented DBMS– Database as a Service (DaaS), Cloud DBMS Web Pagehttp://www.cse.buffalo.edu/ mpetropo/CSE562-SP10/ Ensure that: Newsgroup– You are comfortable using a DBMS– You acquire hands-on experience by implementing theinternal components of a relational database enginesunyab.cse.562UB CSE 562 Spring 20102Goals of the Course Instructor: Dr. Michalis PetropoulosOffice Hours:Location:CSE 7xxDr. Petropoulos’SeminarUB CSE 562 Spring 2010ResourcesOffice Hours:Location:CSE 7xxDr. Chomicki’sSeminar3UB CSE 562 Spring 201041

Course Evaluation Reading MaterialHomework Assignments: 15%Midterm Exam: 20% (in class)Final Exam: 30% (in class)Project: 35%Textbook Database Systems: The Complete Book (2nd Edition)– by Garcia-Molina, Ullman and WidomAlso Recommended Database System Concepts (5th Edition)– Teams of 2– by Avi Silberschatz, Henry F. Korth and S. Sudarshan Database Management Systems (3rd Edition)– by Ramakrishnan and Gehrke Late Submission Policy: Foundations of Databases– Submissions less than 24 hours late will be penalized10%– Submissions more than 24 hours but less than 48hours late will be penalized 25%UB CSE 562 Spring 2010– by Abiteboul, Hull and Vianu5PrerequisitesLet’s Get Started! Chapters 2 through 8 of the textbook:––––6UB CSE 562 Spring 2010 Isn’t Implementing a Database System Simple?Relational Model, Entity/Relationship (E/R) ModelConstraints, Functional DependenciesViews, TriggersDatabase query languages (Relational Algebra, SQL)RelationsStatementsResults Solid background in Data Structures andAlgorithms Significant programming experience in Java Some knowledge of Compilers Curiosity! You should ask a lot of questions!UB CSE 562 Spring 20107UB CSE 562 Spring 201082

Let’s Get Started!Megatron 3000 Implementation Details Relations stored in files (ASCII)– e.g., relation MovieWild # Lynch # WingerSky # Berto # WingerReds # Beatty # Beatty Directory file (ASCII)Movie # Title # STR # Director # STR # Actor # STR Schedule # Theater # STR # Title # STR UB CSE 562 Spring 20109Megatron 3000 Sample Sessions10UB CSE 562 Spring 2010Megatron 3000 Sample Sessions% MEGATRON3000Welcome to MEGATRON 3000!&& select *from Movie #TitleWildSkyRedsTangoTangoTango & ingerWingerBeattyBrandoWingerSnyder&UB CSE 562 Spring 201011UB CSE 562 Spring 2010123

Megatron 3000 Sample SessionsMegatron 3000 To execute select * from Movie where condition(1) Read dictionary to get Movie attributes(2) Read Movie file, for each line:(a) Check condition(b) If OK, display& select Theater, Movie.Titlefrom Movie, Schedulewhere Movie.Title Schedule.TitleAND Actor “Winger” #Theater TitleOdeonWildForumSky&UB CSE 562 Spring 20101314What’s wrong with the Megatron 3000DBMS?Megatron 3000 Tuple layout on disk To executeselect Theater, Movie.Titlefrom Movie, Schedulewhere Movie.Title Schedule.TitleAND Actor “Winger”(1) Read dictionary to get Movie, Schedule attributes(2) Read Movie file, for each line:(a) Read Schedule file, for each line:(i) Create join tuple(ii) Check condition(iii) Display if OKUB CSE 562 Spring 2010UB CSE 562 Spring 2010– Change string from ‘Cat’ to ‘Cats’ and we have torewrite file– Deletions are expensive15UB CSE 562 Spring 2010164

What’s wrong with the Megatron 3000DBMS?What’s wrong with the Megatron 3000DBMS? Brute force query processingFor example: Search expensive; no indexes– Cannot find tuple with given key quickly– Always have to read full relationselect Theater, Movie.Titlefrom Movie, Schedulewhere Movie.Title Schedule.Titleand Actor “Winger” Much better if– Use index to select tuples with “Winger” first– Use index to find theaters where qualified titles play Or– Sort both relations on Title and merge-join Exploit cache and buffersUB CSE 562 Spring 201017What’s wrong with the Megatron 3000DBMS?18What’s wrong with the Megatron 3000DBMS? Concurrency control & recovery No reliability Security Interoperation with other systems Consistency enforcement– Can lose data– Can leave operations half doneUB CSE 562 Spring 2010UB CSE 562 Spring 201019UB CSE 562 Spring 2010205

Course TopicsCourse Topics Hardware Aspects Physical Organization Structure Concurrency ControlCorrectness, locks, deadlocks On-Line Analytical ProcessingRecords in blocks, dictionary, buffer management, Map-Reduce, Indexing Database as a Service (DaaS) Cloud DBMSB-Trees, hashing, Query Processingparsing, rewriting, logical/physical operators,algebraic and cost-based optimization,semantic optimization Crash RecoveryFailures, stable storage, 21UB CSE 562 Spring 2010Database System ArchitectureQuery ProcessingExample Journey of a QueryTransaction ManagementSQL QuerySELECT TheaterFROM Movie M, Schedule SWHERE M.Title S.TitleAND M.Actor “Winger”Calls from Transactions utionEngine22UB CSE 562 Spring 2010ViewDefinitionsStatistics &Catalogs &System DataBufferManagerConcurrencyControllerYet Another logicalquery planLockTableParse/ConvertInitial logicalquery planQuery Rewriterapplies Algebraic RewritingAnother logicalquery planRecoveryManagerQueryRewriterLogData IndexesUB CSE 562 Spring 2010Cont’d23UB CSE 562 Spring 2010246

Example Journey of a Query (cont’d)The Journey of a Query leIndexCost-basedOptimizationWhat are the rules used for thetransformation of the query?How do we evaluate the cost ofa possible execution plan?EXECUTION ENGINEQueryExecutionPlanfind “Winger” tuples using ActorIndexfor each “Winger” tuplefind tuples t with the same titleusing TitleIndexproject the attribute Actor of tIndex on Actor and TitleUnsorted tablesTables MemoryUB CSE 562 Spring 2010TitleWildSkyRedsTangoTangoTango25UB CSE 562 Spring ngerWingerBeattyBrandoWingerSnyderHow is the table arranged onthe disk?Are tuples with the sameActor value clustered?What is the exact structure ofthe index (tree, hash, )?267

– by Avi Silberschatz, Henry F. Korth and S. Sudarshan Database Management Systems (3rd Edition) – by Ramakrishnan and Gehrke Foundations of Databases – by Abiteboul, Hull and Vianu UB CSE 562 Spring 2010 7 Prerequisites Chapters 2 through 8 of the text