Data Base Systems
Data Base Systems EEL 4852C
Popular in Course
Popular in Electrical Engineering
This 12 page Class Notes was uploaded by Mr. Chelsie Bergstrom on Wednesday September 23, 2015. The Class Notes belongs to EEL 4852C at University of South Florida taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/212715/eel-4852c-university-of-south-florida in Electrical Engineering at University of South Florida.
Reviews for Data Base Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/23/15
Databases EEL 4852c Notes from 18 NOV 2008 Transcribed by Jeff George 0 cost example of a basic nested loopjoin Table E 1000 pages 100 tuples per page Table WO 500 pages 80 tuples per page Use equation M Pr N If E is the outer table 1000 100 500 50000000 lOs If WO is the outer table 500 80 1000 40000000 lOs Note If the page size is the same lO cost is constant regardless of which table is the outer table If we use the same tables for a PageBased nested loop join the cost is just M N 1000 500 5000000 lOs Newjoin method Indexed tables Pseudocode For each tuple r in R Find all matching tuples in S Return matched pairs Cost Based on indexing method Hashing 12 lO Pages Average 12 3 Trees 34 lO Pages Total Cost M Pr C where C is some constant cost based on your indexing method In this case the innertable quotSquot is the table which is indexed There s no pagebased method for indexed joins like there is for nested loop joins but it doesn t matter since indexing is really fast regardless Indexing only really helps if you have the quotinnerquot table indexed The outer table can be indexed as well but it won t impact the runtime of the join The only way it could help is during query optimization since the query optimizer would be able to pick the optimal inner table based on of tuples Cost example using the same tables as above assuming both tables are indexed E is the outer table 500 80 C 40000C WO is the outer table 1000 100 C 100000C Obviously if both tables are indexed you would prefer E to be the outer table SortMerge Join Method 1 Sort relation R according to the join attributes store it in R 2 Sort relation S according to the join attributes store it in S 3 Merge R S Essentially step a pointer through each sorted relation If they don t match compare the next elements If they do match copy the tuple into the merged relation Cost M log M N log N MN of matches Plan Evaluation The Cost Model considers 1 Response Time How soon will we start getting results 2 Total Processing Time How soon will the queryfinish Plans gt Cost Model gt Optimal Cost Plan The total number of plans going into the Cost Model may be huge Think about all the different permutations of a Relational Algebra tree you can draw then realize that each step of that tree may have a wide variety of methods of execution We have just shown four different methods of doing a Join The number of potential plans can obviously get out of hand rather quickly If the number of plans grows very rapidly you may end up running into a situation where the time it takes to analyze the time each plan would require to run and then the time it would take to compare all these plans to find the optimal plan may itself be longer than the runtime ofa suboptimal plan that was seen earlier To resolve this issue and speed up the procedure of finding an optimal plan in the real world we use Heuristics to find the best plan or at least find a good plan Cost Evaluation requires 1 Cost model of algorithms 2 Size of intermediary results Some statistics are kept between queries so the cost evaluator can make reasonable approximations Q Circlesa M rm Mans OCTLLmi SQL gumd7 SQL Wm Cwnmm 5 I GQaNT lt L 1 gt GINwsudn LIN lt Milw 7 1h an fa u w 139 uw vmu MMmQM L gf KLEIN 1mm rm U H JHMM APBWE mar Utav5quot 735 Mm fva ml Nbbx K b Swat4 may 3N5 LT fbmm mmcm x Lute a main July I x a 72 Maw aw urr TL LAH M 13 Adan 64 g M gznlu 5dr 0M 5 mm 7 Egg 2 4N 39 k 54 x 7 i2 V m H 0er 3 44 ch We NH 7 BIL x QJQ Lem 941 54 E A39LVMFL V Dcrur lrw f TKLLL 4C iv m f I AIMin n ma Lt vxlufI mammi Mg TL murmw W MLN L I akish t 4 wan TdJsulr7 L A T 7 he V w km m L E a 7 H F f w SL711 1 m EMFo Wk 10qu yum M33797 Nd NULL 77 Lsemp k paws 911 me Qk f 11A Ss 7 7 7 raw mmt l Ewan K gtw L 7 Db 7 ymwmk 7 Kim Emu N Vibiw 39k 7 415 4 rgt M quot3 Tu ii I la 13 muwrm geequot NtQ Zip LE 5mm hm PM rm Munqu Imratzmndm 4 vraug mum 1 gull KKK Nb Nik rusL m Lu c ad or Hum aw mayng lw 1 L 1 mum cm cmm 144 mxtr39Mst39cvo Wm 7 quot ue i iLL highs MUM 1LQMCII m Obey A h ulgt 39 u M 55 431 my UNLAJS MIR rim153 Mg QM a QCquotltvlf 44 tnfunsy39ue q PL SQL 7 i 7 gt 3 Tquot pgsSWLiJui f 5M 3 Ln A an 31g 4 may oul 7 Q aim Luggm 37 1 tau 75 NM h V 7 HA mahtkL lm ydJkn 153 Bat EwiijysLig AazCusLFng t SQL twat 5M u g AL 3lt my r G Vj sm xn Rainy can 16 N quk 15 NaniC SQL sand 9 ruby L Mg3 Admm Him 3 l 5 7 pmle L39alqdrux mgi Ca KM Jam Handwuwr lbw C Nu EMF71 u HWI rt rm 5 4 whom my 114th 4 114 r oLm WA KMT Mm th MK uh e L qu mkm m EMILLLUH 3 LLMJMM 4 JAIN Wu 7 Hr unmL f Hui 3 7 AS MR 7 ASEM3 MW FND Q 5am PHaL LAIn C M gt w 1m 1 EXRMPL mi Wm qugwwqu TAM Quirk1x why a 54 Aim mt t Yum Mun ML Lii L rand WW1 F mwi WW 5 l 7 run 0 mm m4 HAM 139 39ij gym Lka I A Wm m Aloe m MW use A cm 531 K 787W 39me u an akinw rum Mfr n r in gk w x L I g 31kt M g 7 Cam L wmrs fwx 209 v Nested Queries in SQL continued In this episode we do a nal complicated case Implementing DIVIDE in SQL Here s an example problem Find all the entities of type A that are associated with all memebrs of as set of type B To apply this lets use our employee database schema and rephrase the problem to be EX Find the rst names of all employees who work in ALL projects in Brooklyn We imagine two sets the divisor and the dividend which here will be B and A respectively A The set of all Employees B The set of all Brooklyn projects What we want to say is Select any employee who works on all the projects in Brooklyn but this isn t necessarily possible in SQL There s no way to really say works on all Yet it is easy to nd all the projects thatA works on The way you do it in SQL you compare the projects A works on with those in B like this SELECT A WHERE NOT EXISTS B Aprojects Here Aprojects represents all the projects A works on This means that while you can t just see if all projects in A are all in B you CAN subtract the projects from B and see if any are left over This may still be confusing so it might be better to take a simpler database illustrate it there and then take it further to the employee table Let s start with a table about a VIP who wants to select his assets according to a speci c set of parameters please turn the page in your PDF Let s look at our VIP very important pirate I 39 i 390 and his table of assets R arrr Our VIP b quot quot wants to visit some friends but needs to choose swag with the appropriate substanc f O 39 39 abuse and actIVIty 6 While this might look obvious for us let s review how to do it with DIVIDE 39f we diVide R by Recall that DIVIDE is expressed this way Y39P we can see h just what he r I S I W eVe39 should take along Vh I 1153 SA furle m r V sl then right Later we ll show you how SQL looks at this problem using sets instead of a 39F enough w s r calc I sof sorts J quot J u quot right ll 0 r gel quot I g Well indeed the 3 e 4 drumstick fits all i I quotQf 53 our demands quot Booze n crackers Rum n chicks R d t 396 W This is trivial to do 199222 SS1 517 9 in our heads but Q that what naj What about SQL 1 4 boys do statements Will 39 A our VIP manage Clearly we can t choose the cutlass or 1 the butter knife In the first case the cutlass has nothing in common with what the VIP seeks As for the butter knife it just manages to work well with gt booze and crackers Nothing else But when you try B EXCEPT e2 nothing of B will be left The division passes for e2 With SQL we have a new way of see other using subtraction EXCEPT Let s say you want to divide e1 e2 and e3 by B EXCEPT quickly finds matches ing if a set covers an SQL B EXCEPT e1 The result is B The division fails SQL We get some of B back The division still fils B EXCEPT e3 imagine B as a shi sailin into firin ran T Finally the query uses NOT EXIST to see if B successfully divided A Odd huh Hmmm I must admit I didn t eXpect it to be so involved And if you really need a div I quothidquot ducks D l V is on PPCIIJ hEre awn 0139 265T 11c AllSim work ision query to show that butter knives are bad for social encounters With pirates you need a lot more than a Bachelors in Engineering Computer Science Computer Engineers on the other hand don t need a degree program since the only people Who think Comp E should have a program are actual computer engineers and they don t count ahem Using a nested query to replace B and Aprojects we d phrase this as follows in SQL NOTE the usage of EXISTS SELECT E FName FROM E WHERE NOT EXISTS SELECT RPno FROM P WHERE PPLocation Brooklyn EXCEPT SELECT RPno FROM WO WHERE ESSN Pessn AND Plocation Brooklyn We should move on to the next topic now Which is Aggregates in SQL The aggregate functions we ll look at are COUNT SUM MAX MIN AVG A B C D E 14 2 5 38 1 0 84 3 29 47 18 4 8 10 22 14 10 32 20 15 COUNTA on the above table would result in 4 since it doesn t ignore dups uh oh slashdot and it also includes 0 NULL is a different story but don t consider it for now In this introductory class we ll be avoiding NULL Lets use an aggregate query in our Employee Database sorry no more VIP s for now EX Find the max salary and min salary among employees who work for the Research dept SELECT MAXSalary MINSalary FROM E D WHERE E Dno DDNumber AND DDname 2 Research GROUP in SQL Sometimes we want to run aggregates on speci c parameters such as counting the amount of employees on each project in the employee database You simply add a clause at the end of the query to do this Here s how we d do something like that in SQL using the GROUP BY statement EX For each Project retrieve the pno and pname and number of employees that work on that project SELECT PNumber PPname CountWOessn FROM WO P WHERE WOPno PPnumber GROUP BY PPnumber When we want to only select particular groups we do an additional step That is you might think the WHERE clause would be used but that s incorrect as the groups needs to be treated as separate from the rest of the results since the groups are more or less laying on top of the query and cutting it into chunks Instead you use the HAVING keyword to git r dun adding it to the end of the query Since we didn t get any speci c examples of the HAVING keyword I guess I ll have to make one up uh oh SELECT SUMMidgetisEvil COUNTMidgetName FROM Midget WHERE Midgetheight lt 4 GROUP BY MidgethomeCity HAVING MidgetGender 2 male we need the having keyword because women are all evil and no count is necessary for them
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'